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.