Abstract
Mapping applications onto parallel platforms is a challenging problem, that becomes even more difficult when platforms are heterogeneous –nowadays a standard assumption. A high-level approach to parallel programming not only eases the application developer’s task, but it also provides additional information which can help realize an efficient mapping of the application. In this paper, we discuss the mapping of pipeline skeletons onto different types of platforms (from fully homogeneous to heterogeneous). We assume that a pipeline stage must be mapped on a single processor, and we establish new theoretical complexity results for two different mapping policies: a mapping can be either one-to-one (at most one stage per processor), or interval-based (interval of consecutive stages per processor). We provide several efficient polynomial heuristics for the most important policy/platform combination, namely interval-based mappings on platforms with identical communication links but different speed processors.
Chapter PDF
Similar content being viewed by others
Keywords
References
Benoit, A., Robert, Y.: Mapping pipeline skeletons onto heterogeneous platforms. Research Report 2007-05, LIP, ENS Lyon, France (2007), available at http://graal.ens-lyon.fr/~yrobert/
Bhat, P., Raghavendra, C., Prasanna, V.: Efficient collective communication in distributed heterogeneous systems. Journal of Parallel and Distributed Computing 63, 251–263 (2003)
Bokhari, S.H.: Partitioning problems in parallel, pipeline, and distributed computing. IEEE Trans. Computers 37(1), 48–57 (1988)
Cole, M.: Bringing Skeletons out of the Closet: A Pragmatic Manifesto for Skeletal Parallel Programming. Parallel Computing 30(3), 389–406 (2004)
Pinar, A., Aykanat, C.: Fast optimal load balancing algorithms for 1D partitioning. J. Parallel Distributed Computing 64(8), 974–996 (2004)
Rabhi, F., Gorlatch, S.: Patterns and Skeletons for Parallel and Distributed Computing. Springer, Heidelberg (2002)
Saif, T., Parashar, M.: Understanding the behavior and performance of non-blocking communications in MPI. In: Danelutto, M., Vanneschi, M., Laforenza, D. (eds.) Euro-Par 2004. LNCS, vol. 3149, pp. 173–182. Springer, Heidelberg (2004)
Shirazi, B.A., Hurson, A.R., Kavi, K.M.: Scheduling and load balancing in parallel and distributed systems. IEEE Computer Society Press, Los Alamitos (1995)
Subhlok, J., Vondran, G.: Optimal mapping of sequences of data parallel tasks. In: Proc. 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP’95, pp. 134–143. ACM Press, New York (1995)
Subhlok, J., Vondran, G.: Optimal latency-throughput tradeoffs for data parallel pipelines. In: ACM Symposium on Parallel Algorithms and Architectures SPAA’96, pp. 62–71. ACM Press, New York (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Benoit, A., Robert, Y. (2007). Mapping Pipeline Skeletons onto Heterogeneous Platforms. In: Shi, Y., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds) Computational Science – ICCS 2007. ICCS 2007. Lecture Notes in Computer Science, vol 4487. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72584-8_78
Download citation
DOI: https://doi.org/10.1007/978-3-540-72584-8_78
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72583-1
Online ISBN: 978-3-540-72584-8
eBook Packages: Computer ScienceComputer Science (R0)