Japanese
Imai Laboratory > Projects > Adaptive Routing
Last Modified: 2000-08-29 (Minor Update on 2003-05-02)

Adaptive Routing


Adaptive routing algorithm for networks with irreguar topology

The design of interconnection networks is the key issue of that of parallel computers. "Routing" is one of the research interests in this area. Routing algorithms determine which of the possible paths from source to destination is used as route. If you develop a good routing algorithm, both latency and throughput can be largely improved. But if you design it uncarefully, this may cause various problems such as deadlocks. So the design of routing algorithms is a very challenging task.

Routing algorithms are divided into two categories in terms of routing freedom. One is deterministic routing algorithms, and the other is adaptive routing algorithms. Deterministic routing algorithms provide the only one route for a given source-destination pair. On the other hand, adaptive routing algorithms give several routing options and select one of them according to the state of the network. The following examples show the difference between both algorithms. The deterministic routing algorithm provides the only one route for the source-destination pair (shown by green), whereas the adaptive routing algorithm selects an appropriate route from several routing options (shown by red). Thus, the adaptive routing scheme can improve the utilization of the network.

deterministic routing adaptive routing

The performance of both workstaions and PCs grew exponentially during the last decade, and their cost also became very low. Today, a lot of researchers are studying the design of high-performance and low-price parallel computers by using workstations and PCs. These parallel computers usually require networks with irregular topology because of both wiring flexibility and scalability. Although networks with irregular topology are convenient in designing, this "irregularity" makes routing and deadlock avoidance very difficult. The aim of our research is to achieve both lower latency and higher throughput by designing deadlock-free adaptive routing algorithms for networks with irregular topology.


kchiba@is.s.u-tokyo.ac.jp