SYMBOLIC EXPRESSION ANALYSIS FOR COMPILED COMMUNICATION
Abstract
Compiled communication can benefit the parallel application design and performance in several ways such as analyzing the communication pattern to optimize a configurable network for performance improvement or to visualize the communication requirements to study and improve the application design. In this article we present symbolic expression analysis techniques in a MPI parallel compiler. Symbolic expression analysis allows the identification and representation of the communication pattern and also assists in the determination of communication phases in MPI parallel applications at compile-time. We demonstrate that using compiler analysis based on symbolic expression analysis to determine the communication pattern can provide an accurate visualization of the communication requirements. Using information from the compiler to program a circuit switching interconnect in multiprocessor systems has the potential to achieve more efficient communication with lower cost compared to packet/wormhole switching. For example, we demonstrate that our compiler approach provides an average of 2.6 times improvement in message delay over a threshold-based runtime system for our benchmarks with a maximum improvement of 9.7 times.
This work is partially supported by DARPA contract No. NBCH3039004 in the context of the PERCS project and NSF award number 0702452.
References
-
S. Shao , A. K. Jones and R. Melhem , A compiler-based communication analysis approach for multiprocessor systems , Proc. of the Int. Parallel and Distributed Procssing Syrap. (IPDPS) ( 2006 ) . Google Scholar -
K. J. Barker , On the feasibility of optical circuit switching for high performance computing systems , Proc. of SC ( 2005 ) . Google Scholar -
J. Shalf , Analyzing ultra-scale application communication requirements for a reconfigurable hybrid interconnect , Proc. of SC ( 2005 ) . Google Scholar - IEEE Transactions on Parallel and Distributed Systems (2008), http://doi.ieeecomputersociety.org/10.1109/TPDS.2008.82. Google Scholar
- Nature 435, 325 (2005), DOI: 10.1038/nature03569. Crossref, ISI, Google Scholar
- IEEE Photonics Technology Letters 19, 1304 (2007), DOI: 10.1109/LPT.2007.902347. Crossref, ISI, Google Scholar
-
A. Shacham , K. Bergman and L. P. Carloni , The case for low-power photonic networks on chip , Proc. of the Design Automation Conference (DAC) ( 2007 ) . Google Scholar -
A. Shacham , Photonic noc for dma communications in chip multiprocessors , Proc. of Hot Interconnects ( Stanford University , 2007 ) . Google Scholar - MPI: A Message-Passing Interface Standard, Message Passing Interface Forum, June 1995 . Google Scholar
V. Delaluz , Dram energy management using software and hardware directed power mode control, IEEE International Symposium on High-Performance Computer Architecture (2001) pp. 159–169. Google Scholar- ACM Transactions on Programming Languages and Systems 18, 477 (1996), DOI: 10.1145/233561.233568. Crossref, ISI, Google Scholar
P. Tu and D. Padua , Gated ssa-based demand-driven symbolic analysis for parallelizing compilers, Proc. of SC (1995) pp. 414–423. Google Scholar-
X. Yuan , R. Melhem and R. Gupta , Compiled communication for all-optical TDM networks , Proc. of SC ( 1996 ) . Google Scholar -
D. Shires , L. Pollock and S. Sprenkle , Program flow graph construction for static analysis of mpi programs , Proc. of Int. Conf. on Parallel and Distributed Processing Technigues and Applications(PDPTA) ( 1999 ) . Google Scholar F. Cappello and C. Germain , Toward high communication performance through compiled communications on a circuit switched interconnection network, Proc. of the Int. Symp. on High Performance Computer Architecture (HPCA) (1995) pp. 44–53. Google Scholar-
Z. Ding , Switch design to enable predictive multiplexed switching in multiprocessor networks , Proc. of the Int. Parallel and Distributed Procssing Symp. (IPDPS) ( 2005 ) . Google Scholar -
S. Muchnick , Advanced Compiler Design and Implementation ( Morgan Kaufmann , 1997 ) . Google Scholar - SIGPLAN Notices (1994). Google Scholar
- G. R. Watson and C. E. Rasmussen, "A strategy for addressing the needs of advanced scientific computing using eclipse as a parallel tools platform," Los Alamos National Laboratory, P.O. Box 1663, MS B287, Los Alamos, NM 87545, Tech. Rep. LA-UR-05-9114, December 2005 . Google Scholar
- IBM Corporation, "Eclipse platform technical overview," The Eclipse Foundation, Tech. Rep., December 2005, www.eclipse.org . Google Scholar
-
A. K. Jones , Linking compilation and visualization for massively parallel programs , Proc. of the APDCM Workshop at IPDPS ( 2007 ) . Google Scholar - , Multigrid Methods II, eds.
W. Hackbusch and U. Trottenberg (Springer-Verlag, Berlin, 1986) pp. 1–6. Crossref, Google Scholar - C. C. Douglas and M. B. Douglas, "MGNet Bibliography," Department of Computer Science and the Center for Computational Sciences, University of Kentucky, Lexington, KY, USA and Department of Computer Science, Yale University, New Haven, CT, USA, 1991-2002 (last modified on September 28, 2002); see http://www.mgnet.org/mgnet-bib.html . Google Scholar
- NTT Technical Review 1, 37 (2003). Google Scholar
- LLNL, "The asci comops benchmark code," http://www.llnl.gov/asci_ benchmarks/asci/limited/comops/asci_comops.html . Google Scholar


