Research

I have worked on a number of compiler optimization problems. These include formalizing instruction scheduling for clustered architectures, memory hierarchy optimizations and code generation. This work mixes compiler optimization, design, constraint modeling, and graph theoretic analysis. My vitae gives a more complete list of publications.

Compiler Optimization

Automatic Parallelization

Clustering is used in the embedded world to scale up instruction level parallelism in a cost effective manner. But it requires both spatial and temporal scheduling. Scheduling for space and time is known to be a hard problem. Previous work has proposed greedy approaches based on list scheduling, and phased approaches based on graph partitioning. We applied a constraint programming approach to schedule instructions on clustered architectures. We employ a problem decomposition technique that solves spatial and temporal scheduling in an integrated manner. We analyze the effect of different hardware parameters---such as the number of clusters, issue-width and inter-cluster communication cost---on application performance.

Papers

Memory Hierarchy Optimizations

Cache Conscious Data Placement

Embedded systems are increasingly making use of on-chip static memory in the form of caches to improve performance. The efficient utilization of the caches can improve data availability and more predictable cache performance. We tackle the problem of laying out data in memory given the sequence of accesses on a finite set of data objects such that cache-misses are minimized. In this paper we show that given the configuration of a cache and the data access sequence, it is possible to identify instances where there are no conflict misses. We describe an algorithm that can assign the data to cache for minimal number of misses if there exists a way in which conflict misses can be avoided altogether. We also describe the implementation of a heuristic for assigning data to cache for instances where the size of the cache forces conflict misses.

Papers

Foundations of Network Protocols

Axiomatic Basis For Communication

An axiomatic basis for communication presents an approach to formally model communication paradigms. Todays Internet has been extended widely beyond its well defined fundamental networking concepts. An axiomatic framework has been presented describing basic communication paradigms and concepts. Further, this concept is extended to dynamic networks and message processing. A Hoare inspired logic enables correctness proofs and formal analysis of protocols.

Papers