Path Selection for Communicating Tasks in a Wormhole-Routed Multicomputer

In a multicomputer that uses wormhole routing or virtual cut-through circuit switching, the communication delay in sending a message between two processors along a path A increases significantly if the message is "blocked" by another message using one of the channels in path A. Such "blocking" can only occur if there is contention for a common channel by two or more paths. In this paper, we consider the problem of selecting contention-free or minimum-contention paths for a set of communicating tasks that have been mapped onto nodes in a multicomputer, This problem is formalized and shown to be an NPhard problem. thus, a heuristic solution is proposed for general static interconnection networks. Simulations results show that our method performs significantly better than alternative methods for this problem.