World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on High-Level Parallel Programming and ApplicationsNo Access

EXPERIMENTAL EVALUATION OF BSP PROGRAMMING LIBRARIES

    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 Scholar
    • G. Bilardiet al., 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 ) . CrossrefGoogle Scholar
    • V. Blancoet al., Parallel Comput. 30(3), 337 (2004), DOI: 10.1016/j.parco.2003.11.004. Crossref, ISIGoogle Scholar
    • O. Bonordenet al., Parallel Computing 29(2), 187 (2003), DOI: 10.1016/S0167-8191(02)00218-1. Crossref, ISIGoogle 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
    • J. J. Dongarraet al., ACM Transactions on Mathematical Software 16(1), 1 (1990), DOI: 10.1145/77626.79170. Crossref, ISIGoogle 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 et al. , PVM Parallel Virtual Machine, A User's Guide and Tutorial for Networked Parallel Computing ( MIT Press , Cambridge, Mass. , 1994 ) . CrossrefGoogle Scholar
    • A. V. Gerbessiotis and S. Y. Lee, Scientific Programming 12(3), 169 (2004). Crossref, ISIGoogle Scholar
    • J. M. D. Hillet al., Parallel Computing 24(14), 1947 (1998), DOI: 10.1016/S0167-8191(98)00093-3. Crossref, ISIGoogle Scholar
    • J. M. D. Hill and D. B. Skillicorn, Future Generation Computer Systems 13(5), 327 (1998), DOI: 10.1016/S0167-739X(97)00034-4. Crossref, ISIGoogle Scholar
    • W. F. McColl and A. Tiskin, Algorithmica 24(4), 287 (1999), DOI: 10.1007/PL00008264. Crossref, ISIGoogle Scholar
    • R. Miller. Two Approaches to Architecture-Independent Parallel Computation. D.Phil thesis, Oxford University Computing Laboratory, 1994 . Google Scholar
    • D. Skillicorn, J. Hill and W. McColl, Scientific Computing 6(3), 249 (1997). ISIGoogle 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
    • L. G. Valiant, Communications of the ACM 33(8), 103 (1990), DOI: 10.1145/79173.79181. Crossref, ISIGoogle 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