Abstract
Large scale parallel programming projects may become heterogeneous in bothlanguage and architectural model. We propose that skeletal programmingtechniques can alleviate some of the costs involved in designing and portingsuch programs, illustrating our approach with a simple program which combinesshared memory and message passing code. We introduce Activity Graphs as asimple and practical means of capturing model independent aspects of theoperational semantics of skeletal parallel programs. They are independent oflow level details of parallel implementation and so can act as an intermediatelayer for compilation to diverse underlying models. Activity graphs providea notion of parallel activities, dependencies between activities, and theprocess groupings within which these take place. The compilation processuses a set of graph generators (templates) to derive the activity graph. Wedescribe simple schemes for transforming activity graphs into message passingprograms, targeting both MPI and BSP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Batcher, “Sorting networks and their applications,” in Proc. AFIPS Spring Joint Computer Conference, pp. 307–314, 1968.
O. Bonorden, B. Juurlink, I. von Otte, and I. Rieping, “The Paderborn University BSP (PUB) Library–design, implementation, and performance,” in Proceeding of 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP), 1999.
G. Botorog and H. Kuchen, “Efficient parallel programming with algorithmic skeltons,” in L. Bouge, P. Fraigniaud, A. Mignotte, and Y. Robert (eds.), Proceedings of EuroPar '96, Vol. 1123 of LNCS pp. 718–731, 1996.
M. Cole, Algorithmic Skeletons: Structured Management of Parallel Computation. Pitman, London, 1989.
M. Cole, “On dividing and conquering independently,” in Lecture Notes in Computer Science 1300, pp. 634–637, 1997.
J. Darlington, Y. Guo, H. To, and J. Yang, “Parallel skeletons for structured composition,” in Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 19–28, 1995.
I. Foster, J. Geisler, W. Gropp, N. Karonis, E. Lusk, G. Thiruvathukal, and S. Tuecke, “A widearea implementation of the message passing interface.” Parallel Computing 24(12), 1998.
I. Foster and C. Kesselman, 'Globus: A metacomputing infrastructure toolkit. International Journal of Supercomputing Applications 11(2), pp. 115–128, 1997.
I. Foster and C. Kesselman, The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, San Francisco, 1998.
J. Keller, C. Kessler, and J. Traff, Practical PRAM Programming. Wiley, New York, 2001 (to appear).
V. Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing. Benjamin Cummings, Redwood City, 1994.
S. Orlando, P. Palmerini, and R. Perego, “Coordinating HPF programs to mix task and data parallelism,” in Proceedings of 15th ACM Symposium on Applied Computing, 1, pp. 240–247, 2000.
S. Pelagatti and M. Danelutto, Structured Development of Parallel Programs. Taylor and Francis, 1997.
H. To, “Optimising the parallel behaviour of combinations of program components,” Ph.D. thesis, Department of Computing, Imperial College, 1995.
L. G. Valiant, “A bridging model for parallel computation.” Communications of the ACM 33(8), p. 103, 1990.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Cole, M., Zavanella, A. Coordinating Heterogeneous Parallel Systems with Skeletons and Activity Graphs. Journal of Systems Integration 10, 127–143 (2001). https://doi.org/10.1023/A:1011280825682
Issue Date:
DOI: https://doi.org/10.1023/A:1011280825682