Complexity analysis of pipeline mapping problems in distributed heterogeneous networks

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

Research output: Contribution to conferencePaperpeer-review

5 Scopus citations

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 - 2008
EventInternational Symposium on Advances in Computer and Sensor Networks and Systems, 2008 - Zhengzhou, China
Duration: Apr 7 2008Apr 11 2008

Conference

ConferenceInternational Symposium on Advances in Computer and Sensor Networks and Systems, 2008
Country/TerritoryChina
CityZhengzhou
Period04/7/0804/11/08

Keywords

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

Fingerprint

Dive into the research topics of 'Complexity analysis of pipeline mapping problems in distributed heterogeneous networks'. Together they form a unique fingerprint.

Cite this