MPIPP: an automatic profile-guided parallel process placement toolset for SMP clusters and multiclusters

ABSTRACT

SMP clusters and multiclusters are widely used to execute message-passing parallel applications. The ways to map parallel processes to processors (or cores) could affect the application performance significantly due to the non-uniform communicating cost in such systems. It is desired to have a tool to map parallel processes to processors (or cores) automatically.Although there have been various efforts to address this issue, the existing solutions either require intensive user intervention, or can not be able to handle the situation of multiclusters well.In this paper, we propose a profile-guided approach to find the optimized mapping automatically to minimize the cost of point-to-point communications for arbitrary message passing applications. The implemented toolset is called MPIPP (MPI Process Placement toolset), and it includes several components:1) A tool to get the communication profile of MPI applications2) A tool to get the network topology of target clusters3) An algorithm to find optimized mapping, which is especially more effective than existing graph partition algorithms for multiclusters.We evaluated the performance of our tool with the NPB benchmarks and three other applications in several clusters. Experimental results show that the optimized process placement generated by our tools can achieve significant speedup.

REFERENCES

• 1: D. Bailey, T. Harris, W. Saphir, R. van der Wijngaart, A. Woo, and M. Yarrow. The NAS parallel benchmarks 2.0. Technical Report NAS-95-020, NASA Ames Research Center, Dec. 1995.
• 2: ChARMM Team. CHARMM. http://www.charmm.org
• 3: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 4: M. Deilmann, B. Roberg, M. Baum, and V. Scherer. Numerical simulation of evaporation and ignition of non-premixed n-heptane flames. In 5th International Conference on Parallel Processing and Applied Mathematics, Czestochowa, Poland, 2003.
• 5: Josep Díaz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002 [doi>10.1145/568522.568523]
• 6: Robert A. Fiedler, Optimization and scaling of shared-memory and message-passing implementations of the ZEUS hydrodynamics algorithm, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-16, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509598]
• 7: William Gropp , Ewing Lusk , Nathan Doss , Anthony Skjellum, A high-performance, portable implementation of the MPI message passing interface standard, Parallel Computing, v.22 n.6, p.789-828, Sept. 1996 [doi>10.1016/0167-8191(96)00024-5]
• 8: B. Hendrickson and R. Leland. The Chaco User's Guide Version 2. Sandia National Laboratories, Albuquerque NM, 1995.
• 9: Intel Ltd. Intel® Trace Analyzer & Collector. http://www.intel.com/cd/software/products/asmo-na/eng/cluster/tanalyzer/index.htm
• 10: Intel Ltd. Intel® MPI library. http://www.intel.com/cd/software/products/asmo-na/eng/cluster/mpi/index.htm
• 11: G. Karypis and V. Kumar. METIS, Unstructured Graph Partitioning and Sparse Matrix Ordering System. Version 2.0. Technical report, University of Minnesota, Department of Computer Science, Minneapolis, MN 55455, Aug. 1995.
• 12: B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2):291--307, Feb. 1970.
• 13: Thilo Kielmann , Rutger F. H. Hofman , Henri E. Bal , Aske Plaat , Raoul A. F. Bhoedjang, MagPIe: MPI's collective communication operations for clustered wide area systems, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.131-140, May 04-06, 1999, Atlanta, Georgia, United States
• 14: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, Number 4598, 13 May 1983, 220, 4598:671--680, 1983.
• 15: Guan-Joe Lai , Cheng Chen, A new scheduling strategy for NUMA multiprocessor systems, Proceedings of the 1996 International Conference on Parallel and Distributed Systems, p.222, June 03-06, 1996
• 16: Cheol H. Lee , M. Kim , Chan I. Park, An efficient K-way graph partitioning algorithm for task allocation in parallel computing systems, Proceedings of the first international conference on systems integration on Systems integration '90, p.748-751, March 1990, Morristown, New Jersey, United States
• 17: S.-Y. Lee , J. K. Aggarwal, A mapping strategy for parallel processing, IEEE Transactions on Computers, v.36 n.4, p.433-442, April 1987 [doi>10.1109/TC.1987.1676925]
• 18: V. M. Lo, Heuristic Algorithms for Task Assignment in Distributed Systems, IEEE Transactions on Computers, v.37 n.11, p.1384-1397, November 1988 [doi>10.1109/12.8704]
• 19: LS DYNA Team. LS DYNA. http://www.dynalook.com/
• 20: Richard Martin , Amin Vahdat , David Culler , Thomas Anderson, Effect of Communication Latency, Overhead, and Bandwidth on a Cluster, University of California at Berkeley, Berkeley, CA, 1998
• 21: Burkhard Monien , Stefan Schamberger, Graph Partitioning with the Party Library: Helpful-Sets in Practice, Proceedings of the 16th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'04), p.198-205, October 27-29, 2004 [doi>10.1109/SBAC-PAD.2004.18]
• 22: A. Pant , H. Jafri, Communicating efficiently on cluster based grids with MPICH-VMI, Proceedings of the 2004 IEEE International Conference on Cluster Computing, p.23-33, September 20-23, 2004
• 23: S. Sanyal, A. Jain, S. K. Das, and R. Biswas. A hierarchical and distributed approach for mapping large applications to heterogeneous grids using genetic algorithms. In CLUSTER, pages 496--499. IEEE Computer Society, 2003.
• 24: ScaliMPI Team. ScaliMPI. http://www.scali.no/download/doc/Scali_MPI_ Connect_FF_4_3_6_121104_EXT.pdf
• 25: Jesper Larsson Träff, Implementing the MPI process topology mechanism, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-14, November 16, 2002, Baltimore, Maryland
• 26: C. Walshaw , M. Cross, Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm, SIAM Journal on Scientific Computing, v.22 n.1, p.63-80, 2000 [doi>10.1137/S1064827598337373]
• 27: L. Weijian, C. Wenguang, L. Zhiguang, and Z. Weimin. Communication optimization for smp clusters. Tsinghua Science and Technology, 6(1):18--23, 2001.
• 28: WRF Team. WRF. http://www.wrf-model.org/

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

General Terms:
Algorithms, Experimentation, Performance

Keywords:
cluster, graph mapping, graph partitioning, parallel computing, process placement