PDF

Contact Information

Lawrence Berkeley National Laboratory
Mailstop 50B-3238
1 Cyclotron Rd
Berkeley, CA 94720
Phone (O): 510-486-7460 (H): 510-502-0857
Email: KMadduri at lbl.gov

Education

• Georgia Institute of Technology, Atlanta, GA
  Ph.D., Computer Science, 2005 -- 2008
  Specialization: Computational Science and Engineering, Advisor: Prof. David A. Bader
• University of New Mexico, Albuquerque, NM
  M.S., Electrical and Computer Engineering, 2004 -- 2005
  Specialization: Computer Engineering, Advisor: Prof. David A. Bader
• Indian Institute of Technology Madras, Chennai, India
  B.Tech., Electrical Engineering, 2000 -- 2004

Research Interests

I am broadly interested in the areas of high performance computing, parallel graph algorithms, social network analysis, scientific data analysis and management, computational science, and multicore architectures.

Honors and Awards

• Luis W. Alvarez Postdoctoral Fellowship in Computational Science, Lawrence Berkeley National Laboratory, 2008.
• Outstanding Graduate Research Assistant award, College of Computing, Georgia Institute of Technology, 2008.
• Best Poster Award, IEEE Technical Committee for Parallel Processing (TCPP) PhD Forum held at the 22nd International Parallel and Distributed Processing Symposium (IPDPS), 2008.
• Gamma Beta Phi Society, Georgia Institute of Technology, 2008.
• ACM/IEEE-CS High Performance Computing Ph.D. Fellowship Honorable Mention, 2007.
• NASA Graduate Student Researchers Program (GSRP) Fellowship, 2006-07 and 2007-08.
• NSF Graduate Research Fellowship Program (GRFP) Honorable Mention, 2005.
• NSF-UNM Computer Science, Engineering and Mathematics Scholarship (CSEMS), January 2005.
• NSF Research Experience for Undergraduates (REU) award, June 2003.
• National Talent Search (NTSE) Scholarship for Undergraduate studies, National Council for Educational Research and Training (NCERT), Govt. of India, 2000 - 2004.

Research Experience

• Lawrence Berkeley National Laboratory, Postdoctoral researcher, August 2008 to Present.
I joined the Scientific Data Management research group at Berkeley lab as the 2008 Luis Alvarez postdoctoral fellow in Computational Science. I will be working on high-performance algorithms for large-scale graph analysis, research problems in massive scientific data analysis, and performance optimization of scientific applications on emerging high-performance computing systems.
• Georgia Institute of Technology, Graduate Research Assistant, Fall 2005 to Summer 2008.
Primarily conducted research on parallel algorithms for large-scale graph problems arising in Informatics. Notable related projects I have worked on include
a) SWARM: a parallel programming framework for discrete algorithms on multicore processors,
b) an experimental study of combinatorial algorithms on the Sony-Toshiba-IBM Cell processor, and
c) implementation and optimization of the HPCS SSCA Graph Analysis benchmark on emerging architectures and novel programming languages.
Dissertation title: A High-Performance Framework for Analyzing Massive Complex Networks.
Committee: David A. Bader, Jonathan Berry (Sandia Labs), Richard Fujimoto, Subhash Saini (NASA Ames), Richard Vuduc.
• NASA Ames Research Center, Visiting researcher, Summer 2006.
Performance Analysis and Optimization of NAS Parallel Benchmarks on the Cell processor. Research funded by a NASA graduate fellowship.
Advisor: Subhash Saini
• Sandia National Laboratories, Visiting researcher, Summer 2005 and Summer 2006.
Research on efficient graph traversal and shortest path algorithms on massively multithreaded architectures such as the Cray MTA-2.
Advisor: Jonathan Berry, Collaborators: Bruce Hendrickson, Joseph Crobak (Rutgers).
• University of New Mexico, Graduate Research Assistant, Fall 2004 to Summer 2005.
Worked on the design and implementation of the SSCA Graph Analysis benchmark, as part of the High Productivity Computing Systems (HPCS) project.
Advisor: David A. Bader
• University of New Mexico, NSF Research Experience for Undergraduates (REU) intern, Summer 2003.
Parallelized a compute-intensive VLSI CAD application, JEDI, used for state assignment of finite-state machines.
Advisor: David A. Bader
• National Remote Sensing Agency (India), Intern, Summer 2002.

Publications

Refereed Journal Publications

• D.A. Bader and K. Madduri, "A Graph-Theoretic Analysis of the Human Protein-Interaction Network Using Multicore Parallel Algorithms," Parallel Computing, 2008, to appear.
• K. Subramani and K.Madduri, "A Randomized Queueless algorithm for Breadth-First Search," International Journal of Computers and Their Applications, 15(3):177-186, 2008.
• D.A. Bader, V. Agarwal, K. Madduri, and S. Kang, "High performance combinatorial algorithm design on the Cell/B.E. processor," Parallel Computing 33(10-11): 720-740, 2007.
• D.A. Bader, K. Madduri, J.R. Gilbert, V. Shah, J. Kepner, T. Meuse, and A. Krishnamurthy, "Designing Scalable Synthetic Compact Applications for Benchmarking High Productivity Computing Systems," CTWatch Quarterly, 2(4B):41-51, November 2006.

Journal Submissions

• D.A. Bader, C.E. Heitsch, and K. Madduri, "Betweenness Centrality on an Integer Torus," September 2007.

Book Chapters

• K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak, "Parallel Shortest Path Algorithms for Solving Large-Scale Instances," in C. Demetrescu and A.V. Goldberg and D. Johnson, editors, Shortest Path Computations: Ninth DIMACS Challenge, AMS Press, 2008, to appear.
• D.A. Bader, C.E. Heitsch, and K. Madduri, "Large-Scale Network Analysis," in J. Kepner and J. Gilbert, editors, Graph Algorithms in the Language of Linear Algebra, SIAM Press, 2008, to appear.
• D.A. Bader, K. Madduri, G. Cong, and J. Feo, "Design of Multithreaded Algorithms for Combinatorial Problems," in S. Rajasekaran and J. Reif, editors, Handbook of Parallel Computing: Models, Algorithms, and Applications, CRC Press, 2007.
• K. Madduri, D.A. Bader, J.W. Berry, J.R. Crobak, and B.A. Hendrickson, "Multithreaded Algorithms for Processing Massive Graphs," in D.A. Bader, editor, Petascale Computing: Algorithms and Applications, CRC Press, 2007.

Refereed Conference and Workshop Publications

• D.A. Bader and K. Madduri, "SNAP: Small-world Network Analysis and Partitioning: an open-source parallel graph framework for the exploration of large-scale networks," The 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2008), Miami, FL, April 14-18, 2008.
• K. Subramani and K. Madduri, "Accomplishing Approximate FCFS fairness without queues," The 14th International Conference on High Performance Computing (HiPC 2007), Goa, India, December 18-21, 2007.
• D.A. Bader, S. Kintali, K. Madduri, and M. Mihail, "Approximating Betweenness Centrality," The 5th Workshop on Algorithms and Models for the Web-Graph (WAW2007), San Diego, CA, December 11-12, 2007.
• D.A. Bader, V. Agarwal, and K. Madduri, "On the Design and Analysis of Irregular Algorithms on the Cell Processor: A case study on list ranking," The 21th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2007), Long Beach, CA, March 26-30, 2007.
• D.A. Bader and K. Madduri, "A Graph-Theoretic Analysis of the Human Protein-Interaction Network Using Multi-core Parallel Algorithms," Sixth IEEE International Workshop on High Performance Computational Biology (HiCOMB 2007), Long Beach, CA, March 26-30, 2007.
• J.R. Crobak, J. Berry, K. Madduri, and D.A. Bader, "Advanced Shortest Paths Algorithms on a Massively-Multithreaded Architecture," Workshop on Multithreaded Architectures and Applications (MTAAP 2007), Long Beach, CA, March 26-30, 2007.
• D.A. Bader, V. Kanade, and K. Madduri, "SWARM: A Parallel Programming Framework for Multicore Processors," Workshop on Multithreaded Architectures and Applications (MTAAP 2007), Long Beach, CA, March 26-30, 2007.
• K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak, "An Experimental Study of A Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances," Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, January 6, 2007.
• K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak, "Parallel Shortest Path Algorithms for Solving Large-Scale Instances," 9th DIMACS Implementation Challenge -- The Shortest Path Problem, DIMACS Center, Rutgers University, Piscataway, NJ, November 13-14, 2006.
• D.A. Bader and K. Madduri, "Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2," The 35th International Conference on Parallel Processing (ICPP 2006), Columbus, OH, August 14-18, 2006.
• D.A. Bader and K. Madduri, "Parallel Algorithms for Evaluating Centrality Indices in Real-world Networks," The 35th International Conference on Parallel Processing (ICPP 2006), Columbus, OH, August 14-18, 2006.
• D.A. Bader and K. Madduri, "Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors," The 12th International Conference on High Performance Computing (HiPC 2005), D.A. Bader et al., (eds.), Springer-Verlag LNCS 3769, 465-476, Goa, India, December 2005.
• D.A. Bader and K. Madduri, "A Parallel State Assignment Algorithm for Finite State Machines," The 11th International Conference on High Performance Computing (HiPC 2004), L. Bougè and V.K. Prasanna, (eds.), Springer-Verlag LNCS 3296, 297-308, Bangalore, India, December 2004.
• K. Madduri, V.S. Chakravarthy and H.K. Aparna, "PATRAM -- A Handwritten Word Processor for Indian Languages," The 9th International Workshop on Frontiers in Handwriting Recognition (IWFHR-9), Tokyo, Japan, October 26-29, 2004.

Conference and Workshop Publications without Proceedings

• K. Madduri, "High Performance Combinatorial Techniques for Processing Dynamic Interaction Networks," SIAM Conference on Parallel Processing for Scientific Computing (PP08), Atlanta, GA, March 12-14, 2008.
• D.A. Bader and K. Madduri, "High-Performance Combinatorial Techniques for Analyzing Massive Dynamic Interaction Networks," DIMACS Workshop on Computational Methods for Dynamic Interaction Networks, DIMACS Center, Rutgers University, Piscataway, NJ, September 24-25, 2007.
• D.A. Bader and K. Madduri, "Efficient Shared-memory Algorithms and Implementations for Solving Large-scale Graph Problems," Minisymposium on High-Performance Computing with Large Graphs, 2006 SIAM Annual Meeting (AN06), Boston, MA, July 10-14, 2006.

Doctoral Colloquia

• "Efficiently Solving Large-scale graph problems on High-Performance Computing Systems," 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2008), Miami, FL, April 14-18, 2008.
• "Efficiently Solving Large-scale graph problems on High-Performance Computing Systems," IEEE/ACM Supercomputing (SC07), November 10-16, 2007.

Invited Talks

• Computer Science Research Institute, Sandia National Laboratories, April 9, 2008.
• Computer Science Department, University of California Davis, April 1, 2008.
• Computer Science and Mathematics Division, Oak Ridge National Laboratories, March 17, 2008.
• Computational Research Division, Lawrence Berkeley National Laboratory, March 10, 2008.
• National Security Agency, May 25, 2006.

Poster Presentations

• "SNAP: A Parallel Graph Framework for Large-scale Network Analysis," SIAM Conference on Parallel Processing for Scientific Computing (PP08), Atlanta, GA, March 12-14, 2008.
• "Efficient Implementation of Irregular Algorithms on Cell Multi-core Architecture," (with Virat Agarwal), Supercomputing 2006 Workshop: General-Purpose GPU Computing: Practice And Experience, Tampa, FL, November 13, 2006.
• "Parallel Algorithms for large-scale graph traversal and connectivity," Georgia Tech research exhibit, Supercomputing 2005, Seattle, WA, November 12-18, 2005.
• "Efficient Graph Algorithms and Implementations on the Cray MTA-2," Fall Creek Falls Conference: Computational Science at Scale, Pikeville, TN, October 16-18, 2005.

Research Software

I am the lead developer of and maintain the following research software codes:
• SNAP (Small-world Network Analysis and Partitioning) is a parallel framework for exploratory analysis of massive real-world networks.
• GraphAnalysis.org is a compendium of resources related to high-performance computing techniques applied to massive graph analysis.
• The SSCA Graph Analysis benchmark was designed as part of the High Productivity Computing Systems (HPCS) project to characterize performance of novel architectures and programming languages on graph-theoretic kernels.
• Parallel Shortest Paths (DIMACS): A fast, parallel single-source shortest path implementation for the 9th DIMACS Shortest Paths Challenge.
• GTGraph is a suite of synthetic random graph generators.
• Human PIN Analysis: We present the first topological analysis of a large-scale human protein interaction network. The source code for the parallel algorithms discussed in this paper are now part of the SNAP infrastructure.
I contribute to the following software projects:
• MTGL (Multithreaded Graph Library) is a C++ library for implementing complex graph algorithms on massively multithreaded systems.
• SWARM (SoftWare and Algorithms for Running on Multicore) is an open-source POSIX threads-based framework for parallel programming.
• cellbuzz is a collection of general-purpose and scientific libraries optimized for the Sony-Toshiba-IBM Cell processor.

Activities

Academic Community

• Program Committee Member, The 15th International Conference on High Performance Computing (HiPC 2008), Bangalore, India, December 18-21, 2008.
• Cyber co-chair, The 15th International Conference on High Performance Computing (HiPC 2008), Bangalore, India, December 18-21, 2008.
• Reviewer, IEEE Transactions on Parallel and Distributed Systems, Elsevier Parallel Computing, Elsevier Journal of Parallel and Distributed Computing, 2006-08.
• Student volunteer award, Supercomputing 2007, 2006, 2005.
• Judge, OpenMP Programming Contest, November 2005.
• Graduate student travel award, UCLA IPAM Graduate Summer School (GSS 2005), Los Angeles, CA, May 2005.
• Student volunteer, International Parallel and Distributed Processing Symposium (IPDPS 2005), Denver, CO, April 2005.

Professional Membership

• Member, IEEE, ACM, and SIAM.
• Member, IEEE Technical Committee for Parallel Processing (TCPP).

University Service

• Computational Science and Engineering Division liaison, Graduate Student Council (GSC), College of Computing, Georgia Tech, 2007-08.
• Faculty meeting representative, Graduate Student Council (GSC), College of Computing, Georgia Tech, 2006-07.
• High Performance Computing lab manager, CSE Division, College of Computing, Georgia Tech, 2006-08.

Technical Meetings Participation

• The 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2008), Miami, FL, April 2008.
• SIAM Conference on Parallel Processing for Scientific Computing (PP08), Atlanta, GA, March 2008.
• The 14th International Conference on High Performance Computing (HiPC 2007), Goa, India, December 2007.
• Supercomputing 2007 (SC07), Reno, NV, November 2007.
• DIMACS Workshop on Computational Methods for Dynamic Interaction Networks, DIMACS Center, Rutgers University, Piscataway, NJ, September 24-25, 2007.
• Georgia Tech, Sony/Toshiba/IBM Workshop on Software and Applications for the Cell/B.E. processor, Atlanta, GA, June 2007.
• The 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS 2007), Long Beach, CA, March 2007.
• The Second Workshop on Real Time and Interactive Digital Media Supercomputing (RIDMS-2), Phoenix, AZ, February 2007.
• DIMACS - Georgia Tech Workshop on Complex Networks and their Applications, Georgia Institute of Technology, Atlanta, GA, January 2007.
• The 13th International Conference on High Performance Computing (HiPC 2006), Bangalore, India, December 2006.
• Supercomputing 2006 (SC06), Tampa, FL, November 2006.
• The Ninth DIMACS Implementation Challenge: The Shortest Path Problem, DIMACS Center, Rutgers University, Piscataway, NJ, November 2006.
• The 35th International Conference on Parallel Processing (ICPP 2006), Columbus, OH, August 2006.
• SIAM Annual Meeting (AN06), Boston, MA, July 2006.
• The 12th International Conference on High Performance Computing (HiPC 2005), Goa, India, December 2005.
• Workshop on Enabling Petascale Science and Engineering Applications, Georgia Institute of Technology, Atlanta, GA, December 2005.
• Supercomputing 2005 (SC05), Seattle, WA, November 2005.
• Fall Creek Falls Conference: Computational Science at Scale, TN, October 2005.
• UCLA IPAM Graduate Summer School (GSS 2005), Los Angeles, CA, May 2005.
• The 11th International Conference on High Performance Computing (HiPC 2004), Bangalore, India, December 2004.
• The 10th International Conference on High Performance Computing (HiPC 2003), Hyderabad, India, December 2003.

Personal

US citizen.