High-Performance Graph Computations
- G. M. Slota and K. Madduri, “Parallel color-coding,” Parallel Computing, vol. 47, pp. 51-69, 2015.
- G. M. Slota, S. Rajamanickam, and K. Madduri, “High-performance graph analytics on manycore processors,” in Proc. 29th IEEE Int'l. Parallel and Distributed Processing Symposium (IPDPS). IEEE, May 2015, pp. 17-27.
- G. M. Slota and K. Madduri, “Simple parallel biconnectivity algorithms for multicore platforms,” in Proc. 20th IEEE Int'l. Conf. on High Performance Computing (HiPC). IEEE, Dec. 2014, pp. 1-10.
- G. M. Slota, K. Madduri, and S. Rajamanickam, “PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks,” in Proc. 2nd IEEE Int'l. Conf. on Big Data (BigData). IEEE, Oct. 2014, pp. 481-490.
- T. Panitanarak and K. Madduri, “Performance analysis of single-source shortest path algorithms on distributed-memory systems,” in Proc. 6th SIAM Workshop on Combinatorial Scientific Computing (CSC), Jul. 2014, pp. 60-63.
- K. Madduri, V. Rengasamy, and P. Medvedev, “SPRITE: A fast parallel SNP detection pipeline,” poster presentation at the American Society of Human Genetics (ASHG) Annual Meeting, Oct. 2015.
- K. Madduri, “Parallel analysis of graph-structured data in genomics and proteomics,” First Int'l. Workshop on Big Data in Life Sciences (BigLS), Jun. 2013.
- K. Madduri, “High-performance metagenomic data clustering and assembly,” SIAM Annual Meeting, Jul. 2012.
- B. Wang, S. Ethier, W. Tang, T. Williams, K. Ibrahim, K. Madduri, S. Williams, and L. Oliker, “Kinetic turbulence simulations at extreme scale on leadership-class systems,” in Proc. ACM/IEEE Conf. on Supercomputing (SC), Nov. 2013, pp. 82:1-82:12.
- K. Ibrahim, K. Madduri, S. Williams, B. Wang, S. Ethier, and L. Oliker, “Analysis and optimization of gyrokinetic toroidal simulations on homogenous and heterogenous platforms,” Int'l. Journal of High Performance Computing Applications (IJHPCA), vol. 27, no. 4, pp. 454-473, 2013.
- K. Madduri, J. Su, S. Williams, L. Oliker, S. Ethier, and K. Yelick, “Optimization of parallel particle-to-grid interpolation on leading multicore platforms,” IEEE Trans. Parallel Distrib. Syst., vol. 23, no. 10, pp. 1915-1922, 2012.
- K. Madduri, K. Ibrahim, S. Williams, E.-J. Im, S. Ethier, J. Shalf, and L. Oliker, “Gyrokinetic toroidal simulations on leading multi- and manycore HPC systems,” in Proc. Conf. on High Performance Computing, Networking, Storage and Analysis (SC). ACM, Nov. 2011, p. 23.
- D. Hadka, P. Reed, and K. Madduri, “Scalability analysis of the asynchronous, master-slave multiobjective evolutionary algorithm,” in Proc. 16th Int'l. Workshop on Nature Inspired Distributed Computing (NIDISC), May 2013, pp. 425-434.
- A. Chandramowlishwaran, J. Choi, K. Madduri, and R. Vuduc, “Brief announcement: Towards a Communication optimal Fast Multipole Method and its implications at Exascale,” in Proc. 24th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA). ACM, Jun. 2012, pp. 182-184.
- R. Sudarsan, J. Borrill, C. Cantalupo, T. Kisner, K. Madduri, L. Oliker, Y. Zheng, and H. Simon, “Cosmic microwave background map-making at the petascale and beyond,” in Proc. 25th Int'l. Conf. on Supercomputing (ICS). ACM, May-June 2011, pp. 305-316.
- A. Kaiser, S. Williams, K. Madduri, K. Ibrahim, D. Bailey, J. Demmel, and E. Strohmaier, “A case for a testbed of kernels for software/hardware co-design research,” in Proc. 2nd USENIX Workshop on Hot Topics in Parallelism (HotPar). USENIX, Jun. 2010.
- K. Madduri and K. Wu, “Massive-scale RDF processing using compressed bitmap indexes,” in Proc. 23rd Int'l. Conf. on Scientific and Statistical Database Management (SSDBM), ser. LNCS, J. Cushing, J. French, and S. Bowers, Eds., vol. 6809. Springer, Jul. 2011, pp. 470-479.
- K. Wu, K. Madduri, and S. Canon, “Multi-level bitmap indexes for flash memory storage,” in Proc. 14th Int'l. Database Engineering & Applications Symposium (IDEAS). ACM, Aug. 2010, pp. 114-116.
- K. Madduri and K. Wu, “Efficient joins with compressed bitmap indices,” in Proc. 18th ACM Conf. on Information and Knowledge Management (CIKM). ACM, Nov. 2009, pp. 1017-1026.
Graph-based combinatorial analysis of data offers valuable insight, but typical graph computations perform poorly on modern computing platforms. Traditional serial algorithms and graph software achieve a very low fraction of peak system performance (measured through processor, memory bandwidth, and cache utilization) for routine graph analytics on laptops and workstations. The situation gets worse for massive graph analysis on emerging high-end multicore platforms, accelerators, supercomputers, and clouds. The common themes in parallel algorithm design are work efficiency, minimizing communication, improving locality of memory references, and ensuring load-balanced computation. With graph analysis, it is challenging to design algorithms for current platforms that simultaneously optimize for all these constraints. Our group uses a combination of theoretical analysis, architecture and data-dependent performance modeling, new data-centric speedup heuristics, and known parallel performance optimization strategies, to design practical parallel algorithms and develop scalable, efficient implementations. We study algorithms for both classical graph-theoretic problems such as breadth-first search, shortest paths, and graph connectivity, as well as emerging application-driven and application-dependent problem formulations such as centrality analysis, identifying communities, dynamic networks, and detecting frequently-occurring patterns. We gratefully acknowledge support for this work through an NSF CAREER grant and an XSEDE startup allocation.
Computational Genomics
The massive volumes of next-generation sequencing data pose significant computational and data analysis challenges. Several bioinformatics problems have combinatorial problem formulations that utilize string and graph algorithms and discrete data structures. Our group is working on new methods and parallel software for accelerating the genetic variant detection pipeline, and for the problems of de Bruijn graph-based de novo assembly of genomes and microbial metagenomes, metagenomic sequence clustering, and novel virus discovery. This research is supported in part by an NSF XPS award.