Enhancing 'Mobility' through Integrated Transportation and Traffic Management

During the course of preparation of a master plan for the transportation networks in Bangalore city, mapping the various initiatives and interventions planned towards addressing mobility, existing situation and implications of some of the proposed interventions was analysed. The inferences are based on existing transportation network; synthesis of various transportation related studies and proposed infrastructure initiatives (road works) in Bangalore. Broadly, they can be summarized as following five aspects: I. Need for ~Sreclassifying~T existing road networks (arterial and sub-arterial) with effective geospatial database in the back-end. II. The proposed Core Ring Road at surface grade may not be feasible. III. Current interventions encouraging more independent motorable transport by way of road widening, construction of underpasses, flyovers and grade-separators would not ease traffic congestion when addressed in isolation. IV. Factors affecting time and cost-overruns in infrastructure projects and ways to tackle are discussed. V. Initiatives required for addressing effective planning for operations recommended.

Interference Alignment as a Tool in Network Coding as Applied to Distributed Storage

In this paper, we outline an approach to the task of designing network codes in a non-multicast setting. Our approach makes use of the concept of interference alignment. As an example, we consider the distributed storage problem where the data is stored across the network in n nodes and where a data collector can recover the data by connecting to any k of the n nodes and where furthermore, upon failure of a node, a new node can replicate the data stored in the failed node while minimizing the repair bandwidth.

Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Searth Auctions

In pay-per click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their ads. This auction is typically conducted for a number of rounds (say T). There are click probabilities mu_ij associated with agent-slot pairs. The search engine's goal is to maximize social welfare, for example, the sum of values of the advertisers. The search engine does not know the true value of an advertiser for a click to her ad and also does not know the click probabilities mu_ij s. A key problem for the search engine therefore is to learn these during the T rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced and would be referred to as multi-armed-bandit (MAB) mechanisms. When m = 1,characterizations for truthful MAB mechanisms are available in the literature and it has been shown that the regret for such mechanisms will be O(T^{2/3}). In this paper, we seek to derive a characterization in the realistic but nontrivial general case when m > 1 and obtain several interesting results.

Boxicity of Line Graphs

The boxicity of a graph H, denoted by View the MathML source, is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in View the MathML source. In this paper we show that for a line graph G of a multigraph, View the MathML source, where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, View the MathML source. For the d-dimensional hypercube Qd, we prove that View the MathML source. The question of finding a nontrivial lower bound for View the MathML source was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800]. The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).

Rainbow Connection Number and Radius

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) <= r(r+2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that, for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K_{1,n} for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) <= rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 - 1, where n is order of the graph [Caro et al., 2008]

Design and Implementation of a Flexible and Memory Efficient Operating System for Sensor Nodes

Sensor network nodes exhibit characteristics of both embedded systems and general-purpose systems.A sensor network operating system is a kind of embedded operating system, but unlike a typical embedded operating system, sensor network operatin g system may not be real time, and is constrained by memory and energy constraints. Most sensor network operating systems are based on event-driven approach. Event-driven approach is efficient in terms of time and space.Also this approach does not require a separate stack for each execution context. But using this model, it is difficult to implement long running tasks, like cryptographic operations. A thread based computation requires a separate stack for each execution context, and is less efficient in terms of time and space. In this paper, we propose a thread based execution model that uses only a fixed number of stacks. In this execution model, the number of stacks at each priority level are fixed. It minimizes the stack requirement for multi-threading environment and at the same time provides ease of programming. We give an implementation of this model in Contiki OS by separating thread implementation from protothread implementation completely. We have tested our OS by implementing a clock synchronization protocol using it.

Believe it or Not! Multicore CPUs can Match GPUs for FLOP-intensive Applications

In this work, we evaluate performance of a real-world image processing application that uses a cross-correlation algorithm to compare a given image with a reference one. The algorithm processes individual images represented as 2-dimensional matrices of single-precision floating-point values using O(n4) operations involving dot-products and additions. We implement this algorithm on a nVidia GTX 285 GPU using CUDA, and also parallelize it for the Intel Xeon (Nehalem) and IBM Power7 processors, using both manual and automatic techniques. Pthreads and OpenMP with SSE and VSX vector intrinsics are used for the manually parallelized version, while a state-of-the-art optimization framework based on the polyhedral model is used for automatic compiler parallelization and optimization. The performance of this algorithm on the nVidia GPU suffers from: (1) a smaller shared memory, (2) unaligned device memory access patterns, (3) expensive atomic operations, and (4) weaker single-thread performance. On commodity multi-core processors, the application dataset is small enough to fit in caches, and when parallelized using a combination of task and short-vector data parallelism (via SSE/VSX) or through fully automatic optimization from the compiler, the application matches or beats the performance of the GPU version. The primary reasons for better multi-core performance include larger and faster caches, higher clock frequency, higher on-chip memory bandwidth, and better compiler optimization and support for parallelization. The best performing versions on the Power7, Nehalem, and GTX 285 run in 1.02s, 1.82s, and 1.75s, respectively. These results conclusively demonstrate that, under certain conditions, it is possible for a FLOP-intensive structured application running on a multi-core processor to match or even beat the performance of an equivalent GPU version.