Cauligi S. Raghavendra - US grants

This research program in parallel algorithms and architecture examines the design of special purpose VLSI architectures, parallel algorithms for VLSI architectures, and the design and analysis of reliable interconnection networks. An innovative architecture with efficient local and global communication features is designed to support a wide variety of computations: numerical computations, geometric problems, graph problems, and others. The model provides substantial speedups for a wide class of problems in these areas. The regular near-neighbor connections made the architecture suitable for VLSI implementation. This architecture is also well suited to many image-processing applications. Current research is directed towards design of efficient parallel algorithms to run on this architecture, as well as the study of the implementation of these in VLSI.

Rapidly increasing performance requirements of applications have spurred the next generation of complex, dynamic, heterogeneous, parallel/distributed computing system architectures. The emerging computational grid, tightly-coupled petaflop grids-in-a-box (GiBs), distributed sensor networks, System-on-Chip (SoC) and polymorphous computing (PCA) architectures are examples of such systems. To exploit the full potential of this new computing architecture, applications, as they execute, must be able to adapt to the continuously changing system.
Although some support for adaptive application development is available in the form of programming languages and runtime systems, there is a lack of high level system abstractions that model the dynamic behavior and runtime adaptivity.
The proposed research will address fundamental issues in modeling these dynamic, complex architectures and the design and evaluation of adaptive algorithms for such architectures. The focus of the proposed research will be on creating a formal framework to reason about adaptivity at an abstract level.
A direct educational impact of the proposed activity will be the introduction of new curriculum in academia, to impart knowledge on algorithm design aspects for dynamic system architectures. This will include initiating new course-work along with traditional courses offered on analysis of algorithms and architectures. One of the broader impacts we foresee is the preparation of future Grid/GiBs/SoC/PCA application developers.

Current packet networks depend on the fundamental assumption that an end-to-end path exists between a source and a destination. However, in a number of real networks termed Delay Tolerant Networks (DTNs), for example, inter-planetary networks, wildlife tracking networks and military networks, this assumption does not hold. With this in mind, this project designs a family of efficient routing schemes that are suitable for such networks. The routing approaches are innovative in that they exploit scheduled, anticipated, and ad hoc connectivity. The work also introduces an analytical framework to analyze the performance of routing schemes, compare their behavior and refine their design. Performance metrics of interest include average message delivery delay, energy efficiency, network throughput, etc. Finally, the work includes results from extensive simulations of DTN routing algorithms under realistic scenarios, and implementations of the champion algorithms in simulation packages such as ns-2.

The outcome of this project will improve the communication capabilities in space explorations, under-sea experimentation, wildlife tracking and habitat monitoring networks, ad hoc vehicular networks for content distribution, etc. The results are expected to improve DTN's readiness for deployment in NASA's deep space research programs, and NSF's south polar programs. It will become possible to provide Internet services to under-provisioned remote areas, high latitude scientific outposts, nomadic communities, etc. Hence, the proposal will have broad social and economic impact.