|Our group is named Gajendra, and our research focus is compilers and parallelization. We have developed a domain-specific language for graph algorithms, know how to efficiently compute cycles in a graph with millions of vertices, and learning how to deal with evolving social networks.
>>>Systems Research at CSE, IITM
|Graph Algorithms on GPUs
The application of graphs to represent information is not new to computer science, but in recent years the scale of these graphs has grown many-folds and have recently reached the petabyte sizes. The current CPUs are inadequate to process the petabyte scale of the graphs. Modern GPUs are highly parallel, which makes them the right choice for processing such large scale graphs. Real world graphs also evolve over time, which involve repeating analysis, over a large number of versions of the graphs.
We have developed efficient extensions to find strongly connected components, and to find shortest paths in dynamic graphs.
- LightHouse: An Automated Code Generator for Graph Algorithms on GPUs; Shashidhar G, Rupesh Nasre; LCPC 2016 [Download artifact]
- GPU Centric Extensions for Parallel Strongly Connected Components Computation; Shrinivas Devshatwar, Madhur Amilkanthwar, Rupesh Nasre; GPGPU 2016 [Download artifact]
|Scalable Pointer Analysis
We present an information-merging technique and a new constraint graph for efficient computation of points-to information
for C programs. Pointer analysis is an important phase in the compilation process. The computed
points-to information and the alias information are useful for client analyses from varied domains
such as bug finding, data-flow analysis, identifying security vulnerabilities, and parallelization, to
name a few. Former research on pointer analysis has indicated that the main bottleneck towards
scalability is large propagation of points-to information in the constraint graph. To reduce the
propagation cost, we present a technique based on temporal similarity of points-to sets.
We also identify patterns of propagation and exploit those to optimize points-to information propagation.
- EagerMerge: A Technique for Efficient Points-to Analysis; Sudhir Samrit, Rupesh Nasre; ISSTA 2016 [Download artifact]
- Push-pull Constraint Graph for Efficient Points-to Analysis; Ratnakar Bollu, Rupesh Nasre; ISMM 2014
|Effective Synchronization in Parallel Programs
We present an algebraic model of synchronization for hierarchical data structures.
Each element of the algebraic structure denotes a synchronization option and represents a trade-off between the amount of concurrency and the cost of synchronization.
The algebraic formulation forms the basis for a framework of synchronization mechanisms on a hierarchical data structure.
Effective synchronization is key to scalable parallelization.
Several applications work on an abstract hierarchy of objects, and a parallel
execution on this hierarchy necessitates synchronization across workers
operating on different parts of the hierarchy.
Existing synchronization mechanisms are either too coarse, too inefficient, or too ad hoc,
resulting in reduced or unpredictable amount of concurrency.
With our formulation, we offer a range of possibilities in choosing synchronization in a hierarchical structure.
- DomLock: A New Multi-Granularity Locking Technique for Hierarchies; Saurabh Kalikar, Rupesh Nasre; TOPC 2017, PPoPP 2016 [Download Artifact]
Books / Thesis
- Scaling Context-Sensitive Points-to Analysis
- PhD Thesis
- 8,346,732 Method and apparatus for providing high availability of a database
- 8,086,603 Using the LUN type for storage allocation [updated]
- 7,925,631 Method and system for reporting inconsistency of file system persistent point in time images and automatically thawing a file system
- 7,890,504 Using the LUN type for storage allocation [original]
- 7,694,095 Managing snapshots using messages
- Medical Imaging, DBT. Arun Thittai (AM, PI), Ganapathy Krishnamurthi (ED), Rupesh Nasre
- Parallel Clustering, Shell
- Exploratory Research Grant, IITM
- Kris Gopalakrishnan Endowment for YFRA
- Business Rule Extraction, Hitachi. Ravindran Balaraman (PI) and Rupesh Nasre (co-PI)
- University Grant, Accenture. Sutanu Chakrabarti (PI), Deepak Khemani and Rupesh Nasre
- New Faculty Seed Grant, IIT Madras
- New Faculty Initiation Grant, IIT Madras