Path selection for message passing in a circuit-switched multicomputer

Abstract

This paper considers 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. Contention-free path selection results in guaranteed minimum communication delays for all messages sent along the selected paths-this is a particularly important in real-time applications. Minimum-contention path selection can achieve the same result if a small number of partitioned time intervals is used. However, both path selection problems can be shown to be NP-hard. Thus, a heuristic solution is proposed for general point-to-point interconnection networks. The quality of our solution is investigated by simulation on binary n-cube and torus interconnection networks, and it is shown that our method performs significantly better than alternative methods in the literature. (C) 1996 Academic Press, Inc.