Premium
Pipelines on heterogeneous systems: models and tools
Author(s) -
Almeida F.,
Gonzalez D.,
Moreno L. M.,
Rodriguez C.
Publication year - 2005
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.886
Subject(s) - pipeline transport , pipeline (software) , computer science , block (permutation group theory) , computational complexity theory , distributed computing , heterogeneous network , algorithm , mathematics , engineering , wireless network , telecommunications , geometry , environmental engineering , wireless , programming language
We study the performance of pipeline algorithms in heterogeneous networks. The concept of heterogeneity is not only restricted to the differences in computational power of the nodes, but also refers to the network capabilities. We develop a skeleton tool that allows us an efficient block‐cyclic mapping of pipelines on heterogeneous systems. The tool supports pipelines with a number of stages much larger than the number of physical processors available. We derive an analytical formula that allows us to predict the performance of pipelines in heterogeneous systems. According to the analytical complexity formula, numerical strategies to solve the optimal mapping problem are proposed. The computational results prove the accuracy of the predictions and effectiveness of the approach. Copyright © 2005 John Wiley & Sons, Ltd.