Scalable load-balance measurement for SPMD codes

ABSTRACT

Good load balance is crucial on very large parallel systems, but the most sophisticated algorithms introduce dynamic imbalances through adaptation in domain decomposition or use of adaptive solvers. To observe and diagnose imbalance, developers need system-wide, temporally-ordered measurements from full-scale runs. This potentially requires data collection from multiple code regions on all processors over the entire execution. Doing this instrumentation naively can, in combination with the application itself, exceed available I/O bandwidth and storage capacity, and can induce severe behavioral perturbations.

We present and evaluate a novel technique for scalable, low-error load balance measurement. This uses a parallel wavelet transform and other parallel encoding methods. We show that our technique collects and reconstructs system-wide measurements with low error. Compression time scales sublinearly with system size and data volume is several orders of magnitude smaller than the raw data. The overhead is low enough for online use in a production environment.

REFERENCES

• 1: M. D. Adams. The JPEG-2000 still image compression standard. Technical Report 2412, ISO/IEC JTC 1/SC 29/WG, December 2002.
• 2: M. D. Adams and F. Kossentini. JasPer: a software-based JPEG-2000 codec implementation. In Proceedings of the International Conference on Image Processing, 2000.
• 3: L.-M. Ang, H. N. Cheung, and K. Eshragian. EZW lgorith using depth-first representation of the wavelet zerotree. In Fifth International Symposium on Signal Processing and its Applications (ISSPA), pages 75--78, Brisbane, Australia, August 1999.
• 4: S. Browne , J. Dongarra , N. Garner , G. Ho , P. Mucci, A Portable Programming Interface for Performance Evaluation on Modern Processors, International Journal of High Performance Computing Applications, v.14 n.3, p.189-204, August 2000 [doi>10.1177/109434200001400303]
• 5: Holger Brunst , Hans-Christian Hoppe , Wolfgang E. Nagel , Manuela Winkler, Performance Optimization for Large Scale Computing: The Scalable VAMPIR Approach, Proceedings of the International Conference on Computational Science-Part II, p.751-760, May 28-30, 2001
• 6: Vasily Bulatov , Wei Cai , Jeff Fier , Masato Hiratani , Gregg Hommes , Tim Pierce , Meijie Tang , Moono Rhee , Kim Yates , Tom Arsenlis, Scalable Line Dynamics in ParaDiS, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.19, November 06-12, 2004 [doi>10.1109/SC.2004.53]
• 7: M. Casas, R. M. Badia, and J. Labarta. Automatic phase detection of MPI applications. Parallel Commuting: Architectures, Algorithms, and Applications, 38:129--136, 2007.
• 8: M. Casas, R. M. Badia, and J. Labarta. Automatic structure extraction from MPI applications. In European Conference on Parallel Computing (Euro-Par), pages 3--12, 2007.
• 9: Marc Casas , Rosa Badia , Jesús Labarta, Automatic analysis of speedup of MPI applications, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece [doi>10.1145/1375527.1375578]
• 10: P. Colella, D. T. Graves, D. Modiano, D. B. Serafini, and B. v. Straalen. Chombo software package for AMR applications. Technical Report (Lawrence Berkeley National Laboratory), 2000. Available from: http://seesar.lbl.gov/anag/chombo.
• 11: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 12: Luiz A. de Rose , Daniel A. Reed, SvPablo: A Multi-Language Architecture-Independent Performance Analysis System, Proceedings of the 1999 International Conference on Parallel Processing, p.311, September 21-24, 1999
• 13: P. Deutsch , J.-L. Gailly, ZLIB Compressed Data Format Specification version 3.3, RFC Editor, 1996
• 14: K. Fürlinger and M. Gerndt. ompP: A profiling tool for OpenMP. In Proceedings of the First International Workshop on OpenMP (IWOMP), 2005.
• 15: A. Gara, M. A. Blumrich, D. Chen, G. L.-T. Chiu, P. Coteus, M. E. Giampapa, R. A. Haring, P. Heidelberger, D. Hoenicke, G. V. Kopcsay, T. A. Liebsch, M. Ohmacht, B. D. Steinmacher-Burow, T. Takken, and P. Vranas. Overview of the Blue Gene/L system architecture. IBM Journal of Research and Development, 49(2/3), 2005.
• 16: J. Greenough, A. Kuhl, L. Howell, A. Shestakov, U. Creach, A. Miller, E. Tarwater, A. Cook, and B. Cabot. Raptor -- software and applications for BlueGene/L. In BlueGene/L Workshop. Lawrence Livermore National Laboratory, 2003. Available from: http://www.llnl.gov/asci/platforms/bluegene/agenda.html.
• 17: D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the Institute of Radio Engineers, 40(9):1098--1101, September 1952.
• 18: Ted Huffmire , Tim Sherwood, Wavelet-based phase classification, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152172]
• 19: Rade Kutil, Approaches to zerotree image and video coding on MIMD architectures, Parallel Computing, v.28 n.7-8, p.1095-1109, August 2002 [doi>10.1016/S0167-8191(02)00108-4]
• 20: S. Louis and B. R. de Supinski. BlueGene/L: Early application scaling results. In NNSA ASC Principal Investigator Meeting & BG/L Consortium System Software Workshop, February 2005. Available from: http://www-unix.mcs.anl.gov/~beckman/bluegene/SSW-Utah-2005/BGL-SSW22-LLNL-Apps.pdf.
• 21: Allen D. Malony , Wolfgang E. Nagel, The open trace format (OTF) and open tracing for HPC, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188480]
• 22: X. Martorell, N. Smeds, R. Walkup, J. R. Brunheroto, G. Almási, J. A. Gunnels, L. De Rose, J. Labarta, F. Escalé, J. Gimenez, H. Servat, and J. E. Moreira. Blue Gene/L performance tools. IBM Journal of Research and Development, 49(2--3):407--424, 2005.
• 23: J. Mellor-Crummey. HPCToolkit: Multi-platform tools for profile-based performance analysis. In 5th International Workshop on Automatic Performance Analysis (APART), November 2003.
• 24: MPI Forum. MPI: A message passing interface standard. International Journal of Supercomputer Applications and High Performance Computing, 8(3/4):159--416, 1994.
• 25: O. M. Nielsen and M. Hegland. Parallel performance of fast wavelet transforms. International Journal of High Speed Computing, 11(1):55--74, 2000.
• 26: M. Noeth, F. Mueller, M. Schulz, and B. R. de Supinski. Scalable compression and replay of communication traces in massively parallel environments. In International Parallel and Distributed Processing Symposium (IPDPS), March 26--30 2007.
• 27: Paradyn Project, Madison, WI. DynStackwalker Programmer's Guide, July 13 2007. Version 0.6b. Available from: http://ftp.cs.wisc.edu/pub/paradyn/releases/current_release/doc/stackwalker.pdf.
• 28: E. Perelman, M. Polito, J.-Y. Bouget, J. Sampson, B. Calder, and C. Dulong. Detecting phases in parallel applications on shared memory architectures. In International Parallel and Distributed Processing Symposium (IPDPS), 2006.
• 29: Philip C. Roth , Dorian C. Arnold , Barton P. Miller, MRNet: A Software-Based Multicast/Reduction Network for Scalable Tools, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.21, November 15-21, 2003
• 30: Martin Schulz , Bronis R. de Supinski, P^NMPI tools: a whole lot greater than the sum of their parts, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362663]
• 31: J. M. Shapiro. Embedded image coding using zerotrees of wavelet coefficients. IEEE Transactions on Signal Processing, 41(12):3445--3462, December 1993.
• 32: Sameer S. Shende , Allen D. Malony, The Tau Parallel Performance System, International Journal of High Performance Computing Applications, v.20 n.2, p.287-311, May 2006 [doi>10.1177/1094342006064482]
• 33: Brinkley Sprunt, Pentium 4 Performance-Monitoring Features, IEEE Micro, v.22 n.4, p.72-82, July 2002 [doi>10.1109/MM.2002.1028478]
• 34: Raymond S. Wagner , Richard G. Baraniuk , Shu Du , David B. Johnson , Albert Cohen, An architecture for distributed wavelet analysis and processing in sensor networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127816]
• 35: D. F. Walnut. An Introduction to Wavelet Analysis. Birkhäuser Boston, 2004.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Wavelets and fractals

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance