Optimizing end-to-end performance of distributed applications with linear computing pipelines

Yi Gu, Qishi Wu, Anne Benoit, Yves Robert

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationICPADS '09 - 15th International Conference on Parallel and Distributed Systems
Pages252-259
Number of pages8
DOIs
StatePublished - 2009
Externally publishedYes
Event15th International Conference on Parallel and Distributed Systems, ICPADS '09 - Shenzhen, Guangdong, China
Duration: Dec 8 2009Dec 11 2009

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
ISSN (Print)1521-9097

Other

Other15th International Conference on Parallel and Distributed Systems, ICPADS '09
Country/TerritoryChina
CityShenzhen, Guangdong
Period12/8/0912/11/09

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Keywords

  • End-to-end delay
  • Frame rate
  • NP-complete

Fingerprint

Dive into the research topics of 'Optimizing end-to-end performance of distributed applications with linear computing pipelines'. Together they form a unique fingerprint.

Cite this