Brief announcement

Efficient pipeline configuration in distributed heterogeneous computing environments

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

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

3 Citations (Scopus)

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
Number of pages1
StatePublished - 17 Dec 2008
Event27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing - Toronto, ON, Canada
Duration: 18 Aug 200821 Aug 2008

Other

Other27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
CountryCanada
CityToronto, ON
Period18/08/0821/08/08

Fingerprint

Heuristic algorithms
Dynamic programming
Pipelines

Keywords

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

Cite this

Gu, Y., Wu, Q., Zhu, M., & Rao, N. S. V. (2008). Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments. In PODC'08: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing
Gu, Yi ; Wu, Qishi ; Zhu, Michelle ; Rao, Nageswara S.V. / Brief announcement : Efficient pipeline configuration in distributed heterogeneous computing environments. PODC'08: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing. 2008.
@inproceedings{886dd3de5f564ffdbc48f74d4dff5fae,
title = "Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments",
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.",
keywords = "Heuristic algorithm, Maximum frame rate, Minimum end-to-end delay, NP-complete, Optimization problem",
author = "Yi Gu and Qishi Wu and Michelle Zhu and Rao, {Nageswara S.V.}",
year = "2008",
month = "12",
day = "17",
language = "English",
isbn = "9781595939890",
booktitle = "PODC'08",

}

Gu, Y, Wu, Q, Zhu, M & Rao, NSV 2008, Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments. in PODC'08: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing. 27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Toronto, ON, Canada, 18/08/08.

Brief announcement : Efficient pipeline configuration in distributed heterogeneous computing environments. / Gu, Yi; Wu, Qishi; Zhu, Michelle; Rao, Nageswara S.V.

PODC'08: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing. 2008.

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

TY - GEN

T1 - Brief announcement

T2 - Efficient pipeline configuration in distributed heterogeneous computing environments

AU - Gu, Yi

AU - Wu, Qishi

AU - Zhu, Michelle

AU - Rao, Nageswara S.V.

PY - 2008/12/17

Y1 - 2008/12/17

N2 - 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.

AB - 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.

KW - Heuristic algorithm

KW - Maximum frame rate

KW - Minimum end-to-end delay

KW - NP-complete

KW - Optimization problem

UR - http://www.scopus.com/inward/record.url?scp=57549112768&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9781595939890

BT - PODC'08

ER -

Gu Y, Wu Q, Zhu M, Rao NSV. Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments. In PODC'08: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing. 2008