Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments

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

doi:10.1145/1400751.1400825

Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	PODC'08
Subtitle of host publication	Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing
Publisher	Association for Computing Machinery
Pages	432
Number of pages	1
ISBN (Print)	9781595939890
DOIs	https://doi.org/10.1145/1400751.1400825
State	Published - 18 Aug 2008
Event	27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2008 - Toronto, ON, Canada Duration: 18 Aug 2008 → 21 Aug 2008

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference	27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2008
Country/Territory	Canada
City	Toronto, ON
Period	18/08/08 → 21/08/08

Keywords

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

Access to Document

10.1145/1400751.1400825

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 (pp. 432). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). Association for Computing Machinery. https://doi.org/10.1145/1400751.1400825

Gu, Yi ; Wu, Qishi ; Zhu, Mengxia et al. / Brief announcement : Efficient pipeline configuration in distributed heterogeneous computing environments. PODC'08: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2008. pp. 432 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

@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 Mengxia Zhu and Rao, \{Nageswara S.V.\}",

year = "2008",

month = aug,

day = "18",

doi = "10.1145/1400751.1400825",

language = "English",

isbn = "9781595939890",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "432",

booktitle = "PODC'08",

note = "27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2008 ; Conference date: 18-08-2008 Through 21-08-2008",

}

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. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 432, 27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2008, Toronto, ON, Canada, 18/08/08. https://doi.org/10.1145/1400751.1400825

Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments. / Gu, Yi; Wu, Qishi; Zhu, Mengxia et al.
PODC'08: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2008. p. 432 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Brief announcement

T2 - 27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2008

AU - Gu, Yi

AU - Wu, Qishi

AU - Zhu, Mengxia

AU - Rao, Nageswara S.V.

PY - 2008/8/18

Y1 - 2008/8/18

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 - https://www.scopus.com/pages/publications/57549112768

U2 - 10.1145/1400751.1400825

DO - 10.1145/1400751.1400825

M3 - Conference contribution

AN - SCOPUS:57549112768

SN - 9781595939890

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 432

BT - PODC'08

PB - Association for Computing Machinery

Y2 - 18 August 2008 through 21 August 2008

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. Association for Computing Machinery. 2008. p. 432. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). doi: 10.1145/1400751.1400825

Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this