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 language | English |
---|---|
State | Published - 2008 |
Event | International Symposium on Advances in Computer and Sensor Networks and Systems, 2008 - Zhengzhou, China Duration: Apr 7 2008 → Apr 11 2008 |
Conference
Conference | International Symposium on Advances in Computer and Sensor Networks and Systems, 2008 |
---|---|
Country/Territory | China |
City | Zhengzhou |
Period | 04/7/08 → 04/11/08 |
Keywords
- Computational complexity
- Maximum frame rate
- Minimum endto-end delay
- NP-complete
- Pipeline mapping