Complexity analysis of pipeline mapping problems in distributed heterogeneous networks

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

Research output: Contribution to conferencePaper

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

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

    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.