Complexity analysis of pipeline mapping problems in distributed heterogeneous networks

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

Research output: Contribution to conferencePaper

5 Citations (Scopus)

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 interactive user operations or maximizing frame rate for streaming data processing. The study on the computational complexity of pipeline mapping in distributed heterogeneous networks is of both theoretical significance and practical importance. We formulate and categorize the linear pipeline mapping problems into six classes with different mapping objectives and network constraints: (i) Minimum End-to-end Delay with No Node Reuse (MED-NNR), (ii) Minimum Endto-end Delay with Contiguous Node Reuse (MED-CNR), (iii) Minimum End-to-end Delay with Arbitrary Node Reuse (MED-ANR), (iv) Maximum Frame Rate with No Node Reuse or Share (MFR-NNRS), (v) Maximum Frame Rate with Contiguous Node Reuse and Share (MFR-CNRS), and (vi) Maximum Frame Rate with Arbitrary Node Reuse and Share (MFR-ANRS). We design polynomial-time optimal solutions to MED-CNR and MED-ANR, and prove the NP-completeness for the rest.

Original languageEnglish
StatePublished - 1 Jan 2008
EventInternational Symposium on Advances in Computer and Sensor Networks and Systems, 2008 - Zhengzhou, China
Duration: 7 Apr 200811 Apr 2008

Other

OtherInternational Symposium on Advances in Computer and Sensor Networks and Systems, 2008
CountryChina
CityZhengzhou
Period7/04/0811/04/08

Fingerprint

Heterogeneous networks
Pipelines
Wide area networks
Computational complexity
Polynomials

Keywords

  • Computational complexity
  • Maximum frame rate
  • Minimum endto-end delay
  • NP-complete
  • Pipeline mapping

Cite this

Gu, Y., Wu, Q., Zhu, M., & Rao, N. S. V. (2008). Complexity analysis of pipeline mapping problems in distributed heterogeneous networks. Paper presented at International Symposium on Advances in Computer and Sensor Networks and Systems, 2008, Zhengzhou, China.
Gu, Yi ; Wu, Qishi ; Zhu, Michelle ; Rao, Nageswara S.V. / Complexity analysis of pipeline mapping problems in distributed heterogeneous networks. Paper presented at International Symposium on Advances in Computer and Sensor Networks and Systems, 2008, Zhengzhou, China.
@conference{43fb14cb780144458177cd884d6d2302,
title = "Complexity analysis of pipeline mapping problems in distributed heterogeneous networks",
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 interactive user operations or maximizing frame rate for streaming data processing. The study on the computational complexity of pipeline mapping in distributed heterogeneous networks is of both theoretical significance and practical importance. We formulate and categorize the linear pipeline mapping problems into six classes with different mapping objectives and network constraints: (i) Minimum End-to-end Delay with No Node Reuse (MED-NNR), (ii) Minimum Endto-end Delay with Contiguous Node Reuse (MED-CNR), (iii) Minimum End-to-end Delay with Arbitrary Node Reuse (MED-ANR), (iv) Maximum Frame Rate with No Node Reuse or Share (MFR-NNRS), (v) Maximum Frame Rate with Contiguous Node Reuse and Share (MFR-CNRS), and (vi) Maximum Frame Rate with Arbitrary Node Reuse and Share (MFR-ANRS). We design polynomial-time optimal solutions to MED-CNR and MED-ANR, and prove the NP-completeness for the rest.",
keywords = "Computational complexity, Maximum frame rate, Minimum endto-end delay, NP-complete, Pipeline mapping",
author = "Yi Gu and Qishi Wu and Michelle Zhu and Rao, {Nageswara S.V.}",
year = "2008",
month = "1",
day = "1",
language = "English",
note = "null ; Conference date: 07-04-2008 Through 11-04-2008",

}

Gu, Y, Wu, Q, Zhu, M & Rao, NSV 2008, 'Complexity analysis of pipeline mapping problems in distributed heterogeneous networks' Paper presented at International Symposium on Advances in Computer and Sensor Networks and Systems, 2008, Zhengzhou, China, 7/04/08 - 11/04/08, .

Complexity analysis of pipeline mapping problems in distributed heterogeneous networks. / Gu, Yi; Wu, Qishi; Zhu, Michelle; Rao, Nageswara S.V.

2008. Paper presented at International Symposium on Advances in Computer and Sensor Networks and Systems, 2008, Zhengzhou, China.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Complexity analysis of pipeline mapping problems in distributed heterogeneous networks

AU - Gu, Yi

AU - Wu, Qishi

AU - Zhu, Michelle

AU - Rao, Nageswara S.V.

PY - 2008/1/1

Y1 - 2008/1/1

N2 - 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 interactive user operations or maximizing frame rate for streaming data processing. The study on the computational complexity of pipeline mapping in distributed heterogeneous networks is of both theoretical significance and practical importance. We formulate and categorize the linear pipeline mapping problems into six classes with different mapping objectives and network constraints: (i) Minimum End-to-end Delay with No Node Reuse (MED-NNR), (ii) Minimum Endto-end Delay with Contiguous Node Reuse (MED-CNR), (iii) Minimum End-to-end Delay with Arbitrary Node Reuse (MED-ANR), (iv) Maximum Frame Rate with No Node Reuse or Share (MFR-NNRS), (v) Maximum Frame Rate with Contiguous Node Reuse and Share (MFR-CNRS), and (vi) Maximum Frame Rate with Arbitrary Node Reuse and Share (MFR-ANRS). We design polynomial-time optimal solutions to MED-CNR and MED-ANR, and prove the NP-completeness for the rest.

AB - 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 interactive user operations or maximizing frame rate for streaming data processing. The study on the computational complexity of pipeline mapping in distributed heterogeneous networks is of both theoretical significance and practical importance. We formulate and categorize the linear pipeline mapping problems into six classes with different mapping objectives and network constraints: (i) Minimum End-to-end Delay with No Node Reuse (MED-NNR), (ii) Minimum Endto-end Delay with Contiguous Node Reuse (MED-CNR), (iii) Minimum End-to-end Delay with Arbitrary Node Reuse (MED-ANR), (iv) Maximum Frame Rate with No Node Reuse or Share (MFR-NNRS), (v) Maximum Frame Rate with Contiguous Node Reuse and Share (MFR-CNRS), and (vi) Maximum Frame Rate with Arbitrary Node Reuse and Share (MFR-ANRS). We design polynomial-time optimal solutions to MED-CNR and MED-ANR, and prove the NP-completeness for the rest.

KW - Computational complexity

KW - Maximum frame rate

KW - Minimum endto-end delay

KW - NP-complete

KW - Pipeline mapping

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

M3 - Paper

AN - SCOPUS:84899146351

ER -

Gu Y, Wu Q, Zhu M, Rao NSV. Complexity analysis of pipeline mapping problems in distributed heterogeneous networks. 2008. Paper presented at International Symposium on Advances in Computer and Sensor Networks and Systems, 2008, Zhengzhou, China.