Complexity analysis of new task allocation problem using network flow method on multicore clusters (Q1719030)

Summary: The task allocation problem (TAP) generally aims to minimize total execution cost and internode communication cost in traditional parallel computing systems. New TAP (NTAP) considering additive intranode communication cost in emerging multicore cluster systems is investigated in this paper. We analyze the complexity of NTAP with network flow method and conclude that the intranode communication cost is a key to the complexity of NTAP, and prove that (1) the NTAP can be cast as a generalized linear network minimum cost flow problem and can be solved in \(O(m^2 n^4)\) time if the intranode communication cost equals the internode communication cost, and (2) the NTAP can be cast as a generalized convex cost network minimum cost flow problem and can be solved in polynomial time if the intranode communication cost is more than the internode communication cost. More in particular, the uniform cost NTAP can be cast as a convex cost flow problem and can be solved in \(O(m^2 n^2 \log(m + n))\) time. Furthermore, solutions to the NTAP are also discussed. Our work extends currently known theoretical results and the theorems and conclusions presented in this paper can provide theoretical basis for task allocating strategies on multicore clusters.