Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments

Yi Gu, Qishi Wu, Mengxia Zhu, Nageswara S.V. Rao

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

We consider six classes of linear pipeline configuration problems with different mapping objectives and network constraints in distributed heterogeneous computing environments. We prove that two of them are polynomially solvable and the rest are NP-complete, for each of which, an optimal or heuristic algorithm based on dynamic programming is designed. Extensive simulation results illustrate the efficacy of these algorithms in comparison with existing methods.

Original languageEnglish
Title of host publicationPODC'08
Subtitle of host publicationProceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing
Pages432
Number of pages1
StatePublished - 2008
Event27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing - Toronto, ON, Canada
Duration: Aug 18 2008Aug 21 2008

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
Country/TerritoryCanada
CityToronto, ON
Period08/18/0808/21/08

Keywords

  • Heuristic algorithm
  • Maximum frame rate
  • Minimum end-to-end delay
  • NP-complete
  • Optimization problem

Fingerprint

Dive into the research topics of 'Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments'. Together they form a unique fingerprint.

Cite this