Topology-aware tile mapping for clusters of SMPs

ABSTRACT

We propose a technique to optimize the performance of applications using distributed dense arrays and characterized by a nearest-neighbor communication profile by exploiting the topology of SMP clusters. The topological information is used to map array tiles to processors to reduce network communication and improve utilization of shared memory for inter-process communication. The potential benefits of using the SMP-aware mapping are demonstrated through a simulation, as well as a real application solving a wind-driven ocean circulation model on an IBM SP. On 256 processors, the execution time was reduced by almost 30 percent without any changes to the original application source code. The proposed mapping approach is applicable to multiple programming models and distributed array management systems.

REFERENCES

• 1: Olivier Beaumont , Vincent Boudet , Antoine Petitet, A Proposal for a Heterogeneous Cluster ScaLAPACK (Dense Linear Solvers), IEEE Transactions on Computers, v.50 n.10, p.1052-1070, October 2001 [doi>10.1109/12.956091 ]
• 2: Eleanor Chu, Impact of Physical/Logical Network Topology on Parallel Matrix Computation, International Journal of High Performance Computing Applications, v.13 n.2, p.124-145, May 1999 [doi>10.1177/109434209901300203]
• 3: Eleanor Chu , Alan George, QR factorization of a dense matrix on a hypercube multiprocessor, SIAM Journal on Scientific and Statistical Computing, v.11 n.5, p.990-1028, September 1990 [doi>10.1137/0911057]
• 4: Daniel G. Chavarría-Miranda , Alain Darte , Robert Fowler , John M. Mellor-Crummey, Generalized Multipartitioning for Multi-Dimensional Arrays, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.164, April 15-19, 2002
• 5: Alain Darte , John Mellor-Crummey , Robert Fowler , Daniel Chavarría-Miranda, Generalized multipartitioning of multi-dimensional arrays for parallelizing line-sweep computations, Journal of Parallel and Distributed Computing, v.63 n.9, p.887-911, September 2003 [doi>10.1016/S0743-7315(03)00103-5]
• 6: T. A. El-Ghazawi, W. W. Carlson, and J. M. Draper. UPC Language Specifications v1.1.1, October 2003.
• 7: Ian Foster , Jonathan Geisler , Carl Kesselman , Steven Tuecke, Managing multiple communication methods in high-performance networked computing systems, Journal of Parallel and Distributed Computing, v.40 n.1, p.35-48, Jan. 10, 1997 [doi>10.1006/jpdc.1996.1266 ]
• 8: Marc Snir , Steve W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
• 9: Charles H. Koelbel , David B. Loveman , Robert S. Schreiber , Guy L. Steele, Jr. , Mary E. Zosel, The high performance Fortran handbook, MIT Press, Cambridge, MA, 1994
• 10: Steven S. Lumetta , Alan M. Mainwaring , David E. Culler, Multi-protocol active messages on a cluster of SMP's, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-22, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509596]
• 11: Prasant Mohapatra, Wormhole routing techniques for directly connected multicomputer systems, ACM Computing Surveys (CSUR), v.30 n.3, p.374-410, Sept. 1998 [doi>10.1145/292469.292472]
• 12: Jarek Nieplocha , Bryan Carpenter, ARMCI: A Portable Remote Memory Copy Libray for Ditributed Array Libraries and Compiler Run-Time Systems, Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.533-546, April 12-16, 1999
• 13: Jaroslaw Nieplocha , Robert J. Harrison , Richard J. Littlefield, Global arrays: a nonuniform memory access programming model for high-performance computers, The Journal of Supercomputing, v.10 n.2, p.169-189, June 1996
• 14: Jarek Nieplocha , Jialin Ju , Tjerk P. Straatsma, A Multiprotocol Communication Support for the Global Address Space Programming Model on the IBM SP, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.718-728, August 29-September 01, 2000
• 15: Jarek Nieplocha , Bruce Palmer , Vinod Tipparaju , Manojkumar Krishnan , Harold Trease , Edoardo Aprà, Advances, Applications and Performance of the Global Arrays Shared Memory Programming Toolkit, International Journal of High Performance Computing Applications, v.20 n.2, p.203-231, May 2006 [doi>10.1177/1094342006064503]
• 16: Robert W. Numrich , John Reid, Co-array Fortran for parallel programming, ACM SIGPLAN Fortran Forum, v.17 n.2, p.1-31, Aug. 1998 [doi>10.1145/289918.289920]

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Experimentation, Languages, Measurement, Performance

Keywords:
clusters of SMPs, communication optimization, data layout optimization, topology awareness