Complexity analysis of pipeline mapping problems in distributed heterogeneous networks

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.