Abstract
We describe the use of the BSP cost model to optimise programs, based on skeletons or data-parallel operations, in which program components may have multiple implementations. BSP’s view of communication transforms the problem of finding the best implementation choice for each component into a one-dimensional minimisation problem. A shortest-path algorithm that finds optimal implementations in time linear in the number of operations of the program is given.
Chapter PDF
References
B. Bacci, B. Cantalupo, M. Danelutto, S. Orlando, D. Pasetto, S. Pelagatti, and M. Vanneschi. An environment for structured parallel programming. In L. Grandinetti, M. Kowalick, and M. Vaitersic, editors, Advances in High Performance Computing, pages 219–234. Kluwer, Dordrecht, The Netherlands, 1997.
Z. Bozkus, A. Choudhary, G. Fox, T. Haupt, S. Ranka, and M.-Y. Wu. Compiling Fortran 90D/HPF for distributed memory MIMD computers. Journal of Parallel and Distributed Computing, 21(1):15–26, April 1994.
S. Ciarpaglini, M. Danelutto, L. Folchi, C. Manconi, and S. Pelagatti. ANACLETO: a template-based p3l compiler. In Proceedings of the Seventh Parallel Computing Workshop (PCW ’97), Australian National University, Canberra, 1997.
M. Danelutto, F. Pasqualetti, and S. Pelagatti. Skeletons for data parallelism in p3l. In C. Lengauer, M. Griebl, and S. Gorlatch, editors, Proc. of EURO-PAR ’97, Passau, Germany, volume 1300 of LNCS, pages 619–628. Springer-Verlag, August 1997.
S. Pelagatti. Structured development of parallel programs. Taylor&Francis, London, 1997.
T. Rauber and G. Rünger. Deriving structured parallel implementations for numerical methods. The Euromicro Journal, (41):589–608, 1996.
D.B. Skillicorn, J.M.D. Hill, and W.F. McColl. Questions and answers about BSP. Scientific Programming, 6(3):249–274, 1997.
H.W. To. Optimising the Parallel Behaviour of Combinations of Program Components. PhD thesis, Imperial College, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Skillicorn, D.B., Danelutto, M., Pelagatti, S., Zavanella, A. (1998). Optimising data-parallel programs using the BSP cost model. In: Pritchard, D., Reeve, J. (eds) Euro-Par’98 Parallel Processing. Euro-Par 1998. Lecture Notes in Computer Science, vol 1470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0057918
Download citation
DOI: https://doi.org/10.1007/BFb0057918
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64952-6
Online ISBN: 978-3-540-49920-6
eBook Packages: Springer Book Archive