Distributed memory multiprocessor, known as multicomputer, consists of many computing nodes that interact with each other by sending and receiving messages over communication channels between the nodes. Efficient routing of messages is critical to the performance of multicomputers. In order to design a efficient routing algorithm, it is desirable that the routing algorithm reflects the characteristics of the interconnection network topology. In this thesis, a deadlock- and livelock - free routing algorithm in Recursive Circulant G(2m, 4) is proposed. The algorithm proposed in this thesis is fully-adaptive minimal, i.e. all the shortest paths between the source and destination nodes are permitted for routing, and adopts the wormhole switching technique. The proposed algorithm requires only [(3m-1)/4] virtual channels per physical channel that is proportional to the diameter of Recursive Circulant G(2m,4). This is much smaller number of virtual channels compared to the previous design methodologies. We prove that the proposed routing algorithm is deadlock - and livelock - free. Simulation results show that the proposed algorithm has a low latency and a high throughput to the deterministic routing algorithm.
