Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Moshe Y. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany
4757
Franck Cappello Thomas Herault Jack Dongarra (Eds.)
Recent Advances in Parallel Virtual Machine and Message Passing Interface 14th European PVM/MPI Users’ Group Meeting Paris, France, September 30 - October 3, 2007 Proceedings
13
Volume Editors Franck Cappello INRIA Futurs LRI, Bat 490 University Paris South 91405 Orsay France E-mail:
[email protected] Thomas Herault Universite Paris Sud-XI Laboratoire de Recherche en Informatique Bâtiment 490 91405 Orsay France E-mail:
[email protected] Jack Dongarra University of Tennessee Computer Science Department 1122 Volunteer Blvd, Knoxville, TN 37996-3450, USA E-mail:
[email protected]
Library of Congress Control Number: 2007935601 CR Subject Classification (1998): D.1.3, D.2.3, F.1.2, G.1.0, B.2.1, B.2.1, C.1.2 LNCS Sublibrary: SL 2 – Programming and Software Engineering ISSN ISBN-10 ISBN-13
0302-9743 3-540-75415-6 Springer Berlin Heidelberg New York 978-3-540-75415-2 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springer.com © Springer-Verlag Berlin Heidelberg 2007 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 12168712 06/3180 543210
Preface
Thirteen years after the publication of the first MPI (message passing interface) specification and 17 years after the first published paper on PVM (parallel virtual machine), MPI and PVM have emerged as standard programming environments and continue to be the development environment of choice for a large variety of applications, hardware platforms, and usage scenarios. There are many reasons behind this success and one of them is certainly the strength of its community. EuroPVM/MPI is a flagship conference for this community, established as the premier international forum for researchers, users, and vendors to present their latest advances in MPI and PVM. EuroPVM/MPI is the forum where fundamental aspects of message passing, implementations, standards, benchmarking, performance, and new techniques are presented and discussed by researchers, developers and users from academia and industry. EuroPVM/MPI 2007 was organized by INRIA in Paris, September 29 to October 3, 2007. This was the 14th issue of the conference, which takes place each year at a different European location. Previous meetings were held in Bonn (2006), Sorrento (2005), Budapest (2004), Venice (2003), Linz (2002), Santorini (2001), Balatonf¨ ured (2000), Barcelona (1999), Liverpool (1998), Krakow (1997), Munich (1996), Lyon (1995), and Rome (1994). The main topics of the meeting were collective operations, one-sided communication, parallel applications using the message passing paradigm, MPI standard extensions or evolution, fault tolerance, formal verification of MPI processes, MPI-I/O, performance evaluation, and hierarchical infrastructures (parallel computers and Grids). For this year’s conference, the Program Committee Co-chairs invited six outstanding researchers to present lectures on different aspects of the message passing paradigm: Tony Hey, who co-authored the first draft for the MPI standard, presented “MPI: Past, Present and Future,” Al Geist, one of the authors of PVM, presented “Sustained PetaScale, the Next MPI Challenge,” Satoshi Matsuoka, a pioneer of the Grid Computing, presented “The Tsubame Cluster Experience,” Ewing Lusk, one of the leaders of MPICH, presented “New and Old Tools and Programming Models for High-Performance Computing,” George Bosilca, one of the leading members of OpenMPI, presented “The X-Scale Challenge,” and Bernd Mohr, a pioneer in performance analysis tools for Parallel Computing, presented “To Infinity and Beyond!?”. In addition to the conference main track, the meeting featured the sixth edition of the special session “ParSim 2007 – Current Trends in Numerical Simulation for Parallel Engineering Environments.” The conference also included three tutorials, one on “Using MPI-2: A Problem-Based Approach” by William Gropp and Ewing Lusk, the second by Stephen Siegel on “Verifying Parallel Programs with MPI-Spin,” and the third by George Bosilca and Julien Langou on “Advanced MPI Programming.”
VI
Preface
Contributions to EuroPVM/MPI 2007 and the special session ParSim were submitted in May and June, respectively. Out of the 68 submitted full papers, 40 were selected for presentation at the conference. The task of reviewing was carried out smoothly within very strict time limits by a large Program Committee, which included members from most of the American and European groups involved in MPI and PVM development, as well as from significant user communities. Almost all papers received four reviews, some even five, and none fewer than three, which provided a solid basis for the Program Chairs to make the final selection for the conference program. The result was a well-balanced, focused, and high-quality program. Out of the accepted 40 papers, four were selected as outstanding contributions to EuroPVM/MPI 2007, and were presented in special, plenary sessions: – “Full Bandwidth Broadcast, Reduction and Scan With Only Two Trees” by Peter Sanders, Jochen Speck and Jesper Larsson Traff – “Process Cooperation in Multiple Message Broadcast” by Bin Jia – “Self-Consistent MPI Performance Requirements” by Jesper Larsson Traff, William Gropp and Rajeev Thakur – “Test Suite for Evaluating Performance of MPI Implementations That Support MPI THREAD MULTIPLE” by Rajeev Thakur and William Gropp An important part of EuroPVM/MPI is the technically oriented vendor session. At EuroPVM/MPI 2007 seven significant vendors of hardware and software for high-performance computing (Microsoft, Hewlett Packard, IBM, CISCO, Myricom, Intel, and Voltaire) presented their latest products and developments. Information about the conference can be found at the conference Web site: http://pvmmpi07.lri.fr/, which will be kept available. The proceedings were edited by Franck Cappello and Thomas Herault. The EuroPVM/MPI 2007 logo was designed by Ala Rezmerita. The program and general chairs would like to thank all who contributed to making EuroPVM/MPI 2007 a fruitful and stimulating meeting, be they technical paper or poster authors, Program Committee members, external referees, participants, or sponsors. We would like to express our gratitude to all the members of the Program Committee and the additional reviewers, who ensured the high quality of Euro PVM/MPI 2007 with their careful work. Finally, we would like to thank deeply INRIA and LRI for their support and efforts in organizing this event. In particular, we would like to thank Catherine Girard (INRIA), Nicole Lefevre (LRI), Gaelle Dorkeld (INRIA), and Chantal Girodon (INRIA). A special thanks to all PhD students who helped in the logistics of the conference. October 2007
Franck Cappello Thomas Herault Jack Dongarra
Organization
General Chair Jack J. Dongarra
University of Tennessee, Knoxville, USA
Program Chairs Franck Cappello Thomas Herault
INRIA Universit´e Paris Sud-XI / INRIA
Program Committee George Almasi Ranieri Baraglia Richard Barrett Gil Bloch George Bosilca Hakon Bugge Franck Cappello Barbara Chapman Brian Coghlan Yiannis Cotronis Jose Cunha Marco Danelutto Luiz DeRose Frederic Desprez Erik D’Hollander Beniamino Di Martino Jack Dongarra Edgar Gabriel Al Geist Patrick Geoffray Michael Gerndt Andrzej Goscinski Richard L. Graham William Gropp Rolf Hempel
IBM, USA CNUCE Institute, Italy ORNL, USA Mellanox, Israel Univeristy of Tennesse, USA Scali, Norway University of Paris-Sud, France University of Houston, USA Trinity College Dublin, Ireland University of Athens, Greece New University of Lisbon, Portugal University of Pisa, Italy Cray, USA INRIA, France University of Ghent, Belgium Second University of Naples, Italy University of Tennessee, USA University of Houston, USA OakRidge National Laboratory, USA Myricom, USA Technical University of Munich, Germany Deakin University, Australia ORNL, USA Argonne National Laboratory, USA DLR - German Aerospace Center, Germany
VIII
Organization
Thomas Herault Yutaka Ishikawa Rainer Keller Stefan Lankes Erwin Laure Laurent Lefevre Greg Lindahl Thomas Ludwig Ewing Rusty Lusk Tomas Margalef Jean-Franois Mhaut Bernd Mohr Matthias M¨ uller Raymond Namyst Salvatore Orlando Christian Perez Fabrizio Petrini Neil Pundit Rolf Rabenseifner Thomas Rauber Casiano Rodriguez-Leon Martin Schulz Jeffrey Squyres Bernard Tourancheau Jesper Larsson Tr¨aff Carsten Trinitis Roland Wismueller Felix Wolf Joachim Worringen
Universit´e Paris Sud / INRIA, France University of Tokyo, Japan HLRS, Germany RWTH Aachen, Germany CERN, Switzerland INRIA, France Pathscale, USA University of Heidelberg, Germany Argonne National Laboratory, USA Universitat Autonoma de Barcelona, Spain IMAG, France Forschungszentrum J¨ ulich, Germany Dresden University of Technology, Germany University of Bordeaux, France University of Venice, Italy IRISA, France PNNL, USA Sandia National Laboratories, USA HLRS, Germany Universit¨ at Bayreuth, Germany University of La Laguna, Spain Lawrence Livermore National Laboratory, USA Cisco, Inc., USA University of Lyon / INRIA, France C&C Research Labs, NEC Europe, Germany Technische Universit¨ at M¨ unchen, Germany University Siegen, Germany Forschungszentrum J¨ ulich, Germany C&C Research Labs, NEC Europe, Germany
External Referees Toni Cortes Pierre Lemarinier
Universitat Polit`ecnica de Catalunya, Spain Universit´e Paris Sud/INRIA, France
Conference Organization Franck Cappello Gaelle Dorkeld Catherine Girard Chantal Girodon Thomas Herault
INRIA INRIA INRIA INRIA Universit´e Paris Sud-XI / INRIA
Organization
IX
Sponsors The conference would have been significantly more expensive and much less pleasant to organize without the generous support of our industrial sponsors. Platinum and Gold level sponsors also gave talks at the vendor session on their latest products in parallel systems and message passing softwares. EuroPVM/MPI 2007 gratefully acknowledges the contributions of the sponsors to a successful conference.
Platinum Level Sponsors
Gold Level Sponsors
Standard Level Sponsors
Table of Contents
Invited Talks The X-Scale Challenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . George Bosilca
1
Sustained Petascale: The Next MPI Challenge . . . . . . . . . . . . . . . . . . . . . . . Al Geist
3
MPI: Past, Present and Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tony Hey
5
New and Old Tools and Programming Models for High-Performance Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ewing Lusk
7
The TSUBAME Cluster Experience a Year Later, and Onto Petascale TSUBAME 2.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Satoshi Matsuoka
8
To Infinity and Beyond?! On Scaling Performance Measurement and Analysis Tools for Parallel Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bernd Mohr
10
Tutorials Using MPI-2: A Problem-Based Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . William D. Gropp and Ewing Lusk
12
Verifying Parallel Programs with MPI-Spin . . . . . . . . . . . . . . . . . . . . . . . . . . Stephen F. Siegel
13
Advanced MPI Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Julien Langou and George Bosilca
15
Outstanding Papers Full Bandwidth Broadcast, Reduction and Scan with Only Two Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Peter Sanders, Jochen Speck, and Jesper Larsson Tr¨ aff
17
Process Cooperation in Multiple Message Broadcast . . . . . . . . . . . . . . . . . . Bin Jia
27
XII
Table of Contents
Self-consistent MPI Performance Requirements . . . . . . . . . . . . . . . . . . . . . . Jesper Larsson Tr¨ aff, William Gropp, and Rajeev Thakur
36
Test Suite for Evaluating Performance of MPI Implementations That Support MPI THREAD MULTIPLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rajeev Thakur and William Gropp
46
Applications An Improved Parallel XSL-FO Rendering for Personalized Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Luiz Gustavo Fernandes, Thiago Nunes, Mateus Raeder, Fabio Giannetti, Alexis Cabeda, and Guilherme Bedin An Extensible Framework for Distributed Testing of MPI Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Joshua Hursey, Ethan Mallove, Jeffrey M. Squyres, and Andrew Lumsdaine
56
64
A Virtual Test Environment for MPI Development: Quick Answers to Many Small Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wolfgang Schnerring, Christian Kauhaus, and Dietmar Fey
73
Multithreaded Tomographic Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . ´ Jos´e Antonio Alvarez, Javier Roca, and Jose Jes´ us Fern´ andez
81
Parallelizing Dense Linear Algebra Operations with Task Queues in llc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Antonio J. Dorta, Jos´e M. Bad´ıa, Enrique S. Quintana-Ort´ı, and Francisco de Sande
89
ParaLEX: A Parallel Extension for the CPLEX Mixed Integer Optimizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yuji Shinano and Tetsuya Fujie
97
Performance Analysis and Tuning of the XNS CFD Solver on Blue Gene/L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Brian J.N. Wylie, Markus Geimer, Mike Nicolai, and Markus Probst
107
(Sync|Async)+ MPI Search Engines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mauricio Marin and Veronica Gil Costa
117
Collective Operations A Case for Standard Non-blocking Collective Operations . . . . . . . . . . . . . . Torsten Hoefler, Prabhanjan Kambadur, Richard L. Graham, Galen Shipman, and Andrew Lumsdaine
125
Table of Contents
Optimization of Collective Communications in HeteroMPI . . . . . . . . . . . . Alexey Lastovetsky, Maureen O’Flynn, and Vladimir Rychkov
XIII
135
Fault Tolerance Low Cost Self-healing in MPI Applications . . . . . . . . . . . . . . . . . . . . . . . . . . Jacques A. da Silva and Vinod E.F. Rebello
144
Fault Tolerant File Models for MPI-IO Parallel File Systems . . . . . . . . . . A. Calder´ on, F. Garc´ıa-Carballeira, Florin Isailˇ a, Rainer Keller, and Alexander Schulz
153
Library Internals An Evaluation of Open MPI’s Matching Transport Layer on the Cray XT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Richard L. Graham, Ron Brightwell, Brian Barrett, George Bosilca, and Jelena Pjeˇsivac-Grbovi´c Improving Reactivity and Communication Overlap in MPI Using a Generic I/O Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fran¸cois Trahay, Alexandre Denis, Olivier Aumage, and Raymond Namyst Investigations on InfiniBand: Efficient Network Buffer Utilization at Scale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Galen M. Shipman, Ron Brightwell, Brian Barrett, Jeffrey M. Squyres, and Gil Bloch
161
170
178
Message Passing on Hierarchical Machines and Grids Improving MPI Support for Applications on Hierarchically Distributed Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ra´ ul L´ opez and Christian P´erez MetaLoRaS: A Re-scheduling and Prediction MetaScheduler for Non-dedicated Multiclusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J.Ll. L´erida, F. Solsona, F. Gin´e, M. Hanzich, J.R. Garc´ıa, and P. Hern´ andez Using CMT in SCTP-Based MPI to Exploit Multiple Interfaces in Cluster Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Brad Penoff, Mike Tsai, Janardhan Iyengar, and Alan Wagner
187
195
204
MPI-I/O Analysis of the MPI-IO Optimization Levels with the PIOViz Jumpshot Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thomas Ludwig, Stephan Krempel, Michael Kuhn, Julian Kunkel, and Christian Lohse
213
XIV
Table of Contents
Extending the MPI-2 Generalized Request Interface . . . . . . . . . . . . . . . . . . Robert Latham, William Gropp, Robert Ross, and Rajeev Thakur
223
Transparent Log-Based Data Storage in MPI-IO Applications . . . . . . . . . Dries Kimpe, Rob Ross, Stefan Vandewalle, and Stefaan Poedts
233
One-Sided Analysis of Implementation Options for MPI-2 One-Sided . . . . . . . . . . . . . Brian W. Barrett, Galen M. Shipman, and Andrew Lumsdaine MPI-2 One-Sided Usage and Implementation for Read Modify Write Operations: A Case Study with HPCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gopalakrishnan Santhanaraman, Sundeep Narravula, Amith.R. Mamidala, and Dhabaleswar K. Panda
242
251
RDMA in the SiCortex Cluster Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lawrence C. Stewart, David Gingold, Jud Leonard, and Peter Watkins
260
Revealing the Performance of MPI RMA Implementations . . . . . . . . . . . . William D. Gropp and Rajeev Thakur
272
PVM and Harness Distributed Real-Time Computing with Harness . . . . . . . . . . . . . . . . . . . . . Emanuele Di Saverio, Marco Cesati, Christian Di Biagio, Guido Pennella, and Christian Engelmann Frequent Itemset Minning with Trie Data Structure and Parallel Execution with PVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Levent Guner and Pinar Senkul
281
289
Tools Retrospect: Deterministic Replay of MPI Applications for Interactive Distributed Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Aurelien Bouteiller, George Bosilca, and Jack Dongarra
297
Extended MPICC to Generate MPI Derived Datatypes from C Datatypes Automatically . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ Eric Renault
307
Timestamp Synchronization for Event Traces of Large-Scale Message-Passing Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Daniel Becker, Rolf Rabenseifner, and Felix Wolf
315
Table of Contents
XV
Verification of Message Passing Programs Verification of Halting Properties for MPI Programs Using Nonblocking Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stephen F. Siegel and George S. Avrunin
326
Correctness Debugging of Message Passing Programs Using Model Verification Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Robert Lovas and Peter Kacsuk
335
Practical Model-Checking Method for Verifying Correctness of MPI Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Salman Pervez, Ganesh Gopalakrishnan, Robert M. Kirby, Robert Palmer, Rajeev Thakur, and William Gropp
344
ParSim 6th International Special Session on Current Trends in Numerical Simulation for Parallel Engineering Environments: New Directions and Work-in-Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Martin Schulz and Carsten Trinitis
354
Gyrokinetic Semi-lagrangian Parallel Simulation Using a Hybrid OpenMP/MPI Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G. Latu, N. Crouseilles, V. Grandgirard, and E. Sonnendr¨ ucker
356
Automatic Parallelization of Object Oriented Models Executed with Inline Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H˚ akan Lundvall and Peter Fritzson
365
3D Parallel Elastodynamic Modeling of Large Subduction Earthquakes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Eduardo Cabrera, Mario Chavez, Ra´ ul Madariaga, Narciso Perea, and Marco Frisenda
373
Posters Abstracts Virtual Parallel Machines Through Virtualization: Impact on MPI Executions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Benjamin Quetier, Thomas Herault, Vincent Neri, and Franck Cappello
381
Seshat Collects MPI Traces: Extended Abstract . . . . . . . . . . . . . . . . . . . . . . Rolf Riesen
384
Dynamic Optimization of Load Balance in MPI Broadcast . . . . . . . . . . . . Takesi Soga, Kouji Kurihara, Takeshi Nanri, Motoyoshi Kurokawa, and Kazuaki Murakami
387
XVI
Table of Contents
An Empirical Study of Optimization in Seamless Remote MPI-I/O for Long Latency Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yuichi Tsujita Multithreaded and Distributed Simulation of Large Biological Neuronal Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jochen M. Eppler, Hans E. Plesser, Abigail Morrison, Markus Diesmann, and Marc-Oliver Gewaltig
389
391
Grid Services for MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Camille Coti, Ala Rezmerita, Thomas Herault, and Franck Cappello
393
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
395
The X-Scale Challenge George Bosilca Innovative Computing Laboratory Electrical Engineering and Computer Science Department, University of Tennessee, Knoxville, TN, USA
[email protected]
The last few years have seen fast changes in the high performance computing field. Some of these changes are related to the computer hardware and architecture. Multi/many core architecture have become prevalent, with architectures more or less exotic and heterogeneous. The overall theoretical computational power of the new generation processors increased greatly, but their programmability still lacks confidence. The changes in shape of the newest architectures has come so rapidly, that we are still deficient in terms of high performance libraries and applications in order to take advantage of all these new features. At same time, application requirements grow at least at the same pace. Obviously, more computations require more data in order to feed the deepest processor pipelines. More data means either a faster access to the memory, or a faster access to the network. The access speed to all types of memory (network included) lags behind. As a result, extracting the right performance of the current and next generation architectures is still (and will remain for a while) a challenge. These two fields are coming along, providing some very interesting advances over the last few years, but not at the speed of FLOPS. Moreover, the current approach indicates a higher degree of memory hierarchies (Non Uniform Memory Accesses) that have already become another limiting factor for the application performance increase. Simultaneously, increasing the size of the parallel machines triggers an increase in fault tolerance requirements. While the fault management and recovery topic was thoughtfully studied over the last decade, the recent changes in the number and distribution of the processor’s cores have raised some interesting questions. While the question of which fault tolerant approach fits best to the peta-scale environments is still debated, few of these approaches show interesting performances at scale or a low degree of intrusion in the application code. Eventually, the right answer might be somewhere in between a dynamic combination of several of these methods, strictly based on the application’s properties and the hardware environment. As expected, all these changes guarantee a highly dynamic (and exciting from a research point of view) high performance field over the next years. New mathematical algorithms will have to emerge in order to take advantage of these unbalanced architectures. In addition, a tight collaboration between the applications and the high performance libraries developers is/will be critical to the future of HPC fields. F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 1–2, 2007. c Springer-Verlag Berlin Heidelberg 2007
2
G. Bosilca
How MPI will adapt to fit into this conflicting environment is still an open question. Over the last few years, MPI has been a very successful parallel programming paradigm, partially due to its apparent simplicity to express basic message exchange patterns and partially to the fact that it increases the productivity of the programmers and the parallel machines. Whatever the future of MPI will be, these two features should stay an indispensable part of its new direction of development.
Sustained Petascale: The Next MPI Challenge Al Geist Oak Ridge National Laboratory, PO Box 2008, Oak Ridge, TN 37831-6016
[email protected] http://www.csm.ornl.gov/ geist
Abstract. The National Science Foundation in the USA has launched an ambitious project to have a sustained petaflop computer in production by 2011. For applications to run at a sustained petaflop, the computer will need to have a peak performance of nearly 20 PF and millions of threads. This talk will address the challenges MPI must face to be used in sustained petascale applications. The first significant challenge for MPI will be the radical change in supercomputer architectures over the next few years. The architectures are shifting from using faster processors to using multi-core processors. It is also speculated that the processors will be heterogeneous with the cores on a single processor having different functions. This change in architecture is as disruptive to software as the shift from vector to distributed memory supercomputers 15 years ago. That change required complete restructuring of scientific application codes and gave rise to the message passing programming paradigm that drove the popularity of PVM and MPI. Similarly, will these new architectures drive the creation of a new programming paradigm or will MPI survive? Or perhaps MPI becomes part of a new hybrid paradigm. These questions will be addressed in this talk. The configuration of these sustained petascale systems will require applications to exploit million-way parallelism and significant reductions in the bandwidth and amount of memory available to a million cores. Most science teams have no idea how to efficiently scale their applications to this level and those teams that have thought about it believe that MPI may not be the right approach. Several talks at this conference describe potential features and capabilities that may allow MPI to be more effective for the reduced bandwidth and increased parallelism. The talk will point out these features and their associated talks. The third significant challenge for MPI will be fault tolerance and fault recovery. The amount of memory in sustained petascale systems makes writing out checkpoints impractical. While the need to restart an application when 900,000 CPUs are still working fine but one has failed is an inefficient use of resources. This talk will describe the latest ideas for fault recovery in MPI and will describe a new idea called holistic fault tolerance that is being investigated. F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 3–4, 2007. c Springer-Verlag Berlin Heidelberg 2007
4
A. Geist Finally the talk will describe productivity issues for sustained petascale application performance and their implications for MPI. The productivity of scientists and engineers is based on how easy and how fast they can solve a new science problem. Issues such as debugging, performance tuning, scalability, validation, and knowledge discovery all play a part. The talk will address the challenges MPI has in these areas.
MPI: Past, Present and Future Tony Hey Microsoft Corporation One Microsoft Way Redmond, WA 98052-6399
Abstract. This talk will trace the origins of MPI from the early messagepassing, distributed memory, parallel computers in the 1980’s, to today’s parallel supercomputers. In these early days, parallel computing companies implemented proprietary message-passing libraries to support distributed memory parallel programs. At the time, there was also great instability in the market and parallel computing companies could come and go, with their demise taking with them a great deal of effort in parallel programs written to their specific call specifications. In January 1992, Geoffrey Fox and Ken Kennedy had initiated a community effort called Fortran D, a precursor to High Performance Fortran and a high level data parallel language that compiled down to a distributed memory architecture. In the event, HPF proved an over ambitious goal: what was clearly achievable was a message-passing standard that enabled portability across a variety of distributed memory message-passing machines. In Europe, there was enthusiasm for PARMACS libraries: in the US, PVM was gaining adherents for distributed computing. For these reasons, in November 1992 Jack Dongarra and David Walker from the USA and Rolf Hempel and Tony Hey from Europe wrote an initial draft of the MPI standard. After a birds of a feather session at the 1992 Supercomputing Conference, Bill Gropp and Rusty Lusk from Argonne volunteered to create an open source implementation of the emerging MPI standard. This proved crucial in accelerating take up of the community-based standard, as did support from IBM, Intel and Meiko. Because of the need for the MPI standardization process to converge to agreement in a little over a year, the final agreed version of MPI contains more communication calls than most users now require. A later standardization process increased the functionally of MPI as MPI-2. Where are we now? It is clear that MPI provides effective portability for data parallel distributed memory message passing programs. Moreover, such MPI programs can scale to large numbers of processors. MPI therefore still retains its appeal for closely coupled distributed computing and the rise of HPC clusters as a local resource has made MPI ubiquitous for serious parallel programmers. However, there are two trends that may limit the usefulness of MPI in the future. The first is the rise of the Web and of Web Services as a paradigm for distributed, service oriented computing. In principle, using Web Service protocols that expose functionality as a service offers the prospect of building more robust software for distributed systems. The second trend is the move towards MultiCore processors as semi-conductor manufacturers are finding that they F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 5–6, 2007. c Springer-Verlag Berlin Heidelberg 2007
6
T. Hey can no longer increase the clock speed as the feature size continues to shrink. Thus, although Moore’s Law, in the sense that the feature size will continue to shrink, will continue for perhaps a decade or more, the accompanying increase in speed as the clock speed is increased will no longer be possible. For this reason, 2, 4 and 8 core chips, in which the processor is replicated several times, are already becoming commonplace. However, this means that any significant performance increase will depend entirely on the programmer’s ability to exploit parallelism in their applications. This talk will end by reviewing these trends and examining the applicability of MPI in the future.
New and Old Tools and Programming Models for High-Performance Computing Ewing Lusk Mathematics and Computer Science Division Argonne National Laboratory
Abstract. The computing power to be made available to applications in the coming years continues to increase. Hardware vendors anticipate many cores on single chips and fast networks connecting them, enabling a bewildering array of new approaches to parallel programming whose superiority to ”classical” approaches (MPI) remains uncertain. One certainty is that application developers will need tools that promote understanding of their parallel codes. In this talk we will review a number of approaches to application development, from Fortran77+MPI to the relatively exotic DARPA ”high productivity” languages, together with a sampling of tools, both new and old, that aid programmers in application development.
F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, p. 7, 2007. c Argonne National Laboratory 2007
The TSUBAME Cluster Experience a Year Later, and onto Petascale TSUBAME 2.0 Satoshi Matsuoka Global Scientific Information and Computing Center Tokyo Institute of Technology 2-12-1 Oo-Okayama, Meguro-ku, Tokyo 152-8550, Japan
[email protected] http://www.gsic.titech.ac.jp
TSUBAME (Tokyo-tech Supercomputer and Ubiquitously Accessible Massstorage Environment) is a new supercomputer installed at Tokyo Institute of Technology in Tokyo, Japan, on April 1st, 2006, and as of 2007 facilitating over 85 Teraflops of peak compute power with acceleration, 22 Terabytes of memory, and 1.6 Petabytes of online disk storage, ”Fat Node” as well as fast parallel interconnect—architectural principles based on traditional supercomputers. TSUBAME became the fastest and largest supercomputer in Asia in terms of performance, memory and storage capacity etc., starting from the 38.18 Teraflops performance (7th overall) for the June 2006 Top500 announcement, and taking the fastest in Asia crown for 3 consecutive Top500s in a row (currently at 48.88 Teraflops). At the same time, being PC architecture-based, TSUBAME, being a large collection of PC servers, allows for offering much broader services than traditional supercomputers resulting in a much wider user base, including incubation of novice students. We term such architectural and operational property of TSUBAME as “Everybody’s Supercomputer”, as opposed to traditional supercomputers with very limited number of users, thus making their financial justifications increasingly difficult. Tsubame is a result of collaborative effort between the univerity academia at the Tokyo Institute of Technology, and multiple industrial partners worldwide. The contract was awarded to NEC, who jointly with Sun Microsystems built and installed the entire machine, and also collaboratively provide on-site engineering to operate the machine. Other commercial partners, such as AMD (Opteron CPUs), Voltaire (Infiniband), ClearSpeed (Accelerator), CFS (LUSTRE parallel filesystem), Novell (SUSE Linux), provided their own products and expertise as building blocks. It was installed in just three weeks, and when its operation started on April 3rd, 2006 Overall, TSUBAME’s installation space is approximately 350m2 including the service area. There are approximately 80 compute/storage/network racks, as well as 32 CRC units for cooling, that are laid out in a customized fashion to maximize cooling efficiency, instead of the machine itself merely being placed as an afterthought. This allows for considerable density and much better cooling efficiency compared to other machines of similar performance. TSUBAME occupies three rooms, where room-to-room Infiniband connections are achieved F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 8–9, 2007. c Springer-Verlag Berlin Heidelberg 2007
The TSUBAME Cluster Experience a Year Later
9
via optical fiber connection, whereas uses the CX4 copper cable within a room. The total power consumption of TSUBAME is less than a Megawatt even at peak load, making it one of the most power- and space- efficient genera-purpose cluster supercomputer in the 100Teraflops performance scale. TSUBAME’s lifetime was initially designed to be 4 years, until the spring of 2010, with possible short-term extensions realized by incremental upgrades to maintain the competitiveness of the machine. However, eventually the lifetime will expire, and we are already beginning the plans for designing the next generaion “TSUBAME 2.0”. Here, simply waiting for processor improvements relying on CPU vendors would not be sufficient to meet the growing computational demands, as a result of success of ”Everybody’s Supercomputer”, in growth of the supercomputing community itself, not just the individual needs. Another requirement is not to increase the power or the footprint requirement of the current machine, resulting in a considerable challenge in supercomputer design we are researching at the current moment. One research investment we are conducting in this regard is in the area of acceleration technologies, which will provide vastly improved Megaflops/Watt ratio. In fact, even currently, two-fifth of TSUBAME’s peak computing power is provided by the ClearSpeed Advanced Accelerator PCI-X board. However, acceleration technology is still narrowly scoped in terms of its applicability and user base; as such, we must generalize the use of acceleration via advances in algorithm and software technologies, as well as design a machine with right mix of various heterogeneous resources, including general-purpose processors, and various types of accelerators. Another factor is storage, where multi-Petabyte storage with high bandwidth must be accommodated. Challenges are in devising more efficient cooling, better power control, etc. There are various challenges abound, and it will require advances in multi-disciplinary fashion to meet this challenge. This is not a mere pursuit of FLOPS, but rather, ”pursuit of FLOPS usable by everyone”—a challenge worthwhile taking for those of us who are computer scientists. And the challenge will continue beyond TSUBAME 2.0 for many years to come.
To Infinity and Beyond?! On Scaling Performance Measurement and Analysis Tools for Parallel Programming Bernd Mohr Forschungszentrum J¨ ulich John-von-Neumann Institute for Computing Virtual Institute for High-Productivity Supercomputing J¨ ulich, Germany
[email protected]
Extended Abstract. The number of processor cores available in highperformance computing systems is steadily increasing. A major factor is the current trend to use multi-core and many-core processor chip architectures. In the latest list of the TOP500 Supercomputer Sites[1], 63% of the systems listed have more than 1024 processor cores and the average is about 2400. While this promises ever more compute power and memory capacity to tackle today’s complex simulation problems, it forces application developers to greatly enhance the scalability of their codes to be able to exploit it. This often requires new algorithms, methods or parallelization schemes to be developed as many well-known and accepted techniques stop working at these large scales. It starts with simple things like opening a file per process to save checkpoint information, or collecting simulation results of the whole program via a gather operation on a single process, or previously unimportant order O(n2 )-type operations which quickly dominate the execution. Unfortunately many of these performance problems only show up when executing with very high numbers of processes and cannot be easily diagnosed or predicted from measurements at lower numbers. Detecting and diagnosing these performance and scalability bottlenecks requires sophisticated performance instrumentation, measurement and analysis tools. Simple tools typically scale very well but the information they provide proves to be less and less useful at these high scales. It is clear that tool developers face exactly the same problems as application developers when enhancing their tools to handle and support highly scalable applications. In this talk we discuss the major limitations of currently used state-of-the-art performance measurement, analysis and visualisation methods and tools. We give an overview about experiments, new approaches and first results of performance tool projects which try to overcome these limits. This includes new scalable and enhanced result visualization methods used in the performance analysis framework TAU[2], methods to automatically extract key execution phases from long traces used by the Paraver toolset[3], more scalable client/server tool architecture like the one of VampirServer[4] for scalable timeline visualisations, and highly-parallel automatic performance bottleneck searches utilized by the Scalasca toolset[5]. F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 10–11, 2007. c Springer-Verlag Berlin Heidelberg 2007
On Scaling Performance Measurement and Analysis Tools
11
References 1. TOP500 Supercomputer Sites (June 2007) → http://www.top500.org/ 2. Shende, S., Malony, A.D.: TAU: The TAU Parallel Performance System. International Journal of High Performance Computing Applications 20(2), 287–331 (2006) 3. Labarta, J., Gimenez, J., Martinez, E., Gonzales, P., Servat, H., Llort, G., Aguilar, X.: Scalability of visualization and tracing tools. In: Proceedings Parallel Computing (ParCo) 2005, Malaga, Spain (2005) 4. Kn¨ upfer, A., Brunst, H., Nagel, W.E.: High Performance Trace Visualization. In: Proceedings of the 13th Euromicro Conference on Parallel, Distributed and Networkbased Processing, Lugano, Switzerland (February 2005) 5. Geimer, M., Wolf, F., Wylie, B.J.N., Mohr, B.: Scalable Parallel Trace-Based Performance Analysis. In: Mohr, B., Tr¨ aff, J.L., Worringen, J., Dongarra, J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 4192, pp. 303–312. Springer, Heidelberg (2006)
Using MPI-2: A Problem-Based Approach William D. Gropp and Ewing Lusk Mathematics and Computer Science Division Argonne National Laboratory Argonne, IL 60439, USA {thakur,gropp}@mcs.anl.gov
Abstract. MPI-2 introduced many new capabilities, including dynamic process management, one-sided communication, and parallel I/O. Implementations of these features are becoming widespread. This tutorial shows how to use these features by showing all of the steps involved in designing, coding, and tuning solutions to specific problems. The problems are chosen for their practical use in applications as well as for their ability to illustrate specific MPI-2 topics. Complete examples that illustrate the use of MPI one-sided communication and MPI parallel I/O will be discussed and full source code will be made available to the attendees. Each example will include a hands-on lab session; these sessions will also introduce the use of performance and correctness debugging tools that are available for the MPI environment. Guidance on tuning MPI programs will be included, with examples and data from MPI implementations on a variety of parallel systems, including Sun, IBM, SGI, and clusters. Examples in C, Fortran, and C++ will be included. Familiarity with basic MPI usage will be assumed.
F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, p. 12, 2007. c Argonne National Laboratory 2007
Verifying Parallel Programs with MPI-Spin Stephen F. Siegel Verified Software Laboratory Department of Computer and Information Sciences University of Delaware Newark, DE 19716, USA
[email protected] http://www.cis.udel.edu/∼ siegel
Standard testing and debugging techniques are notoriously ineffective when applied to parallel programs, due to the numerous sources of nondeterminism arising from parallelism. MPI-Spin, an extension of the model checker Spin for verifying and debugging MPI-based parallel programs, overcomes many of the limitations associated with the standard techniques. By exploring all possible executions of an MPI program, MPI-Spin can conclude, for example, that a program cannot deadlock on any execution. If the program can deadlock, MPI-Spin can exhibit a trace showing exactly how the program fails, greatly facilitating debugging. This tutorial will serve as an introduction to MPI-Spin. Through a series of examples and exercises, participants will learn to use MPI-Spin to check for deadlocks, race conditions, and discrepancies in the numerical computations performed by MPI programs. The only prerequisites are familiarity with C and the basic MPI operations; no prior verification experience is required. Participants are encouraged to download and install MPI-Spin before the tutorial, following the instructions at http://vsl.cis.udel.edu/mpi-spin. The tutorial is divided into four parts, each lasting approximately 45 minutes: (1) introduction and tool demonstration, (2) language basics, (3) using MPISpin, and (4) verifying correctness of numerical computations. 1. Introduction and Demonstration. The introduction will begin with a discussion of some of the most common problems plaguing developers of MPI programs. In addition to the issues mentioned above, issues related to performance, such as the question of whether or not it is safe to remove a particular barrier statement from an MPI program, will also receive attention. The limitations of testing and other dynamic methods will also be explored. The basic tasks involved in model checking will then be introduced: the construction of a model of the program being verified, the formulation of one or more properties of the model, and the use of automated algorithmic techniques for checking that every execution of the model satisfies the property. The limitations of model checking will also be discussed; these include the state explosion problem and the problem of accurately constructing appropriate models of programs. It will be emphasized that, while modeling requires a certain degree of
This material is based upon work supported by the National Science Foundation under Grant No. 0541035.
F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 13–14, 2007. c Springer-Verlag Berlin Heidelberg 2007
14
S.F. Siegel
skill, it is not more difficult than programming and with a little practice most MPI programmers can become very effective modelers. The remainder of this part of the tutorial will consist of a tool demonstration, which will also introduce the main example used throughout the tutorial, the diffusion program. 2. Language Basics. Some knowledge of programming languages carries over into modeling languages, but modeling differs in several significant ways. In this part of the tutorial, the basic syntax and semantics of the MPI-Spin input language will be described in a progressive, methodical way. The description will start with those syntactic elements dealing with process declaration and management, then move on to variables and types, then expressions, and finally the different types of statements provided by the language. Throughout, the diffusion example will be used to illustrate the various language constructs. 3. Using MPI-Spin. This part will begin with a discussion of abstraction and how the choice of appropriate abstractions can lead to models that are both efficient and conservative. These notions will be defined precisely and illustrated using diffusion and matmat, a program that computes the product of two matrices using a master-slave pattern. In the latter example, the consequences of using various abstractions for the variables in the program will be explored. It will be shown that different choices are appropriate for verifying different properties of matmat. Once a model has been constructed, the MPI-Spin tool itself must be executed on that model. As is the case for any complex tool (such as a compiler), there are many options, parameters, and flags available to the user. The most commonly used options will be described and their effects demonstrated using the examples introduced previously. This will be followed by a “hands-on” exercise in which MPI-Spin is used to explore the consequences of modifications to the diffusion code. 4. Verifying Correctness of Numerical Computations. The fourth part of the tutorial deals with a recent and exciting development in the field of model checking for HPC: techniques using symbolic execution to verify properties of the numerical computations carried out by parallel programs. These techniques are supported in MPI-Spin through an abstract datatype MPI_Symbolic together with a number of operations on that type, such as SYM_add and SYM_multiply. The idea is to model the inputs to the program as symbolic constants xi and the output as a vector of symbolic expressions in the xi . The output vector can be analyzed for a number of purposes. Most importantly, it can be compared against the symbolic output vector produced by a trusted sequential version of the program. In this way, model checking can be used to show that for all inputs, and for all possible executions of the parallel program on the input, the parallel program will produce the same results as the sequential one. This technique will be illustrated using matmat and, if time permits, a more complex example implementing the Gaussian elimination algorithm.
Advanced MPI Programming Julien Langou1 and George Bosilca2 1
Department of Mathematical Sciences, University of Colorado, Denver, CO, USA
[email protected] 2 Innovative Computing Laboratory, University of Tennessee, Knoxville, TN, USA
[email protected]
MPI provides a large range of features allowing various approaches for parallel computing. This tutorial will present interesting features from the MPI-1 standard. These features extend the user knowledge about MPI way beyond the few basic standard functions, giving them the opportunity to implement better, simpler and potentially faster parallel algorithms. This tutorial will cover several features from medium level to advanced of the MPI-1 standard to enable users to exploit fully MPI. Identifying the bottlenecks. Once an initial version of a parallel application exists, the first question raised is how to improve it. While a large improvement might come from algorithmic modifications, there is usually a large space of improvements that might come from a correct useage of the MPI specification. Before starting any optimization, the user has first to identify the portions of the application that have the greatest potential for improvement. The basic approach is to use the MPI profiling layer. Unfortunately, this layer lacks the transparency required to show the effective data transfer over the network, missing a rich set of information about the application behavior. PERUSE is a more suitable layer to get access to all the hidden information available from the MPI libraries. Optimizing memory accesses. The MPI specification introduces a number of functions for creating MPI data-types. These data-types represent memory layouts and can be used for message exchange; both in point-to-point or collective communications. Choosing the right data-type is a performance critical choice as its impact on the communication performance is tremendous. Advanced point-to-point communications. While blocking communications are easier to masterize, they introduce one synchronization stage per communication which might be harmful to the overall performance of the application. Moving away from this blocking model, by using non-blocking point-to-point communications, usually allows the user for a better overlap between multiple communications leading to a shorter execution time of the parallel application. F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 15–16, 2007. c Springer-Verlag Berlin Heidelberg 2007
16
J. Langou and G. Bosilca
Collective communications. The collective communications provides a highly optimized variety of algorithms for global data exchange between a set of MPI processes. These algorithms cover some of the most generic collective communications such as broadcast, barrier, etc. Some of them (i.e. those derived from the reduce operation) can be extended using user-provided operations. For each item in the above list, we will provide attendees with small and comprehensible example codes that have been identified as critical part of larger relevant application codes. Starting from these small codes, we will show how to exploit MPI functionallities in order to improve simplicity and efficiency of the application. The example codes and their modifications will be made available to the attendees.
Full Bandwidth Broadcast, Reduction and Scan with Only Two Trees Peter Sanders1 , Jochen Speck1 , and Jesper Larsson Tr¨aff2 1
Universit¨ at Karlsruhe Am Fasanengarten 5, D-76131 Karlsruhe, Germany
[email protected] 2 NEC Laboratories Europe, NEC Europe Ltd. Rathausallee 10, D-53757 Sankt Augustin, Germany
[email protected]
Abstract. We present a new, simple algorithmic idea for exploiting the capability for bidirectional communication present in many modern interconnects for the collective MPI operations broadcast, reduction and scan. Our algorithms achieve up to twice the bandwidth of most previous and commonly used algorithms. In particular, our algorithms for reduction and scan are the currently best known. Experiments on clusters with Myrinet and InfiniBand interconnects show significant reductions in running time for broadcast and reduction, for reduction even close to the best possible factor of two.
1
Introduction
The Message Passing Interface (MPI) [12] offers a set of collective communication and computation operations that are eminently useful for expressing parallel computations. It is therefore important that MPI libraries implement these operations as efficiently as possible for the intended target architectures. Hence, algorithms that can fully exploit the given communication capabilities are needed. Consequently, recent years has seen a lot of activity on algorithms and implementations for MPI collectives for different communication architectures, see [3,8,10,13] to mention but a few. In this paper we give new algorithms with implementations for three important MPI collectives, namely MPI Bcast (broadcast), MPI Reduce (reduction to root) and MPI Scan/MPI Exscan (parallel prefix). The new algorithms are able to fully exploit bidirectional communication capabilities as offered by modern interconnects like InfiniBand, Myrinet, Quadrics, and the NEC IXS, and thus in contrast to many commonly used algorithms for these operations have the potential of achieving the full bandwidth offered by such interconnects. For broadcast this has previously been achieved also by other algorithms [1,6,16], but these are typically more complicated and do not extend to the reduction and parallel prefix operations. We believe the results achieved for reduction and parallel prefix to be the theoretically currently best known. The algorithms are still simple to implement, and have been implemented within the framework of NEC proprietary MPI libraries. F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 17–26, 2007. c Springer-Verlag Berlin Heidelberg 2007
18
2
P. Sanders, J. Speck, and J.L. Tr¨ aff
Two Pipelined Binary Trees Instead of One
To explain the new algorithm we focus on the MPI Bcast operation, and illustrate the improvement achieved by comparing to a linear pipeline and a pipelined binary tree. We let p denote the number of processors which are numbered from 0 to p − 1, and m the size of the data to be broadcast from a given root processor r. As in MPI Bcast we assume that all processors know p, r and m. We assume that communication is homogeneous, one-ported, and bidirectional in the sense that each processor can at the same time send a message to a processor and receive a message from another, possibly different processor. Assume first that p = 2h − 1 for some tree height h > 1. A binary tree broadcast algorithm uses a balanced, ordered binary tree rooted at processor r. To broadcast, the root sends its data to its left and right child processors, and upon receiving data each processor which is not a leaf sends data to its left and right child processors in that order. As can be seen the rightmost leaf receives data at communication step 2h. Assuming that the time to transfer data of size m is α + βm, the total broadcast time is 2h(α + βm). The binary tree algorithm can be pipelined, and sending instead the m data as N blocks of size m/N yields a broadcast time (for the rightmost leaf) of 2(h + N − 1)(α + βm/N ) (even exploiting bidirectional communication: each interior processor receives a new block from its parent at the same time as it sends a block to its right child). Balancing the terms√N α and (h − 1)βm/N yields a best broadcast time of 2(h − 1)α + 4 (h − 1)α βm + 2βm. This is roughly a factor of two from the lower bound of min{αh, βm}. Using instead a linear pipeline in which processor i receives a new block from processor i − 1 and a the same time sends the previous blocks on to√processor i+1, a broadcast time (for the last processor) of (p−2)α+2 (h − 1)α βm+βm can be achieved. This algorithm has asymptotically optimal broadcast time βm but at the cost of a large latency term (p − 2)α and is therefore interesting only when m is large compared to p. We are interested in algorithms that combine the low latency of the pipelined binary tree and the optimal time achieved by the linear pipeline, while retaining as far as possible the implementation simplicity of these algorithms (as well as other properties such as low demands on bisection bandwidth, and embeddability in non-homogeneous networks). The problem with the pipelined binary tree algorithm is that the bidirectional communication is only exploited in every second communication step for the interior node processors and not at all for the root and leaf processors. In particular, the leaves are only receiving blocks of data. We propose to use two binary trees simultaneously in order to achieve a more balanced use of the communication links. The two trees are constructed in such a way that the interior nodes of one tree correspond to leaf nodes of the other. This allows us to take full advantage of the bidirectional communication capabilities. In each communication step a processor receives a block from its parent in one of the two trees and sends the previous block to one of its children in the tree in which it is an interior node. To make this work efficiently, the task is to devise a construction
Full Bandwidth Broadcast, Reduction and Scan with Only Two Trees
19
of the two trees together with a schedule which determines for each time step1 from which parent a block is received and to which child the previous block is sent so that each communication step consists in at most one send and at most one receive operation for each processor. For now we (w.l.o.g) assume that r = p − 1 and construct the two binary trees T1 and T2 over processors 0 . . . p − 2 as follows. Let 2h be the smallest power of two larger or equal to p − 1 and let P = 2h − 1. T1 1 1 1
0
0
0 1
0
0
Processors 0 1 2 3 4 5 6 7 8 9 0 1
0
1
1
0
1 0
1
T2
Fig. 1. The two inorder binary trees T1 (top to bottom) and T2 (bottom to top) with broadcast root r = 9 for p = 10. A 0/1 coloring is also shown.
1. Construct an inorder numbered balanced tree of size P , such that that the leaves have even numbers 0, 2, . . . P − 2. 2. If P > p − 1 eliminate nodes starting from the highest numbered node u as follows: if u is a leaf simply remove it; otherwise set the parent of u’s (only) child to be the parent of u and remove u. This tree is T1 . 3. Construct an inorder numbered balanced tree of size P . 4. Shift the tree one position to the left, e.g. rename node u to u − 1. Remove the leftmost leaf −1. In this tree leaves have odd numbers 1, 3, . . .. 5. If P − 1 > p − 1 eliminate nodes from the right as in Step 2. This tree is T2 . To complete the construction for the broadcast algorithm, the roots of the two trees are connected to the broadcast root node p − 1. An example of the construction for p = 10 is shown in Figure 1. The construction obviously has the desired property that leaves of T1 are interior nodes of T2 and vice versa. To use the two trees for broadcast, the idea is to pipeline half the data through T1 , and the other half of the data through T2 . With bidirectional communication capabilities, the two pipelines can run concurrently, yieldinga broadcast time of 2[2(h − 1)α + 4 (h − 1)α βm/2 + 2βm/2] = 4(h − 1)α + 4 (h − 1)α βm/2 + βm. This is half the time of the pipelined binary tree at the expense of only twice the (still) logarithmic latency. 1
Note that no explicit global synchronization is necessary. Point-to-point communication suffices to implicitly synchronize the processors to the extent necessary.
20
P. Sanders, J. Speck, and J.L. Tr¨ aff
The left to right order of the children is not sufficient to avoid that a node in the same communication step receives a block from both of its parents (which would compromise the analysis and slow down the algorithm). We need an evenodd (0/1) coloring of the parent to child edges without such conflicts. Even (0) edges are then used in even communication steps, odd (1) edges in odd steps. More precisely we need the following Lemma. Lemma 1. The edges of T1 and T2 can be colored with colors 0 and 1 such that 1. no PE is connected to its parent nodes in T1 and T2 using edges of the same color and 2. no PE is connected to its children nodes in T1 or T2 using edges of the same color. Proof. Consider the bipartite graph B = ({s0 , . . . , sp−1 } ∪ {r1 , . . . , rp−1 }, E) where {si , rj } ∈ E iff j is a successor of i in T1 or T2 . This graph models the sender role of processor i with node si and the receiver role of processor i with node ri . By the construction of T1 and T2 , B has maximum degree two, i.e., B is a collection of paths and even cycles. Hence, the edges of B can be two-colored by just traversing these paths and cycles. Computing the coloring as described in the proof can be done in O(p) steps. In the appendix we outline how (with another construction of the two trees) each processor i can compute all relevant information (neighbors in the trees, colors of incident edges) in time O(log p) given only p and i. 2.1
Broadcast
If the broadcast root is not r = p − 1 as in the above, we simply renumber each processor i to instead play the role of processor (i − (r + 1)) mod p. To be useful in MPI libraries the coloring should be done at communicator construction time so that the coloring time is amortized over all subsequent broadcast operations on the communicator. For broadcast the idea of using two trees to improve bandwidth was previously introduced in [5], but the need for coloring was not realized (due to the TCP/IP setting of this work). 2.2
Reduction
Let ⊕ denote an associative (possibly commutative) binary operation, and let processor i have a data vector mi of size m. The reduction to root operation MPI Reduce computes ⊕p−1 i=0 mi and stores the result at the root processor r. Assuming r = 0 or r = p − 1, the two tree construction can be used for reduction to root by reversing the flow of data from the leaves towards the root in both of the trees. Since the trees are inorder numbered the reduction order can be maintained such that only associativity of ⊕ is exploited. We have the following Theorem.
Full Bandwidth Broadcast, Reduction and Scan with Only Two Trees
21
Theorem 1. For r = 0 or r = p − 1 reduction to root of data m i (each of size m) can be done in communication time 4(h − 1)α + 4 (h − 1)α βm/2 + βm. The amount of data reduced per processor is 2m. If the operator ⊕ is commutative the result can be achieved for any root r. 2.3
Scan
The (inclusive) parallel prefix operation MPI Scan computes ⊕ji=0 mi for each processor j. Using an inorder binary tree parallel prefixes can be computed by first performing an up-phase in which each interior node computes a partial sum ⊕ri= for left- and rightmost leaves and r, followed by a down-phase in which prefixes of the form ⊕−1 i=0 are sent down the tree and allow each processor to finish computing its parallel prefix. Both phases can be pipelined, and for each N blocks can be completed in 2h − 1 + 2(N − 1) communication steps. This is explained in more detail in [7,11]. With the two tree construction two up-phases and two down-phases can take place simultaneously. This halves the number of steps for N blocks for each phase. The total number of steps required for the parallel prefix computation is therefore 4h − 2 + 2(N − 2). This is roughly two thirds the 4h − 2 + 3(N − 1) steps required by the doubly pipelined parallel prefix algorithm described in [11]. Theorem 2. The parallelprefix operation on data mi can be done in communi cation time 2((2h − 3) + 2 (2h − 3)α βm/2 + βm. The amount of data reduced per processor is (at most) 3m.
3
Experimental Results
The two tree algorithms for MPI Bcast and MPI Reduce have been implemented within proprietary NEC MPI implementations. Experiments comparing the bandwidth achieved with the new algorithms to other, commonly used broadcast and reduction algorithms have been conducted on a small AMD Athlon based cluster with Myrinet 2000 interconnect, and a larger Intel Xeon based InfiniBand cluster. Bandwidth is computed as data size m divided by the time to complete for the slowest process. Completion time is the smallest measured time (for the slowest process) over a small number of repetitions. We give only results for the case with one MPI process per node, thus the number of processors p equals the number of nodes of the cluster. 3.1
Broadcast
We compare to the following algorithms: – Circulant graphfirst presented in [16]. This algorithm has asymptotically optimal completion time, and only half the latency of the two tree algorithm presented here, but is significantly more complex and requires a more involved precomputation than the simple coloring needed for the two tree algorithm.
22
P. Sanders, J. Speck, and J.L. Tr¨ aff
– Scatter-allgather for broadcast [2] as developed in [14]. We also contrast to the implementation of this algorithm in MVAPICH. – Simple binomial tree as in the original MPICH implementation [4]. – Pipelined binary tree – Linear pipeline Various MPI_Bcast Implementations, 28 nodes 90 MPI_Bcast (binomial tree) MPI_Bcast (linear pipeline) MPI_Bcast (pipelined binary tree) MPI_Bcast (Scatter+Allgather) MPI_Bcast (circulant graph) MPI_Bcast (two tree)
80
Bandwidth (MBytes/second)
70 60 50 40 30 20 10 0 1
10
100
1000
10000 Size
100000
1e+06
1e+07
1e+08
Fig. 2. Broadcast algorithms on the AMD/Myrinet cluster, 28 nodes
Bandwidth results for the two systems are shown in Figure 2 and Figure 3. On both systems the two tree algorithm asymptotically achieves the same bandwidth as the optimal circulant graph algorithm, but can of course not compete for small problems where the circulant graph algorithm degenerates into a binomial tree which has only half the latency of the binary tree. Even for large m (up to 16MBytes) both algorithms fare better than the linear pipeline, although none of the algorithms have reached their full bandwidth on the InfiniBand cluster. On the Myrinet cluster the algorithms achieve more than 1.5 times the bandwidth of the scatter-allgather and pipelined binary tree algorithms. For the Myrinet cluster where we also compared to the simple binomial tree a factor 3 higher bandwidth is achieved for 28 processors. The two tree broadcast algorithm is a serious candidate for improving the broadcast bandwidth for large problems on bidirectional networks. It is arguably simpler to implement than the optimal circulant graph algorithm [16], but have to be combined with a binomial tree algorithm for small to√medium sized problems. Being a pipelined algorithm with small blocks of size Θ( m) it is also well suited to implementation on SMP clusters [15]. 3.2
Reduction
We compare to the following algorithms: – Improved butterfly [9]
Full Bandwidth Broadcast, Reduction and Scan with Only Two Trees
23
Various MPI_Bcast Implementations, 150 nodes 450 MPI_Bcast (linear pipeline) MPI_Bcast (Scatter+Allgather) MPI_Bcast (circulant) MPI_Bcast (two tree)
400
Bandwidth (MBytes/second)
350 300 250 200 150 100 50 0 1
10
100
1000
10000 Size
100000
1e+06
1e+07
1e+08
Fig. 3. Broadcast algorithms on the Xeon/InfiniBand cluster, 150 nodes
– Binomial tree – Pipelined binary tree – Linear pipeline Bandwidth results for the two systems are shown in Figure 4 and Figure 5. The two tree algorithm achieves about a factor 1.5 higher bandwidth than the second best algorithm which is either the pipelined binary tree (on the Myrinet cluster) or the butterfly (on the InfiniBand cluster). On both systems the linear pipeline achieves an even higher bandwidth, though, but problem sizes have to be larger than 1MByte (for p = 28 on the Myrinet cluster), or 16Mbyte (for p = 150 on the InfiniBand cluster), respectively. For smaller problems the linear pipeline is inferior and should not be used. On the InfiniBand cluster there is a considerable difference of almost a factor 2 between the two implementations of the butterfly algorithm (with the implementation of [9] being the faster). The sudden drop in bandwidth for the butterfly algorithm on the Myrinet cluster is due to a protocol change in the underlying point-to-point communication, but for this algorithm it is difficult to avoid getting into the less suitable protocol domain. The pipelined algorithms give full flexibility in the choice of block sizes and such effects can thus better be countered. 3.3
Coloring
Table 1 compares the preprocessing times for a simple linear time implementation of two tree coloring and the O(p log p) time algorithm for computing the block schedule required for the circulant graph algorithm from [16]. The coloring algorithm is always faster than the block scheduling algorithm. It is to be expected that with the logarithmic time coloring algorithm, the speed difference would become quite dramatic for large p. However, for currently used machine sizes, both scheduling times are not a big issue when they are only needed once for each communicator.
24
P. Sanders, J. Speck, and J.L. Tr¨ aff Various MPI_Reduce Implementations, 28 nodes 90 MPI_Reduce (binomial tree) MPI_Reduce (linear pipeline) MPI_Reduce (pipelined binary tree) MPI_Reduce (butterfly) MPI_Reduce (two tree)
80
Bandwidth (MBytes/second)
70 60 50 40 30 20 10 0 1
10
100
1000
10000 Size
100000
1e+06
1e+07
1e+08
Fig. 4. Reduction algorithms on the AMD/Myrinet cluster, 28 nodes Various MPI_Reduce Implementations, 150 nodes 400 MPI_Reduce (linear pipeline) MPI_Reduce (MVAPICH butterfly) MPI_Reduce (butterfly) MPI_Reduce (two tree)
350
Bandwidth (MBytes/second)
300
250
200
150
100
50
0 1
10
100
1000
10000
100000
1e+06
1e+07
1e+08
Size
Fig. 5. Reduction algorithms on the Xeon/InfiniBand cluster, 150 nodes Table 1. Computing times in microseconds on an AMD 2.1GHz Athlon processor for the precomputation of double-tree coloring and block schedule Processors Two tree 0/1-coloring Circulant graph block schedule 100 71.75 99.15 1000 443.37 1399.43 10000 13651.42 20042.28 100000 209919.33 248803.58 1000000 1990228.74 3074909.75
Full Bandwidth Broadcast, Reduction and Scan with Only Two Trees
4
25
Conclusion
We presented a new, simple algorithmic idea for broadcast, reduction and parallel prefix operations as found in MPI. The theoretical result and achieved performance for MPI Bcast is similar to that achieved by other, recent, but more complicated algorithms [16]. The theoretical results for reduction to root and parallel prefix are presumably the best currently known, and the implementation of MPI Reduce show a significant improvement over several other algorithms. We expect a similar result for the MPI Scan implementation.
References 1. Bar-Noy, A., Kipnis, S., Schieber, B.: Optimal multiple message broadcasting in telephone-like communication systems. Discrete Applied Mathematics 100(1–2), 1–15 (2000) 2. Barnett, M., Gupta, S., Payne, D.G., Schuler, L., van de Geijn, R., Watts, J.: Building a high-performance collective communication library. In: Supercomputing’94, pp. 107–116 (1994) 3. Chan, E.W., Heimlich, M.F., Purkayastha, A., van de Geijn, R.A.: On optimizing collective communication. In: IEEE International Conference on Cluster Computing CLUSTER 2004, IEEE Computer Society Press, Los Alamitos (2004) 4. Gropp, W., Lusk, E., Doss, N., Skjellum, A.: A high-performance, portable imlementation of the MPI message passing interface standard. Parallel Computing 22(6), 789–828 (1996) 5. Happe, H.H., Vinter, B.: Improving TCP/IP multicasting with message segmentation. In: Communicating Process Architectures (CPA 2005) (2005) 6. Kwon, O.-H., Chwa, K.-Y.: Multiple message broadcasting in communication networks. Networks 26, 253–261 (1995) 7. Mayr, E.W., Plaxton, C.G.: Pipelined parallel prefix computations, and sorting on a pipelined hypercube. Journal of Parallel and Distributed Computing17, 374–380 (1993) 8. Pjesivac-Grbovic, J., Angskun, T., Bosilca, G., Fagg, G.E., Gabriel, E., Dongarra, J.: Performance analysis of MPI collective operations. In: International Parallel and Distributed Processing Symposium (IPDPS 2005), Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO) (2005) 9. Rabenseifner, R., Tr¨ aff, J.L.: More efficient reduction algorithms for messagepassing parallel systems. In: Kranzlm¨ uller, D., Kacsuk, P., Dongarra, J.J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 3241, pp. 36–46. Springer, Heidelberg (2004) 10. Ritzdorf, H., Tr¨ aff, J.L.: Collective operations in NEC’s high-performance MPI libraries. In: International Parallel and Distributed Processing Symposium (IPDPS 2006), p. 100 (2006) 11. Sanders, P., Tr¨ aff, J.L.: Parallel prefix (scan) algorithms for MPI. In: Mohr, B., Tr¨ aff, J.L., Worringen, J., Dongarra, J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 4192, pp. 49–57. Springer, Heidelberg (2006) 12. Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J.: MPI – The Complete Reference, 2nd edn. The MPI Core, vol. 1. MIT Press, Cambridge (1998)
26
P. Sanders, J. Speck, and J.L. Tr¨ aff
13. Thakur, R., Gropp, W.D., Rabenseifner, R.: Improving the performance of collective operations in MPICH. International Journal on High Performance Computing Applications 19, 49–66 (2004) 14. Tr¨ aff, J.L.: A simple work-optimal broadcast algorithm for message-passing parallel systems. In: Kranzlm¨ uller, D., Kacsuk, P., Dongarra, J.J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 3241, pp. 173–180. Springer, Heidelberg (2004) 15. Tr¨ aff, J.L., Ripke, A.: An optimal broadcast algorithm adapted to SMP-clusters. In: Di Martino, B., Kranzlm¨ uller, D., Dongarra, J.J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 3666, pp. 48– 56. Springer, Heidelberg (2005) 16. Tr¨ aff, J.L., Ripke, A.: Optimal broadcast for fully connected networks. In: Yang, L.T., Rana, O.F., Di Martino, B., Dongarra, J.J. (eds.) HPCC 2005. LNCS, vol. 3726, pp. 45–56. Springer, Heidelberg (2005)
Logarithmic Time Scheduling Algorithm The algorithm below assumes that p is even and T2 is the mirror image of T1 . The tree construction is a straight forward recursive algorithm. In the full paper we prove the (non obvious) correctness of the simple coloring algorithm below. Function inEdgeColor(p, i, h) If i is the root of T1 Then Return 1 While 2h = 0 Do h++ – – compute height i bitand h i − 2 if 2h+1 bitand i = 1 ∨ i + 2h > p i := – – compute parent of i i + 2h otherwise Return inEdgeColor(p, i, h) xor (p/2 mod 2) xor [i > i]
Process Cooperation in Multiple Message Broadcast Bin Jia IBM Advanced Clustering Technology Team Poughkeepsie, NY 12601
[email protected]
Abstract. We present a process cooperation algorithm for broadcasting m messages among n processes, m ≥ 1, n ≥ 1, in one-port fully-connected communication systems. In this algorithm, the n processes are organized into 2log n one- or two-process units. Messages are broadcast among the units according to a basic communication schedule. Processes in each two-process unit cooperate to carry out the basic schedule in a way that at any step, either process has at most one message that the other has not received. This algorithm completes the broadcast in log n + m − 1 communication steps, which is theoretically optimal. Empirical study shows that it outperforms other widely used algorithms significantly when the data to broadcast is large. Efficient communication schedule construction is a salient feature of this algorithm. Both the basic schedule and the cooperation schedule are constructed in O(log n) bitwise operations on process ranking. Keywords: Broadcast, process cooperation, MPI collective communication, one-port fully-connected system, communication schedule.
1
Introduction
Broadcast is one of the most important communication primitives in parallel and distributed systems. The MPI standard [11] defines a MPI BCAST interface for single source broadcast operation, in which data available at the source process is copied to all other processes. When the amount of data to broadcast is large, the data is often split into multiple messages, which are pipelined individually for better bandwidth utilization [2,12,1,3,4,13,9]. In this paper, we investigate the problem of broadcasting m messages among n processes in one-port fully-connected communication systems, m ≥ 1, n ≥ 1. Distances between any two processes in such a system are equal. Every process can send a message to one process and receive a message from another process in a single communication step. It takes the source process at minimum m− 1 steps before the last message can be sent and at least log n steps are needed for the last message to reach all processes. Therefore the lower bound on communication steps is log n + m − 1. A multiple message broadcast algorithm is optimal if the number of steps it needs to complete the broadcast matches the lower bound. F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 27–35, 2007. c Springer-Verlag Berlin Heidelberg 2007
28
B. Jia
The communication schedule of a multiple message broadcast algorithm defines which part of the data should a message contain; when to send the message; and the source/destination processes of the message. Widely adopted algorithms such as the pipelined chain algorithm and the pipelined binary tree algorithm have simple communication schedules that can be easily determined on-line. Those algorithms, however, are not optimal in the one-port fully-connected system. Other algorithms [1,12] exploit complicated communication schedules to achieve optimal broadcast time. Except for in special cases such as with power-of-twoprocess [6,12], the schedule construction in those algorithms is so expensive that it can only be done off-line, which hinders their incorporation in communication libraries. We present an optimal process cooperation algorithm with efficient communication schedule construction. The algorithm includes a basic schedule for broadcasting among power-of-two processes and a cooperation schedule. The n processes are organized into n one-process or two-process units, where n = 2log n . Following the cooperation schedule, processes in each two-process unit cooperate to carry out the basic schedule. At any step, either process has at most one message that the other process has not received. This schedule can be constructed efficiently on-line in only O(log n) bit operations on process ranking. We have implemented and incorporated this algorithm in IBM Parallel Environment/MPI [5]. The rest of the paper is organized as follows. Section 2 overviews existing multiple message broadcast algorithms. Section 3 describes the construction of the basic schedule for power-of-two processes. Section 4 details the process cooperation in multiple message broadcast and its schedule construction. Correctness proof is also given. Performance results of MPI BCAST implementation using the process cooperation algorithm are reported and compared with other commonly used algorithms in Section 5. Section 6 concludes the paper and discusses future study directions.
2
Related Work
A straightforward pipeline approach for multiple message broadcast is to arrange the processes into a communication chain with the source at the head and pipeline the messages along the chain. m + n − 2 steps are needed by this type of pipelined chain algorithm to complete the broadcast since it takes a message n − 1 steps to reach the end of the chain. The pipelined binary tree algorithm reduces the n dependent cost to 2 × log n steps by pipelining messages along a binary tree of processes. However, it takes twice as many steps before the source can send the last message. Total number of steps required is therefore 2 × (m + log n − 1). Further tradeoff between the n dependent steps and the m dependent steps can be made in the fractional tree algorithm [10] — a generalization of the pipelined chain and binary tree algorithms where node in the binary tree is replaced by a chain of processes. In the scatter-allgather algorithm [2], data is split into m = n messages. The messages are first scattered
Process Cooperation in Multiple Message Broadcast
29
among the processes and then each process collects the rest of the messages from other processes through an allgather operation. Therefore it takes the scatterallgather algorithm 2×(n−1) steps to complete the broadcast. These algorithms are easy to implement but not optimal. Johnsson and Ho [6] have developed an Edge-disjoint Spanning Binomial Tree (ESBT) algorithm for hypercube systems, which can be easily embedded into fully-connected system. The processes are organized into log n binomial trees each consisting of all n processes. The source sends messages to different trees in a round robin fashion. Messages are passed along the trees in parallel and free of edge contention. The algorithm is optimal but it only works when n is a power-of-two. Bar-Noy et al. [1] have sketched an optimal multiple message broadcast algorithm for any number of processes as a by-product of their study on the problem in fully-connected systems using the telephone model. The algorithm is complicated when n is not a power-of-two since it is based on the more restrictive telephone model. The focus of both their algorithm and the ESBT algorithm is more on showing the existence of an optimal schedule but less attention is paid to the practical implementation issue of how to construct the schedule. Tr¨ aff and Ripke [12] have recently extended the ESBT algorithm to any number of processes by allowing incomplete binomial trees and implemented the algorithm in a MPI library. They have developed an O(n × log n) greedy algorithm to construct the optimal but complex schedule. The construction is so expensive that it can only be done off-line at MPI communicator creation and cached with the MPI communicator object for use in MPI BCAST operation.
3
Efficient Schedule Construction for Power of Two Processes
In this section, we describe an optimal algorithm for broadcasting m messages among n = 2q processes. It will be used as the base for our process cooperation algorithm. In the rest of the paper, the m messages are denoted by M0 , M1 , . . . through Mm−1 and the n processes are ranked from 0 through n − 1. Without loss of generality, let process 0 be the source process of the broadcast. The algorithm begins with a setup phase consisting of q steps. Processes are organized into a binomial tree rooted at process 0. Process 0 sends a distinct message to one of its children during each step. Each of the other processes forwards the message received from its parent to all its children. A pipeline phase of m − 1 steps then follows. During each step, every process exchanges messages with a partner process. Figure 1 (right) outlines the algorithm. This algorithm works similarly to other known optimal algorithms [1,6,12]. Contribution of this paper on this part is an efficient construction of the communication schedule, referred to hereafter as the basic schedule. To construct the basic schedule, r, s, t, P arent, Child and P artner in Figure 1 (right) need to be determined. Simple bit operations on process ranking are performed for this purpose. Let (iq−1 iq−2 . . . i0 ) be the binary representation of
30
B. Jia
000
100 010
001
110 101
011
111
if i = 0 then for j ← 0, q − 1 do send Mj to Child(0, j) otherwise receive Mr from P arent(i) for j ← 0, q − l − 2 do send Mr to Child(i, j) for j ← 0, m − 2 do receive Mt from P artner(i, j); send Ms to P artner(i, j)
Fig. 1. Left: example of process relationship, n = 8. Arrows point to children processes. Dashed, solid and dotted lines denote partnership in pipeline step 0, 1, and 2 respectively. Right: algorithm outline.
process i. r and l can be determined easily by scanning the binary representation to locate the rightmost nonzero bit: ir and the leftmost nonzero bit: il . Also define l = −1 for i = 0, parent and the j-th child of process i are given by: P arent(i) = (iq−1 . . . il . . . i0 ) , Child(i, j) = (iq−1 . . . il+j+1 . . . i0 ) . where 0 ≤ j ≤ q − l − 2. Let e = (j mod q), partner process of process i during step j, 0 ≤ j ≤ m − 2, of the pipeline phase is given by: , P artner(i, j) = (iq−1 . . . ie . . . i0 ) . Figure 1 (left) shows an example of the parent-children relationship in the setup phase and the partnership in the pipeline phase. For process 0, s = j + q and t = j. In fact, process 0’s receive and its partner’s send can be replaced by no-op. To determine s and t for process i that is neither the source nor its partner, we first build a q-element array Dis to store the distance between each bit and the next nonzero bit to the left by scanning the binary representation: – let f = 1, g = 1. – while g ≤ q − 1, • if ig = 1, fill up a section of the array: Dis[h] = g − h for f − 1 ≤ h < g and then let f = g + 1. • let g = g + 1 – if iq−1 = 1, let Dis[q − 1] = r + 1. Otherwise, let Dis[h] = r + q − h for f − 1 ≤ h ≤ q − 1. Table 1 gives an example of the Dis array. Finally, at pipeline step j, if ie = 0, then s = j + Dis[e], t = j; otherwise it is the other way around. It can be seen that in the pipeline phase, the communication pattern repeats every q steps and all processes have Mj after step j. When the schedule requires a message labeled beyond m − 1 to be sent/received, message Mm−1 is
Process Cooperation in Multiple Message Broadcast
31
sent/received instead. The source injects Mm−1 during pipeline step m − 1 − q and keeps doing the same thereafter. Therefore the broadcast completes in log n + m − 1 steps, matching the lower bound. Correctness of this basic schedule can be proved by induction. Both the time and space complexity of building the schedule are O(log n).
4
Process Cooperation
In this section, we extend the algorithm described in Section 3 to arbitrary number of processes. The ides is to organize the n processes into n units each having one or two processes, q = log n and n = 2q . The basic schedule is applied to broadcast among the n units. Processes in each two-process unit cooperate in: 1) sending/receiving messages to/from other units according to the basic schedule; and 2) passing message between themselves such that at any step, either process has at most one message that the other process has not received. For this purpose, we construct a process cooperation schedule as an extension to the basic schedule. First we define a simple scheme to organize processes into units. For process i, define: ⎧ i ≥ n ⎨ i − n + 1 0 < i ≤ n − n Co(i) = n − 1 + i ⎩ i otherwise i i < n Rep(i) = Co(i) otherwise Also, the unit to which i belongs is defined as U nit(i). The first row of Table 2 shows an example of the scheme. Process i participates in the setup phase if and only if i < n . The setup phase is the same as in the basic schedule. During each step of the pipeline phase, on the other hand, Rep(i)’s binary representation is used in determining s, t, and P artner(i, j), instead of i’s. Since Rep(i) < n , q-bit binary representation is still sufficient. In a two-process unit, one process is called the output of the unit and the other the input. The output sends a message to the partner unit and the input receives a message from the partner unit. The input also passes a message it received during the setup phase or previous steps of the pipeline phase to the output. In a one-process unit, the process is both the input and the output. Process’s role changes from step to step and its determination is the core of the cooperation schedule. Initial roles are assigned at the beginning of the pipeline phase: Rep(i) is the output of U nit(i) and Co(Rep(i)) is the input. If bit (j mod q) in Rep(i)’s binary representation is equal to 1, the input and output of U nit(i) switch roles after pipeline step j. Let Switch(i, j) be the number of nonzero bits in Rep(i)
32
B. Jia Table 1. Example of Dis, and Switch, i = 406, n = 512 j ij Dis[j] Switch(i, j)
8 1 2 5
7 1 1 4
6 0 1 3
5 0 2 3
4 1 3 3
3 0 1 2
2 1 2 2
1 1 1 1
0 0 1 0
between bit 0 and bit (j mod q), then according to the rule of role switch, the number of role switches for process i before pipeline step j is: u = Switch(i, q − 1) × (j − 1)/q + Switch(i, (j − 1)) . Process i’s role during step j is the same as its initial assignment if u is even. It is the opposite if u is odd. Table 1 shows an example of the Switch function. The input and output of the partner unit also need to be determined if the partner unit is a two-process unit. Since there is only one bit difference between the binary representations of Rep(i) and P artner(i, j), P artner(i, j)’s role during pipeline step j is the same as its initial assignment if v = u + (j − 1)/q is even. It is the opposite otherwise. It can be seen that both the time and space complexity of the role determination are O(log n). With the roles determined, the pipeline phase of the process cooperation algorithm can be described as follows: for j ← 0, m − 2 do output of U nit(i) sends Ms to input of U nit(P artner(i, j)) input of U nit(i) receives Mt from output of U nit(P artner(i, j)) if j > 0 and i = Co(i) then input of U nit(i) passes Mj−1 to the output of U nit(i) if i = Co(i) then input of U nit(i) passes Mm−2 to the output of U nit(i) output of U nit(i) passes Mm−1 to the input of U nit(i) If a message labeled beyond m − 1 is scheduled in the above, Mm−1 is used instead. Note that if n = n , an extra step is taken at the end of the pipeline phase for the input and output to exchange Mm−2 and Mm−1 . Therefore the total number of steps needed by this algorithm is q + m = log n + m − 1, matching the lower bound on communication steps. Table 2 depicts an example of the schedule. The correctness of the cooperation schedule can be proved by showing that at each pipeline step, every process has the message it needs to send according to the schedule. Here we sketch a proof by induction on pipeline step j for process i. The initial condition can be verified from the result of the setup phase and the initial role assignment. Now suppose the cooperation schedule is correct before step j = J of the pipeline phase. Without loss of generality, assume i = Rep(i) and let e = (J mod q), f = ((J + 1) mod q). During step J, we have: – if ie = 1, the output of U nit(i) has MJ and the input receives MJ+Dis[e] from the partner unit. i and Co(i) switch roles after the step.
Process Cooperation in Multiple Message Broadcast
33
Table 2. Cooperation schedule, n = 6, m = 4, cooperative process units are {0}, {1, 4}, {2, 5}, {3}. The top row gives (i, Co(i), Rep(i)) tuple for each process. The middle section shows the source and destination of each message during each step. The right section of the table shows messages received by every process after each step. phase step M0 setup 0 0→1 1 1→3 pipeline 0 3 → 5 1 5→2 1→4 2 3
M1
M2
0→2 2→30→4 3→14→3 1→43→2 2→5 4→1 2→5
M3
(1,4,1) (2,5,2) (3,3,3) M0 M0 M1 M0 M0 M1 M0 , M1 0 → 5 M0 , M1 M1 , M0 M0 , M1 , M2 5 → 3 M0 , M1 , M1 , M0 , M0 , M1 , 0→1 M3 M2 M2 , M3 1 → 4 M0 , M1 , M1 , M0 , M0 , M1 , 5 → 2 M3 , M2 M2 , M3 M2 , M3
(4,1,1)
(5,2,2)
M2 M0 M2 , M0 M0 , M3 M2 , M0 , M0 , M3 , M1 M1 M2 , M0 , M0 , M3 , M1 , M3 M1 , M2
– if ie = 0, the output of U nit(i) has MJ+Dis[e] and the input receives MJ from the partner unit. There is no switch of roles after step J. So before step J+1, the input of U nit(i) has MJ that it needs to send during step J + 1. The output has MJ+Dis[e] . During step J + 1, it needs to send out MJ+1 or MJ+1+Dis[f ] , for if = 1 or if = 0 respectively. According to the construction of Dis: – if if = 0, then Dis[e] = Dis[f ] + 1; – otherwise Dis[e] = 1. In either case, the output has the message it needs to send during step J + 1. The correctness of the cooperation schedule follows.
5
Performance Studies
To evaluate the performance of the process cooperation algorithm, we have run experiments of MPI BCAST implemented using the process cooperation algorithm and three other widely used algorithms: binomial tree, pipelined chain and pipelined binary tree. The experiment platform is a cluster of 32 IBM P5 [8] nodes connected by IBM HPS switch [7]. For each of the pipelined algorithms, we have experimented various m values and selected different m values that give the best performance for different data size ranges. Figure 2 compares the MPI BCAST implementations on 18 processes (left) and 32 processes (right) respectively, running one process per node, for data sizes up to 16MB. It can be seen that for large data sizes, the process cooperation algorithm outperforms the other algorithms by large margins: as much as 50% improvement in bandwidth over the pipelined chain algorithm, 80% over the pipelined binary tree algorithm and more than two times better than the binomial tree algorithm. Figure 3 shows latency of 256KB (left) and 4MB (right)
34
B. Jia MPI_BCAST - 18 processes
MPI_BCAST - 32 processes
1000
1000 pipelined chain pipelined binary tree binomial tree process cooperation
pipelined chain pipelined binary tree binomial tree process cooperation
900
800
800
700
700
bandwidth (MB/s)
bandwidth (MB/s)
900
600 500 400
600 500 400
300
300
200
200
100
100
0
0 1
10
100
1000 10000 100000 message size (byte)
1e+06
1e+07
1e+08
1
10
100
1000 10000 100000 message size (byte)
1e+06
1e+07
1e+08
Fig. 2. Bandwidth comparison of MPI BCAST, on 18 (left) and 32 (right) processes, data size up to 16MB MPI_BCAST - 256KB
MPI_BCAST - 4MB
1200
12000 pipelined chain pipelined binary tree binomial tree process cooperation
1000
10000
800
8000
time (us)
time (us)
pipelined chain pipelined binary tree binomial tree process cooperation
600
6000
400
4000
200
2000
0
0 0
5
10
15 20 number of processes
25
30
35
0
5
10
15 20 number of processes
25
30
35
Fig. 3. Latency comparison of MPI BCAST on 2 to 32 processes, data sizes: 256KB (left) and 4MB (right)
MPI BCAST on varying number of processes (one per node). The process cooperation algorithm shows the best scaling as number of processes increases. The overall results demonstrate performance trends similar to those reported in [12], which is expected since the communication schedules constructed by the process cooperation algorithm and the algorithm in [12] are both optimal. The O(log n) schedule construction of the process cooperation algorithm, however, is more efficient than the O(n × log n) schedule construction in [12].
6
Conclusion and Future Studies
In this paper, we present a process cooperation algorithm for multiple message broadcast. This algorithm is optimal in one-port fully-connected systems. It provides a feasible and efficient solution to the practical implementation issue of on-line communication schedule construction in communication libraries, such as MPI. We have implemented and incorporated the process cooperation algorithm in IBM Parallel Environment/MPI. On fully-connected system, the idea of process cooperation can be extended to multi-port communication models. We have developed new multi-port multiple
Process Cooperation in Multiple Message Broadcast
35
message broadcast algorithm that is theoretically better than known algorithms on arbitrary number of processes. Further performance study on multi-port broadcast will be conducted. We also plan to investigate the effectiveness of process cooperation in communication models that are more realistic for short messages.
References 1. Bar-Noy, A., Kipnis, S., Schieber, B.: Optimal multiple message broadcasting in telephone-like communication systems. In: Proceedings of the 6th Symposium on Parallel and Distributed Processing, IEEE, Los Alamitos (1996) 2. Barnett, M., Gupta, S., Payne, D., Shuler, L., van de Geijn, R., Watts, J.: Interprocessor collective communication library (intercom). In: Proceedings of the Scalable High Performance Computing Conference 1994 (1994) 3. Beaumont, O., Legrand, A., Marchal, L., Robert, Y.: Pipelining broadcasts on heterogeneous platforms. In: Proceedings of 18th IEEE International Parallel and Distributed Processing Symposium IPDPS04, IEEE Computer Society Press, Los Alamitos (2004) 4. Chan, E., Heimlich, M., Purkayastha, A., Van de Geijn, R.: On optimizing collective communication. In: Proceedings of 2004 IEEE International Conference on Cluster Computing, IEEE Computer Society Press, Los Alamitos (2004) 5. IBM PE for AIX 5L V4.3: MPI Programming Guide http://publib.boulder. ibm.com/infocenter/clresctr/vxrx/index.jsp?topic=/com.ibm.cluster.pe. doc/pebooks.html 6. Johnsson, S., Ho, C.T.: Optimum broadcasting and personalized communication in hypercubes. IEEE Transactions on Computers 38(9), 1249–1268 (1989) 7. Johnston, F., King-Smith, B.: Ibm pseries high performance switch. Technical report, IBM System and Technology Group (2006) 8. IBM System p5 UNIX servers www.ibm.com/systems/p/ 9. Patarasuk, P., Faraj, A., Yuan, X.: Pipelined broadcast on ethernet swtiched clusters. In: Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE Computer Society Press, Los Alamitos (2006) 10. Sanders, P., Sibeyn, J.F.: A bandwidth latency tradeoff for broadcast and reduction. In: Bode, A., Ludwig, T., Karl, W.C., Wism¨ uller, R. (eds.) Euro-Par 2000. LNCS, vol. 1900, pp. 918–926. Springer, Heidelberg (2000) 11. Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J.: MPI – The Complete Reference, 2nd edn. The MPI Core, vol. 1. MIT Press, Cambridge (1998) 12. Tr¨ aff, J., Ripke, A.: Optimal broadcast for fully connected networks. In: Yang, L.T., Rana, O.F., Di Martino, B., Dongarra, J.J. (eds.) HPCC 2005. LNCS, vol. 3726, pp. 45–56. Springer, Heidelberg (2005) 13. Worringen, J.: Pipelining and overlapping for mpi collective operations. In: 28th Annual IEEE International Conference for Local Computer Networks (LCN03), IEEE Computer Society Press, Los Alamitos (2003)
Self-consistent MPI Performance Requirements Jesper Larsson Tr¨aff1 , William Gropp2 , and Rajeev Thakur2 1
NEC Laboratories Europe, NEC Europe Ltd. Rathausallee 10, D-53757 Sankt Augustin, Germany
[email protected] 2 Mathematics and Computer Science Division Argonne National Laboratory Argonne, IL 60439, USA {gropp,thakur}@mcs.anl.gov
Abstract. The MPI Standard does not make any performance guarantees, but users expect (and like) MPI implementations to deliver good performance. A common-sense expectation of performance is that an MPI function should perform no worse than a combination of other MPI functions that can implement the same functionality. In this paper, we formulate some performance requirements and conditions that good MPI implementations can be expected to fulfill by relating aspects of the MPI standard to each other. Such a performance formulation could be used by benchmarks and tools, such as SKaMPI and Perfbase, to automatically verify whether a given MPI implementation fulfills basic performance requirements. We present examples where some of these requirements are not satisfied, demonstrating that there remains room for improvement in MPI implementations.
1
Introduction
For good reasons MPI (the Message Passing Interface) [4,9] comes without a performance model and, apart from some “advice to implementers,” without any requirements or recommendations as to what a good implementation should satisfy regarding performance. The main reasons are, of course, that the implementability of the MPI standard should not be restricted to systems with specific interconnect capabilities and that implementers should be given maximum freedom in how to realize the various MPI constructs. The widespread use of MPI over an extremely wide range of systems, as well as the many existing and quite different implementations of the standard, show that this was a wise decision. On the other hand, for the analysis and performance prediction of applications, a performance model is needed. Abstract models such as LogP [3] and
This work was supported in part by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy, under Contract DE-AC0206CH11357.
F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 36–45, 2007. c Springer-Verlag Berlin Heidelberg 2007
Self-consistent MPI Performance Requirements
37
BSP [13] tend to be too complex (for full applications), too limited, or too abstract to have predictive power. MPI provides much more flexible (but also much more complex) modes of communication than catered to in these models. An alternative is to use MPI itself as a model and analyze applications in terms of certain basic MPI primitives. This may work well for restricted usages of MPI to, say, the MPI collectives, but full MPI is probably too large to be a tractable model for performance analysis and prediction. A related consideration is a hard-to-quantify desire for performance portability—the desire that an application should, in some qualitative sense, behave the same when ported to a new system or linked with a different MPI library. Detailed, public benchmarks of MPI constructs can help in translating the performance of an application on one system and MPI library to another system with another MPI library [8]. Accurate performance models would also facilitate translation between systems and MPI libraries, but in their absence simple MPIintrinsic requirements to MPI implementations might serve to guard against the most unpleasant surprises. MPI has many ways of expressing the same communication (patterns), with varying degrees of generality and freedom for the application programmer. This kind of universality makes it possible to relate aspects of MPI to each other also in terms of the expected performance. This is utilized already in the MPI definition itself, where certain MPI functions are explained in a semi-formal way in terms of other MPI functions. The purpose of this paper is to discuss whether it is possible, sensible, and desirable to formulate system-independent, but MPI-intrinsic performance requirements that a “good” MPI implementation should fulfill. Such requirements should not make any commitments to particular system capabilities but would enforce a high degree of performance consistency of an MPI implementation. For example, similar optimizations would have to be done for collective operations that are interlinked through such performance rules. Furthermore, such rules, even if relatively trivial, would provide a kind of “sanity check” of an MPI implementation, especially if they could be checked automatically. In this paper, we formulate a number of MPI-intrinsic performance requirements by semi-formally relating different aspects of the MPI standard to each other, which we refer to as self-consistent performance requirements. By their very nature the rules can be used only to ensure consistency—a trivial, bad MPI implementation could fulfill them as well as a carefully tuned library. Related work includes quality of service for numerical library components [5,6]. Because of the complexity of these components, it is not possible to provide the sort of definitive ordering that we propose for MPI communications.
2
General Rules and Notation
We first formulate and discuss a number of general self-consistent MPI performance requirements, presupposing reasonable familiarity with MPI. We consider the following relationships (metarules) between MPI routines:
38
J.L. Tr¨ aff, W. Gropp, and R. Thakur
1. Replacing all communication with the appropriate use of MPI Isend, MPI Ir ecv, and MPI Wait should not reduce the communication time. In the context of MPI-2, this can be applied even to the MPI one-sided communication routines. 2. Subdividing messages into multiple messages should not reduce the communication time. 3. Replacing a routine with a similar routine that provides additional semantic guarantees should not reduce the communication time. 4. For collective routines, replacing a collective routine with several routines should not reduce the communication time. In particular, the specification of most of the MPI collective routines includes a description in terms of other MPI routines; each MPI collective should be at least as fast as that description. 5. For process topologies, communicating with a communicator that implements a process topology should not be slower than using a random communicator. The first of these requirements provides a formal way to derive relationships between the MPI communication routines—write each routine in terms of an equivalent use of MPI Isend, MPI Irecv, and MPI Wait, and then compare the time taken. In the rest of this paper, we give more specific examples of each of these rules. We use the notation that MPI A(n) MPI B(n)
(1)
means that MPI functionality A is not slower than B when evoked with parameters resulting in the same amount of communication or computation n. Note that MPI buffers are not always specified in this way. We use p to denote the number of processes involved in a call, and MPI A{c} for A called on communicator c. As an example MPI Send(n) MPI Isend(n) + MPI Wait
(2)
states that an MPI Send call is possibly faster, but at least not slower than a call to MPI Isend with the same parameters followed by an MPI Wait call. In this case, it would probably make sense to require more strongly that MPI Send(n) ≈ MPI Isend(n) + MPI Wait
(3)
which means that the alternatives perform similarly. Quantifying the meaning of “similarly” is naturally contentious. A strong definition would say that there is a small confidence interval such that for any data size n, the running time of the one construct is within the running time of the other with this confidence interval. A somewhat weaker definition could require that the running time of the two constructs is within a small constant factor of each other for any data size n.
Self-consistent MPI Performance Requirements
3
39
General Communication
Rule 2 can be made more precise as follows: Splitting a communication buffer of kn units into k buffers of n units, and communicating separately, never pays off. MPI A(kn) MPI A(n) + · · · + MPI A(n)
(4)
k
For an example where this rule is violated with A = Bcast, see [1, p. 68]. Similarly, splitting possibly structured data into its constituent blocks of fixed size k should also not be faster. MPI A(kn) MPI A(k) + · · · + MPI A(k)
(5)
n
One might be able to elaborate this requirement into a formal requirement for the performance of user-defined MPI datatypes, but this issue would require much care. Note that many MPI implementations will violate Rule 2 and ( 4) because of the use of eager and rendezvous message protocols. An example is shown in Figure 1. A user with a 1500-byte message will achieve better performance on this system by sending two 750-byte messages. This example shows one of the implementation features that competes with performance portability—in this case, the use of limited message buffers. To satisfy Rule 2, an MPI implementation would need a more sophisticated buffer management strategy, but in turn this could decrease the performance of all short messages. Comm Perf for MPI (Processor <0,0,0,0> in a <4, 4, 2, 1> mesh) type blocking 70
60
time (us)
50
40
30
20
10
0 0
500
1000
1500
2000 2500 Size (bytes)
3000
3500
4000
4500
Fig. 1. Measured performance of short messages on IBM BG/L. Note the large jump around 1024 bytes; this is the transition from eager to rendezvous protocol in the MPI implementation.
As an example of Rule 3, we have the following MPI Send MPI Ssend
(6)
40
J.L. Tr¨ aff, W. Gropp, and R. Thakur
Since the synchronous send routine has an additional semantic guarantee (the routine cannot return until the matching receive has started), it should not be faster than the regular send.
4
Collective Communication
The MPI collectives are strongly interrelated semantically, and often one collective can be implemented in terms of one or more other related collectives. A general requirement (metarule) is that a specialized collective should not be slower than a more general collective. Thus, with good conscience, users can be given the advice to always use the most specific collective (which is, of course, exactly the motivation for having so many collectives in MPI). 4.1
Regular Communication Collectives
The following three rules are instances of the metarule that specialized functions should not be slower than more general ones. MPI Gather(n) MPI Allgather(n) MPI Scatter(n) MPI Allgather(n) MPI Allgather(n) MPI Alltoall(n)
(7) (8) (9)
The next rule implements a collective operation in terms of two others. Again the specialized function (MPI Allgather) should not be slower. MPI Allgather(n) MPI Gather(n) + MPI Bcast(n)
(10)
This is not as trivial as it may look. If, for instance, a linear ring algorithm is used for the MPI Allgather, but tree-based algorithms for MPI Gather and MPI Bcast, the relationship will not hold (at least for small n). A less obvious requirement relates MPI Scatter to MPI Bcast. The idea is to implement the MPI Scatter function, which scatters individual data to each of the p processes, by a broadcast of the combined data of size pn; each process copies out its block from the larger buffer. MPI Scatter(n) MPI Bcast(pn)
(11)
Again this is a nontrivial requirement for small n for MPI libraries with an efficient MPI Bcast implementation and forces an equally efficient implementation of MPI Scatter. A currently popular implementation of broadcast for large messages is by a scatter followed by an allgather operation [2,10]. Since this is an algorithm expressed purely in terms of collective operations, it makes sense to require that the native broadcast operation should behave at least as well. MPI Bcast(n) MPI Scatter(n) + MPI Allgather(n)
(12)
Self-consistent MPI Performance Requirements
4.2
41
Reduction Collectives
The second half of the next rule states that a good MPI implementation should have an MPI Allreduce that is faster than the trivial implementation of reduction to root followed by a broadcast. MPI Reduce(n) MPI Allreduce(n) MPI Reduce(n) + MPI Bcast(n)
(13)
A similar rule can be formulated for MPI Reduce scatter. MPI Reduce(n) MPI Reduce scatter(n) MPI Reduce(n) + MPI Scatterv(n)
(14)
The next two rules implement MPI Reduce and MPI Allreduce in terms of MPI Reduce scatter and are similar to the broadcast implementation of requirement (12). MPI Reduce(n) MPI Reduce scatter(n) + MPI Gather(n) MPI Allreduce MPI Reduce scatter(n) + MPI Allgather(n)
(15) (16)
For the reduction collectives, MPI provides a set of built-in binary operators, as well as the possibility for users to define their own operators. A natural requirement is that a user-defined implementation of a built-in operator should not be faster. MPI Reduce(MPI SUM) MPI Reduce(user sum)
(17)
A curious example where this is violated is again given in [1, p. 65]. For a particular vendor MPI implementation, a user-defined sum operation was significantly faster than the built-in MPI SUM operation! 4.3
Irregular Communication Collectives
The irregular collectives of MPI, in which the amount of data communicated between pairs of processes may differ, are obviously more general than their regular counterparts. It is desirable that performance be similar when an irregular collective is used to implement the functionality of the corresponding regular collective. Thus, we have requirements like the following. MPI Gatherv(v) ≈ MPI Gather(n)
(18)
This requires that the performance of MPI Gatherv be in the same ballpark as the regular MPI Gather for uniform p element vectors v with v[i] = n/p. Again this is not a trivial requirement. For instance, there are easy tree-based algorithms for MPI Gather but not for MPI Gatherv (at least not as easy because the irregular counts are not available on all processes), and thus performance characteristics of the two collectives may be quite different [11]. Thus, ≈ should be formulated carefully and leave room for some overhead.
42
4.4
J.L. Tr¨ aff, W. Gropp, and R. Thakur
Constraining Implementations
In addition to the rule above that relates collective operations to other collective operations, it would be tempting to require that a good MPI implementation fulfill some minimal requirements regarding the performance of its collectives. For example, the MPI standard already explains many of the collectives in terms of send and receive operations. MPI Gather(n) MPI Recv(n/p) + · · · + MPI Recv(n/p)
(19)
p
Extending this, one could define a set of “minimal implementations,” for example, an MPI Bcast implementation by a simple binomial tree. Correspondingly one could require that the collectives of an MPI library perform at least as well. This requirement could prevent trivial implementations from fulfilling the rules, but how far this idea could and should be taken is not clear at present.
5
Communicators and Topologies
Let c be a communicator (set of processes) of size p representing an assignment of p processes to p processors. Let c be a communicator representing a different (random) assignment to the same processors. A metarule like MPI A{c} ≈ MPI A{c }
(20)
can be expected to hold for homogeneous systems for any MPI communication operation A. For non-homogeneous systems, such as SMP clusters with a hierarchical communication system, such a rule will not hold. For some collectives, it is still reasonable to require communicator independence (irrespective of system), for example, the following. MPI Allgather{c} ≈ MPI Allgather{c }
(21)
This is not a trivial requirement. A linear ring or logarithmic algorithm designed on the assumption of a homogeneous system may, when executed on a SMP system and depending on the distribution of the MPI processes over the SMP nodes, have communication rounds in which more than one MPI process per SMP node communicates with processes on other nodes. The effect of the resulting serialization of communication is shown in Figure 2. It seems reasonable to require communicator independence for all symmetric (non-rooted communication) collectives, that is, requirement (20) for A ∈ {Allgather, Alltoall, Barrier}. MPI contains routines for defining process topologies, and these should not decrease performance for their preferred communication patterns. As an example of Rule 5, using a Cartesian communicator c and then communicating to the Cartesian neighbors should be no slower than using an arbitrary communicator c . MPI Send{c} MPI Send{c }
(22)
Self-consistent MPI Performance Requirements MPI_Allgather, 36 nodes, Linear algorithm, MPI_COMM_WORLD versus random 100000 Linear, 8 proc/node (MPI_COMM_WORLD) Linear, 8 proc/node (random communicator)
MPI_Allgather, 36 nodes, New algorithm, MPI_COMM_WORLD versus random 100000 New 8, proc/node (MPI_COMM_WORLD) New 8, proc/node (random communicator)
10000 Time (micro seconds)
10000 Time (micro seconds)
43
1000
100
1000
100
10
10 1
10
100
1000 10000 Size (Bytes/proc)
100000
1e+06
1
10
100
1000 10000 Size (Bytes/proc)
100000
1e+06
Fig. 2. Left: performance of a simple, non-SMP-aware linear ring algorithm for MPI Allgather when executed on the ordered MPI COMM WORLD communicator and on a communicator where the processes have been randomly permuted. Right: performance of an SMP-aware algorithm for MPI Allgather on ordered and random communicator. The degradation for small data for the random communicator is due to specifics of the target (vector) system; see [12].
6
One-Sided Communication
The one-sided communication model of MPI-2 is interrelated to both point-topoint and collective communication, and a number of performance requirements can be formulated. We give a single example. For the fence synchronization method, the performance of a fence-put-fence should be no worse than a barrier on the same communicator, followed by an MPI Send of the datatype and address information, followed by another barrier: MPI Win fence + MPI Put(n) + MPI Win fence
(23)
MPI Barrier + MPI Send(d) + MPI Send(n) + MPI Barrier where d represents information about the address and datatype on the target. Figure 3 shows an example where this requirement is violated. On an IBM SMP system with IBM’s MPI, the performance of a simple nearest-neighbor halo exchange is about three times worse with one-sided communication and fence synchronization compared with regular point-to-point communication, even when two processors are available for each MPI process.
7
Automating the Checks
With a precise definition of the and ≈ relations, it would in principle be possible to automate the checking that a given MPI implementation (on a given system) fulfills a set of self-consistent performance requirements. A customizable benchmark such as SKaMPI [1,7,8] already has some patterns that allow the comparison
44
J.L. Tr¨ aff, W. Gropp, and R. Thakur
Fig. 3. Performance of MPI Put with fence synchronization versus point-to-point communication on an IBM SMP with IBM’s MPI for a simple nearest-neighbor halo exchange. The middle line shows the performance bound based on using barrier and send.
of alternative implementations of the same MPI functionality, similar to many of the rules formulated above. It would be easy to incorporate a wider set of rules into SKaMPI. By combining this with an experiments-management system such as Perfbase [14,15], one could create a tool that automatically validates an MPI implementation as to its intrinsic performance. (We have not done so yet.)
8
Concluding Remarks
Users often complain about the poor performance of some of the MPI functions in MPI implementations and of the difficulty of writing code whose performance is portable. Solving this problem requires defining performance standards that MPI implementations are encouraged to follow. We have defined some basic, intrinsic performance rules for MPI implementations and provided examples where some of these rules are being violated. Further experiments might reveal more such violations. We note that just satisfying these rules does not mean that an implementation is good, because even a poor, low-quality implementation can trivially do so. They must be used in conjunction with other benchmarks and performance metrics for a comprehensive performance evaluation of MPI implementations.
References 1. Augustin, W., Worsch, T.: Usefulness and usage of SKaMPI-bench. In: Dongarra, J.J., Laforenza, D., Orlando, S. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 2840, pp. 63–70. Springer, Heidelberg (2003) 2. Barnett, M., Gupta, S., Payne, D.G., Schuler, L., van de Geijn, R., Watts, J.: Building a high-performance collective communication library. In: Supercomputing’94, pp. 107–116 (1994)
Self-consistent MPI Performance Requirements
45
3. Culler, D.E., Karp, R.M., Patterson, D., Sahay, A., Santos, E.E., Schauser, K.E., Subramonian, R., von Eicken, T.: LogP: A practical model of parallel computation. Communications of the ACM 39(11), 78–85 (1996) 4. Gropp, W., Huss-Lederman, S., Lumsdaine, A., Lusk, E., Nitzberg, B., Saphir, W., Snir, M.: MPI – The Complete Reference. The MPI Extensions, vol. 2. MIT Press, Cambridge (1998) 5. McInnes, L.C., Ray, J., Armstrong, R., Dahlgren, T.L., Malony, A., Norris, B., Shende, S., Kenny, J.P., Steensland, J.: Computational quality of service for scientific CCA applications: Composition, substitution, and reconfiguration. Technical Report ANL/MCS-P1326-0206, Argonne National Laboratory (February 2006) 6. Norris, B., McInnes, L., Veljkovic, I.: Computational quality of service in parallel CFD. In: Proceedings of the 17th International Conference on Parallel Computational Fluid Dynamics, University of Maryland, College Park, MD, May 24–27 (to appear, 2006) 7. Reussner, R., Sanders, P., Prechelt, L., M¨ uller, M.: SKaMPI: A detailed, accurate MPI benchmark. In: Alexandrov, V.N., Dongarra, J.J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 1497, pp. 52– 59. Springer, Heidelberg (1998) 8. Reussner, R., Sanders, P., Tr¨ aff, J.L.: SKaMPI: A comprehensive benchmark for public benchmarking of MPI. Scientific Programming 10(1), 55–65 (2002) 9. Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J.: MPI – The Complete Reference, 2nd edn. The MPI Core, vol. 1. MIT Press, Cambridge (1998) 10. Thakur, R., Gropp, W.D., Rabenseifner, R.: Improving the performance of collective operations in MPICH. International Journal on High Performance Computing Applications 19, 49–66 (2004) 11. Tr¨ aff, J.L.: Hierarchical gather/scatter algorithms with graceful degradation. In: International Parallel and Distributed Processing Symposium (IPDPS 2004), p. 80 (2004) 12. Tr¨ aff, J.L.: Efficient allgather for regular SMP-clusters. In: Mohr, B., Tr¨ aff, J.L., Worringen, J., Dongarra, J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 4192, pp. 58–65. Springer, Heidelberg (2006) 13. Valiant, L.G.: A bridging model for parallel computation. Communications of the ACM 33(8), 103–111 (1990) 14. Worringen, J.: Experiment management and analysis with perfbase. In: IEEE International Conference on Cluster Computing (2005) 15. Worringen, J.: Automated performance comparison. In: Mohr, B., Tr¨ aff, J.L., Worringen, J., Dongarra, J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 4192, pp. 402–403. Springer, Heidelberg (2006)
Test Suite for Evaluating Performance of MPI Implementations That Support MPI THREAD MULTIPLE Rajeev Thakur and William Gropp Mathematics and Computer Science Division Argonne National Laboratory Argonne, IL 60439, USA {thakur,gropp}@mcs.anl.gov
Abstract. MPI implementations that support the highest level of thread safety for user programs, MPI THREAD MULTIPLE, are becoming widely available. Users often expect that different threads can execute independently and that the MPI implementation can provide the necessary level of thread safety with only a small overhead. The MPI Standard, however, requires only that no MPI call in one thread block MPI calls in other threads; it makes no performance guarantees. Therefore, some way of measuring an implementation’s performance is needed. In this paper, we propose a number of performance tests that are motivated by typical application scenarios. These tests cover the overhead of providing the MPI THREAD MULTIPLE level of thread safety for user programs, the amount of concurrency in different threads making MPI calls, the ability to overlap communication with computation, and other features. We present performance results with this test suite on several platforms (Linux cluster, Sun and IBM SMPs) and MPI implementations (MPICH2, Open MPI, IBM, and Sun).
1
Introduction
With thread-safe MPI implementations becoming increasingly common, users are able to write multithreaded MPI programs that make MPI calls concurrently from multiple threads. Thread safety does not come for free, however, because the implementation must protect certain data structures or parts of the code with mutexes or critical sections. Developing a thread-safe MPI implementation is a fairly complex task, and the implementers must make several design choices, both for correctness and for performance [2]. To simplify the task, implementations often focus on correctness first and performance later (if at all). As a result, even though an MPI implementation may support multithreading, its performance may be far from optimized. Users, therefore, need a way to determine how efficiently an implementation can support multiple threads. Similarly, as implementers experiment with a potential performance optimization, they need a way to measure the outcome. (We ourselves face this situation in MPICH2.) To meet these needs, we have created a test suite that can shed light F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 46–55, 2007. c Springer-Verlag Berlin Heidelberg 2007
Test Suite for Evaluating Performance of MPI THREAD MULTIPLE
47
on the performance of an MPI implementation in the multithreaded case. We describe the tests in the suite, the rationale behind them, and their performance with several MPI implementations (MPICH2, Open MPI, IBM MPI, and Sun MPI) on several platforms. Related Work. The MPI benchmarks from Ohio State University [4] contain a multithreaded latency test, which is a ping-pong test with one thread on the sender side and two (or more) threads on the receiver side. A number of other MPI benchmarks exist, such as SKaMPI [6] and the Intel MPI Benchmarks [3], but they do not measure the performance of multithreaded MPI programs. A good discussion of the issues in developing a thread-safe MPI implementation is given in [2]. Other thread-safe MPI implementations are described in [1,5].
2
Overview of MPI and Threads
To understand the test suite and the rationale behind each test, one must understand the thread-safety specification in MPI. For performance reasons, MPI defines four “levels” of thread safety and allows the user to indicate the level desired—the idea being that the implementation need not incur the cost for a higher level of thread safety than the user needs. The four levels of thread safety are as follows: 1. MPI THREAD SINGLE Each process has a single thread of execution. 2. MPI THREAD FUNNELED A process may be multithreaded, but only the thread that initialized MPI may make MPI calls. 3. MPI THREAD SERIALIZED A process may be multithreaded, but only one thread at a time may make MPI calls. 4. MPI THREAD MULTIPLEA process may be multithreaded, and multiple threads may simultaneously call MPI functions (with some restrictions mentioned below). An implementation is not required to support levels higher than MPI THREAD SINGLE; that is, an implementation is not required to be thread safe. A fully thread-compliant implementation, however, will support MPI THREAD MULTIPLE. MPI provides a function, MPI Init thread, by which the user can indicate the level of thread support desired, and the implementation will return the level supported. A portable program that does not call MPI Init thread should assume that only MPI THREAD SINGLE is supported. The tests described in this paper focus on the MPI THREAD MULTIPLE (fully multithreaded) case. For MPI THREAD MULTIPLE, the MPI Standard specifies that when multiple threads make MPI calls concurrently, the outcome will be as if the calls executed sequentially in some (any) order. Also, blocking MPI calls will block only the calling thread and will not prevent other threads from running or executing MPI functions. MPI also says that it is the user’s responsibility to prevent races when threads in the same application post conflicting MPI calls. For example,
48
R. Thakur and W. Gropp Process 0 Thread 0 MPI_Recv(src=1)
Process 1 Thread 1
MPI_Send(dest=1)
Thread 0 MPI_Recv(src=0)
Thread 1 MPI_Send(dest=0)
Fig. 1. An implementation must ensure that this example never deadlocks for any ordering of thread execution
the user cannot call MPI Info set and MPI Info free on the same info object concurrently from two threads of the same process; the user must ensure that the MPI Info free is called only after MPI Info set returns on the other thread. Similarly, the user must ensure that collective operations on the same communicator, window, or file handle are correctly ordered among threads. A straightforward implication of the MPI thread-safety specification is that an implementation cannot implement thread safety by simply acquiring a lock at the beginning of each MPI function and releasing it at the end of the function: A blocked function that holds a lock may prevent MPI functions on other threads from executing, a situation that in turn might prevent the occurrence of the event that is needed for the blocked function to return. An example is shown in Figure 1. If thread 0 happened to get scheduled first on both processes, and MPI Recv simply acquired a lock and waited for the data to arrive, the MPI Send on thread 1 would not be able to acquire its lock and send its data; hence, the MPI Recv would block forever. Therefore, the implementation must release the lock at least before blocking within the MPI Recv and then reacquire the lock if needed after the data has arrived. (The tests described in this paper provide some information about the fairness and granularity of how blocking MPI functions are handled by the implementation.)
3
The Test Suite
Users of threads in MPI often have the following expectations of the performance of threads, both those making MPI calls and those performing computation concurrently with threads that are making MPI calls. – The cost of thread safety, compared with lower levels of thread support, such as MPI THREAD FUNNELED, is relatively low. – Multiple threads making MPI calls, such as MPI Send or MPI Bcast, can make progress simultaneously. – A blocking MPI routine in one thread does not consume excessive CPU resources while waiting. Our tests are designed to test these expectations; in terms of the above categories, they are as follows: Cost of thread safety. One simple test to measure MPI THREAD MULTIPLE overhead.
Test Suite for Evaluating Performance of MPI THREAD MULTIPLE
49
Concurrent progress. Tests to measure concurrent bandwidth by multiple threads of a process to multiple threads of another process, as compared with multiple processes to multiple processes. Both point-to-point and collective operations are included. Computation overlap. Tests to measure the overlap of communication with computation and the ability of the application to use a thread to provide a nonblocking version of a communication operation for which there is no corresponding MPI call, such as nonblocking collectives or I/O operations that involve several steps. We describe the tests below and present performance results on the following platforms and MPI implementations: Linux Cluster. We used the Breadboard cluster at Argonne, in which each node has two dual-core 2.8 GHz AMD Opteron CPUs. The nodes are connected by Gigabit Ethernet. We used MPICH2 1.0.5 and Open MPI 1.2.1. Sun Fire SMP. We used a Sun Fire SMP from the Sun cluster at the RWTH Aachen University. The specific machine we ran on was a Sun Fire E2900 with eight dual-core UltraSPARC IV 1.2 GHz CPUs. It runs Sun’s MPI (ClusterTools 5). IBM SMP. We also used an IBM p655+ SMP from the DataStar cluster at the San Diego Supercomputer Center. The machine has eight 1.7 GHz POWER4+ CPUs and runs IBM’s MPI. 3.1
MPI THREAD MULTIPLE Overhead
Our first test measures the ping-pong latency for two cases of a single-threaded program: initializing MPI with just MPI Init and initializing it with MPI Init thread for MPI THREAD MULTIPLE. This test demonstrates the overhead of ensuring thread safety for MPI THREAD MULTIPLE—typically implemented by acquiring and releasing locks—even though no special steps are needed in this case because the process is single threaded (but the implementation does not know that). Figure 2 shows the results. On the Linux cluster, with both MPICH2 and Open MPI, the overhead of MPI THREAD MULTIPLE is less than 0.5 μs. On the IBM SMP with IBM MPI, it is less than 0.25 μs. On the other hand, on the Sun SMP with Sun MPI, the overhead is very high—more than 3 μs. 3.2
Concurrent Bandwidth
The second test measures the cumulative bandwidth obtained when multiple threads of a process communicate with multiple threads of another process compared with multiple processes instead of threads (see Figure 3). It demonstrates how much thread locks affect the cumulative bandwidth; ideally, the multiprocess and multithreaded cases should perform similarly. Figure 4 shows the results. On the Linux cluster, the tests were run on two nodes, with all communication happening across nodes. We ran two cases: one
50
R. Thakur and W. Gropp 100
9
MPICH2 thread-single MPICH2 thread-multiple Open MPI thread-single 90 Open MPI thread-multiple
SUN MPI thread-single SUN MPI thread-multiple IBM MPI thread-single IBM MPI thread-multiple
8
Time (microsec.)
Time (microsec.)
7 80
70
60
6 5 4
50
3
40
2 0
200
400
600
800
1000
0
200
Size (bytes)
400
600
800
1000
Size (bytes)
Fig. 2. Overhead of MPI THREAD MULTIPLE on the Linux cluster (left) and Sun and IBM SMPs (right)
where there were as many processes/threads as the number of processors on a node (four) and one where there were eight processes/threads running on four processors. In both cases, there is no measurable difference in bandwidth between threads and processes with MPICH2. With Open MPI, there is a decline in bandwidth with threads in the oversubscribed case. On the Sun and IBM SMPs, on the other hand, there is a substantial decline (more than 50% in some cases) in the bandwidth when threads were used instead of processes. Although it is harder to provide low overhead in these sharedmemory environments because the communication bandwidths are so high, we believe a tuned implementation should be able to support concurrent threads with a much smaller loss in performance.
T
T
P
P
T
T
P
P
T
T
P
P
T
T
P
P
Fig. 3. Communication test when using multiple threads (left) versus multiple processes (right)
3.3
Concurrent Latency
Our third test is similar to the concurrent bandwidth test except that it measures the time for individual short messages instead of concurrent bandwidth for large messages. Figure 5 shows the results. On the Linux cluster with MPICH2, there is a 20 μs overhead in latency when using concurrent threads instead of processes. With Open MPI, the overhead is about 30 μs. With Sun and IBM MPI, the latency with threads is about 10 times the latency with processes.
Test Suite for Evaluating Performance of MPI THREAD MULTIPLE 1200
4.5 Cumulative bandwidth (GBytes/s)
Cumulative bandwidth (Mbits/s)
5
4P-4P 4T-4T 8P-8P 8T-8T
1000
51
800
600
400
200
4
4P-4P 4T-4T 8P-8P 8T-8T
3.5 3 2.5 2 1.5 1
0
0.5 MPICH2
Open MPI
Sun MPI
IBM MPI
Fig. 4. Concurrent bandwidth test on Linux cluster (left) and Sun and IBM SMPs (right)
Again, although it is more difficult to provide low overhead on these machines because the basic message-passing latency is so low, a tuned implementation should be able to do better than a factor of 10 higher latency in the threaded case. 150
40 MPICH2 4P-4P MPICH2 4T-4T Open MPI 4P-4P Open MPI 4T-4T
140
35 30
120
Time (microsec.)
Time (microsec.)
130
110 100 90
Sun MPI 4P-4P Sun MPI 4T-4T IBM MPI 4P-4P IBM MPI 4T-4T
25 20 15 10
80
5
70 60
0 0
200
400 600 Size (bytes)
800
1000
0
200
400 600 Size (bytes)
800
1000
Fig. 5. Concurrent latency test on Linux cluster (left) and Sun and IBM SMPs (right)
3.4
Concurrent Short-Long Messages
The fourth test is a blend of the concurrent bandwidth and concurrent latency tests. It has two versions. In the threads version, rank 0 has two threads: one sends a long message to rank 1, and the other sends a series of short messages to rank 2. The second version of the test is similar except that the two senders are processes instead of threads. This test tests the fairness of thread scheduling and locking. If they were fair, one would expect each of the short messages to take roughly the same amount of time. The results are shown in Figure 6. With both MPICH2 and Open MPI, the cost of communicating the long message is evenly distributed among a number
52
R. Thakur and W. Gropp 2000
140
MPICH2 (with processes) MPICH2 (with threads) 1800 Open MPI (with processes) Open MPI (with threads) 1600
100 Time (microsec.)
1400 Time (microsec.)
Sun MPI (with processes) Sun MPI (with threads) IBM MPI (with processes) IBM MPI (with threads)
120
1200 1000 800 600
80 60 40
400 20 200 0
0 10
20
30
40
50
60
70
80
90
10
Iteration
20
30
40
50
60
70
80
90
Iteration
Fig. 6. Concurrent short-long messages test on Linux cluster (left) and Sun and IBM SMPs (right)
of short messages. A single short message is not penalized for the entire time the long message is communicated. This result demonstrates that, in the threaded case, locks are fairly held and released and that the thread blocked in the longmessage send does not block the other thread. With Sun and IBM MPI, however, one sees spikes in the graphs. This behavior may be because these implementations use memory copying to communicate data, and it is harder to overlap this memory-copy time with the memory copying on the other thread. 3.5
Computation/Communication Overlap
Our fifth test measures the ability of an implementation to overlap communication with computation and provides users an alternative way of achieving such an overlap if the implementation does not do so. The test has two versions. The first version has an iterative loop in which a process communicates with its four nearest neighbors by posting nonblocking sends and receives, followed by a computation phase, followed by an MPI Waitall for the communication to complete. The second version is similar except that, before the iterative loop, each process spawns a thread that blocks on an MPI Recv. The matching MPI Send is called by the main thread only at the end of the program, just before MPI Finalize. The thread thus blocks in the MPI Recv while the main thread is in the communication-computation loop. Since the thread is executing an MPI function, whenever it gets scheduled by the operating system, it can cause progress to occur on the communication initiated by the main thread. This technique effectively simulates asynchronous progress by the MPI implementation. If the total time taken by the communication-computation loop in this case is less than that in the nonthreaded version, it indicates that the MPI implementation on its own does not overlap communication with computation. Figure 7 shows the results. Here, “no overlap” refers to the test without the thread, and “overlap” refers to the test with the thread. The results with MPICH2 demonstrate no asynchronous progress, as the overlap version of the
Test Suite for Evaluating Performance of MPI THREAD MULTIPLE
1400
1000 800 600 400 200
6 procs, no overlap 6 procs, overlap 8 procs, no overlap 8 procs, overlap
8000 Time per iteration (millisec.)
1200 Time per iteration (millisec.)
9000
6 procs, no overlap 6 procs, overlap 12 procs, no overlap 12 procs, overlap
53
7000 6000 5000 4000 3000 2000 1000
0
0 MPICH2
Open MPI
Open MPI, progress thread
Sun MPI
IBM MPI
Fig. 7. Computation/communication overlap test on Linux cluster (left) and Sun and IBM SMPs (right)
test performs better. With Open MPI, we ran two experiments. We first used the default build; the results indicate that it performs similarly to MPICH2—no overlap of computation and communication. Open MPI can also be optionally built to use an extra thread internally for asynchronous progress. With this version of the library, we see that indeed there is asynchronous progress, as the performance is nearly the same as for the “overlap” test with the default build. That is, the case with the implementation-created progress thread performs similarly to the case with the user-created thread. We note that always using an extra thread for progress has other performance implications. For example, it can result in higher communication latencies because of the thread-switching overhead. Due to lack of space, we did not run all the other tests with the version of Open MPI configured to use an extra thread. The results on the Sun and IBM SMPs indicate no overlap. In fact, with eight processes, the performance was worse with the overlap thread because of the high overhead when using threads with these MPI implementations. 3.6
Concurrent Collectives
Our sixth test compares the performance of concurrent calls to a collective function (MPI Allreduce) issued from multiple threads to that when issued from multiple processes. The test uses multiple communicators, and processes are arranged such that the processes belonging to a given communicator are located on different nodes. In other words, collective operations are issued by multiple threads/processes on a node, with all communication taking place across nodes (similar to Figure 3 but for collectives and using multiple nodes). Figure 8 (left) shows the results on the Linux cluster. MPICH2 has relatively small overhead for the threaded version, compared with Open MPI.
54
R. Thakur and W. Gropp Concurrent Collectives
Concurrent Collectives and Computation
0.55 MPICH2, processes MPICH2, threads Open MPI, processes Open MPI, threads
MPICH2 with allreduce thread MPICH2 without allreduce thread Open MPI with allreduce thread Open MPI without allreduce thread
70 Iterations per thread per sec.
Time (millisec.)
0.5
75
0.45
0.4
0.35
0.3
65 60 55 50 45 40
0.25
35 12 (4x3) processes/threads
24 (4x6) processes/threads
3 SMP nodes
6 SMP nodes
Fig. 8. Left: Concurrent collectives test on the Linux cluster (4x3 refers to 4 process/threads each on 3 nodes). Right: Concurrent collectives and computation test on the Linux cluster.
3.7
Concurrent Collectives and Computation
Our final test evaluates the ability to use a thread to hide the latency of a collective operation while using all available processors to perform computations. It uses p+1 threads on a node with p processors. Threads 0–(p−1) perform some computation iteratively. Thread p does an MPI Allreduce with its corresponding threads on other nodes. When the allreduce completes, it sets a flag, which stops the iterative loop on the other threads. The average number of iterations completed on the threads is reported. This number is compared with the case with no allreduce thread (the higher the better). Figure 8 (right) shows the results on the Linux cluster. MPICH2 demonstrates a better ability than Open MPI to hide the latency of the allreduce.
4
Concluding Remarks
As MPI implementations supporting MPI THREAD MULTIPLE become increasingly available, there is a need for tests that can shed light on the performance and overhead associated with using multiple threads. We have developed such a test suite and presented its performance on multiple platforms and implementations. The results indicate relatively good performance with MPICH2 and Open MPI on Linux clusters, but poor performance with IBM and Sun MPI on IBM and Sun SMP systems. We plan to add more tests to the suite, such as to measure the overlap of computation/communication with the MPI-2 file I/O and connect-accept features. We will also accept contributions from others to the test suite. The test suite will be available for download from www.mcs.anl.gov/~thakur/thread-tests.
Test Suite for Evaluating Performance of MPI THREAD MULTIPLE
55
Acknowledgments We thank the RWTH Aachen University and the San Diego Supercomputer Center for providing computing time on their systems. This work was supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy, under Contract DE-AC02-06CH11357.
References 1. Garc´ıa, F., Calder´ on, A., Carretero, J.: MiMPI: A multithread-safe implementation of MPI. In: Margalef, T., Dongarra, J.J., Luque, E. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 1697, pp. 207–214. Springer, Heidelberg (1999) 2. Gropp, W., Thakur, R.: Issues in developing a thread-safe MPI implementation. In: Mohr, B., Tr¨ aff, J.L., Worringen, J., Dongarra, J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 4192, pp. 12– 21. Springer, Heidelberg (2006) 3. Intel MPI benchmarks, http://www.intel.com 4. OSU MPI benchmarks, http://mvapich.cse.ohio-state.edu/benchmarks 5. Protopopov, B.V., Skjellum, A.: A multithreaded message passing interface (MPI) architecture: Performance and program issues. Journal of Parallel and Distributed Computing 61(4), 449–466 (2001) 6. Reussner, R., Sanders, P., Tr¨ aff, J.L.: SKaMPI: A comprehensive benchmark for public benchmarking of MPI. Scientific Programming 10(1), 55–65 (2002)
An Improved Parallel XSL-FO Rendering for Personalized Documents Luiz Gustavo Fernandes1 , Thiago Nunes1 , Mateus Raeder1 , Fabio Giannetti2 , Alexis Cabeda3 , and Guilherme Bedin3 1
PPGCC/PUCRS - Porto Alegre, Brazil {gustavo,tnunes,mraeder}@inf.pucrs.br 2 HP Laboratories - Bristol, United Kingdom
[email protected] 3 HP Brazil R&D - Porto Alegre, Brazil {alexis.cabeda,guilherme.bedin}@hp.com
Abstract. The use of personalized documents has become a helpful practice on the digital printing area. Automatic procedures to create and transform these documents have become necessary to deal with the growing market demand. Languages such as XSL-FO (eXtensible Stylesheet Language-Formatting Objects) and PPML (Personalized Print Markup Language) have been developed to facilitate the way variable content is inserted within a document. However, these languages have brought together an increasing computational cost of those documents rendering process. Considering that printing shops need to render jobs with thousands of personalized documents within a short period of time, high performance techniques appear as an interesting alternative to improve this rendering process throughput. In this work, we present improvements and new results of a MPI solution previously developed for the FOP (Formatting Objects Processor) tool. FOP is the Apache project rendering tool for personalized documents and its parallel version was optimized in order to allow the computation in parallel of larger input jobs composed of thousands of personalized documents.
1
Introduction
Due to the growing demand for personalized documents, printing high data volume is becoming a common practice among print shops. Most of the digital publishing production environments use digital presses in parallel to maximize the overall document production (jobs). In such an environment, all activities related to the document preparation need to be executed in a constrained time slot, since jobs are completed in a sequential order. The main step on the document preparation is the rendering phase, which is usually quite expensive and in case of thousands of documents it easily becomes the bottleneck of the whole process. Nowadays, modern digital presses are used in parallel, increasing the overall printing speed significantly. In this context, it can become very difficult to feed all the presses with the necessary rendered documents throughput to make the most of their printing speed. F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 56–63, 2007. c Springer-Verlag Berlin Heidelberg 2007
An Improved Parallel XSL-FO Rendering for Personalized Documents
57
Similarly to the concept of using presses in parallel to achieve better performance and quickly consume jobs, researches have been carried out to propose a parallelization of the rendering engines. Previous results [1] show that the proposed solution can match the presses speed at the rendering stage, but only for jobs with at maximum 2,000 documents (which have the same structure of test cases described at table 1). The aim of the present work is to optimize this previous parallel solution in such a way it could be used to larger input jobs. A final constraint must be observed: the proposed solution must be restricted to execute over a small set of processors. That is necessary once print shops (which are the target users) do not intend to invest on very expensive and complex parallel platforms. The remainder of this paper is organized as follows: Section 2 presents in details the research context of rendering personalized documents. Section 3 describes the improvements added to the previous parallel solution. An analysis for experimental results of a test cases set is reported on Section 4. Finally, some concluding remarks and future works are discussed in Section 5.
2
Rendering Personalized Documents
The combination of PPML (Personalized Print Markup Language) [2] and XSLFO (eXtensible Stylesheet Language-Formatting Objects) [3] has been employed to represent document templates with a high degree of flexibility, reusability and printing optimization. The main advantage of this combination is the expressibility of invariant portions of the template as re-usable objects and variable parts as XSL-FO fragments. Once the variable data is merged into the template, various document instances are formed. The final step is to compose or render the XSL-FO parts into a Page Description Language (PDL). Before describing the processing environment, it is relevant to highlight the most important aspects of these XML (eXtensible Markup Language) [4] formats: PPML and XSL-FO. PPML is a standard language for digital print built from XML developed by PODi (Print on Demand Initiative) [5] which is a consortium of leading companies in digital printing. PPML has been designed to improve the rendering process of the content of documents using traditional printing languages. It is a hierarchical language that contains documents, pages and objects, which are classified as reusable or disposable. The reusable content represents the concept where data, which is used on many pages, can be sent to the printer once and accessed as many times as needed from the printer’s memory. This concept allows high graphical content to be rendered once as well and to be accessed by sending layout instructions instead of re-sending the whole graphic every time it is printed [6]. The variable data is merged and formatted inside the PPML object element using XSL-FO. The containing PPML element is named “copy-hole”, which is a defined area in the PPML code that can contain the variable data expressed in XSL-FO, or a non variable content such as images. XSL-FO (also abbreviated as FO - from Formatting Objects) is a W3C [7] standard introduced to format
58
L.G. Fernandes et al.
XML content for paginated media. It ideally works in conjunction with XSL-T (eXtensible Styleshee Language - Transformations) [8] to map XML content into formatted content. Once the XSL-FO is completed with the formatted content, its rendering engine executes the composition step to lay out the content inside the pages and obtain the final composed document. The rendering process in our environment is carried out by Apache’s rendering engine named FOP (Formatting Objects Processor) [9]. FOP is one of the most common processors in the market not only because it is an open source application, but also because it provides a variety of output formats and it is flexible and easily extendable. It is a Java application that reads formatting objects and renders to different output formats such as PDF (Portable Document Format), plain text, Post Script, SVG (Scalable Vector Graphics), among others. The rendering process is typically composed of three distinctive steps: 1. Generation of a formatting object tree and properties resolution; 2. Generation of an area tree representing the document having as leafs text elements or images; 3. Converting or mapping the area tree to the output format. The advantages of this approach are related to the complete independence between the XSL-FO representation of the document and the internal area tree construction. Using this approach makes it possible to map the area tree to a different set of PDLs.
3
Improving Parallel FOP
The parallel implementation for Apache’s rendering tool (FOP) discussed on this section was first proposed in [1]. It was designed aiming to speed up the performance of the sequential tool increasing its capacity to feed properly large presses with rendered documents. The basic restriction of this research was the necessity to avoid the use of parallel programming models oriented to very expensive (but not frequently used) platforms because the target users (print shops) do not want to invest on expensive hardware. Typically, useful parallel versions for this tool should run distributed over a small number of processors connected by a fast network. Therefore, the natural choice was a cluster with a message passing programming model. Considering that the original FOP tool was developed in Java for portability reasons, its parallel version should keep this feature matching Java with MPI (Message Passing Interface) [10]. This was achieved through the mpiJava [11] implementation. After the analysis of the original work, two possible optimization points were detected: (i) the distribution of data among the rendering modules, and (ii) the generation of the final document. These two factors acting together have limited the scalability of the proposed parallel version, not allowing performance benefits in the rendering process of input jobs with more than 2,000 documents. At this point, it is important to mention that there is a multitude of
An Improved Parallel XSL-FO Rendering for Personalized Documents
59
possible configurations of documents that can be represented matching PPML and XSL-FO. Therefore, in order to provide a standard to allow comparisons, documents in the context of this work have a set of characteristics that will be presented to readers in the next section. A detailed description of the original parallel FOP tool will not be discussed here. Readers interested in more details should read [1]. The improvements proposed in this paper will be discussed during the explanation of the new parallel architecture of the FOP tool showed in Fig. 1.
Fig. 1. New parallel FOP architecture
The improved parallel architecture is composed of four modules as follows: PPMLParser, PPMLReceiver, Broker and FOP. The PPMLParser is responsible for parsing the input PPML document, separating variable content to be rendered (XSL-FO) from invariant parts of the document. Considering that the parallel FOP tool is supposed to deal with jobs containing thousands of documents, the parse procedure takes thus a long time. Therefore, it is interesting to provide a way for the rendering modules (called FOPs) to carry out the XSL-FO formatting in parallel with the parsing. This is possible due to the module called Broker. The Broker implements a queue, which contains buffers fulfilled with XSL-FOs found at the input documents, and works in a producer/consumer model using threads. Buffers are generated by the PPMLParser and consumed by the FOPs modules. The first optimization is related to the distribution of the communication buffers. In the first parallel version of the FOP tool, the Broker started to distribute buffers with XSL-FOs to FOPs modules as soon as it received the first buffer from the PPMLParser. Besides, the buffers had a fixed size, not taking into account the number of FOP modules running. In the new parallel version, this procedure was optimized by two modifications: (i) the Broker now waits for having at least one buffer per FOP module queued to start the distribution, and
60
L.G. Fernandes et al.
(ii) the size of the buffers is now calculated considering the amount of FOP modules running. The first optimization avoids the Broker receiving new requests for more work from a FOP module before all FOP modules have work to do. The second modification introduces bigger buffers as the number of available FOP modules grows, which allows the Broker to deal with all FOP modules without making them wait due to concurrent messages. Both modifications help to improve the Broker scalability, increasing the lack of time between the reception of buffers with rendered content from the FOP modules. FOP modules remain idle until they receive a XSL-FO buffer and start to render its content. When the render is completed, each FOP module sends back to the Broker the result indicating that it is now free to receive more work. FOP modules could send results directly to the PPML Receiver, but this operation would double the number of messages sent by each FOP module: one for the Broker, indicating that it has completed its work and another for the PPMLReceiver with the results. Obviously, this is not interesting because FOP modules should remain rendering as long as possible. Once the Broker receives rendered buffers from FOP modules, it then sends the results to the PPMLReceiver. Before, this operation along with the XSL-FOs buffers management created an overhead for the Broker. Now, the Broker can easily deal with all these operations without being the bottleneck of the system, because it is not interrupted frequently to manage the XSL-FO buffers. In the original parallel version, the PPMLReceiver put the rendered FOs in the output file each time a new buffer with results arrived. However, with a larger number of FOP modules running, the PPMLReceiver was overloaded. This fact did not affect the FOP modules, because the communication with the PPMLReceiver was asynchronous. Nevertheless, at the end of all rendering process, a large queue of rendered FOs was formed in the PPMLReceiver waiting to be inserted into the output file. The second optimization improves this procedure. In fact, now the PPMLParser gives an identification for each XSLFO extracted from the input file. The identification helps the PPMLReceiver to avoid a sequential seek in the output file. Plus, while waiting for results and mainly in parallel with the Broker initialization, the PPMLReceiver reads and parses a copy of the input file, storing all the static content in a temporary structure in memory. Each time a buffer with rendered FOs arrives, the operation now consists of locating the right position of the identified FO in memory. As the temporary structure is filled, it is flushed to the output file in parts. This simple procedure saves time and does not require any special component for performing I/O operations in parallel.
4
Experimental Results
The experiments performed to test the improvements proposed in this paper have been carried out in the same environment using the same input data according to the following description. An analysis of the obtained results is done at the end of this section.
An Improved Parallel XSL-FO Rendering for Personalized Documents
4.1
61
Platform
The software platform adopted to implement the solution proposed is composed of the Java Standard Development Kit (J2SDK, version 1.4.2) plus the standard Message Passing Interface (MPI) [10] to provide communication among processes. More specifically, we choose the mpich implementation (version 1.2.6) along with mpiJava [11] (version 1.2.5) which is an object-oriented Java interface to the standard MPI. The experiments were carried out over processors running Linux. The target hardware platform is a multi-computer composed of 14 AMD Opteron 2.4 Ghz nodes, each one with 8GB RAM and connected through a 1 Gb network. 4.2
Input Data
PPML files may appear in a large variety of layouts presenting different number of pages, XSL-FOs and amount of content to be rendered. The size in bytes of a PPML file content is directly related to the computational cost of its rendering. The test cases presented in this section have their layouts as close as possible to the input files used in [1]. However, all test cases used in this work are composed of 20,000 documents. The amount of documents was substantially increased in order to take advantage of the higher computational power offered by the hardware platform aiming to stress the scalability of the improved parallel FOP. The characteristics of these input files are summarized in Tab. 1. Table 1. Summary of the test cases
File Label Pages XSL-FOs Size (Mb) Sequential Time (s) Earth 2 6 160 2,800.77 Fire 2 4 105 2,283.25 Wind 2 8 273 6,285.98
The first input PPML file (Fire) is the smallest test case. The amount of the variable content to be rendered is around 105 MB and each of its documents has 2 pages: the first page has only one XSL-FO and the second has 3 XSL-FOs. The second test case (Earth) is also composed of 2 pages, each one of them with 3 XSL-FOs. This file has 160 MB of variable content to be rendered. Finally, the last input file (Wind) also has 2 pages configured as follows: the first one has 3 XSL-FOs and the second one 5 XSL-FOs. It is the largest PPML file, having 273 MB of variable content. 4.3
Results Analysis
The results presented in this section were obtained through a mean of 10 executions discarding the lowest and the highest times. This procedure is required in order to minimize the influence of environment fluctuations in the final results. Comparing the sequential times in Tab. 1 with the results in Fig. 2, one can observe the performance gains achieved by the improved parallel FOP. It
62
L.G. Fernandes et al.
is important to notice that the parallel FOP needs at least 4 processors to be executed, one for each module described in Sec. 3. That is the reason why there are no execution times for configurations with 2 and 3 processors. The execution with 5 processors means that there were 2 FOP modules running, 6 processors means 3 FOP modules and so on. As expected, the 4 processors execution has a better performance than the sequential version, even though it has just one process rendering. This happens because there are now time intersections between the parse of the input file, the rendering process and the writing of the output file. Execution Time Earth 20,000 documents Fire 20,000 documents Wind 20,000 documents
2000 1800 1600
time (sec)
1400 1200 1000 800 600 400 200 3
4
5
6
7
8
9
10
11
12
13
14
number of processors
T S T Fire S T Wind S
Earth
number of processors 4 5 6 7 8 9 10 11 12 13 941.51 625.56 507.99 460.46 417.81 389.51 376.61 354.58 345.49 338.73 2.98 4.78 5.51 6.08 6.70 7.19 7.44 7.89 8.11 8.27 639.98 476.02 385.88 336.37 302.66 282.90 276.43 260.75 258.26 251.95 3.57 4.79 5.92 6.78 7.54 8.07 8.26 8.75 8.84 9.06 2,013.39 1,307.33 1,092.30 969.71 902.99 836.94 805.70 776.85 748.33 735.11 3.12 4.81 5.75 6.48 6.96 7.51 7.80 8.09 8.40 8.55
Fig. 2. Results: execution time (T, in seconds) and speedup (S)
5
Conclusions
The results presented in this work indicate that it is possible to achieve promising results rendering XSL-FO personalized documents using the message passing paradigm over a multi-computer. In this improved parallel version of the one introduced by the authors in a previous work [1], the FOP tool was optimized to allow the rendering of larger input jobs (20,000 documents). In the largest input case, it was possible to decrease the execution time from 6,285.98 to 735.11 seconds over 13 processors without using a prohibitive cost hardware platform.
An Improved Parallel XSL-FO Rendering for Personalized Documents
63
Despite the results obtained so far, it is the authors’ opinion that there are still others improvements which can be added to the parallel FOP in order to achieve higher performance gains. One potential research line is to forward the analysis of the PPML template content in order to previously identify characteristics of the input documents. In this scenario, a smarter version of the parallel FOP would be capable to take advantage of this information to automatically configure itself aiming the best possible performance.
References 1. Giannetti, F., Fernandes, L.G., Timmers, R., Nunes, T., Raeder, M., Castro, M.: High performance XSL-FO rendering for variable data printing. In: ACM Symposium on Applied Computing, Dijon, France, pp. 811–817. ACM Press, New York (2006) 2. Davis, P., de Bronkart, D.: PPML (Personalized Print Markup Language). In: Proceedings of the XML Europe 2000, Paris, France, International Digital Enterprise Alliance (2000) 3. XSL-FO: The Extensible Stylesheet Language Family. section XSL Formatting Objects April 26th, 2007 Extracted from http://www.w3.org/Style/{X}{S}{L} 4. XML: Extensible Markup Language April 26th, 2007 Extracted from http://www.w3.org/{X}{M}{L} 5. PODi: Print on Demand Initiative April 26th, 2007 Extracted from http://www.podi.org/ 6. Bosschere, D.D.: Book ticket files & imposition templates for variable data printing fundamentals for PPML. In: Proceedings of the XML Europe 2000, Paris, France, International Digital Enterprise Alliance (2000) 7. W3C: The World Wide Web Consortium April 26th, 2007 Extracted from http://www.w3.org/ 8. XSL-T: XSL-Transformations section References April 26th, 2007 Extracted from http://www.w3.org/TR/1999/REC-xslt-19991116 9. FOP: Formatting Objects Processor April 26th, 2007 Extracted from http://xml.apache.org/fop/ 10. Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J.: MPI: the complete reference. MIT Press, Cambridge (1996) 11. mpiJava: The mpiJava Home Page April 26th, 2007 Extracted from http://www.hpjava.org/mpiJava.html
An Extensible Framework for Distributed Testing of MPI Implementations Joshua Hursey1 , Ethan Mallove2 , Jeffrey M. Squyres3 , and Andrew Lumsdaine1 1
Indiana University Open Systems Laboratory Bloomington, IN USA {jjhursey,lums}@osl.iu.edu 2 Sun Microsystems, Inc. Burlington, MA USA
[email protected] 3 Cisco, Inc. San Jose, CA USA
[email protected]
Abstract. Complex code bases require continual testing to ensure that both new development and routine maintenance do not create unintended side effects. Automation of regression testing is a common mechanism to ensure consistency, accuracy, and repeatability of results. The MPI Testing Tool (MTT) is a flexible framework specifically designed for testing MPI implementations across multiple organizations and environments. The MTT offers a unique combination of features not available in any individual testing framework, including a built-in multiplicative effect for creating and running tests, historical correctness and performance analysis, and support for multiple cluster resource managers.
1
Introduction
High quality MPI implementations are software packages so large and complex that automated testing is required to effectively develop and maintain them. Performance is just as important as correctness in MPI implementations, and therefore must be an integral part of the regression testing assessment. However, the number of individual tests taken in combination with portability requirements, scalability needs, and runtime parameters generates an enormous set of testing dimensions. The resulting testing space is so large that no single organization can fully test an MPI implementation. Therefore, a testing framework suitable for MPI implementations must be able to combine testing results from multiple organizations to generate a complete view of the testing coverage. Many MPI test suites and benchmarks already exist that can verify the correctness and performance of an MPI implementation. Additionally, MPI implementation projects tend to have their own internal collection of tests. However, running a large set of tests manually on a regular basis is problematic; human error and changing underlying environments will cause repeatability issues. A good method for regression testing in large software projects is to incorporate automated testing and reporting, run on a regular basis. Abstractly, a testing framework is required to: obtain and build the software to test; obtain F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 64–72, 2007. c Springer-Verlag Berlin Heidelberg 2007
An Extensible Framework for Distributed Testing of MPI Implementations
65
and build individual tests; run all tests variations; and report both detailed and aggregated testing results. Additionally, since the High Performance Computing (HPC) community produces open source implementations of MPI that include contributions from many different organizations, MPI implementation testing methodology and technology must also: – Be freely available to minimize the deployment cost. – Easily incorporate thousands of existing MPI tests. – Support simultaneous distributed testing across multiple sites, including operating behind organizational security boundaries (e.g., firewalls). – Support on-demand reporting, specialization, and email reports. – Support execution of parallel tests, and therefore also support a variety of cluster resource managers. We have therefore created the MPI Testing Tool (MTT), an MPI implementation-agnostic testing tool to satisfy these needs, and have prototyped its use in the Open MPI project [1]. The rest of this paper is organized as follows: related work is presented in Section 2. Section 3 describes the MPI Testing Tool (MTT) in more detail. Section 4 presents MTT experiences with the Open MPI project. Finally, we present conclusions and a selection of future work items in Section 5.
2
Related Work
There is a large field of research surrounding optimal testing techniques, but only a few of those ideas seem to have any impact on the software engineering process used to develop and maintain large software systems [2,3]. To maintain the high quality of large software systems, continual regression testing is required. Onoma et al. [4] describe vital components of an effective software testing suite. The MTT is designed to satisfy these requirements for MPI implementations. TET [5] is a widely adopted tool among hundreds of free and open source testing frameworks. However, TET does not provide mechanisms for obtaining the software to be tested, therefore requiring an additional layer of software to determine whether new versions are available to prevent duplicate testing results. TET also has a crude reporting mechanism which requires searching through flat file logs for test results. Although logs can be exported to a database for historical data mining, no front-end is provided for querying the test results. Perfbase [6] presents a front-end to a SQL database for storing historical performance data. Perfbase does not provide a framework for obtaining, building, and testing software, but rather focuses on archiving and querying test results. Although the first generation of MTT used Perfbase as a back-end data store, MTT evolved its own data store mechanisms due to inflexibility of Perfbase’s storage and retrieval model. DejaGNU [7] is a testing framework from which testing harnesses and suites can be derived. Similar to TET, no rich reporting mechanisms are provided, and native support for parallelism is not included. DejaGNU also requires individualized test suite scripts for each test conducted.
66
J. Hursey et al.
Many other testing harnesses are available, including Kitware’s Dart system, the Boost C++ regression testing system, Mozilla Tinderbox and Testopia, and the buildbot project. However, none of the products and projects surveyed met the full set of requirements needed for testing MPI implementations in a distributed, scalable fashion.
3
The MPI Testing Tool (MTT)
The MTT was created to solve many of the issues cited above. At its core, the MTT is a testing engine that executes the following phases: 1. MPI Get: Obtain MPI implementations. Implementations are obtained from the Internet (via HTTP/S, FTP, Subversion), local copies (e.g., tarball or directory), or by reference to a working installation. 2. MPI Install: Specify how to build/install MPI implementations. 3. Test Get: Obtain test suite source codes, similar to the MPI Get phase. 4. Test Build: Compile test suites against all successfully installed MPI implementations. 5. Test Run: Run individual tests in each successfully built test suite. The MPI Install, Test Build, and Test Run phase results are stored in a central database (or other user specified mechanism). All MTT tests will generate one of four possible results: pass, fail, timeout, or skip. Each test defines specific criteria indicating success. For example, an MPI implementation must compile and install successfully to qualify as “pass.” A test is “failed” if the test completes but the “pass” criteria is not met. A test is killed and declared a “timeout” if its execution did not finish within the allotted time period. A test is declared “skip” if it elects not to run. For example, an InfiniBand-specific test may opt to be skipped if there are no InfiniBand networks available. Phases are templates which allow multiple executions of each step based on parametrization. Later phases are combined with all successful invocations of prior phase invocations, creating a natural multiplicative effect. – M : MPI implementations – I: MPI installations, each of which are applied against all M MPI implementations. – Nt : Individual tests, grouped by test suite (t), each of which is compiled against all (M × I) MPI installations. – Rt : Run parameters specified for tests, each of which is applied against (M × I × Nt ) tests. Fig. 1 shows the general sequence of the phases as well as their relationships to each other and the natural multiplicative effect. The figure shows one MPI implementation that is installed two different ways (e.g., with two different compiler suites). Each installation is then used to build two tests; each test is run
An Extensible Framework for Distributed Testing of MPI Implementations
MPI #1
MPI Get
Configuration #1 Configuration #2
MPI Install Reporter
67
Netpipe Intel Tests
Test Get
Test Build Test Run Reporter
Fig. 1. MTT phase relationship diagram. Phases labeled with “Reporter” contain tests that are saved to a back-end data store such as a database.
two different ways. Hence, the total number of reported tests will follow the equation: num M P I installs + num test builds + num test runs (M × I) + (M × I × Nt ) + (M × I × Nt × Rt ) Therefore Fig. 1 shows a total of 14 tests (2 MPI installs + 4 test builds + 8 test runs). While the multiplicative effect is a deliberate design decision, users must be careful to not create test sets that incur prohibitively long run times. 3.1
Configuration
The MTT test engine is configured by an INI-style text file specified on the command line. In the INI file format, sections are denoted with strings inside brackets and parameters are specified as key = value pairs. Fig. 2 shows a sample fragment of an MTT INI configuration file. A typical configuration file contains a global parameters section, one or more MPI Details sections, and one or more sections for each of the execution phases. The global parameters section is used to specify testing parameters and user preferences across an entire run of the MTT. MPI Details sections specify how to run executables for a specific MPI. For example, these sections contain nuances such as whether mpirun or mpiexec should be used, what command line options to use, etc. Each execution phase will also be specified by at least one section in the configuration file. The phase INI sections are comprised of phase-specific parameters, the designation of a plugin module to use, and module-specific parameters. Fig. 2 shows an INI file example that downloads two different versions of Open MPI detailed in the MPI Get phases and compiles both of them with two different compilers (GNU, Intel) detailed in the two MPI Install phases. Any number of MPI implementations can be specified for download in MPI Get sections. Since each MPI Get section will potentially download a different MPI implementation (and therefore require a different installation process), MPI Install sections must specify which MPI Get section(s) to install. Phases are linked together in the configuration file by back-referencing one or more prior phase names. For example, lines 10 and 14 in Fig. 2 show the two MPI Install sections back-referencing the “Open MPI nightly trunk” and “Open
68
1 2 3
J. Hursey et al. [MPI Get: Open MPI nightly trunk] module = SVN svn url = http://svn.open−mpi.org/svn/ompi/trunk
4 5 6 7
[MPI Get: Open MPI v1.2 snapshots] module = OMPI Snapshot ompi snapshot url = http://www.open−mpi.org/nightly/v1.2
8 9 10 11
[MPI Install: GNU compilers] mpi get = Open MPI nightly trunk,Open MPI v1.2 snapshots module = OMPI
12 13 14 15 16
[MPI Install: Intel compilers] mpi get = Open MPI nightly trunk,Open MPI v1.2 snapshots module = OMPI ompi configure arguments = CC=icc CXX=icpc F77=ifort FC=ifort CFLAGS=−g
17 18 19 20
[MPI Details: Open MPI] exec = mpirun −−mca btl self,&enumerate(‘‘tcp’’, ‘‘openib’’) \ −np &test np() &test executable()
Fig. 2. Fragment of a simplified MTT configuration file. Two MPI Get phases are paired with two MPI Install phases, resulting in four MPI installations. The MPI EAM: template is not listed as a verb on dictionary.com, but oh well :) Details section templates an execution command for invoking MPI tests. This example shows at least two executions for each test: one each for TCP and OpenFabrics networks.
MPI v1.2 snapshots” MPI Get sections. Hence, these two MPI Install sections will be used to install both MPI Get sections. Similar back-referencing mechanisms are used for the other phases. MTT will conditionally execute phases based on the outcome of prior phases. For example, the MPI Install phase is only executed in the case where the prior execution of the corresponding MPI Get phase was both successful and yielded a new version of the MPI implementation (unless otherwise specified). Similarly, Test Run sections will only execute tests where all prior phases were successful: a new MPI implementation was obtained and successfully installed, and tests were successfully obtained and compiled against the MPI installation. 3.2
Funclets
Additional combinations of testing parameters can be specified via “funclets” in the configuration file. “Funclets” are Perl-like function invocations that provide both conditional logic and and text expansion capabilities in the configuration file, enabling it to serve as a template that is applicable to a variety of different scenarios. A common use of funclets is to expand a configuration parameter to be an array of values. For example, the np parameter in Test Run sections specifies how many processes to run in the test. np can be set to one or more integer values.
An Extensible Framework for Distributed Testing of MPI Implementations
69
The following example assigns an array of values to the np parameter by using three funclets: np = &pow(2, 0, &log(2, &env_max_procs())) – &env max procs(): Returns the maximum number of processes allowed in this environment (e.g., number of processors available in a SLURM or Torque job, the number of hosts in a hostfile, etc.). – &log(): Returns the log of the first parameter to the second parameter. – &pow(): Returns an array of integer values. The first parameter is the base, the second and third parameters are the minimum and maximum exponents, respectively. In the above example, when running in a SLURM job of 32 processors, np would be assigned an array containing the values 2, 4, 8, 16, and 32. This causes the MTT execution engine to run each test multiple times: one for each value in the array. 3.3
Test Specification
The MTT supports adding tests in a modular and extensible manner. The procedures to obtain and build test suites (or individual tests) are specified in the configuration file. Although the MTT can execute arbitrary shell commands from the configuration file to build test suites, complex build scenarios are typically better performed via MTT plugin modules. Tests to run are also specified in the configuration file; the MTT provides fine-grained control over grouping of tests, pass/fail conditions, timeout values, and other run-time attributes. 3.4
Test Execution
The MPI Details section tells the MTT how to run an executable with a particular MPI implementation. Each MPI Get section forward-references an MPI Details section that describes how to run executables for that MPI. This feature allows the MTT to be MPI-implementation-agnostic. For example, line 18 inFig. 2 shows an MPI Details section for Open MPI. The exec parameter provides a command line template to run tests. The funclets &test np() and &test executable() are available to “paste in” the values specific to the individual test being invoked. Note, too, the use of the &enumerate() funclet. This funclet will return an array of all of the values passed as parameters, effectively causing the exec parameter to expand into at least two mpirun command lines: one with the string “--mca btl self,tcp” and another with the string “--mca btl self,openib” (forcing Open MPI to use the TCP and OpenFabrics network transports, respectively). Combining the use of multiple funclets can result in a multiplicative effect. For example, using the same 32 processor SLURM job and funclet-driven np value from Section 3.2, the exec parameter from Fig. 2 will expand to invoke ten command lines for each test: five with the TCP transport (with 2, 4, 8, 16, and 32 processes), and five with the OpenFabrics transport.
70
3.5
J. Hursey et al.
Reporting Testing Results
Fig. 1 illustrates that the Reporter phase is run after the MPI Install, Test Build, and Test Run phases. The Reporter phase writes testing results to a back-end data store such as a central database, but may also log information to local text files (or a terminal). The MTT features a web interface to the central database to facilitate complex interactive explorations of the testing data, including comparisons of performance and correctness over multiple versions of an MPI implementation. The web interface is specifically designed to aggregate the testing results into high level summary reports that can be used to repetitively narrow searches in order to find specific data points. Such “drill down” methods are commonly used to aid in discovering trends in test failures, displaying historical performance results, comparing results between different configurations, etc. Additionally the web-based reporter interface provides custom stored queries, allowing developers to easily share views of the testing data. Absolute and relative date range reports are useful when citing a specific testing result and tracking its progress over time, respectively.
4
Case Study: The Open MPI Project
The Open MPI project relies on the MTT for daily correctness and performance regression testing. Open MPI is a portable implementation of the MPI standard that can run in a wide variety of environments; testing it entails traversing a complex parameter space due to the enormous number of possible environments, networks, configurations, and run-time tunable parameters supported. The enormous parameter space, in combination with limited available testing resources, prevents any one member organization from achieving complete code coverage in their testing. By running the MTT at each Open MPI member organization, the project effectively pools the resources of all members and is able to achieve an adequate level of testing code coverage. This scheme naturally allows each organization to test only the specific configurations that are important to their goals. Member testing resources range from small to large collections of machines; unscheduled and scheduled environments; with and without firewall restrictions. Each organization has their own site-specific MTT configuration files that detail exactly which scenarios and environments to test. The Open MPI project has two distinct testing schedules (weekday for “short” 24-hour testing, and weekend for longer / higher process count testing); both follow the same general format: Open MPI snapshot tarballs are generated from the Open MPI Subversion development trunk and release branches and are posted on the Open MPI website. Member organizations use the MTT to download and test the snapshots on their local testing resources. Several well-known MPI test suites are run against Open MPI via the MTT, including the Intel MPI test suite, the LAM/IBM MPI test suite, the Notre
An Extensible Framework for Distributed Testing of MPI Implementations
71
Dame C++ MPI test suite, the Intel MPI Benchmarks (IMB), NetPIPE, etc. Many tests internal to the Open MPI project are also run via the MTT. As each member’s testing completes, results are uploaded to a central database hosted by Indiana University and made available through the MTT’s web-based reporter interface. On weekdays, rollup summary reports are e-mailed to the Open MPI development team 12 and 24 hours after the daily cycle begins. Summary reports of weekend-long testing are sent on Monday morning. The e-mail reports, combined with detailed drill-down queries, form the basis of daily discussions among developers, corrections and modifications to recent changes, and decisions about release schedules. Using the MTT, the Open MPI project has accumulated over 7 million test results between November 2006 and May 2007. Approximately 100,000 tests are run each weekday/weekend cycle, spanning six platforms, six compiler suites, and seven network transports.
5
Conclusions
The MTT successfully supports the active development of the Open MPI project providing correctness and performance regression testing. The MTT provides a full suite of functionality useful in the automated routine testing required of a high quality MPI implementation. By fully automating the testing process, developers spend more time developing software than routinely testing it. Although this paper has focused on the MTT’s testing of Open MPI, the MTT is MPI implementation agnostic, and has been used to test other MPI implementations, such as LAM/MPI [8] and MPICH2 [9]. The MTT is available at: http://www.open-mpi.org/projects/mtt/ 5.1
Future Work
While the MTT currently supports many modes of operation, there are several areas where its support could be expanded, including: supporting testing in heterogeneous environments, supporting complex “disconnected” scenarios for environments not directly (or even indirectly) connected to the Internet, exploiting the natural parallelism exhibited by orthogonal steps within the MTT testing cycle to make more efficient use of testing resources, and expanding the MTT to support general middleware testing.
References 1. Gabriel, E., et al.: Open MPI: Goals, concept, and design of a next generation MPI implementation. In: Proceedings, 11th European PVM/MPI Users’ Group Meeting, Budapest, Hungary, pp. 97–104 (2004) 2. Osterweil, L.: Strategic directions in software quality. ACM Comput. Surv. 28(4), 738–750 (1996) 3. Harrold, M.J.: Testing: a roadmap. In: ICSE ’00: Proceedings of the Conference on The Future of Software Engineering, pp. 61–72. ACM Press, New York (2000)
72
J. Hursey et al.
4. Onoma, A.K., Tsai, W.T., Poonawala, M., Suganuma, H.: Regression testing in an industrial environment. Commun. ACM 41(5), 81–86 (1998) 5. TET Team: TETware white paper. Technical report, The Open Group (2005), http://tetworks.opengroup.org/Wpapers/TETwareWhitePaper.htm 6. Worringen, J.: Experiment management and analysis with perfbase. In: IEEE Cluster Computing 2005, pp. 1–11. IEEE Computer Society Press, Los Alamitos (2005) 7. Free Software Foundation: DejaGnu (2006), http://www.gnu.org/software/dejagnu/ 8. Squyres, J.M., Lumsdaine, A.: A Component Architecture for LAM/MPI. In: Dongarra, J.J., Laforenza, D., Orlando, S. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 2840, pp. 379–387. Springer, Heidelberg (2003) 9. Gropp, W., Lusk, E., Doss, N., Skjellum, A.: A high-performance, portable implementation of the MPI message passing interface standard. Parallel Computing 22(6), 789–828 (1996)
A Virtual Test Environment for MPI Development: Quick Answers to Many Small Questions Wolfgang Schnerring, Christian Kauhaus, and Dietmar Fey Lehrstuhl f¨ ur Rechnerarchitektur und -kommunikation, Institut f¨ ur Informatik, Friedrich-Schiller-Universit¨ at, 07737 Jena, Germany {wosc,kauhaus,fey}@cs.uni-jena.de
Abstract. MPI implementations are faced with growingly complex network configurations containing multiple network interfaces per node, NAT, or dual stacks. To implement handling logic correctly, thorough testing is necessary. However, the cost of providing such diverse setups in real hardware is prohibitively high, resulting in a lack of testing. In this article, we present a Virtual Test Environment (VTE) that considerably lowers this barrier by providing complex network environments on a single computer and thus enables testing in situations where it otherwise would not be feasible.
1
Introduction
As today’s cluster computers become more and more sophisticated, complex network setups are increasingly common. Of course, application writers do not want to be bothered with network topology and expect their MPI implementation to cover the details. In consequence, nearly any modern MPI library contains nontrivial amounts of logic to perform the initial wire-up: starting daemons, querying addresses, selecting network interfaces, etc. To implement wire-up logic code properly, frequent and thorough testing is necessary. During the development of our IPv6 extension to Open MPI [1], we ran into the problem of verifying correct behaviour on configurations like clusters with multiple networks, multi-domain clusters using both private and public IPv4 addressing, mixed IPv4/IPv6 environments, and others. The cost of providing such setups was prohibitively high, resulting in a lack of testing and, in consequence, undiscovered bugs. To remedy this problem, we present a Virtual Test Environment 1 that lowers the testing effort significantly, so that the execution of some classes of functional tests becomes practicable at all. Additionally, it is lightweight enough to facilitate a rapid feedback cycle during development. VTE builds virtual clusters on the developer’s workstation from high-level descriptions by employing kernel virtualisation. The Unit Under Test (UUT), e. g., a MPI implementation, is exercised in a variety of network setups. Although VTE was created to facilitate 1
The software can be obtained from http://www2.informatik.uni-jena.de/cmc/vte/.
F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 73–80, 2007. c Springer-Verlag Berlin Heidelberg 2007
74
W. Schnerring, C. Kauhaus, and D. Fey
the development of our IPv6 extension to Open MPI, it is not constrained to this task. In fact, VTE is useful for the development of any distributed application which interacts with a TCP/IP network environment. This paper is organised as follows. Section 2 explains the design and implementation of VTE. Section 3 illustrates the capabilities of VTE using real-world examples. Section 4 concludes and outlines VTE’s further development.
2
Design and Implementation
The aim of VTE is to lower the cost associated with the testing process. As VTE has been specifically designed to reflect this goal, we have made several architectural decisions. We first give an overview over those decisions, and then present them in more detail. First, VTE needs a concise description language for test networks. If it is too difficult to specify the test setup (e. g., spending a day in the machine room installing cables), the developer is very likely to skip testing. Second, tests should run quickly. If tests take longer than a few minutes, it is too tedious to test frequently. Third, the test environment should be transparent to the UUT, requiring no test-specific modifications. But the test environment should not be transparent to the developer, providing him with effective control and inspection devices. Fourth, the test environment should be able to model complex network configurations to be representative of most cluster environments seen today. Related to our work are MLN [2], an administration tool for virtual machines that allows a declarative description, and Xen-OSCAR [3], a virtualisation-based tool to test cluster installation processes. Unfortunately, both are not fit for MPI implementation testing, since they are not optimised for short running time and provide no means to reconfigure the network during runtime. 2.1
Concise Description of Network Configurations
To provide the developer with concise means of specifying tests, we designed a domain-specific language to describe network configurations. The virtual network can be built out of components like host and switch, which model physical devices, but do more than their real-world counterparts. For example, when connecting VMs with a switch, they are assigned IP addresses automatically. To enable for such concise expression, VTE is implemented in Ruby, a language that allows to express facts on a very high, abstract level. Configurations are executable Ruby programs that specify all necessary information to create virtual machines and networks. While executing a network description, VTE both builds internal data structures describing the configuration and interacts with the host system through shell commands to realise those structures. Thus, specifying cluster = Cluster.new(16) switch = Switch.new(”192.168.5.0/24”).connect(cluster.vm)
A Virtual Test Environment for MPI Development
75
configures a virtual cluster with 16 nodes that are connected through a switch and have IP addresses from the subnet 192.168.5.0/24. This example shows some of the most important language elements. The Cluster class governs a set of virtual machines. With Cluster.new, virtual machines are booted and the Cluster.vm accessor provides references to all running VMs. After startup, VMs do not have a network connection. A virtual network is created using Switch.new, which also causes VTE to create the supporting operating system structures (see 2.4). The Switch.connect method creates network interfaces, allocates IP addresses, and creates the connections. More configuration language elements are documented in the API reference. We designed the configuration language to use sensible defaults, while allowing exceptions to be specified if desired. If the network above was not given explicitly but rather just as the type (using Switch.new(:ipv4)), a suitable IPv4 address range would be allocated automatically. 2.2
Fast Execution
To run fast, VTE requires a lightweight virtualisation technology, since the main overhead stems from running virtual machines. The “smallest” form of virtualisation is kernel-based virtualisation [4], which merely creates a compartment inside the running kernel to isolate processes of one VM from those of other VMs. We have chosen OpenVZ [5] since it is the most mature of the freely available kernel-based virtualisers for Linux and offers thorough network support. Kernel-based virtualisation allows for rapid creation of virtual machines, since creating a VM mostly consists of spawning another init process and a few required daemons, for example sshd, reusing the already running kernel. This also means that VMs are not able to use a different operating system than the one which is already present, but since VTE focuses on complex network configurations, heterogeneous operating systems are not a primary concern. We accelerate the startup process even further by reusing one file system image for all virtual machines: Instead of setting up separate file systems for newly created VMs, only one master file system is mounted repeatedly using copy-on-write semantics. Write operations are diverted to a separate location, while the master file system stays read-only. With this technique, VTE is able to create VMs very quickly: Figure 1 shows the total time required for starting VMs and shutting them down again on an Intel Pentium 4 at 3 GHz with 2 GB RAM running kernel version 2.6.18-ovz028test019. Even 50 VMs take only about a minute, but most tests will not require much more than 10 VMs. Since their startup and shutdown takes only 16 seconds, this presents practically no barrier to frequent testing. OpenVZ is also quite efficient: VTE is capable of simulating a cluster with 300 nodes on the same machine. An MPI ring test then takes about 3 minutes, plus about 8 minutes VM startup and shutdown time. To test the UUT with several network configurations, it should not be necessary to stop the VMs and start them again in a different setup. Therefore, we implemented all virtual network components in a way they can be completely removed and new ones added while the VMs keep running.
76
W. Schnerring, C. Kauhaus, and D. Fey 70 60
Time (s)
50 40 30 20 10 0 0
10
20 30 VM count
40
50
Fig. 1. Time required for startup and shutdown
To bring the UUT into the test environment, it is not necessary to copy it onto all virtual machines. OpenVZ allows to simply mount directories of the host into a VM, which saves a potentially large amount of data transfers. For example, to inject a MPI implementation into the test environment, the developer’s working directory can be mounted, even under the same path as on the host, so the MPI implementation does not notice any difference. 2.3
Semi-transparency
VTE is able to run real software, and it appears as a real cluster to the software running inside it. But the developer has full control over this environment, so VTE could be imagined as a semi-transparent mirror. The test environment can be controlled by executing shell commands inside the virtual machines and examining their output. We implemented running shell commands using OpenVZ’s vzctl exec mechanism. An alternative would be to inject commands into VMs using ssh calls via a virtual service network, which would of course influence the network setup. This way, however, VTE can be configured exactly as required for the tests—even completely without a network. Since the virtual machines export their network interfaces to the host, network sniffers or any other tools can be run on the host to examine traffic on the virtual network. VTE provides a self-contained environment. Its only external dependencies are OpenVZ to provide the virtualisation, and root privileges for operations concerning the virtual environment, which are encapsulated in sudo calls. 2.4
Complex Network Configuration
To be able to test the behaviour of MPI implementations even for complicated cases, VTE should model fairly complex network environments. We limited the network support to TCP/IP though, favouring simplicity and conciseness of the configuration language over heterogeneous network families. Figure 2 shows an example setup where two clusters are connected via a router. VTE constructs this virtual network on the host, since the network interfaces of
A Virtual Test Environment for MPI Development
77
Fig. 2. Example network configuration
the virtual machines are easily accessible from there. Switches are implemented by using standard Linux bridge−utils to create virtual bridges that connect the network interfaces of the VMs. Since the bridges can serve a dual purpose and function as network interfaces of the host, the host itself can also be connected to a virtual switch if desired. We use this to implement a router using the host’s routing table. Network Address Translation (NAT) is also performed on the host via iptables. Thus, virtual network components can be combined to model multi-cluster setups, multi-link connections (e. g. channel bonding), dual stack (IPv4/IPv6) networks, and other configurations.
3
Examples
To show the ease of use that VTE offers for specifying and running tests, we examine the behaviour of MPI implementations that occurred to us during our day-to-day development work to show how VTE can help preventing this kind of problems by facilitating regular testing. 3.1
Striping
If there are multiple network paths between any two nodes, Open MPI optionally uses striping to maximise throughput. With striping, Open MPI fragments big messages and sends them in parallel through several interfaces. VTE allows for each VM to have multiple network interfaces, for example by specifying an interface number when connecting VMs with a switch: cluster = Cluster.new(2) Switch.new(:ipv4).connect(cluster.vm, 0) Switch.new(:ipv4).connect(cluster.vm, 1)
In this example, each VM will be configured with two network interfaces, eth0 and eth1. Running the ping-pong benchmark from the Intel MPI Benchmark Suite (IMB) 3.0 shows that once the payload is large enough, Open MPI will use striping to distribute the traffic over all available interfaces. The tcpdump output shows connections on both switches.
78
W. Schnerring, C. Kauhaus, and D. Fey
# tcpdump −i sw1 IP 1.0.0.2.56003 > 1.0.0.3.33364 IP 1.0.0.3.33364 > 1.0.0.2.56003 # tcpdump −i sw2 IP 2.0.0.2.54115 > 2.0.0.3.59036 IP 2.0.0.3.59036 > 2.0.0.2.54115
3.2
NAT
Many clusters use private IPv4 addresses for their nodes, which connect to the outside world using a NAT gateway. Combining two clusters of this kind to a multi-cluster is not possible, since the private addresses of one cluster are not reachable from the other. MPI implementations should detect this erroneous condition. We examine the behaviour of LAM/MPI and Open MPI using VTE. Two clusters with 3 nodes each that use private IPv4 addresses and are connected with NAT (see Figure 2) can be modelled like this: cluster1 = Cluster.new(3) cluster2 = Cluster.new(3) switch1 = Switch.new(”192.168.5.0/24”).connect(cluster1.vm) switch2 = Switch.new(”192.168.6.0/24”).connect(cluster2.vm) router = Router.new.connect(switch1, nat=true).connect(switch2, nat=true)
LAM/MPI [6] is started with the lamboot command. The required host file is automatically constructed by concatenating the host names of all VMs. hostnames = (cluster1.vm + cluster2.vm).map { |vm| vm.hostname }.join(”\n”) cluster1.vm[0].cmd(”echo ’#{hostnames}’ > lamhosts”) cluster1.vm[0].cmd(”lamboot lamhosts”) lamboot tries to start LAM’s management daemon lamd on all hosts, but since
some hosts use private addresses and are unreachable, it terminates with an error message: ERROR: LAM/MPI unexpectedly received the following on stderr: ssh: connect to host vm3 port 22: Network is unreachable
Open MPI [7] starts its daemon orted implicitly when mpirun is called. hostnames = (cluster1.vm + cluster2.vm).map { |vm| vm.hostname }.join(”,”) cluster1.vm[0].cmd(”mpirun −np #{cluster.vm.size} −host #{hostnames} ./ringtest”)
Open MPI also fails to contact some hosts, but instead of terminating it hangs until VTE’s timeout kills it: ssh: connect to host vm3 port 22: Network is unreachable [vm0:21702] ERROR: A daemon on node vm3 failed to start as expected. [vm0:21702] ERROR: There may be more information available from [vm0:21702] ERROR: the remote shell (see above). Timeout: aborting command ”vzctl” with signal 9
The problem is that after Open MPI notices the error, it terminates by telling orted on all hosts to shut down—including those hosts that it was unable to
A Virtual Test Environment for MPI Development
79
connect in the first place. Since these hosts never return a “shutdown successful” notification, the process keeps waiting for them forever. 3.3
Installation Prefix
If Open MPI is installed below a different path than the prefix specified at compile time, it is unable to find its binaries and libraries. One method of explicitly specifying installation locations is to use application context files. The manual page for mpirun states that “[. . . ] --prefix can be set on a per-context basis, allowing for different values for different nodes.” With VTE, two nodes with different Open MPI installation locations can be described as follows: cluster = Cluster.new(2) switch = Switch.new(:ipv4).connect(cluster.vm) cluster.vm[0].mount(”/real/path/to/openmpi”, ”/usr/local/openmpi”) cluster.vm[1].mount(”/real/path/to/openmpi”, ”/opt/openmpi”) cluster.vm[0].cmd(”echo ’#{<< EOT }’ > appfile”) −np 1 −host vm0 −−prefix /usr/local/openmpi hostname −np 1 −host vm1 −−prefix /opt/openmpi hostname EOT cluster.vm[0].cmd(”mpirun −−appfile appfile date”)
Unfortunately, the −−prefix settings does not take effect and mpirun fails with /usr/local/openmpi/bin/orted: No such file or directory on vm1 . Perhaps the writing of the manual page proceeded a little bit quicker than the writing of the code. 3.4
Dual-Stack
When migrating to IPv6 [8], it is quite common to have a dual-stack setup, that is both address families on a single interface, connected by the same switch. In VTE an IP subnet is usually represented by a switch, but in this case there is only one switch but two networks. Therefore we have to configure the second set of IP addresses explicitly, using the provided helper functions: cluster = Cluster.new(3) Switch.new(:ipv6).connect(cluster.vm) net = Switch.generate network(:ipv4) cluster.vm.each with index do |v, i| v.configure ipv4(net.nth(i+1)) unless v.hostname short == ”vm1” end Cluster.update hostfile
VTE’s configuration language is plain Ruby, so all normal language constructs are available to the developer. This makes it easy to describe exceptions like “every host has IPv4 except vm1 .” Running a ring test and observing the traffic on the switch with tcpdump shows that Open MPI with our IPv6 extension now opens connections via both IPv4 and IPv6, depending on the connectivity available. vm0 connects to vm2 via IPv4 (1.0.0.1–1.0.0.3), but to vm1 via IPv6 (aa01::1–aa01::2).
80
W. Schnerring, C. Kauhaus, and D. Fey
# tcpdump −i sw1 IP 1.0.0.1.33126 > 1.0.0.3.52353 IP 1.0.0.3.52353 > 1.0.0.1.33126 [...] 2001:638:906:aa01::1.38252 > 2001:638:906:aa01::2.43756 2001:638:906:aa01::2.43756 > 2001:638:906:aa01::1.38252
These examples show some of the VTE’s possibilities to exercise MPI implementations in a variety of environments. The configuration language is expressive enough to formulate even bug-provoking border cases in a compact form.
4
Conclusion
We have presented a Virtual Test Environment that considerably lowers the barrier to functional testing of distributed applications, thereby enabling testing in cases where it were not feasible otherwise, since the costs of physical test setups are too high. VTE has an expressive configuration language for describing complex network environments and short execution times. Being able to run networking tests in just a few minutes allows the developer to establish a close feedback loop, which results in better software quality.
References 1. Kauhaus, C., Knoth, A., Peiselt, T., Fey, D.: Efficient message passing on multiclusters: An IPv6 extension to Open MPI. In: Proceedings of KiCC’07, Chemnitzer Informatik Berichte CSR-07-02 (2007) 2. Begnum, K.M.: Managing large networks of virtual machines. In: Proc. LISA’06: 20th Large Installation System Administration Conference, pp. 205–214. USENIX Association, Washington, D.C (2006) 3. Vall´ee, G., Scott, S.L.: OSCAR testing with Xen. In: Proc. 20th Int. Symp. on HighPerformance Computing in an Advanced Collaborative Environment (HPCS’06), pp. 43–48. IEEE Computer Society, Washington, DC (2006) 4. Soltesz, S., P¨ otzl, H., Fiuczynski, M., Bavier, A., Peterson, L.: Container-based operating system virtualization: A scalable, high-performance alternative to hypervisors. In: Proceedings of EuroSys 2007, Lisbon, Portugal (March 2007) 5. SWSoft: OpenVZ – server virtualization open source project. Accessed on June 27, 2007, http://openvz.org/ 6. Squyres, J.M., Lumsdaine, A.: A Component Architecture for LAM/MPI. In: Dongarra, J.J., Laforenza, D., Orlando, S. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 2840, pp. 379–387. Springer, Heidelberg (2003) 7. Gabriel, E., Fagg, G.E., Bosilca, G.: Open MPI: Goals, concept, and design of a next generation MPI implementation. In: Proceedings, 11th European PVM/MPI Users’ Group Meeting, Budapest, Hungary, pp. 97–104 (2004) 8. Deering, S., Hinden, R.: Internet Protocol, Version 6 (IPv6) Specification. RFC 2460 (Draft Standard) (December 1998)
Multithreaded Tomographic Reconstruction ´ Jos´e Antonio Alvarez, Javier Roca, and Jose Jes´ us Fern´ andez Departamento de Arquitectura de Computadores y Electr´ onica. Universidad de Almer´ıa {jaberme,jroca,jose}@ace.ual.es
Abstract. An option to increase performance in grand-challenge applications is overlap computation and communication. In applications developed using C and MPI, this overlapping is usually left to the programmer, but this is a tedious task. Switching from the process model to a threaded model in the parallel environment via user level threads takes advantage of the existing concurrence in an application. In this paper we expose and analyze our research group’s tomographic reconstruction software developed using AMPI, a user level thread framework that provides a solution to port legacy MPI code into a multithreaded environment where overlapping is achieved. Keywords: User level threads; Parallel iterative reconstruction algorithms; Electron tomography.
1
Introduction
Cluster computing is a cost-effective solution for supercomputing, based on the usage of commodity hardware and standard software components. Parallel applications developed using message passing libraries such as MPI make intensive use of the concept of process as a building block, these applications therefore lack flexibility. Applications based on processes are monolithic computing entities, dulling important capabilities such as awareness of communication latencies because only one control stream is possible per process. Therefore when a process yields due a communication phase there will be no computation associated to that process. Latency hiding is up to the programmer. Multithreaded programming provides a way to divide a program into different flows of control. Moreover using user level threads[1], [2] in places where concurrence can be exploited would allow us to achieve latency hiding, better scalability, skills to avoid overhead on processors due to faster context switching and abilities to migrate threads for load balancing purposes. As opposed to the process monolithic approach, languages based on multithreaded and concurrent constructs allow easily more than one active flow of control within a process. Each active thread has even its own stack area and is executed concurrently under the control of a thread scheduler. Adaptive MPI
Work supported through grants MEC-TIN 2005-00447 and JA-P06-TIC-01426.
F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 81–88, 2007. c Springer-Verlag Berlin Heidelberg 2007
82
´ J.A. Alvarez, J. Roca, and J.J. Fern´ andez
(AMPI) [3] embeds MPI processes into user level threads, a more efficient technique in aspects like context switching, migration of tasks, etc. Our application addresses the tomographic reconstruction problem using iterative methods. These methods are far superior to the standard technique, weighted backprojection, in terms of reconstruction quality [4]. However, they are much more computationally demanding. The capability of representing the density function in the volume by means of basis functions more general than the traditional voxels, is doubtlessly one of their main advantages. Research carried out during the 1990s [5], concluded that spherically symmetric volume elements (blobs) yield better reconstructions than voxels, as assessed in the fields of medicine [6] and electron tomography [4]. As drawbacks blobs lack resources when compared to voxel’s computing needs. In this work, we present and evaluate a parallel implementation of blob-based iterative reconstruction methods using a multithreaded approach with AMPI. The aim is to face the computational demands of these methods by exploiting concurrency and minimizing latency due to message passing. This paper is organized as follows. Next section analyzes the iterative reconstruction techniques. Section 3 describes the user level threads framework and Section 4 exposes how the tomographic reconstruction problem was parallelized based on the AMPI framework. Section 5 analyzes how this threaded implementation behaves when compared with its MPI version, by varying the thread’s population. Finally the conclusions are exposed in last section.
2
Iterative Image Reconstruction
Let f be the function that represents the object to be reconstructed. Series expansion reconstruction methods assume that the 3D object or function, f , can be approximated by a linear combination of a finite set of known and fixed basis functions, bj , with density xj : f (r, θ1 , θ2 ) =
J
xj · bj (r, θ1 , θ2 )
(1)
j=1
where (r, θ1 , θ2 ) are spherical coordinates. The aim is to estimate the unknowns, xj . These methods are based on an image formation model where the measurements depend linearly on the object in such a way that J yi = li,j · xj (2) j=1 th
where yi denotes the i measurement of f and li,j the value of the ith projection of the j th basis function. Under those assumptions, the image reconstruction problem can be modeled as the inverse problem of estimating the xj ’s from the yi ’s by solving the system of linear equations given by Eq. (2). Algebraic reconstruction techniques (ART) constitute one of the best known families of iterative algorithms to solve such systems [6]. The main drawback of iterative methods are their high computational requirements. These demands can be faced by means of
Multithreaded Tomographic Reconstruction
83
parallel computing and efficient reconstruction methods with fast convergence. Component averaging methods (CAV ) have been developed recently [7] as efficient iterative algorithms for solving large and sparse systems of linear equations. In essence, these methods have been derived from ART methods, with the important innovation of a weighting related to the sparsity of the system. This component-related weighting provides the methods with a convergence rate that may be far superior to the ART methods. Assuming that the whole set of equations in the linear system -Eq. (2)- may be subdivided into B blocks each of size S, a generalized version of component averaging methods (BICAV ) can be described via its iterative step from the k th estimate to the (k + 1)th estimate: S yi − Jv=1 li,v xkv k+1 k xj = xj + λk · · J · li,j (3) b 2 s=1 v=1 sv (li,v ) where λk denotes the relaxation parameter; b = (k mod B) and denotes the index of the block; i = bS + s and represents the ith equation of the whole system; and Svb denotes the number of times that the component xv of the volume contributes with nonzero value to the equations in the bth block. The processing of all the equations in one of the blocks produces a new estimate. All blocks are processed in one iteration of the algorithm. This technique produces iterates which converge to a weighted least squares solution of the system of equations provided that the relaxation parameters are within a certain range and the system is consistent [4]. Using higher number of blocks allows faster convergence. Conceptually, block-iterative reconstruction algorithms may be decomposed into three subsequent stages: (i) computation of the forward-projection of the model; (ii) computation of the error between the experimental and the calculated projections; and (iii) refinement of the model by means of backprojection of the error. Aforementioned stages can be easily identified in Eq. (3). Those reconstruction algorithms pass through the stages for every block of equations and for every iteration. 2.1
Data Dependences Basis Functions
In the field of image reconstruction, the choice of the set of basis functions to represent the object to be reconstructed greatly influences the result of the algorithm. Overlapping spherically symmetric volume elements (blobs) with smooth transition to zero have been thoroughly investigated [5] as alternatives to voxels for image representation, concluding that the properties of blobs make them well suited to represent natural structures of all physical sizes. In addition, the use of blobs provides the reconstruction algorithm with an implicit regularization mechanism, very appropriate to work under noisy conditions. A volume can be considered made up of 2D slices. When voxel basis functions are used, the slices are independent. However, the use of the blobs makes slices interdependent because of blob’s overlapping nature. The interdependence depends on the blob extension.
84
´ J.A. Alvarez, J. Roca, and J.J. Fern´ andez
3
User-Level Threads Framework
We have implemented the parallel iterative reconstruction method adapting legacy MPI code into a multithreaded environment by means of Adaptive MPI. AMPI is a virtualized implementation of MPI in which several MPI processes can efficiently share a single processor. This virtualization is achieved by making each traditional MPI process a migratable ”user-level” thread, which can be thought of as a virtual processor [8], [9] (vp from now). AMPI embodies a MPI process within an user level thread. Each thread is now a virtual processor, many AMPI virtual processors can coexist in the same processor. AMPI threads are lightweight and are managed by the Converse runtime [10] and not by OS routines. Typically user level threads are implemented entirely in user’s space. As a result, context switching between user level threads in a process does not require any interaction with the kernel at all and is therefore extremely efficient: a context switch can be performed by locally saving the CPU registers used by the currently executing user level thread and loading the registers required by the user level thread to be executed. Since scheduling occurs in user’s space, the scheduling policy provided by Converse can be easily tailored to the requirements of the program’s workload. In MPI programming, having to block the CPU and wait for communication to complete can result in inefficiency. However, communication between AMPI threads is carried out through asynchronous calls, which do not block the objects involved in the communication. To get this, Converse maintains a couple of special data structures in each processor. One of them is the sent messages table which maintains a list of sent messages that are still pending for delivery, the other data structure is the threads table containing threads waiting for a message. When the processor gets an incoming message, it checks which thread is waiting for it, if any, and activates it. When a thread expresses the intention to receive a message, if the message is not ready, the thread will then be inserted into the threads table and put to sleep, and it will be tagged so that it can be identified and activated as soon as the message arrives.
4
Parallel Iterative Reconstruction Method
The block iterative version of the component averaging methods, BICAV, has been parallelized following the Single Program Multiple Data (SPMD) approach [4]. The volume is decomposed into slabs of slices that will be distributed across the nodes (for MPI) or virtual processors (for AMPI), see Fig.1 right, where slices are sketched with columns. The virtual processors can then process their own data subdomain, however, the interdependence among neighbor slices due to the blob extension makes necessary the inclusion of redundant slices into the slabs (see columns in light gray in Fig.1 right). In addition, there must be a proper exchange of information between neighbor nodes to compute the forwardprojection or the error back-projection for a given slab and to keep redundant slices updated [4] (see Fig.1 left). These communication points constitute synchronization points in every pass of the algorithm in which the nodes must wait
Multithreaded Tomographic Reconstruction
85
Volume Initialization
Forward Projection
Volume Refinement
Compute error with experimental projections Communication of differences Error BackProjection
New Block
Communication of reconstructed slices
New Iteration
Fig. 1. Flow of the iterative reconstruction algorithm (left). Data decomposition (right).
for the neighbors. The amount of communications is proportional to the number of blocks and iterations. In any parallelization project where communication between nodes is involved, latency hiding becomes an issue. That term stands for overlapping communication and computation so as to keep the processor busy while waiting for the communications to be completed. Our improvement proposal is based upon AMPI user level thread’s characteristic, used to achieve such latency hiding [3] by providing computationcommunication overlapping. AMPI user level threads, -which embodies a classical MPI process- can switch from one thread to another when the running thread enters into one of the synchronization points. So while one thread is waiting, another one can take idle cpu cycles to progress with the application. Performance improvement depends on the algorithm used, the underlying network architecture and the system support for the context switching. As aforementioned, reconstruction yields better results when the number of blocks are increased. However, this rises communication needs, thereby prompting a performance loss. Now, with AMPI, each slab is embodied into a thread, so each node will be assigned as many slabs as threads. Communication patterns among neighboring nodes will maintain the same as each node will still communicate the same number of boundary slices in either AMPI or MPI implementations. As a remark, AMPI allows sleeping threads to come into action whenever some communication operation is in process, therefore performance is improved.
5
Results
Two different computing platforms were used to evaluate our reconstruction algorithm. One of the platforms used was NCSA’s Linux cluster, TUNGSTEN, which owns a Dell poweredge 1750 server as front-end with 3GB ECC DDR SDRAM and compute nodes based on the Intel Xeon 3.2 GHz (32 bits), 512 KB L2 Cache and 1MB L3 Cache, all nodes interconnected with 1 Gb Ethernet Myrinet 2000. The second platform was our research group cluster, VERMEER, which owns
86
´ J.A. Alvarez, J. Roca, and J.J. Fern´ andez
as a front-end a dual Pentium IV XEON 3.2 Ghz, 512KB Cache node with Gentoo Linux, Kernel 2.4.32 SMP and two Pentium IV XEON 3.06 Ghz, 512KB L2 Cache per computing node with 2GB of ECC DDR SDRAM, connected via 1Gb Ethernet. We were interested in the gain obtained by the multithreaded implementation with automatic overlapping of computation/communication, compared to the MPI version with the programmed latency hiding technique included. Scaling tests were carried out on both systems varying the number of threads per processor and the number of processors, for both versions AMPI and MPI. Two types of experiments were carried out to assess the performance of our multithreaded approach compared to the MPI implementation. In the first experiment, we aimed to measure the net gain by the implicit latency hiding mechanism provided in the AMPI implementation. This experiment was performed on the Tungsten cluster, using a dataset for a reconstruction of a volume of 256x256x256 from 70 projection images of 256x256 with the BICAV algorithm with a number of blocks of K=70. The number of processors was varied from 1 to 64, and the speedup was computed using (a) one thread per processor and (b) two threads per processor. Fig. 2 clearly shows that the use of two threads per processor allows fully exploitation of the thread concurrency and that the implicit latency hiding succeeds in increasing the speedup, especially as the number of processors increases. The second experiment was intended to quantify the influence of the number of blocks over the global performance. As the number of blocks increases, the convergence of the algorithm is faster, but the amount of communications also increases. This scenario harms the MPI version whereas AMPI is expected to keep good performance. This test was performed on the Vermeer cluster using up to 32 physical processors. Two datasets with different problem sizes were used. First, a dataset for a reconstruction of a volume of 256x256x256 from 256 projection images of 256x256. Second, a dataset for a reconstruction of a volume of 512x512x512 from 512 projection images of 512x512. The BICAV algorithms,
Fig. 2. Speedups obtained for BICAV in Tungsten cluster
Multithreaded Tomographic Reconstruction
87
in MPI and multithread AMPI versions, were executed with the two datasets. Two different numbers of blocks of equations K were used, one of them with the highest number of blocks for convergence purposes in BICAV and the other with an intermediate value. Fig. 3 shows the gain obtained by the multithreaded of BICAV with 128 virtual processors, for two numbers of blocks K and for the two datasets. The speedup curves clearly show that the application implemented with MPI loses the linear speedup when using more than eight processors. However, AMPI keeps speedup almost linear up to 32 processors. Therefore, thread switching succeeds in maintaining the speedup optimal.
Fig. 3. Speedup in Vermeer cluster for 256 volume (left) and 512 volume (right) Table 1. CPU and Wall time differences. Concurrency (k256-512) K 256 (volume 256) MPI AMPI
K 512 (volume 512) MPI AMPI
Procs CPU WALL % CPU WALL % CPU WALL % CPU WALL % 2 4 8 16 32
991 502 251 126 63
1021 2.9 1012 1013 0.1 16749 520 3.5 509 509 0 8432 265 5.6 257 257 0 4222 147 17.1 130 131 0.8 2128 192 62.4 67 68 1.5 1071
17217 8705 4418 2334 1417
2.8 3.2 4.7 9.7 32.3
16989 8479 4251 2138 1092
16988 8481 4263 2154 1094
0.0 0.0 0.3 0.7 0.2
Table 1 presents the relative difference (columns %) among cputime and walltime for both problem sizes. This table shows the cases of the highest communication for both volumes (K=256 and K=512, respectively). It is easy to see how for AMPI walltime and cputime are almost the same, which means that the cpu was mostly in use and not idle. In contrast, the differences from the MPI version may turn out to be significant, especially for increasing number of processors. Taking into account that there are neither I/O operations nor function/method calls apart from those related to the own algorithm, we can conclude that for our multithreaded version for BICAV algorithm the concurrence is therefore seized at maximum.
88
6
´ J.A. Alvarez, J. Roca, and J.J. Fern´ andez
Discussion and Conclusions
We presented a study about how multithreading can exploit latency hiding for grand-challenge applications like BICAV tomographic reconstruction. We based our study on AMPI supported by a powerful runtime called Converse that allows automatic user level thread switching avoiding idle cpu cycles. Through experiments we illustrated how one of our scientific iterative applications (BICAV ) was directly benefited as the difference among cpu and walltime per iteration was nearly zero in contrast to the version based on MPI which did not respond so well. We further analyzed the performance of this technique while varying parameters as the number of physical processors and the population of virtual processors (threads) and we can state that the threaded version of BICAV scaled significantly better than the MPI version. From these experiments we conclude that user level threads are an attractive approach for programming parallel scientific applications, which can be benefited from having multiple flows of control.
References 1. Oikawa, S., Tokuda, H.: Efficient Timing Management for User-Level Real-Time Threads. In: Proceedings of the IEEE Real-Time Technology and Applications Symposium, pp. 27–32. IEEE, Los Alamitos (1995) 2. Price, G.W., Lowenthal, D.K.: A comparative analysis of fine-grain threads packages. Journal of Parallel and Distributed Computing 63, 1050–1063 (2003) 3. Huang, C., Lawlor, O., Kale, L.V.: Adaptive MPI. In: Rauchwerger, L. (ed.) LCPC 2003. LNCS, vol. 2958, pp. 306–322. Springer, Heidelberg (2004) 4. Fern´ andez, J., Lawrence, A.F., Roca, J., Garc´ıa, I., Ellisman, M.H., Carazo, J.M.: High performance electron tomography of complex biological specimens. Journal of Structural Biology 138, 6–20 (2002) 5. Matej, S., Lewitt, R., Herman, G.: Practical considerations for 3-D image reconstruction using spherically symmetric volume elements. IEEE Trans. Med. Imag. 15, 68–78 (1996) 6. Herman, G.: Algebraic reconstruction techniques in medical imaging. In: Leondes, C. (ed.) Medical Imaging. Systems: Techniques and Applications, pp. 1–42. Gordon and Breach, New York (1998) 7. Censor, Y., Gordon, D., Gordon, R.: BICAV: a block-iterative, parallel algorithm for sparse systems with pixel-related weighting. IEEE Trans. Med. Imag. 20, 1050–1060 (2001) 8. Kale, L.V.: The Virtualization Model of Parallel Programming: Runtime Optimizations and the State of Art. In: Los Alamos Computer Science Institute Symposium (LACSI 2002). Alburquerque (2002) 9. Kale, L.V., Lawlor, O.S., Bhandarkar, M.: Parallel Objects: Virtualization and inProcess Components. In: Proceedings of the Workshop on Performance Optimization via High-Level Languages and Libraries (POHLL-02), 16th Annual ACM International Conference on Supercomputing (ICS’02), ACM Press, New York (2002) 10. Bhandarkar, M.A.: Charisma: A Component Architecture for Parallel Programming. PhD thesis, University Illinois at Urbana-Champaign (2002)
Parallelizing Dense Linear Algebra Operations with Task Queues in llc Antonio J. Dorta1 , Jos´e M. Bad´ıa2 , Enrique S. Quintana-Ort´ı2, and Francisco de Sande1 1
Depto. de Estad´ıstica, Investigaci´ on Operativa y Computaci´ on Universidad de La Laguna, 38271–La Laguna, Spain {ajdorta,fsande}@ull.es 2 Depto. de Ingenier´ıa y Ciencia de Computadores Universidad Jaume I, 12.071–Castell´ on, Spain {badia,quintana}@icc.uji.es
Abstract. llc is a language based on C where parallelism is expressed using compiler directives. The llc compiler produces MPI code which can be ported to both shared and distributed memory systems. In this work we focus our attention in the llc implementation of the Workqueuing Model. This model is an extension of the OpenMP standard that allows an elegant implementation of irregular parallelism. We evaluate our approach by comparing the OpenMP and llc parallelizations of the symmetric rank-k update operation on shared and distributed memory parallel platforms. Keywords: MPI, OpenMP, Workqueuing, cluster computing, distributed memory.
1
Introduction
The advances in high performance computing (HPC) hardware have not been followed by the software. The tools used to express parallel computations are nowadays one of the major obstacles for the massive use of HPC technology. Two of these tools are MPI [1] and OpenMP [2]. Key advantages of MPI are its portability and efficiency, with the latter strongly influenced by the control given to the programmer of the parallel application. However, a deep knowledge of low-level aspects of parallelism (communications, synchronizations, etc.) is needed in order to develop an efficient MPI parallel application. On the other hand, OpenMP allows a much easier implementation. One can start from a sequential code and parallelize it incrementally by adding compiler directives to specific regions of the code. An additional advantage is that it
This work has been partially supported by the EC (FEDER) and the Spanish MEC (Plan Nacional de I+D+I, TIN2005-09037-C02).
F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 89–96, 2007. c Springer-Verlag Berlin Heidelberg 2007
90
A.J. Dorta et al.
follows the sequential semantic of the program. The main drawback of OpenMP is that it only targets shared memory architectures. As an alternative to MPI and OpenMP, we have designed llc [3] to exploit the best features of both approaches. llc shares the simplicity of OpenMP: we can start from a sequential code and parallelize it incrementally using OpenMP and/or llc directives and clauses. The code annotated with parallel directives is compiled by llCoMP, the llc compiler-translator, which produces an efficient and portable MPI parallel source code, valid for both shared and distributed memory architectures. An additional advantage of llc is that all the OpenMP directives and clauses are recognized by llCoMP. Therefore, we have three versions in the same code: sequential, OpenMP and llc/MPI, and we only need to choose the proper compiler to obtain the appropriate binary. Different directives have been designed in llc to support common parallel constructs in the past as forall, sections, and pipelines [4,5]. In previous studies [4] we have investigated the implementation of Task Queues in llc. In this paper we focus our attention in the last feature added to llc: the support for the Workqueuing Model using Task Queues [6]. In order to do so, we explore the possibilities of parallelizing (dense) linear algebra operations, as developed in the frame of the FLAME (Formal Linear Algebra Method Environment) project [7]. The rest of the paper is organized as follows. In Section 2 we present the symmetric rank-k update (SYRK) operation as well as a FLAME code for its computation. Section 3 reviews the parallelization of this code using OpenMP and llc. Experimental results for both OpenMP and llc codes are reported and discussed in Section 4. Finally, Section 5 offers some concluding remarks and hints on future research.
2
The SYRK Operation
The SYRK operation is one of the Basic Linear Algebra Subprograms (BLAS) [8] most often used. It plays an important role, e.g., in the formation of the normal equations in linear least-squares problems and the solution of symmetric positive definite linear systems via the Cholesky factorization [9]. The operation computes the lower (or upper) triangular part of the result of the matrix product C := βC + αAAT , where C is an m× m symmetric matrix, A is an m× k matrix, and α, β are scalars. Listing 1 presents the FLAME code for the SYRK operation [10]. The partitioning routines (FLA Part x, FLA Repart x to y and FLA Cont with x to y) are indexing operations that identify regions (blocks) into the matrices but do not modify their contents. Thus, e.g., the invocation to FLA Part 2x1 in lines 7– 8 “divides” matrix (object) A into two submatrices (blocks/objects), AT and AB, with the first one having 0 rows. Then, at each iteration of the loop, certain operations are performed with the elements in these submatrices (routines FLA Gemm and FLA Syrk). More details can be consulted in [7].
Parallelizing Dense Linear Algebra Operations with Task Queues in llc
1 2 3 4 5
int FLA_Syrk_ln_blk_var1_seq ( FLA_Obj FLA_Obj F L A _ O b j AT , AB , CTL , CBL , CTR , A0 , A1 , A2 , C00 , C01 , C02 , int b;
91
alpha , FLA_Obj A , beta , FLA_Obj C , int nb_alg ) { CBR , C10 , C11 , C12 , C20 , C21 , C 2 2 ;
7 8 9 10
F L A _ P a r t _ 2 x 1 ( A , &AT , &AB , 0 , F L A _ T O P ) ; F L A _ P a r t _ 2 x 2 ( C , &CTL , &CTR , &CBL , &CBR , 0 , 0 , F L A _ T L ) ;
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
while ( F L A _ O b j _ l e n g t h ( A T ) < F L A _ O b j _ l e n g t h ( A ) ) { b = min ( F L A _ O b j _ l e n g t h ( AB ) , nb_alg ) ; F L A _ R e p a r t _ 2 x 1 _ t o _ 3 x 1 ( AT , &A0 , &A1 , AB , &A2 , b , F L A _ B O T T O M ) ; F L A _ R e p a r t _ 2 x 2 _ t o _ 3 x 3 ( CTL , CTR , &C00 , &C01 , &C02 , &C10 , &C11 , &C12 , CBL , CBR , &C20 , &C21 , &C22 , b , b , F L A _ B R ) ; /∗−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−∗/ /∗ C10 := C10 + A1 ∗ A0 ’ ∗/ F L A _ G e m m ( F L A _ N O _ T R A N S P O S E , F L A _ T R A N S P O S E , a l p h a , A1 , A0 , beta , C10 , n b _ a l g ) ; /∗ C11 := C11 + A1 ∗ A1 ’ ∗/ F L A _ S y r k ( F L A _ L O W E R _ T R I A N G U L A R , F L A _ N O _ T R A N S P O S E , a l p h a , A1 , beta , C11 , n b _ a l g ) ; /∗−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−∗/ F L A _ C o n t _ w i t h _ 3 x 1 _ t o _ 2 x 1 (&AT , A0 , A1 , &AB , A2 , F L A _ T O P ) ; F L A _ C o n t _ w i t h _ 3 x 3 _ t o _ 2 x 2 (& CTL , &CTR , C00 , C01 , C02 , C10 , C11 , C12 , &CBL , &CBR , C20 , C21 , C22 , F L A _ T L ) ; } return F L A _ S U C C E S S ;
}
Listing 1. FLAME code for the SYRK operation
3
Parallelization of the SYRK Operation
A remarkable feature of FLAME is its capability for hiding intricate indexing in linear algebra computations. However, this feature is a drawback for the traditional OpenMP method to obtain parallelism from a sequential code, based on exploiting the parallelism of for loops. Thus, the OpenMP approach requires loop indexes for expressing parallelism which are not available in FLAME codes. Task Queues [6] have been proposed for adoption in OpenMP 3.0 and are currently supported by the Intel OpenMP compilers. Their use allows an elegant implementation of loops when the space iteration is not known in advance or, as in the case of FLAME code, when explicit indexing is to be avoided. 3.1
OpenMP Parallelization
The parallelization of the SYRK operation using the Intel implementation of Task Queues is described in [10]. The Intel extension provides two directives to specify tasks queues. The omp parallel taskq directive specifies a parallel region where tasks can appear. Each task found in this region will be queued for later
92
A.J. Dorta et al.
computation. The omp task identifies the tasks. For the SYRK operation, the first clause is used to mark the while loop (line 12 in Listing 1), while the second one identifies the invocations to FLA Gemm and FLA Syrk as tasks (lines 21–26 in Listing 1). Listing 2 shows the parallelization using taskq of the loop in the
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# p r a g m a i n t e l omp p a r a l l e l t a s k q { while ( F L A _ O b j _ l e n g t h ( A T ) < F L A _ O b j _ l e n g t h ( A ) ) { ... #p r a g m a i n t e l omp t a s k c a p t u r e p r i v a t e ( A0 , A1 , C10 , C 1 1 ) { /∗ C10 := C10 + A1 ∗ A0 ’ ∗/ F L A _ G e m m ( F L A _ N O _ T R A N S P O S E , F L A _ T R A N S P O S E , a l p h a , A1 , A0 , beta , C10 , n b _ a l g ) ; /∗ C11 := C11 + A1 ∗ A1 ’ ∗/ F L A _ S y r k ( F L A _ L O W E R _ T R I A N G U L A R , F L A _ N O _ T R A N S P O S E , a l p h a , A1 , beta , C11 , n b _ a l g ) ; } ... } }
Listing 2. FLAME code for the SYRK operation parallelized using OpenMP
FLAME code for the SYRK operation. The directive omp task that appears in line 4 is used to identify the tasks. Function calls to FLA Gemm and FLA Syrk are in the scope of the taskq directive in line 1 and, therefore, a new task that computes both functions is created at each iteration of the loop. The first of these functions computes C10 := C10 + A1 AT0 , while the second one computes C11 := C11 + A1 AT1 . All the variables involved in these computations have to be private to each thread (A0 , A1 , C10 , and C11 ), ant thus they must be copied to each thread during execution time. The captureprivate clause that complements the omp parallel task directive serves this purpose. 3.2
llc Parallelization
In this section we illustrate the use of llc to parallelize the SYRK code. Further information about the effective translation of the directives in the code to MPI can be found in [4]. The parallelization using llc resembles that carried out using OpenMP, with a few differences that are illustrated in the following. After identifying the task code, we annotate the regions using llc and/or OpenMP directives. All the OpenMP directives and clauses are accepted by llCoMP, though not all of them have meaning and/or effect in llc [4]. We will start from the OpenMP parallel code shown in Listing 2 and we will add the necessary llc directives in order to complete the llc parallelization. The OpenMP captureprivate clause has no sense in llc, because llCoMP produces a MPI code where each processor has its private memory. (llc follows the OTOSP model [3], where all the processors on the same group have the same data in their private memories.) Unlike OpenMP, in llc all the variables are private by default, and we have to use llc directives to specify shared data. Listing 3 shows the parallelization of the FLAME code for the SYRK operation using llc.
Parallelizing Dense Linear Algebra Operations with Task Queues in llc
1 2 3 4 5 6 7 8 9
10
11 12 13 14 15 16 17 18
93
# p r a g m a i n t e l omp t a s k # p r a g m a l l c t a s k m a s t e r d a t a (&A0 .m, 1 , &A1 . offm , 1 , &A1 .m, 1 ) # p r a g m a l l c t a s k m a s t e r d a t a (&C11 . offm , 1 , & C11 . o f f n , 1 , & C11 .m, 1 , & C11 . n , 1 ) # p r a g m a l l c t a s k m a s t e r d a t a (&C10 . offm , 1 , & C10 . o f f n , 1 , & C10 .m, 1 , & C10 . n , 1 ) # p r a g m a l l c t a s k s l a v e s e t d a t a (&A1 . base , 1 ,A. base ,&A0 . base , 1 ,A . b a s e ) # p r a g m a l l c t a s k s l a v e s e t d a t a (&C11 . base , 1 ,C . base ,&C10 . base , 1 , C . b a s e ) # p r a g m a l l c t a s k s l a v e s e t d a t a (&A0 . offm , 1 ,A. offm ,&A0 . o f f n , 1 ,A . o f f n ,&A0 . n , 1 ,A. n ) # p r a g m a l l c t a s k s l a v e s e t d a t a (&A1 . o f f n , 1 ,A. o f f n ,&A1 . n , 1 ,A. n ) # p r a g m a l l c t a s k s l a v e r n c d a t a ( ( C10 . base−>b u f f e r +((C10 . o f f n ∗C10 . base−> l d i m+C10 . o f f m ) ∗ s i z e o f ( double ) ) ) , ( C10 .m ∗ s i z e o f ( double ) ) , ( ( C10 . base−>l d i m − C10 .m) ∗ s i z e o f ( double ) ) , C10 . n ) # p r a g m a l l c t a s k s l a v e r n c d a t a ( ( C11 . base−>b u f f e r +((C11 . o f f n ∗C11 . base−> l d i m+C11 . o f f m ) ∗ s i z e o f ( double ) ) ) , ( C11 .m ∗ s i z e o f ( double ) ) , ( ( C11 . base−>l d i m − C11 .m) ∗ s i z e o f ( double ) ) , C11 . n ) { /∗ C10 := C10 + A1 ∗ A0 ’ ∗/ F L A _ G e m m ( F L A _ N O _ T R A N S P O S E , F L A _ T R A N S P O S E , a l p h a , A1 , A0 , beta , C10 , n b _ a l g ) ; /∗ C11 := C11 + A1 ∗ A1 ’ ∗/ F L A _ S y r k ( F L A _ L O W E R _ T R I A N G U L A R , F L A _ N O _ T R A N S P O S E , a l p h a , A1 , b e t a , C11 , n b _ a l g ) ; }
Listing 3. FLAME code for the SYRK operation parallelized using llc
A first comparison of Listings 2 and 3 shows an apparent increase in the number of directives when llc is used. However, note that only three directives are actually needed, but we split those in order to improve the readability. Although llc code can be sometimes as simple as OpenMP code (see, e.g., [4]), here we preferred to use an elaborated algorithm to illustrate how llc overcomes difficulties that usually appear when targeting parallel distributed memory architectures: references to specific data inside a larger data structure (submatrices instead of the whole matrix), access to non-contiguous memory locations, etc. In the llc implementation of Task Queues, a master processor handles the task queue, sends subproblems to the slaves, and gathers the partial results to construct the solution. Before the execution of each task, the master processor needs to communicate some initial data to the slaves, using the llc task master data directive. As the master and slaves processors are on the same group, they have the same values in each private memory region. Exploiting this, the master processor only sends those data that have been modified. With this approach the number of directives to be used is larger than in the OpenMP case, but the amount of communications is considerably reduced. The master needs to communicate to each slave the offset and number of elements of the objects A0 , A1 , C10 , and C11 (lines 2–4). After each execution, the slave processors “remember” the last data used. To avoid this, we employ the llc task slave set data directives in lines 5–8 that initialize the variables before each task execution to certain fixed values (with no communications involved). The code inside the parallel task computes C10 := C10 + A1 AT0 and C11 := C11 +A1 AT1 . The slaves communicate to the master the results obtained (C10 and C11 ). These data are not stored in contiguous memory positions and therefore can not be communicated as a single block. However, the data follow a regular
94
A.J. Dorta et al.
pattern and can be communicated using the llc task slave rnc data directive (lines 9–10). This directive specifies r egular non-contiguous memory locations.
4
Experimental Results
All the experiments reported in this section for the SYRK operation (C := C + AAT , with an m × m matrix C and an m × k matrix A) were performed using double-precision floating point arithmetic. The results correspond to the codes that have been illustrated previously in this paper (FLAME Variant 1 of the SYRK operation, Var1) as well as a second variant (Var2) for the same operation [10]. Three different platforms were employed in the evaluation, with the common building block in all these being an Intel Itanium2 1.5GHz processor. The first platform is a shared-memory (SM) Bull NovaScale 6320 with 32 processors. The second platform is a SM SGI Altix 250 with 16 processors. The third system is a hybrid cluster composed of 9 nodes connected via a 10 Gbit/s InfiniBand switch; each node is a SM architecture with 4 processors, yielding a total of 36 processors in the system. An extensive experimentation was performed to determine the best block size (parameter nb alg in the algorithms) for each variant and architecture. Only those results corresponding to the optimal block size (usually, around 96) are reported next. The OpenMP implementations were compiled with the Intel C compiler, while the llc binaries were produced with llCoMP combined with the mpich implementation of MPI on the SGI Altix and hybrid cluster, and MPIBull-Quadrics 1.5 on the NovaScale server. The goal of the experiments on SM platforms is to compare the performance of the SYRK implementation in OpenMP and llc. The results on the hybrid system are presented to demonstrate that high performance can be also achieved when the portability of llc is exploited. Table 1 reports the results for the SYRK codes. In particular, the second row of the table shows the execution time of the sequential code, while the remaining rows illustrate the speed-up of the OpenMP and llc parallelizations on the SGI Altix and the Bull NovaScale. The results show a similar performance for OpenMP and our approach on both architectures. OpenMP obtains a higher performance than llc when the number of processors is small. The reason for this behavior is that in the llc implementation one of the processors acts as the master. As the number of processors grows, the speed-up of llc increases faster than that of OpenMP. When the number of processors is large, llc yields better performance than OpenMP because it is less affected by memory bandwidth problems. The second variant of the algorithm exhibits a better performance than the first one, because it generates a larger number of tasks with finer granularity during the computations following a bidimensional partitioning of the work; see [10]. Figure 1 shows the speed-up obtained on the hybrid system. Again the second variant exhibits a better performance, and a maximum speed-up slightly above 25 is attained using 36 processors.
Parallelizing Dense Linear Algebra Operations with Task Queues in llc
95
Table 1. Sequential time and speed-up obtained on the SM platforms for Variants 1 and 2 of the SYRK operation for both OpenMP and llc. For the Bull NovaScale 6320 (Bull), m=10000 and k=7000. For the SGI Altix 250 (SGI), m=6000 and k=3000.
#Proc. seq.
Var1 SGI 19.0 sec.
Var1 Bull
Var2 SGI
176.5 sec.
19.0 sec.
Var2 Bull 176.5 sec.
–
omp
llc
omp
llc
omp
llc
omp
llc
3 4 6 8 10 12 14 16
2.13 2.85 3.97 4.60 5.78 6.76 6.69 7.41
1.58 2.22 3.49 4.68 5.70 7.41 7.81 9.02
2.75 3.48 4.25 5.16 6.83 7.34 7.93 8.61
1.85 2.65 4.16 5.59 6.98 7.81 8.90 9.35
2.83 3.72 5.51 7.16 8.82 10.24 11.67 12.71
1.89 2.82 4.72 6.52 8.33 10.09 11.79 13.62
2.94 3.84 5.34 6.74 8.16 9.53 9.37 9.56
1.98 2.96 4.91 7.21 8.62 10.65 13.20 13.76
Fig. 1. Speed-up on the hybrid system for Variants 1 and 2 of the SYRK operation parallelized using llc. On this system, m=5000 and k=3000.
5
Conclusions and Future Work
llc is an language based on C that, given a sequential code annotated with directives and using the llCoMP translator-compiler, produces MPI parallel code. llc combines the high productivity in code development of OpenMP with the high performance and the portability of MPI. In this paper we have evaluated the performance of the Task Queues implementation in llc using FLAME codes for the SYRK operation. We have shown that the llc directives facilitate optimization and tuning. The additional complexity
96
A.J. Dorta et al.
introduced in the llc version with respect to the OpenMP version is clearly paid off by the portability of the code. The performance achieved with our approach is comparable to that obtained using OpenMP. Taking into account the smaller effort to develop codes using llc compared with a direct MPI implementation, we conclude that llc is appropriate to implement some classes of parallel applications. Work in progress concerning this topic includes the following: – To study other variants and parallelization options for the SYRK operation, such as using two tasks per iteration or splitting the while loop. – To study other FLAME operations. We are currently working on the matrixvector product. – To apply our approach to other scientific and engineering applications. – To extend the computational results to other machines and architectures.
References 1. Message Passing Interface Forum: MPI: A Message-Passing Interface Standard. University of Tennessee, Knoxville, TN (1995), http://www.mpi-forum.org/ 2. OpenMP Architecture Review Board: OpenMP Application Program Interface v. 2.5 (2005) 3. Dorta, A.J., Gonz´ alez, J.A., Rodr´ıguez, C., de Sande, F.: llc: A parallel skeletal language. Parallel Processing Letters 13(3), 437–448 (2003) 4. Dorta, A.J., Lopez, P., de Sande, F.: Basic skeletons in llc. Parallel Computing 32(7–8), 491–506 (2006) 5. Dorta, A.J., Bad´ıa, J.M., Quintana, E.S., de Sande, F.: Implementing OpenMP for clusters on top of MPI. In: Di Martino, B., Kranzlm¨ uller, D., Dongarra, J.J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface. LNCS, vol. 3666, pp. 148–155. Springer, Heidelberg (2005) 6. Shah, S., Haab, G., Petersen, P., Throop, J.: Flexible control structures for parallelism in OpenMP. Concurrency: Practice and Experience 12(12), 1219–1239 (2000) 7. Bientinesi, P., Gunnels, J.A., Myers, M.E., Quintana-Ort´ı, E.S., van de Geijn, R.A.: The science of deriving dense linear algebra algorithms. ACM Trans. on Mathematical Software 31(1), 1–26 (2005) 8. Lawson, C.L., Hanson, R.J., Kincaid, D.R., Krogh, F.T.: Basic linear algebra subprograms for fortran usage. ACM Trans. Math. Softw. 5(3), 308–323 (1979) 9. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore, MD (1996) 10. Van Zee, F., Bientinesi, P., Low, T.M., van de Geijn, R.A.: Scalable parallelization of FLAME code via the workqueuing model (ACM Trans. on Mathematical Software) (to appear) Electronically, available at http://www.cs.utexas.edu/users/flame/pubs.html
ParaLEX: A Parallel Extension for the CPLEX Mixed Integer Optimizer Yuji Shinano1 and Tetsuya Fujie2 1
Division of Systems and Information Technology, Institute of Symbiotic Science and Technology, Tokyo University of Agriculture and Technology, 2-24-16, Naka-cho, Koganei-shi, Tokyo 184-8588, Japan
[email protected] 2 School of Business Administration, University of Hyogo, 8-2-1, Gakuen-nishimachi, Nishi-ku, Kobe 651-2197, Japan
[email protected]
Abstract. The ILOG CPLEX Mixed Integer Optimizer is a state-ofthe-art solver for mixed integer programming. In this paper, we introduce ParaLEX which realizes a master-worker parallelization specialized for the solver on a PC cluster using MPI. To fully utilize the power of the solver, the implementation exploits almost all functionality available in it. Computational experiments are performed for MIPLIB instances on a PC cluster composed of fifteen 3.4GHz pentiumD 950 (with 2G bytes RAM) PCs (running a maximum of 30 CPLEX Mixed Integer Optimizers). The results show that ParaLEX is highly effective in accelerating the solver for hard problem instances. Keywords: Mixed Integer Programming, Master-Worker, Parallel Branch-and-cut.
1
Introduction
The ILOG CPLEX Mixed Integer Optimizer [6] is one of the most successful commercial codes for MIP (Mixed Integer Programming). MIP problem is to optimize (minimize or maximize) a linear function subject to linear inequalities and/or linear equalities with the restriction that some or all of the variables must take integer values. MIP has a wide variety of industrial, business, science and educational applications. In fact, recent remarkable progress of MIP optimizers, including CPLEX, leads to the increased importance of MIP models. CPLEX has continued to incorporate computational improvements into a branch-andcut implementation, which results an efficient and robust code. It involves both standard and advanced techniques such as preprocessing, many kinds of cutting planes, heuristics, and strong branching. Due to limited space, we omitted MIPrelated from this paper (see [8,11] for MIP models and algorithms). In [2], recent software systems for MIP are introduced. Many researchers have developed
This work was partially supported by MEXT in Japan through Grants-inAid(18510118).
F. Cappello et al. (Eds.): EuroPVM/MPI 2007, LNCS 4757, pp. 97–106, 2007. c Springer-Verlag Berlin Heidelberg 2007
98
Y. Shinano and T. Fujie
parallelization frameworks of branch-and-bound and branch-and-cut algorithms, including ALPS/BiCeOS, PICO, SYMPHONY, BCP, PUBB. See recent surveys [3,4,9]. In this paper, we propose a master-worker parallelization of CPLEX, named ParaLEX (Parallel extension for CPLEX MIP optimizer). The main feature of our implementation is that it fully utilizes the power of CPLEX : The entire search tree (or, branch-and-cut tree) produced by ParaLEX is composed of subtrees produced by CPLEX on master and workers. ParaLEX has a simpler structure than our previous work of a parallelization of CPLEX using the PUBB2 framework [10].
2
ParaLEX
In this section, we introduce ParaLEX briefly. We had three major goals for the design of ParaLEX. – Most of all the functionality of CPLEX must be available. – Future versions of CPLEX must be “parallelizable” without any code modification needed. – Parallel implementation must be as simple as possible. To achieve these design goals, ParaLEX is – composed of two types of solvers, each of which runs CPLEX with almost full functionality, – is implemented in C++ but the most primitive CPLEX Callable Library is used, and – is essentially a simple Master-Worker parallelization. The branch-and-cut algorithm is an enumerative algorithm which repeatedly partitions a given problem instance into several subproblems. The algorithm therefore forms a tree called search tree or branch-and-cut tree. Subproblems will be also referred to as nodes in the subsequent of this paper. Similarly, a given problem instance will be also referred to as a root node. Next, we introduce the notion of the ParaLEX instance which comprises a preprocessed problem instance and global cuts applied to the root node. Preprocessing and generation of global cuts (or, cutting planes), both of which are applied to the root node, are quite effective in CPLEX in giving a tighter reformulation of MIP even though they are time consuming. It is certain that, if we drop these functionalities in parallelization, the solution time of MIP becomes greater than that by a sequential CPLEX solver. On the other hand, if these functionalities are performed from scratch on each PE (Processing Element), the parallelization cannot achieve high performance in general. ParaLEX instances are introduced based on the observation. A subproblem representation used in ParaLEX is the difference between a node LP object in the branch callback routine of CPLEX and the ParaLEX instance.
ParaLEX: A Parallel Extension for the CPLEX Mixed Integer Optimizer
99
PE CPLEX environment
PE statuses
Incumbent solution
Incumbent value CPLEX env.
CPXmipopt
PE
Incumbent value
Incumbent value CPLEX env.
CPXmipopt n
Fig. 1. Initialization phase of ParaLEX
ParaLEX is implemented as a SPMD-type MPI program1 but is composed of the following two types of objects (solvers) depending on the rank of the process, which we call the PE rank. MainSolver (PE rank = 0). This solver reads an original problem instance data, and then performs preprocessing, and generates global cuts to create the ParaLEX instance. It not only manages the PEs on the system but also solves nodes by applying the CPXmipopt function of CPLEX. It keeps an incumbent solution which is the best solution found so far among all the PEs and, at the end of computation, outputs an optimal solution. SubtreeSolver (PE rank ≥ 1). This solver first receives the ParaLEX instance from the MainSolver. It also receives nodes from the MainSolver or other SubtreeSolvers. The nodes received are solved by CPLEX. If an improved incumbent solution is found in this solver, the solution is sent to the MainSolver. At first, the MainSolver starts solving the ParaLEX instance by CPLEX. When the number of unexplored nodes in the CPLEX environment has been exceeded the threshold value given by the ParaLEX run-time parameter, the MainSolver starts distributing its unexplored nodes one by one to SubtreeSolvers. In our computational experiments reported in Section 3, we set the threshold parameter as min{200, 5.0/(average time to compute one node in the sequential run)}. Figure 1 shows the initialization phase. When ParaLEX runs with several PEs, a search tree is partitioned into several subtrees produced by the corresponding PEs. Each subtree is maintained in the 1
The Master-Worker program can also be implemented as an MPMD-type MPI program. However, we have been familiar with an SPMD implementation due to the requirement of MPI-1 functionality.
100
Y. Shinano and T. Fujie
CPLEX environment of the corresponding PE (MainSolver or SubtreeSolver). In normal running situations, communications between the MainSolver and the SubtreeSolver and between the SubtreeSolvers are done in the branch callback routine of CPLEX. In this callback routine, the PE from which the callback is called sends a node to a PE if necessary. The node is then solved as a problem instance by CPLEX. Note that the node transferred is solved twice, once in the sender as a node and once in the receiver as a root node. In the receiver side, however, the root node is not solved from scratch, because its LP (Linear Programming) basis generated in the sender side is also transferred and is used as the starting basis. Though it is solved as a root node, it may be pruned without any branch by trying to apply extra cuts to the node. Eventually, it may lead to reduced total computation times. The MainSolver maintains statuses of all the PEs. Each SubtreeSolver notifies to the MainSolver the number of unexplored nodes in the CPLEX environment and the best bound value among these nodes as the PE status, when the number of nodes processed from the previous notification has been exceeded the threshold value given by the ParaLEX run-time parameter. When a PE has finished solving an assigned node, it becomes an idle solver. If the MainSolver detects an idle solver, it sends a subproblem-transfer request message to a PE which has an unexplored node with the best bound value by referring to the PE statuses. There is a delay updating the PE statuses in the MainSolver. Therefore, the PE which receives the subproblem-transfer request may not have enough many nodes in its CPLEX environment. In such a case, the solver rejects the request. If the solver has more nodes than the threshold value given by the ParaLEX run-time parameter, it accepts the request and sends a node to the destination PE that is indicated in the request message. Note that at most one node can be transferred in one request message. Figure 2 shows a message sequence for the subproblem transfer. The node to be transferred can be selected in the selection callback routine of CPLEX. When the node with the best bound transfer is specified in the ParaLEX run-time parameter, the best bound node is selected in this callback routine. The selection is done by a computationally intensive linear search of the unexplored nodes in the CPLEX environment. On the other hand, when a default selection is specified in this parameter, a node is selected according to the selection rule specified in the CPLEX run-time parameter. In this case, the unexplored nodes are arranged by the selection rule order in the CPLEX environment, and thus selection does not take a long time. When an improved solution is found in the MainSolver, its incumbent value is sent to all the SubtreeSolvers. When an improved solution is found in the SubtreeSolver, the incumbent solution is sent to the MainSolver and the MainSolver sends the incumbent value to all the SubtreeSolvers. Improved incumbent solutions are detected in the incumbent callback routine of CPLEX and its notification is done in the branch callback of CPLEX. The CPXmipopt function that solves a problem instance is suspended after the number of nodes specified in the ParaLEX run-time parameter has
ParaLEX: A Parallel Extension for the CPLEX Mixed Integer Optimizer
101
MainSolver PE CPLEX environment
PE statuses
Incumbent solution
Incumbent value
SubtreeSolver
SubtreeSolver
Incumbent value
Incumbent value
CPLEX env.
CPLEX env.
PE
! "
n
Fig. 2. Message sequence for the subproblem transfer
been processed. When suspended time comes, the latest incumbent value is set on CPLEX environment using the CPXsetdblparam function of CPLEX with CPX PARAM CUTUP (if the problem is minimization) or with CPX PARAM CUTLO (if the problem is maximization). After that, the suspension is resumed. Therefore, there is a delay in the notification of the incumbent value.
3
Computational Experiments
In this section, we report our computational results. We used a PC cluster composed of fifteen 3.4GHz pentiumD 950 (with 2Gbytes RAM) PCs connected with Gigabit Ethernet, where 30 CPLEX Mixed Integer Optimizers (version 10.1) were available. The MPI library used is mpich2-1.0.5p4. Problem instances were selected from the MIPLIB2003 library2 [1] which is a standard test set to evaluate the performance of MIP optimizers. We first discuss the effects of the ParaLEX run-time parameters described in Section 2. – MIP emphasis indicator CPX PARAM MIPEMPHASIS (CPLEX) : This is a parameter prepared by CPLEX to tell the solver whether it should find a feasible solution with high quality or prove the optimality. Among several options, we selected the following ones, which are concerned with the optimality. • CPX MIPEMPHASIS BALANCED : Balance optimality and integer feasibility (default parameter of CPLEX). • CPX MIPEMPHASIS OPTIMALITY : Emphasizing optimality over feasibility. 2
URL: http://miplib.zib.de
102
Y. Shinano and T. Fujie
• CPX MIPEMPHASIS BESTBOUND : Emphasizing moving best bound. – Subproblem transfer mode (ParaLEX) : This is a parameter for PEs to transform a node. • best bound transfer : The best bound node is selected. • cplex default transfer : A node is selected according to the CPLEX run-time parameter. – CPXmipopt interval (ParaLEX) : This is a parameter for PEs to specify the suspended time of CPXmipopt. • fixed iter : Every time CPXmipopt terminates with the node limit of this value to check a subproblem-request from an another PE. In this paper, we set fixed iter = 20. • fixed time : By a sequential run, we estimate the number of nodes generated by CPXmipopt during the time fixed time. Then, this estimated value is used for the node limit of CPXmipopt. In this paper, we set fixed time = 1 (sec.). Table 1 displays the parallel speedups obtained over 5 runs for the easy instances fast0507 and mas74 with possible combinations of the following two parameters, the Subproblem transfer mode and the CPXmipopt interval. CPX PARAM MIPEMPHASIS is set to CPX MIPEMPHASIS BALANCED. As the table shows, it is hard to determine the most suitable combination of the parameter values. On the other hand, cplex default transfer is competitive or better than best bound transfer, which indicates that a PE which receives a transferred node should continue the branch-and-cut search along with the parent PE (i.e., the PE which sends the node). Hence, we selected cplex default transfer for the subsequent computations. We observed that the effect of the CPXmipopt interval depends on the behavior of a sequential run of CPLEX since computing time per node varies considerably with problem instances. Hence, we decided to use fixed time. Table 2 shows the results for the CPX PARAM MIPEMPHASIS parameter. The results are obtained over 5 runs except that the noswot instance is examined over 1 run. We note that the computing time of sequential run varies with this parameter, and the most suitable parameter-choice also varies with the problem instance. From the table, we see that superlinear speedup results are obtained for several problem instances. In particular, noteworthy speedup is obtained for the noswot instance. We observed that superlinear speedup occurs when a good feasible solution is hardly obtained by CPLEX. In this case, a parallel search could find a good feasible solution faster than a sequential search. Since fast finding of a good feasible solution can lead to pruning of many unexplored nodes, the parallel search could generate a smaller search tree than the sequential search. Therefore, computation is performed to a smaller number of nodes by many PEs and, as a result, the superlinear speedup is obtained. We also observe that high speedup results are obtained for CPX MIPEMPHASIS OPTIMALITY. Finally, we report the results for hard problem instances with 30 PEs. We continue to use the parameters cplex default transfer and fixed time. CPX PARAM MIPEMPHASIS was determined by an observation of the behavior of upper and lower bounds within several hours from the beginning and by the information in the MIPLIB 2003 website.
ParaLEX: A Parallel Extension for the CPLEX Mixed Integer Optimizer
103
Table 1. Parallel speedups for easy instances (CPX MIPEMPHASIS BALANCED) # of PEs 3 5 10 20 30 fast0507, best bound transfer, fixed iter : 880.61 sec. (sequential) ave. 0.45 1.16 1.38 1.98 2.96 3.07 min. 0.45 1.13 1.37 1.97 2.93 3.04 max. 0.45 1.21 1.39 1.99 3.00 3.13 fast0507, best bound transfer, fixed time : 880.61 sec. (sequential) ave. 0.99 1.04 1.33 3.07 3.56 3.71 min. 0.99 1.03 1.30 3.03 3.51 3.68 max. 0.99 1.05 1.42 3.21 3.63 3.78 fast0507, cplex default transfer, fixed iter : 880.61 sec. (sequential) ave. 0.87 1.11 0.61 2.36 3.39 3.15 min. 0.76 1.10 0.61 2.30 3.37 3.13 max. 0.96 1.12 0.61 2.52 3.43 3.15 fast0507, cplex default transfer, fixed time : 880.61 sec. (sequential) ave. 1.23 1.15 1.36 1.56 2.41 2.71 min. 1.23 1.04 1.31 1.51 2.11 2.65 max. 1.24 1.36 1.44 1.72 2.92 2.75 mas74, best bound transfer, fixed iter : 1292.99 sec. (sequential) ave. 0.04 0.06 0.28 1.39 1.84 0.50 min. 0.03 0.05 0.21 1.29 1.19 0.34 max. 0.06 0.06 0.33 1.64 4.36 0.64 mas74, best bound transfer, fixed time : 1292.99 sec. (sequential) ave. 0.12 0.04 0.25 1.40 3.21 0.35 min. 0.11 0.04 0.24 1.32 1.59 0.30 max. 0.12 0.04 0.27 1.45 5.40 0.39 mas74, cplex default transfer, fixed iter : 1292.99 sec. (sequential) ave. 0.57 0.51 1.09 1.38 5.21 8.36 min. 0.46 0.34 0.84 1.11 4.43 7.14 max. 0.67 0.86 1.38 2.26 6.32 10.77 mas74, cplex default transfer, fixed time : 1292.99 sec. (sequential) ave. 0.82 0.91 1.34 1.90 4.66 10.01 min. 0.80 0.78 1.22 1.79 4.39 8.62 max. 0.85 1.09 1.49 2.08 5.11 13.98 2
– – – – –
a1c1s1 : 142960.36 (sec.) with CPX MIPEMPHASIS BESTBOUND arki001 : 3924.87 (sec.) with CPX MIPEMPHASIS OPTIMALITY glass4 : 2001.50 (sec.) with CPX MIPEMPHASIS BALANCED roll3000 : 173.73 (sec.) with CPX MIPEMPHASIS BESTBOUND atlanta-ip : 2512451.70 (sec.) with CPX MIPEMPHASIS BALANCED
These problem instances have been solved to optimality recently [5,7], and they are still hard to be solved with sequential and default solver strategies. Actually, the roll3000 instances cannot be solved sequentially within 230464.65 sec. with CPX MIPEMPHASIS BESTBOUND. 2213435 nodes remain unexplored. Hence,
104
Y. Shinano and T. Fujie
Table 2. Parallel speedups for easy instances (cplex default transfer, fixed time) # of PEs 3 5 10 20 30 fast0507, CPX MIPEMPHASIS BALANCED : 880.61 sec. (sequential) ave. 1.23 1.15 1.36 1.56 2.41 2.71 min. 1.23 1.04 1.31 1.51 2.11 2.65 max. 1.24 1.36 1.44 1.72 2.92 2.75 fast0507, CPX MIPEMPHASIS OPTIMALITY : 10704.98 sec. (sequential) ave. 9.70 14.19 14.93 15.53 15.52 15.53 min. 9.63 13.73 14.71 15.50 15.49 15.50 max. 9.77 14.65 15.15 15.56 15.53 15.56 fast0507, CPX MIPEMPHASIS BESTBOUND : 15860.45 sec. (sequential) ave. 0.47 0.63 0.72 0.71 2.03 2.48 min. 0.44 0.48 0.72 0.68 2.01 2.45 max. 0.65 0.69 0.73 0.74 2.07 2.52 mas74, CPX MIPEMPHASIS BALANCED : 1292.99 sec. (sequential) ave. 0.82 0.91 1.34 1.90 4.66 10.01 min. 0.80 0.78 1.22 1.79 4.39 8.62 max. 0.85 1.09 1.49 2.08 5.11 13.98 mas74, CPX MIPEMPHASIS OPTIMALITY : 1759.18 sec. (sequential) ave. 1.48 1.52 1.47 2.14 7.48 11.23 min. 1.40 1.46 1.41 1.91 6.86 10.07 max. 1.56 1.64 1.62 2.27 7.86 13.09 mas74, CPX MIPEMPHASIS BESTBOUND : 3674.92 sec. (sequential) ave. 1.02 0.96 0.94 1.02 1.01 1.04 min. 1.01 0.95 0.81 0.97 0.97 0.91 max. 1.03 0.98 1.04 1.06 1.05 1.21 harp2, CPX MIPEMPHASIS BALANCED : 5586.38 sec. (sequential) ave. 8.93 5.15 8.28 8.98 13.96 24.94 min. 5.34 3.24 5.90 3.15 8.58 17.67 max. 13.70 22.00 13.55 35.23 24.76 40.86 harp2, CPX MIPEMPHASIS OPTIMALITY : 2014.80 sec. (sequential) ave. 2.16 1.87 2.53 2.47 4.15 24.16 min. 1.53 1.10 2.05 1.61 2.49 20.61 max. 3.34 2.71 4.34 6.16 7.34 32.02 harp2, CPX MIPEMPHASIS BESTBOUND : 2974.34 sec. (sequential) ave. 1.43 2.62 3.10 2.71 4.70 8.22 min. 1.24 1.88 2.12 1.78 3.11 4.03 max. 1.59 3.41 6.95 5.67 8.17 18.64 noswot, CPX MIPEMPHASIS OPTIMALITY : 38075.95 sec. (sequential) − − − 27.01 119.61 276.03 noswot, CPX MIPEMPHASIS BESTBOUND : 193373.54 sec. (sequential) − − − 10.58 17.44 71.02 2
ParaLEX: A Parallel Extension for the CPLEX Mixed Integer Optimizer
105
12000
11800
objective function value
11600
11400
11200
11000
10800
10600 0
18000
36000
54000
72000
90000
108000
126000
144000
time (sec.)
Fig. 3. Upper and lower bounds for the a1c1s1 instance
we have a superlinear speedup result for this problem instance. We remark that R. Miyashiro reports that the roll3000 instance were solved in about half a day with CPX MIPEMPHASIS BESTBOUND (see the MIPLIB2003 website). However, the computing environment is different: He used a 32-bit PC while we used a 64bit machine, and the mipgap tolerances he used are different from ours (private communication). In Figure 3, we draw upper and lower bounds as functions of time for the a1c1s1 instance.
4
Concluding Remarks
The development of ParaLEX is still in its preliminary stages. In the initial design of ParaLEX, we intended to transfer nodes to the SubtreeSolvers only from the MainSolver or via the MainSolver to simplify the communication mechanism. However, this did not work well in many cases. Hence, we modified the transfer sequence as described in this paper. It is still a simple concept, but its implementation becomes complicated. We aim to reconsider the mechanism using what was learned in this development. ParaLEX was originally developed by using CPLEX 9.0, but it could be compiled with CPLEX 10.1 without any modification of the codes related to the CPLEX Callable Library. Using CPLEX 9.0, ParaLEX solved the rout instance about 66 times faster than the cplex command of the version did. However, CPLEX 10.1 can solve the instance about 22 times faster than CPLEX 9.0. We observed that ParaLEX with CPLEX 10.1 is not so attractive for the rout instance. To solve MIP problems faster, algorithmic improvements may be more significant than that by using parallelization. On the other hand, it is still quite hard to find a good feasible solution for some problem instances. If fast finding
106
Y. Shinano and T. Fujie
of a good feasible solution becomes possible by using new heuristic algorithms or different search strategies, this could lead to a tremendous speedups. However, ParaLEX is still very attractive to solve much harder instances for CPLEX 10.1. The significance of our approach is that ParaLEX has a potential to accelerate the latest version of CPLEX using parallelization. The parallel search itself is a method to obtain a good feasible solution faster than the sequential search. This is a reason why ParaLEX achieved superlinear speedups for several problem instances. Moreover, by only using the latest version with parallelization (note that we did not use any special structure of problem instances), several of today’s hardest instances of MIPLIB were solved to optimality. Therefore, ParaLEX is highly effective to solve hard problem instances.
References 1. Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34, 361–372 (2006) 2. Atamt¨ urk, A., Martin, W.P., Savelsbergh, M.W.P.: Integer-Programming Software Systems. Ann. Oper. Res. 140, 67–124 (2005) 3. Bader, D.A., Hart, W.E., Phillips, C.A.: Parallel Algorithm Design for Branch and Bound. In: Greenberg, H.J. (ed.) Tutorials on Emerging Methodologies and Applications in Operations Research, ch. 5, Kluwer Academic Press, Dordrecht (2004) 4. Crainic, T., Le Cun, B., Roucairol, C.: Parallel Branch-and-Bound Algorithms. In: Talbi, E. (ed.) Parallel Combinatorial Optimization, ch. 1, Wiley, Chichester (2006) 5. Ferris, M.: GAMS: Condor and the grid: Solving hard optimization problems in parallel. Industrial and Systems Engineering, Lehigh University (2006) 6. ILOG CPLEX 10.1 User’s Manual, ILOG, Inc. (2006) 7. Laundy, R., Perregaard, M., Tavares, G., Tipi, H., Vazacopoulos, A.: Solving Hard Mixed Integer Programming Problems with Xpress-MP: A MIPLIB 2003 Case Study. Rutcor Research Report 2-2007, Rutgers University (2007) 8. Nemhauser, G.L., Wolsey, L.A.: Integer Programming and Combinatorial Optimization. John Wiley & Sons, New York (1988) 9. Ralphs, T.K.: Parallel Branch and Cut. In: Talbi, E. (ed.) Parallel Combinatorial Optimization, ch. 3, Wiley, Chichester (2006) 10. Shinano, Y., Fujie, T., Kounoike, Y.: Effectiveness of Parallelizing the ILOGCPLEX Mixed Integer Optimizer in the PUBB2 Framework. In: Kosch, H., B¨ osz¨ orm´enyi, L., Hellwagner, H. (eds.) Euro-Par 2003. LNCS, vol. 2790, pp. 451– 460. Springer, Heidelberg (2003) 11. Wolsey, L.A.: Integer Programming. John Wiley & Sons, New York (1998)
Performance Analysis and Tuning of the XNS CFD Solver on Blue Gene/L Brian J. N. Wylie1 , Markus Geimer1 , Mike Nicolai2 , and Markus Probst2 1
2
John von Neumann Institute for Computing (NIC), Forschungszentrum J¨ ulich GmbH, D-52425 J¨ ulich, Germany {b.wylie,m.geimer}@fz-juelich.de Chair for Computational Analysis of Technical Systems (CATS), Centre for Computational Engineering Science (CCES), RWTH Aachen University, D-52074 Aachen, Germany {nicolai,probst}@cats.rwth-aachen.de
Abstract. The xns computational fluid dynamics code was successfully running on Blue Gene/L, however, its scalability was unsatisfactory until the first J¨ ulich Blue Gene/L Scaling Workshop provided an opportunity for the application developers and performance analysts to start working together. Investigation of solver performance pin-pointed a communication bottleneck that appeared with approximately 900 processes, and subsequent remediation allowed the application to continue scaling with a four-fold simulation performance improvement at 4,096 processes. This experience also validated the scalasca performance analysis toolset, when working with a complex application at large scale, and helped direct the development of more comprehensive analyses. Performance properties have now been incorporated to automatically quantify pointto-point synchronisation time and wait states in scan operations, both of which were significant for xns on Blue Gene/L. Keywords: performance analyses, scalability, application tuning.
1
Introduction
xns is an academic computational fluid dynamics (cfd) code for effective simulations of unsteady fluid flows, including micro-structured liquids, in situations involving significant deformations of the computational domain. Simulations are based on finite-element techniques using stabilised formulations, unstructured three-dimensional meshes and iterative solution strategies [1]. Main and novel areas of xns are: simulation of flows in the presence of rapi