Parallel computing is entering the era of petascale machines, which brings
enormous computing power with it and new challenges to harness this power
efficiently. Machines with hundreds of thousands of processors already exist,
connected by complex interconnect topologies. Communication and specifically,
network contention is becoming an increasingly important factor affecting
overall performance.
The further different messages travel on the network, greater is the chance of
resource sharing between messages and hence, of contention. Recent studies on
IBM Blue Gene and Cray XT machines have shown that under contention, message
latencies can be severely affected. Realizing this fact, application developers
have started paying attention to the mapping of tasks to physical processors to
minimize contention. Placement of communicating tasks on nearby physical
processors can minimize the distance traveled by messages and reduce the
chances of contention.
This dissertation proposes algorithms and techniques for automatic mapping of
parallel applications to relieve the application developers of this burden.
The effect of contention on message latencies is studied in depth to guide the
design of mapping algorithms. The {\em hop-bytes} metric is proposed for the
evaluation of mapping algorithms and proved to be a better metric than the
previously used {\em maximum dilation} metric. The main focus of this
dissertation is on developing topology aware mapping algorithms for parallel
applications with regular and irregular communication patterns. These
algorithms along with pattern matching algorithms for communication graphs of
the applications form the automatic mapping framework suitable for most
parallel applications.
|
Prof. Laxmikant V. Kale (Chair and Director of Dissertation Research), Professor of Computer Science and Director, Parallel Programming Laboratory, UIUC
Prof. David A. Padua, Donald Biggar Willett Professor of Computer Science, UIUC
Prof. William D. Gropp, Paul and Cynthia Saylor Professor of Computer Science, UIUC
Dr. Matthew H. Reilly, Co-founder, Vice President of Semiconductor Development and Chief Engineer, SiCortex, Inc.
|
- Abhinav Bhatele and Laxmikant V. Kale, Quantifying Network Contention on Large Parallel Machines, submitted to Parallel Processing Letters (Special Issue on Large-Scale Parallel Processing), 2009 [pdf]
- Abhinav Bhatele, Eric Bohm, Laxmikant V. Kale, A Case Study of Communication Optimizations on 3D Mesh Interconnects, To appear in Proceedings of Euro-Par (Topic 13 - High Performance Networks), 2009 [pdf]
- Abhinav Bhatele, Laxmikant V. Kale, Nicholas Chen and Ralph E. Johnson, A Pattern Language for Topology Aware Mapping, Workshop on Parallel Programming Patterns (ParaPLOP 2009) [pdf]
- Abhinav Bhatele, Laxmikant V. Kale, Sameer Kumar, Dynamic Topology Aware Load Balancing Algorithms for MD Applications, Proceedings of International Conference on Supercomputing, 2009 [pdf]
- Abhinav Bhatele, Laxmikant V. Kale, An Evaluative study on the Effect of Contention on Message Latencies in Large Supercomputers, Proceedings of Workshop on Large-Scale Parallel Processing (IPDPS), 2009 [pdf]
- Abhinav Bhatele, Laxmikant V. Kale, Benefits of Topology-aware Mapping for Mesh Topologies, Parallel Processing Letters (Special issue on Large Scale Parallel Processing), Vol. 18, Issue 4, Pages 549-566, 2008 [pdf]
- Abhinav Bhatele, Laxmikant V. Kale, Application-specific Topology-aware Mapping for Three Dimensional Topologies, Proceedings of Workshop on Large-Scale Parallel Processing (IPDPS), 2008 [pdf]
- Abhinav Bhatele, Application-specific Topology-aware Mapping and Load Balancing for three-dimensional Torus Topologies, Master's Thesis, Department of Computer Science, University of Illinois, 2007 [pdf]
|
- Abhinav Bhatele, Automating Topology Aware Task Mapping for Large Supercomputers, Doctoral Showcase, SC '09, Portland, OR [pptx] [pdf]
- Abhinav Bhatele, Load Balancing and Topology Aware Mapping for Petascale Machines, Scaling to Petascale Summer School, UIUC, Urbana, IL [pptx] [pdf]
- Abhinav Bhatele, A Case Study of Communication Optimizations on 3D Interconnects, Euro-Par 2009, Delft, The Netherlands [pptx] [pdf]
- Abhinav Bhatele, Dynamic Topology Aware Load Balancing Algorithms for MD Applications, International Conference on Supercomputing (ICS) 2009, New York, NY [pptx] [pdf]
- Abhinav Bhatele, An Evaluative Study on the Effects of Contention on Message Latencies in Large Supercomputers, Workshop on Large-Scale Parallel Processing (IPDPS 2009), Rome, Italy [pptx] [pdf]
- Abhinav Bhatele, IS TOPOLOGY IMPORTANT AGAIN? - Effects of Contention on Message Latencies in Large Supercomputers, ACM Student Research Competition, SC '08, Austin, TX [pptx] [pdf]
- Abhinav Bhatele, Topology Aware Mapping for Performance Optimization of Science Applications, IACAT Seminar, UIUC, Urbana, IL [pptx]
- Abhinav Bhatele, Dynamic Topology Aware Load Balancing Algorithms for MD Applications, UK e-Science All Hands Meeting 2008, Edinburgh, UK [ppt]
- Abhinav Bhatele, Application-specific Topology-aware Mapping for Three Dimensional Topologies, LSPP (IPDPS '08), Miami, FL, 2008 [ppt]
- Abhinav Bhatele, Eric Bohm, Laxmikant V. Kale, Topology Aware Task Mapping Techniques: An API and Case Study (poster), PPoPP 2009 [pdf]
- Abhinav Bhatele, Laxmikant V. Kale, Effects of Contention on Message Latencies in Large Supercomputers (poster), ACM Student Research Competition, SC, 2008 [pdf]
- Abhinav Bhatele, Laxmikant V. Kale, Automatic Topology-Aware Task Mapping for Parallel Applications Running on Large Parallel Machines (poster), TCPP PhD Forum, IPDPS, 2008 [pdf]
|