article

Bsp2omp: A Compiler For Translating Bsp Programs To Openmp

Author:

Ami MarowkaAuthors Info & Claims

International Journal of Parallel, Emergent and Distributed Systems, Volume 24, Issue 4

Pages 293 - 310

https://doi.org/10.1080/17445760902719927

Published: 01 August 2009 Publication History

Abstract

The convergence of the two widely used parallel programming paradigms, shared-memory and distributed-shared-memory parallel programming models, into a unified parallel programming model is crucial for parallel computing to become the next mainstream programming paradigm. We study the design differences and the performance issues of two parallel programming models: a shared-memory programming model (OpenMP) and a distributed-shared programming model (BSP). The study was carried out by designing a compiler for translating BSP parallel programs to an OpenMP programming model called BSP2OMP. Analysis of the compiler outcome, and of the performance of the compiled programs, show that the two models are based on very similar underlying principles and mechanisms.

References

[1]

Asanovic, K., Bodik, R., Catanzaro, B. C., Gebis, J. J., Husbands, P., Keutzer, K., Patterson, D. A., Plishker, W. L., Shalf, J., Williams, S. W. and Yolick, K. A. The landscape of parallel computing research: A view from Berkeley.

[2]

Bailey, D. H. (1990) FFTs in external or hierarchical memory. J. Supercomput., 4:1, pp. 23-35.

Digital Library

[3]

Bell, C., Chen, W., Bonachea, D. and Yelick, K. (2004) Evaluating support for global address space languages on the Cray X1. Proceeding of ICS

[4]

Berlin, K., Huan, J., Jacob, M., Kochhar, G., Prins, J., Pugh, W., Sadayappan, P., Spacco, J. and Tseng, C. W. (2003) Evaluating the impact of programming language features on the performance of parallel applications on cluster architectures. Proceeding of 16th International Workshop, LCPC, College Station, TX, USA, October 2-4

[5]

Bircsak, J., Craig, P., Crowell, R., Cvetanovic, Z., Harris, J., Nelson, C. A. and Offner, C. D. (2000) Extending OpenMP for NUMA machines. Sci. Program., 8:3, pp. 163-181.

Digital Library

[6]

Bissling, R. H. (2004) Parallel Scientific Computation: A Structured Approach Using BSP and MPI, Oxford Press, New York

[7]

Brieger, L. (2000) HPF to OpenMP on the Origin2000: A case study. Concurr. Pract. Exp., 12:12, pp. 1147-1154.

[8]

Bull, J. M. and O'Neill, D. (2001) Microbenchmark suite for OpenMP 2.0. Proceedings of the Third European Workshop on OpenMP (EWOMP'01), Barcelona, Spain. pp. 41-48.

[9]

Cantonnet, F., Yao, Y., Annareddy, S., Mohamed, A. S. and El-Ghazawi, T. (2003) Performance monitoring and evaluation of a UPC implementation on a NUMA architecture. Proceeding of IPDPS, Nice, France. pp. 22-26.

[10]

Cantonnet, F., Yao, Y., Zahran, M. and El-Ghazawi, T. (2004) Productivity analysis of the UPC language. Proceeding of IPDPS, Santa Fe, New Mexico, USA

[11]

Cappello, F., Richard, O. and Etiemble, D. (1999) Performance of the NAS benchmarks on a cluster of SMP PCs using a parallelization of the MPI programs with OpenMP. 5th International Conference, PaCT-99. Proceedings (Lecture Notes in Computer Science Vol. 1662), pp. 339-350. Springer-Verlag, Berlin, Germany

[12]

Chen, W., Bonachea, D., Duell, J., Husbands, P., Iancu, C. and Yelick, K. (2003) Performance analysis of the Berkeley UPC Compiler. Proceeding of ICS03, June 23-26, San Francisco, California, USA

[13]

Cooley, J. W. and Tukey, J. W. (1965) An algorithm for the machine calculation of complex Fourier series. Math. Comput., 19, pp. 297-301.

[14]

Dorta, A. J., Rodriguez, C. and de Sande, F. (2005) The OpenMP source code repository. IEEE proceeding of 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing, (PDP 2005), pp. 244-250.

[15]

Hill, J. M. D., Crumpton, P. I. and Burgess, D. A. (1996) The theory, practice, and a tool for BSP performance prediction. EuroPar'96, number 1124 in LNCS. pp. 697-705. Springer-Verlag, New York, NY

[16]

Hill, J. M. D., McColl, B., Stefanescu, D. C., Goudreau, M. W., Lang, K., Rao, S. B., Suel, T., Tsantilas, T. and Bissling, R. H. (1998) BSPlib: The BSP programming library. Parallel Comput., 24, pp. 1947-1980.

Digital Library

[17]

Hockney, R. W. (1991) Performance parameters and benchmarking of supercomputers. Parallel Comput., 17, pp. 1111-1130.

Digital Library

[18]

Mark Bull, J. (1999) Measuring synchronisation and scheduling overheads in OpenMP. Proceeding of First European Workshop on OpenMP (EWOMP '99), Lund, Sweden

[19]

Marowka, A. (2003) Extending OpenMP for task parallelism. Parallel Process. Lett., 13:3, pp. 341-352.

[20]

Marowka, A. (2005) Execution model of three parallel languages: OpenMP, UPC and CAF. Sci. Program., 13:2, pp. 127-135.

Digital Library

[21]

Marowka, A. (2007) Parallel computing on any desktop. Commun. ACM, 50:9, pp. 74-78.

Digital Library

[22]

Marowka, A. (2008) BSP2OMP: A compiler for translating BSP programs to OpenMP. 10th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), IEEE Proceeding of IPDPS'08, Miami, USA, April 14-18

[23]

Marowka, A. (2008) Performance of OpenMP benchmarks on multicore processors. 8th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP), LNCS proceeding, Agia Napa, Cyprus, June 9-11. 5022, pp. 208-219.

[24]

Marowka, A., Liu, Z. and Chapman, B. (2004) OpenMP-oriented applications for distributed shared memory architectures. Concurr. Comput. Practice Exp., 16:4, pp. 371-384.

Digital Library

[25]

Mendelson, A., Mandelblat, J., Gochman, S., Shemer, A., Chabukswar, R., Niemeyer, E. and Kumar, A. (2006) CMP implementation in systems based on the Intel&#174; Core&#8482; Duo Processor. Intel&#174; Technol. J., 10:2, pp. 99-108.

[26]

Merlin, J., Miles, D. and Schuster, V. (2000) Distributed OMP: Extensions to OpenMP for SMP clusters. EWOMP 2000, Second European Workshop on OpenMP, Edinburgh, Scotland, U.K., September 14-15

[27]

Skillicorn, D. B., Hill, J. M. D. and McColl, W. F. (1997) Questions and answers about BSP. J. Sci. Program., 6:3, pp. 249-274.

[28]

Smith, L. and Kent, P. (2000) Development and performance of a mixed OpenMP/MPI quantum Monte Carlo code. Concurr. Pract. Exp., 12:12, pp. 1121-1129.

[29]

Sosa, C. P., Scalmani, C., Gomperts, R. and Frisch, M. J. (2000) Ab initio quantum chemistry on a ccNUMA architecture using OpenMP. Parallel Comput., 26:7, pp. 843-856.

Digital Library

[30]

Sutter, H. (2005) The free lunch is over: A fundamental turn toward concurrency in software. Dr. Dobb's J., 30:3, pp. 202-210.

[31]

Valiant, L. G. (1990) A bridging model for parallel computation. Commun. ACM, 33:8, pp. 103-111.

Digital Library

[32]

Valiant, L. G. (1982) A scheme for fast parallel communication. SIAM J. Comput., 11, pp. 350-361.

Digital Library

Cited By

Krieger CStone AStrout M(2010)Mechanisms that separate algorithms from implementations for parallel patternsProceedings of the 2010 Workshop on Parallel Programming Patterns10.1145/1953611.1953622(1-12)Online publication date: 30-Mar-2010
https://dl.acm.org/doi/10.1145/1953611.1953622

Bsp2omp: A Compiler For Translating Bsp Programs To Openmp

Recommendations

Teaching Parallel Computing Concepts with OpenMP (Abstract Only)
SIGCSE '16: Proceedings of the 47th ACM Technical Symposium on Computing Science Education

OpenMP is an industry-standard, platform-independent parallel programming library built into all modern C and C++ compilers. Unlike complex parallel platforms, OpenMP is designed to make it relatively easy to add parallelism to existing sequential ...
Teaching shared memory parallel concepts with OpenMP (abstract only)
SIGCSE '14: Proceedings of the 45th ACM technical symposium on Computer science education

Curriculum 2013 brings parallelism into the CS curricular mainstream. This hands-on workshop is intended for faculty with little or no background in parallel computing. OpenMP is a platform independent, industry-standard library for shared-memory ...
Performance-based parallel loop self-scheduling using hybrid OpenMP and MPI programming on multicore SMP clusters

Parallel loop self-scheduling on parallel and distributed systems has been a critical problem and it is becoming more difficult to deal with in the emerging heterogeneous cluster computing environments. In the past, some self-scheduling schemes have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Parallel, Emergent and Distributed Systems

International Journal of Parallel, Emergent and Distributed Systems Volume 24, Issue 4

Advances in Parallel and Distributed Computational Models

August 2009

92 pages

ISSN:1744-5760

EISSN:1744-5779

Issue’s Table of Contents

Publisher

Taylor & Francis, Inc.

United States

Publication History

Published: 01 August 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Krieger CStone AStrout M(2010)Mechanisms that separate algorithms from implementations for parallel patternsProceedings of the 2010 Workshop on Parallel Programming Patterns10.1145/1953611.1953622(1-12)Online publication date: 30-Mar-2010
https://dl.acm.org/doi/10.1145/1953611.1953622

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents