No Access

SYMBOLIC EXPRESSION ANALYSIS FOR COMPILED COMMUNICATION

Department of Electrical and Computer Engineering, University of Pittsburgh, Benedum Hall, Pittsburgh, Pennsylvania 15261, USA

Search for more papers by this author

SHUYI SHAO

Computer Science Department, University of Pittsburgh, Sennott Square Bldg., Pittsburgh, Pennsylvania 15260, USA

Search for more papers by this author

YU ZHANG

Department of Electrical and Computer Engineering, University of Pittsburgh, Benedum Hall, Pittsburgh, Pennsylvania 15261, USA

Search for more papers by this author

, and

RAMI MELHEM

Computer Science Department, University of Pittsburgh, Sennott Square Bldg., Pittsburgh, Pennsylvania 15260, USA

Search for more papers by this author

https://doi.org/10.1142/S0129626408003570Cited by:2 (Source: Crossref)

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.

Keywords:

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 et al. , On the feasibility of optical circuit switching for high performance computing systems , Proc. of SC ( 2005 ) . Google Scholar
J. Shalf et al. , Analyzing ultra-scale application communication requirements for a reconfigurable hybrid interconnect , Proc. of SC ( 2005 ) . Google Scholar
S. Shao, A. K. Jones and R. Melhem, IEEE Transactions on Parallel and Distributed Systems (2008), http://doi.ieeecomputersociety.org/10.1109/TPDS.2008.82. Google Scholar
Q. Xuet al., Nature 435, 325 (2005), DOI: 10.1038/nature03569. Crossref, Web of Science, Google Scholar
C. Kochar, A. Kodi and A. Louri, IEEE Photonics Technology Letters 19, 1304 (2007), DOI: 10.1109/LPT.2007.902347. Crossref, Web of Science, 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 et al. , 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. Delaluzet al., 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
M. R. Haghighat and C. D. Polychronopoulos, ACM Transactions on Programming Languages and Systems 18, 477 (1996), DOI: 10.1145/233561.233568. Crossref, Web of Science, 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 et al. , 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
R. P. Wilsonet al., 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 et al. , Linking compilation and visualization for massively parallel programs , Proc. of the APDCM Workshop at IPDPS ( 2007 ) . Google Scholar
A. M. Abdalass, J. F. Maitre and F. Musy, 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
T. Yamamotoet al., 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