An efficient routing algorithm can significantly improve overall performance of multicomputer systems. In this thesis, we try to solve the problem of compile-time wormhole routing in mesh-connected multicomputers, exploiting communication characteristics of applications. Such a routing can produce less communication overhead making use of global communication characteristics of applications and is applicable to real-time applications where prediction of message transfer time is important. Problem, given all the message passing requirements of application, to decide path for each message passing requirement at compile time to reduce contention was proved NP-hard. There are two issues in solving the problem. First is routing rule to provide deadlock freedom and second is heuristic algorithm suitable for the problem.
In our heuristic algorithm, routes are decided from the messages which is predicted to have less paths with less-contention among all the eligible paths. Our routing algorithm also permits non-minimal paths and provides deadlock-freedom by turn model extended to arbitrary dimension. Performance of our algorithm is compared with closely related Xzhong's by simulations. Simulation shows that proposed routing algorithm has less channel contention which is direct factor to communication time of wormhole routed multicomputers than previous work. Ours algorithm specifically outperforms previous one for traffic patterns with messages concentrating in specific areas like hot-spot.
