Loading...
Please wait, while we are loading the content...
Similar Documents
Chaotic routing: design and implementation of an adaptive multicomputer network router
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bolding, Kevin |
| Copyright Year | 1993 |
| Abstract | A crucial component of a massively parallel multicomputer is the interconnection network which links all of the nodes of the computer together. This network provides the primary method of communication between the hundreds or thousands of processing nodes and is, thus, critical to the successful operation of the multicomputer. Current state-of-the-art interconnection networks use simple, oblivious routing techniques which achieve very good performance when loading is light, but do not perform well in the presence of non-uniform congestion or faults. Chaotic routing, a non-minimal adaptive routing technique, provides a mechanism which takes into account the presence of congestion and faults when choosing a path for a message and can, thus, achieve better performance. Chaotic routing is shown to be applicable to all finite-sized networks of bounded degree with bi-directionally connected links. A design for a chaotic router is presented which includes both the features of virtual cut-through routing and the advantages of internal non-blocking buffering. This design allows messages to follow minimum-latency paths when network loading is light, and provides sufficient buffering to ensure high throughput when the network is heavily loaded. The resulting design is compared with other minimal and non-minimal adaptive designs, as well as with oblivious routing. Chaotic routing is shown to be superior to most other adaptive designs due to its lower design complexity, and simulations are used to compare it with oblivious and deflection routing. The simulations show that, for mesh-connected networks, chaotic routing performs only slightly better than oblivious routing. However, for torus- and hypercube-connected networks, chaotic routing is superior to oblivious and deflection routing, achieving much higher throughput and lower latency. To demonstrate the feasibility of chaotic routing, a prototype chaos router chip is presented. This chip, fabricated in 1.2$\mu$m CMOS, implements a two-dimensional chaos router. The chip, in simulations, operates at 66MHz, with the speed being limited only by the speed at which the 5V CMOS pads can be switched. Thus, the chip should operate at the same clock speed as oblivious routers using the same technology, giving an equivalent bandwidth capability. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://wotug.ukc.ac.uk/parallel/simulation/communications/chaos/docs/boldingPhd.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
