A MAPPING HEURISTIC FOR MINIMIZING NETWORK CONTENTION

The combinatorial optimization problem of assigning tasks of a paralle l program to processing nodes (gn's) of a parallel system is a well-kn own NP-hard problem. In this paper a new greedy heuristic for compile- time mapping of tasks without precedence constraints is proposed. The solution is addressed to modern multicomputers based on k-ary n-cube d irect interconnection networks exploiting the e-cube routing algorithm and the wormhole flow control strategy. The proposed algorithm takes into account communication delays due to network blocking of colliding messages. Results achieved on several program-derived graphs with up to 784 tasks demonstrate the effectiveness of the approach followed. ( C) 1998 Elsevier Science B.V. All rights reserved.