TY - GEN
T1 - Optimizing end-to-end performance of distributed applications with linear computing pipelines
AU - Gu, Yi
AU - Wu, Qishi
AU - Benoit, Anne
AU - Robert, Yves
PY - 2009
Y1 - 2009
N2 - Supporting high-performance computing pipelines in wide-area networks is crucial to enabling large-scale distributed scientific applications that require minimizing end-to-end delay for fast user interaction or maximizing frame rate for smooth data flow. We formulate and categorize the linear pipeline configuration problems into six classes with two mapping objectives, i.e. minimum end-to-end delay and maximum frame rate, and three network constraints, i.e. no, contiguous, and arbitrary node reuse. We design a dynamic programming-based optimal solution to the problem of minimum end-to-end delay with arbitrary node reuse and prove the NP-completeness of the rest five problems, for each of which, a heuristic algorithm based on a similar optimization procedure is proposed. These heuristics are implemented and tested on a large set of simulated networks of various scales and their performance superiorities are illustrated by extensive experimental results in comparison with existing methods.
AB - Supporting high-performance computing pipelines in wide-area networks is crucial to enabling large-scale distributed scientific applications that require minimizing end-to-end delay for fast user interaction or maximizing frame rate for smooth data flow. We formulate and categorize the linear pipeline configuration problems into six classes with two mapping objectives, i.e. minimum end-to-end delay and maximum frame rate, and three network constraints, i.e. no, contiguous, and arbitrary node reuse. We design a dynamic programming-based optimal solution to the problem of minimum end-to-end delay with arbitrary node reuse and prove the NP-completeness of the rest five problems, for each of which, a heuristic algorithm based on a similar optimization procedure is proposed. These heuristics are implemented and tested on a large set of simulated networks of various scales and their performance superiorities are illustrated by extensive experimental results in comparison with existing methods.
KW - End-to-end delay
KW - Frame rate
KW - NP-complete
UR - http://www.scopus.com/inward/record.url?scp=77949577465&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77949577465&partnerID=8YFLogxK
U2 - 10.1109/ICPADS.2009.18
DO - 10.1109/ICPADS.2009.18
M3 - Conference contribution
AN - SCOPUS:77949577465
SN - 9780769539003
T3 - Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
SP - 252
EP - 259
BT - ICPADS '09 - 15th International Conference on Parallel and Distributed Systems
T2 - 15th International Conference on Parallel and Distributed Systems, ICPADS '09
Y2 - 8 December 2009 through 11 December 2009
ER -