EXPERIMENTAL EVALUATION OF BSP PROGRAMMING LIBRARIES
Abstract
The model of bulk-synchronous parallel computation (BSP) helps to implement portable general purpose algorithms while maintaining predictable performance on different parallel computers. Nevertheless, when programming in ‘BSP style’, the running time of the implementation of an algorithm can be very dependent on the underlying communication library. In this study, an overview of existing approaches to practical BSP programming in C/C++ or Fortran is given and benchmarks were run for the two main BSP-like communication libraries, the Oxford BSP Toolset and PUB. Furthermore, a memory efficient matrix multiplication algorithm was implemented and used to compare their performance on different parallel computers and to evaluate the compliance with predictions by theoretical results.
References
M. Bianco and G. Pucci , On the Predictive Quality of BSP-like Cost Functions for NOWs, Euro-Par 20001900,Lecture Notes in Computer Science (2000) pp. 638–646. Google ScholarG. Bilardi , On the Effectiveness of D-BSP as a Bridging Model of Parallel Computation, ICCS '012074,Lecture Notes in Computer Science (2001) pp. 579–588. Google Scholar-
R. H. Bisseling , Parallel Scientific Computation: A Structured Approach Using BSP and MPI ( Oxford University Press , 2004 ) . Crossref, Google Scholar - Parallel Comput. 30(3), 337 (2004), DOI: 10.1016/j.parco.2003.11.004. Crossref, ISI, Google Scholar
- Parallel Computing 29(2), 187 (2003), DOI: 10.1016/S0167-8191(02)00218-1. Crossref, ISI, Google Scholar
A. Chan and F. K. H. A. Dehne , CGMgraph/CGMlib: Implementing and Testing CGM Graph Algorithms on PC Clusters, EuroPVM/MPI2840,Lecture Notes in Computer Science , eds.J. Dongarra , D. Laforenza and S. Orlando (Springer, 2003) pp. 117–125. Google Scholar- ACM Transactions on Mathematical Software 16(1), 1 (1990), DOI: 10.1145/77626.79170. Crossref, ISI, Google Scholar
M. Essaidi , I. Guérin Lassous and J. Gustedt , SSCRAP: An Environment for Coarse Grained Algorithms, 14th IASTED International Conference on Parallel and Distributed Computing and Systems - PDCS'2002,IASTED (2002) pp. 398–403. Google Scholar-
A. Geist , PVM Parallel Virtual Machine, A User's Guide and Tutorial for Networked Parallel Computing ( MIT Press , Cambridge, Mass. , 1994 ) . Crossref, Google Scholar - Scientific Programming 12(3), 169 (2004). Crossref, ISI, Google Scholar
- Parallel Computing 24(14), 1947 (1998), DOI: 10.1016/S0167-8191(98)00093-3. Crossref, ISI, Google Scholar
- Future Generation Computer Systems 13(5), 327 (1998), DOI: 10.1016/S0167-739X(97)00034-4. Crossref, ISI, Google Scholar
- Algorithmica 24(4), 287 (1999), DOI: 10.1007/PL00008264. Crossref, ISI, Google Scholar
- R. Miller. Two Approaches to Architecture-Independent Parallel Computation. D.Phil thesis, Oxford University Computing Laboratory, 1994 . Google Scholar
- Scientific Computing 6(3), 249 (1997). ISI, Google Scholar
- M. Snir, S. W. Otto, S. Huss-Lederman, D. W. Walker, and J. Dongarra. MPI: The Complete Reference. Volume 1, The MPI-1 Core. MIT Press, Cambridge, MA, USA, second edition, Sept. 1998 . Google Scholar
- Communications of the ACM 33(8), 103 (1990), DOI: 10.1145/79173.79181. Crossref, ISI, Google Scholar
- ATLAS: http://math-atlas.sourceforge.net/ . Google Scholar
-
A. Zavanella and A. Milazzo , Predictability of Bulk Synchronous Programs Using MPI , Proc. 8th Workshop Euromicro PDF 2000 IEEE ( 2000 ) . Google Scholar - CGMLib: http://www.scs.carleton.ca/~cgm/ . Google Scholar
- PUB library: http://www.uni-paderborn.de/\~sp/ . Google Scholar
- The Oxford BSP Toolset: http://www.bsp-worldwide.org/implmnts/oxtool/ . Google Scholar


