Research On Exact Model And Complexity For Task Assignment Problem In Multi-core Environment

Task assignment problem (TAP) is an important problem in the area of parallel computing, whose goal is minimization of the total execution and communication cost. However, as the performance of computer hardware has been incredibly improved, multi-core became the mainstream, unprecedented challenges for traditional TAP are following. In multi-core clusters, we not only need to consider the inter-node communication cost, but also the intra-node communication cost (contains both inter-processor and inter-core communication). It has been proved that an average about 50% messages are transferred through intra-node communication. In this situation, we propose the task assignment problem in multi-core based system, whose goal is to minimize the total execution, inter-node communication and intra -node communication cost.The task assignment problem in multi-core based system is facing two kinds of challenges. One on side, the traditional task assignment problem is NP-hard problem, the task assignment problem in multi-core based system is more complicated, but is this new problem sure to be NP-hard problem? In the multi-core cluster, as the number of core is becoming more and more, the intra-node communication cost is becoming larger, will the changing in quantity lead to the changing in quality? That is to say, to make the NP-hard problem become the P problem? Such problems which have great significance are difficulties in the studying of the complexity theory. One the other side, the best exact solution of the traditional task assignment problem is obtained by the mathematical programming method. So on the research of the task assignment problem, how to establish the effective exact mathematical programming model? This paper focuses on these two challenges, and has finally gotten two original innovations.First, this paper studies the complexity of task assignment problem in multi-core based system. Moreover, we proved that 0-1TAP with interference cost is NPC for the first time, this conclusion keep true even when the communication graph is planar and bipartite.Second, by analyzing the effect of communication cost on the complexity of the problem, we come to an important conclusion: along with the increasing of the intra-node communication cost, this new NP-hard problem may become a P problem.At last, we use the integer programming theory to solve the TAP which considers both communication and interference. We established the integer nonlinear programming model for this problem for the first, and then, using the linear relaxation technology, we got two new integer linear programming model.