Design, Implementation and Evaluation of a Deadlock-Free Routing Algorithm for Concurrent Computers

This paper describes the design, the implementation, and the performance results of a routing algorithm which provides deadlock-free communication in a tightly coupled message-passing concurrent computer. The algorithm is adaptive, isolated and uses the store-and-forward technique. It allows message communication between two processes regardless of where they are physically located on the network. The routing algorithm has many positive characteristics including provable deadlock freedom, guaranteed message arrival, and automatic local congestion reduction. It can be used as a basis for the design of high-level communication primitives. An Occam implementation on a network of inmos Transputers is discussed. The experimental results show that the routing algorithm is effective to support process to process communication on a concurrent computer.