Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments

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

Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments

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

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

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 (US)
Title of host publication	PODC'08
Subtitle of host publication	Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing
Number of pages	1
State	Published - Dec 17 2008
Externally published	Yes
Event	27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing - Toronto, ON, Canada Duration: Aug 18 2008 → Aug 21 2008

Other

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

All Science Journal Classification (ASJC) codes

Software
Hardware and Architecture
Computer Networks and Communications

Cite this

@inproceedings{2c9de7547c0d427d8d10d29177581549,

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.",

author = "Yi Gu and Chase Wu and Mengxia Zhu and Rao, {Nageswara S.V.}",

year = "2008",

month = dec,

day = "17",

language = "English (US)",

isbn = "9781595939890",

booktitle = "PODC'08",

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

}

TY - GEN

T1 - Brief announcement

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

AU - Gu, Yi

AU - Wu, Chase

AU - Zhu, Mengxia

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.

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

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

M3 - Conference contribution

AN - SCOPUS:57549112768

SN - 9781595939890

BT - PODC'08

Y2 - 18 August 2008 through 21 August 2008

ER -

Brief announcement: Efficient pipeline configuration in distributed heterogeneous computing environments

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this