Description

This is the page related to the ASCR DOE X-Stack software research project "Compiled MPI" (short: compi) at the University of Illinois at Urbana-Champaign (UIUC) led by Torsten Hoefler. This project is a joint project with Lawrence Livermore National Laboratory (LLNL, Co-PIs Dan Quinlan and Greg Bronevetsky) and Indiana University (IU, Co-PI Andrew Lumsdaine).

UIUC and IU are responsible for runtime optimization and integration while LLNL handles the compiler infrastructure based on ROSE and the transformations.

Grad Student RAs Needed

Communication Optimization

This project deals with the static and dynamic optimization of communication schedules. Communication schedules are a set of communication operations and dependencies and define an order of their execution. A set of such operations and dependencies form a global communication graph. The goal of this project is to optimize the communication graph in a given model (e.g., LogGP) and to compare the quality of solutions.

For example, a broadcast communication from node 0 to nodes 1..3 can be expressed as the set {(0,1), (0,2), (0,3), (0,4)} (where a tuple (x,y) represents communication from x to y) or {(0,1}, (1,3), (0,2)} in a tree-like shape. Using a broadcast tree is more efficient in this trivial example. The project aims to develop model-based optimization techniques for the optimization of such communication operation represented in the tuple-form above. The main work is to develop and proof optimality of algorithms working on this tuple-form using well-known communication models such as LogGP.

Reaching optimality is generally very hard. We plan to follow three avenues: (1) analytical algorithms and proofs, (2) well-known optimization methods (linear or integer optimization), and (3) heuristics and learning-based methods. The results should be implemented in an MPI-like library.

The student working on this project should know what MPI is, be familiar with the C and C++ programming languages and he should be very familiar with linear optimization, (mixed) integer programming and basic network models. The student should understand the papers Alexandrov et al. "LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation" and Bruck et al. "Efficient Algorithms for All-to-All Communications in Multi-Port Message-Passing Systems" well.

For previous work in this area see references [3].

MPI Shared Memory Optimization

References

PPoPP'13	[1] A. Friedley, Torsten Hoefler, G. Bronevetsky, Andrew Lumsdaine:
		Ownership Passing: Efficient Distributed Memory Programming on Multi-core Systems In Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming, presented in Shenzen, China, pages 177--186, ACM, ISBN: 978-1-4503-1922-5, Feb. 2013, (acceptance rate: 18%, 26/146)

PACT'12	[1] Torsten Hoefler, Timo Schneider:
		Runtime Detection and Optimization of Collective Communication Patterns In Proceedings of the 21st international conference on Parallel Architectures and Compilation Techniques (PACT), presented in Minneapolis, MN, USA, pages 263--272, ACM, ISBN: 978-1-4503-1182-3, Sep. 2012, (acceptance rate: 18.9%, 39/207)

EuroMPI'12	[1] Timo Schneider, Robert Gerstenberger, Torsten Hoefler:
		Micro-Applications for Communication Data Access Patterns and MPI Datatypes Vol 7490, In Recent Advances in the Message Passing Interface - 19th European MPI Users' Group Meeting, EuroMPI 2012, Vienna, Austria, September 23-26, 2012. Proceedings, presented in Vienna, Austria, pages 121-131, Springer, ISBN: 978-3-642-33517-4, Sep. 2012, Invited to a journal special issue on top picks from EuroMPI'12.

EuroMPI'11	[1] William Gropp, Torsten Hoefler, Rajeev Thakur and Jesper Larsson Träff:
		Performance Expectations and Guidelines for MPI Derived Datatypes Vol 6960, In Recent Advances in the Message Passing Interface (EuroMPI'11), presented in Santorini, Greece, pages 150-159, Springer, ISBN: 978-3-642-24448-3, Sep. 2011,

EuroMPI'10	[2] Torsten Hoefler and S. Gottlieb:
		Parallel Zero-Copy Algorithms for Fast Fourier Transform and Conjugate Gradient using MPI Datatypes Vol LNCS 6305, In Recent Advances in the Message Passing Interface (EuroMPI'10), presented in Stuttgart, Germany, pages 132--141, Springer, ISSN: 0302-9743, ISBN: 078-3-642-15645-8, Sep. 2010,

ICPP'09	[3] Torsten Hoefler, Christian Siebert and Andrew Lumsdaine:
		Group Operation Assembly Language - A Flexible Way to Express Collective Communication In ICPP-2009 - The 38th International Conference on Parallel Processing, presented in Vienna, Austria, IEEE, ISBN: 978-0-7695-3802-0, Sep. 2009, (acceptance rate 32%, 71/220)