Andrew A. Chien
Jae H. Kim
Abstract
Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels. We describe a family of deadlock-free routing algorithms, called planar-adaptive routing algorithms, that require only a constant number of virtual channels, independent of networks size and dimension. Planar-adaptive routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each routing step. In the fault-free case, planar-adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar-adaptive networks can simultaneously support both in-order and adaptive, out-of-order packet delivery.
Planar-adaptive routing is of practical significance. It provides the simplest known support for deadlock-free adaptive routing in k-ary n-cubes of more than two dimensions (with k>2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-adaptive routers is amenable to efficient implementation.
Simulation studies show that planar-adaptive routers can increase the robustness of network throughput for nonuniform communication patterns. Planar-adaptive routers outperform deterministic routers with equal hardware resources. Further, adding virtual lanes to planar-adaptive routers increases this advantage. Comparisons with fully adaptive routers show that planar-adaptive routers, limited adaptive routers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual lanes.
Planar-adaptive routers are a special case of limited adaptivity routers. We define a class of adaptive routers with f degrees of routing freedom. This class, termed f-flat adaptive routers, allows a direct cost-performance tradeoff between implementation cost (speed and silicon area) and routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with the routing freedom. However, the rate of growth is a much larger constant for high-dimensional networks. All of the properties proven for planar-adaptive routers, such as deadlock and livelock freedom, also apply to f-flat adaptive routers.
- ~AGARWAL, A. 1991. Limits on interconnection network performance. IEEE Trans. Paral. Dist. ~Syst. 2, (4), 398-412. Google Scholar
- ~AOYAMA, K., AND CHIEN, A.A. 1994. The cost of adaptivity and virtual lanes in a wormhole ~router. J. VLSI Deszgn, Special Issue on Interconnection Networks.Google Scholar
- ~BERMAN, P., GRAVANO, L., PIFARRE, G., AND SANZ, J. 1992. Adaptive deadlock- and livelock- ~tree routing with all minimal paths in torus networks. In Proceedings of the 4th AnnualACM ~Symposium on ParallelAlgorithms and Arehitectures (San Diego, Calif., June 29-July 1). ACM, ~New York, pp. 3-i2. Google Scholar
- ~BLUMENTHAL, D., CHEN, K., MA, J., FEUERSTEIN, R., AND SAUER, J. 1992. Demonstration of a ~deflection routing 2 x 2 photomc switch for computer interconnects. IEEE Photo. Tech. Lett. 4, ~1, 169-73.Google Scholar
- ~BORODIN, A., AND HOPCROFT, J. 1985. Routing, merging and sorting on parallel models of ~computation. J. Comput. Syst. Sci. 30, 130-45. Google Scholar
- ~CHAIKEN, D., FIELDS, C., KURIHARA, K., AND AOARWAL, A. 1990. Directory-based cache ~coherence in large-scale multiprocessors. IEEE Computer, June. Google Scholar
- ~CHIEN, A.A. 1993. A cost and performance model for k-ary n-cube wormhole touters. In ~Proceedings of Hot bltercomlects Workshop (Aug).Google Scholar
- ~CHIEN, A. A., AND KIM, J.H. 1992. Planar-adaptive routing: Low-cost adaptive network for ~multiprocessors. In Proceedings of the 19th Annual hlternattonal Symposium on Computer ~Architecture (Gold Const, Australia, May 19 21). ACM, New York, pp. 268 277. Google Scholar
- ~DALLY, W. J. 1987. A VLSI Archttecture for Concurrent Data Structures. Kluwer Academic ~Publishers, Boston, Mass. Google Scholar
- ~DALLY, W. J. 1990. Performance analysis of k-ary n-cube interconnectlon networks. IEEE ~Trans. Comput. 39, 6 (June). Google Scholar
- DALLY, W.J. 1992. Virtual channel flow control. IEEE Trans. Paral. Dist. Syst. 3, 2, 194 205. Google Scholar
- ~DALLY, W. J., AND AOKI, H. 1993. Deadlock-free adaptive routing in multicomputer networks ~using ~virtual channels. IEEE Trans. Paral. Dist. Syst 4, 4 (Apr), 466-474. Google Scholar
- ~DALLY, W. J., CHIEN, A., FISKE, S., HORWAT, W., KEEN, J., LARIVEE, M., LETHIN, R., NUTH, P., ~W~LLS, S., CARRICK, P., AND FYLER, G. 1989. The J-Machine: A fine-grain concurrent ~computer. In bzformation Processing 89, Proceedings of the IFIP Congress. pp. 1147-1153.Google Scholar
- ~DALLY, W. J., AND SEITZ, C. 1987. Deadlock-free message routing in multiprocessor intercon- ~ection networks. IEEE Trans. Comput. C-36, 5. Google Scholar
- ~DALLY, W. J., AND SONG, P. 1987. Design of a self-timed vlsi multicomputer communication ~controller. In Proceedings of the blternattonal Conference on Computer Design. IEEE Computer ~Society Press, New York, pp. 230-234.Google Scholar
- ~UATO, J. 1991. On the design of deadlock-free adaptive routing algorithms for multicomput- ~ers: Design methodologies. In Proceedings of Parallel Architectures and Languages Europe. ~Springer-Verlag, Berlin. Google Scholar
- ~DUBOIS, M., SCHEURICH, C., AND BRIGGS, F. 1988. Synchronization, coherence and event ~ordering in multiprocessors. IEEE Comput. (9-21). Google Scholar
- ~FELPERIN, S., GRAVANO, L., PIFARR~, G., AND SANZ, J. 1991. Fully-adaptive routing: Packet- ~switching performance and wormhole algorithms. In Proceedings of Supercomputing '91 (Al- ~buquerque, N. M., Nov. 18-22). ACM, New York, pp. 654-663. Google Scholar
- ~GELERNTER, D. 1981. A dag-based algorithm for prevention of store-and-forward deadlock in ~packet networks. IEEE Trans. Comput. C-30, 10:12 (Oct.) pp. 709-715.Google Scholar
- ~GLASS, C., AND NI, L. 1992. The turn model for adaptive routing. In Proceedings of the 19th ~Annual International Symposium on Computer Architecture, (Gold Coast, Australia, May 19-21). ~ACM, New York, pp. 278-287. Google Scholar
- ~GUNTHER, K. D. 1981. Prevention of deadlocks in packet-switched data transport systems. ~IEEE Trans. Commun. COM-29, 4.Google Scholar
- ~KERMANI, P. AND KLEINROCK, L. 1974. Virtual cut-through: A new computer communications ~switching technique. Computer Networks 3, 4, 267-86.Google Scholar
- ~riM, J. H., AND CHIEN, m. m. 1992. An evaluation of planar-adaptive routing (PAR). In ~Proceedings of the 4th Symposium on Parallel and Distributed Processing. IEEE Computer Society ~Press, New York, pp. 470-478.Google Scholar
- ~KONSTANTINIDOU, S. 1990. Adaptive, minimal routing in hypercubes. In Proceedings of the 6th ~MIT Conference on Adl,anced Research in VLSI. (W. J. Dally, eds.), MIT Press, Cambridge, ~Mass., 139-453. Google Scholar
- ~KONSTANTINIDOU, S., AND SNYDER, L. 1991. Chaos router: Architecture and performance. In ~Proceedings of the I8th Annual International Symposium on Computer Architecture, (Toronto, ~Ont., Canada, May 27-30), ACM, New York, p. 212-221. Google Scholar
- ~LANDIN, A., HAGERSTEN, E., AND HARIDI, S. 1991. Race-free interconnection networks and ~multiprocessor consistency. In Proceedings of the 18th Annual bzternational Symposium on ~Computer Architecture (Toronto, Ont., Canada, May 27-30). ACM, New York, pp. 106-115. Google Scholar
- ~lINDER, D., AND HARDEN, J. 1991. An adaptive and fault tolerant wormhole routing strategy ~for k-ary n-cubes. IEEE Trans. Comput., C-40, 1 (Jan.) 2-12. Google Scholar
- ~NGAI, J. 1989. A framework for adaptive routing in multicomputer networks. Ph.D. disserta- ~tion, California Institute of Technology. Caltech-CS-TR-89-09. Pasadena, Calif. Google Scholar
- ~NGAI, J., AND SEITZ, C. 1989. A framework for adaptive routing in multicomputer networks. In ~Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures (Sante Fe, ~N. M., June 18-21). ACM, New York, pp. 2-10. Google Scholar
- ~LILLEVIK, S. 1990. Intel Corporation. Touchstone program overview. In Proceedings of the 5th ~Distributed Memory Computers Conference. American Mathematical Society, Providence, RI.Google Scholar
- ~SEITZ, C.L. 1985. The cosmic cube. Commun. ACM 28, 1 (Jan.), 22-33. Google Scholar
- ~SEITZ, C. L., ATHAS, W. C., FLAIG, C. M., MARTIN, A. J., SEIZOVIC, J., STEELE. C. S., AND SU, W. ~1988. The architecture and programming of the Ametek Series 2010 multicomputer. In ~Proceedings of the 3rd Conference on Hypercube Computers (Pasadena, Calif., Jan. 19-20). ACM, ~New York, pp. 33-36. Google Scholar
Index Terms
- Planar-adaptive routing: low-cost adaptive networks for multiprocessors
Recommendations
Network-on-chip architecture design based on mesh-of-tree deterministic routing topology
Network-on-Chip (NoC) is a new paradigm for designing future System-on-Chips (SoCs) where large numbers of Intellectual Property (IP) cores are connected through an interconnection network. The communication between the nodes is achieved by routing ...
A Theory of Deadlock-Free Adaptive Multicast Routing in Wormhole Networks
A theory for the design of deadlock-free adaptive routing algorithms for wormhole networks was proposed in [12], [16]. This theory supplies the sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic ...
An Analytical Model of Adaptive Wormhole Routing in Hypercubes in the Presence of Hot Spot Traffic
Analytical models of fully adaptive routing for common wormhole-routed networks (e.g., hypercubes) under the uniform traffic pattern have recently been reported in the literature. However, many studies have revealed that the performance advantages of ...
Reviews
Festus Gail Gray
A class of restricted adaptive routing algorithms suitable for packet-switched data transmission in multiprocessor applications is described. This well-written research paper will interest researchers and designers in multiprocessor architectures and interconnection networks. The paper assumes familiarity with networking terms, such as deadlock, livelock, virtual channels, and virtual lanes. Deterministic routing algorithms that use fixed paths do not take advantage of available network resources to route around busy channels. Fully adaptive routing algorithms allow full use of available resources but demand a high price to avoid deadlock. Planar-adaptive routing provides an effective compromise that sacrifices some routing freedom to drastically reduce the possibility of deadlock. Restricting routing at each step to a specific hyperplane in k -ary n -cubes still leaves many alternative routes, but the restriction allows provably deadlock-free (and livelock-free) operation at a cost of only 3 virtual channels, regardless of the number of dimensions in the n -cube. (Fully adaptive routing algorithms require on the order of 2 n virtual channels.) The result is a much lower hardware cost for deadlock-free routers. Additional features include deadlock-free fault-tolerant operation and the ability to handle both in-order and out-of-order packet transmission protocols. The authors also mention an extension to a family of f -flat routers that are also deadlock-free. Whereas planar routers restrict the choice of routes to two dimensions (a plane), f -flat routers allow routes to proceed in f or fewer dimensions for any arbitrary value of f . The family of adaptive routers allows designers to make cost-performance tradeoffs between increased channel utilization and increased cost of the routers. Finally, the paper includes a series of studies to verify that planar-adaptive routing significantly improves network performance relative to deterministic routing. More surprising, perhaps, is that planar-adaptive routing actually outperforms fully adaptive routing for some loading situations.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments