Minimizing network contention for mapping tasks onto massively parallel computers

This paper presents a new framework aimed at compile-time determination of satisfactory sub-optimal solutions to the mapping problem onto modern massively parallel computing systems. The approach incorporates realistic assumptions on the models both for parallel programs and target architectures. It is refined for the K-ary n-cube family of processor networks that use a deterministic routing algorithm and the wormhole flow control strategy. The proposed mapping heuristic is guided by an evaluation function that approximates the total completion time of a given assignment by taking into account communication delays caused by network contention which are the major contributors to message latencies when network traffic is heavy or unevenly distributed. Results achieved on several program-derived graphs with up to 784 tasks prove the effectiveness of this approach