A comparative study of arbitration algorithms for the Alpha 21364 pipelined router

ABSTRACT

Interconnection networks usually consist of a fabric of interconnected routers, which receive packets arriving at their input ports and forward them to appropriate output ports. Unfortunately, network packets moving through these routers are often delayed due to conflicting demand for resources, such as output ports or buffer space. Hence, routers typically employ arbiters that resolve conflicting resource demands to maximize the number of matches between packets waiting at input ports and free output ports. Efficient design and implementation of the algorithm running on these arbiters is critical to maximize network performance.This paper proposes a new arbitration algorithm called SPAA (Simple Pipelined Arbitration Algorithm), which is implemented in the Alpha 21364 processor's on-chip router pipeline. Simulation results show that SPAA significantly outperforms two earlier well-known arbitration algorithms: PIM (Parallel Iterative Matching) and WFA (Wave-Front Arbiter) implemented in the SGI Spider switch. SPAA outperforms PIM and WFA because SPAA exhibits matching capabilities similar to PIM and WFA under realistic conditions when many output ports are busy, incurs fewer clock cycles to perform the arbitration, and can be pipelined effectively. Additionally, we propose a new prioritization policy called the Rotary Rule, which prevents the network's adverse performance degradation from saturation at high network loads by prioritizing packets already in the network over new packets generated by caches or memory.

REFERENCES

• 1: M. G. Ajmone Marshan, A. Bianco, and E. Leonardi, "RPA: A Flexible Scheduling Algorithm for Input Buffered Switches," IEEE Transaction on Communications, vol. 47, no. 12, pp. 1921-1933, Dec. 1999.
• 2: Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High speed switch scheduling for local area networks, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.98-110, October 12-15, 1992, Boston, Massachusetts, United States
• 3: Peter Bannon, "Alpha 21364: A Scalable Single-Chip SMP," 11th Annual Microprocessor Forum, Microdesign Resources, Sebastopol, California, 1998.
• 4: A Simple and Efficient Mechanism to Prevent Saturation in Wormhole Networks, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.617, May 01-05, 2000
• 5: Laxmi N. Bhuyan, Analysis of interconnection networks with different arbiter designs, Journal of Parallel and Distributed Computing, v.4 n.4, p.384-403, August 1, 1987 [doi>10.1016/0743-7315(87)90026-8]
• 6: Alan Charlesworth, The Sun Fireplane Interconnect, IEEE Micro, v.22 n.1, p.36-45, January 2002 [doi>10.1109/40.988688]
• 7: Andrew Chien and Magda Konstantinidou, "Workloads and Performance Metrics for Evaluating Parallel Interconnects," IEEE TCCA Newsletter, Fall 1994.
• 8: R. Cutler and S. Atkins, "IBM e-Server pSeries 680 Handbook," IBM, Armonk, N. Y., 2000; http://www.redbooks.ibm.com/pubs/pdfs/redbooks/sg246023.pdf.
• 9: William J. Dally, Virtual-channel flow control, Proceedings of the 17th annual international symposium on Computer Architecture, p.60-68, May 28-31, 1990, Seattle, Washington, United States
• 10: William J. Dally and Charles L. Seitz, "The Torus Routing Chip," Distributed Computing, vol. 1, no. 4, pp. 187-196, Oct. 1986.
• 11: A. DeHon , F. Chong , M. Becker , E. Egozy , H. Minsky , S. Peretz , T. F. Knight, Jr., METRO: a router architecture for high-performance, short-haul routing networks, Proceedings of the 21ST annual international symposium on Computer architecture, p.266-277, April 18-21, 1994, Chicago, Illinois, United States
• 12: Haoran Duan , J. W. Lockwood , S. M. Kang , J. D. Will, A High-Performance OC-12/OC-48 Queue Design Prototype for Input-buffered ATM Switches, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.20, April 09-11, 1997
• 13: José Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1320-1331, December 1993 [doi>10.1109/71.250114]
• 14: Jose Duato , Sudhakar Yalamanchili , Lionel Ni, Interconnection Networks: An Engineering Approach, IEEE Computer Society Press, Los Alamitos, CA, 1997
• 15: Joel Emer , Pritpal Ahuja , Eric Borch , Artur Klauser , Chi-Keung Luk , Srilatha Manne , Shubhendu S. Mukherjee , Harish Patil , Steven Wallace , Nathan Binkert , Roger Espasa , Toni Juan, Asim: A Performance Model Framework, Computer, v.35 n.2, p.68-76, February 2002 [doi>10.1109/2.982918]
• 16: Mike Galles, Spider: A High-Speed Network Interconnect, IEEE Micro, v.17 n.1, p.34-39, January 1997 [doi>10.1109/40.566196]
• 17: Kourosh Gharachorloo , Madhu Sharma , Simon Steely , Stephen Van Doren, Architecture and design of AlphaServer GS320, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.13-24, November 2000, Cambridge, Massachusetts, United States
• 18: Paolo Giaccone , Devavrat Shah , Balaji Prabhakar, An Implementable Parallel Scheduler for Input-Queued Switches, IEEE Micro, v.22 n.1, p.19-25, January 2002 [doi>10.1109/40.988686]
• 19: Hewlett-Packard, "Meet the HP Superdome Servers," September, 2001; http://www.hp.com/products1/servers/scalableservers/superdome/infolibrary/whitepapers/technical_wp.pdf.
• 20: Mark D. Hill, A Case for Direct-Mapped Caches, Computer, v.21 n.12, p.25-40, December 1988 [doi>10.1109/2.16187]
• 21: Pedro López , Juan Miguel Martínez , José Duato, DRIL: Dynamically Reduced Message Injection Limitation Mechanism for Wormhole Networks, Proceedings of the 1998 International Conference on Parallel Processing, p.535-542, August 10-14, 1998
• 22: Pedro López , Juan Miguel Martínez , José Duato , Fabrizio Petrini, On the Reduction of Deadlock Frequency by Limiting Message Injection in Wormhole Networks, Proceedings of the Second International Workshop on Parallel Computer Routing and Communication, p.295-307, June 26-27, 1997
• 23: Nick McKeown, The iSLIP scheduling algorithm for input-queued switches, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.188-201, April 1999 [doi>10.1109/90.769767]
• 24: Nicholas William McKeown, Scheduling algorithms for input-queued cell switches, University of California at Berkeley, Berkeley, CA, 1996
• 25: Devavrat Shah , Paolo Giaccone , Balaji Prabhakar, Efficient Randomized Algorithms for Input-Queued Switch Scheduling, IEEE Micro, v.22 n.1, p.10-18, January 2002 [doi>10.1109/40.988685]
• 26: Shubhendu S. Mukherjee , Peter Bannon , Steven Lang , Aaron Spink , David Webb, The Alpha 21364 Network Architecture, IEEE Micro, v.22 n.1, p.26-35, January 2002 [doi>10.1109/40.988687]
• 27: Li-Shiuan Peh , William J. Dally, A Delay Model and Speculative Architecture for Pipelined Routers, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.255, January 20-24, 2001
• 28: G. E. Pfister and V. A. Norton, "Hot-Spot Contention and Combining in Multistage Interconnection Networks," IEEE Transaction on Computers, C-34(10):943-948, October 1985.
• 29: Parthasarathy Ranganathan , Kourosh Gharachorloo , Sarita V. Adve , Luiz André Barroso, Performance of database workloads on shared-memory systems with out-of-order processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.307-318, October 02-07, 1998, San Jose, California, United States
• 30: S. L. Scott , G. S. Sohi, The Use of Feedback in Multiprocessors and Its Application to Tree Saturation Control, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.385-398, October 1990 [doi>10.1109/71.80178]
• 31: S. L. Scott and G. M. Thorson, "The Cray T3E Network," Hot Interconnects IV, pp. 147-156, 1996.
• 32: Simon Steely, Compaq Computer Corporation, Personal Communication.
• 33: Silicon Graphics, "SGI 3000 Family Reference Guide," 2001; http://www.sgi.com/origin/3000/3000_ref.pdf.
• 34: A. Smai , L. Thorelli, Global Reactive Congestion Control in Multicomputer Networks, Proceedings of the Fifth International Conference on High Performance Computing, p.179, December 17-20, 1998
• 35: Craig B. Stunkel , Jay Herring , Bulent Abali , Rajeev Sivaram, A new switch chip for IBM RS/6000 SP systems, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.16-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331548]
• 36: Y. Tamir , H. C. Chi, Symmetric Crossbar Arbiters for VLSI Communication Switches, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.13-27, January 1993 [doi>10.1109/71.205650]
• 37: J. M. Tendler, et al., "IBM e-server POWER4 System Microarchitecture," IBM, Armonk, N.Y., 2001; http://www-1.ibm.com/servers/eserver/pseries/hardware/whitepapers/power4.pdf.
• 38: Mithuna Thottethodi , Alvin R. Lebeck , Shubhendu S. Mukherjee, Self-Tuned Congestion Control for Multiprocessor Networks, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.107, January 20-24, 2001
• 39: Brian Towles and William J. Dally, "Worst-case Traffic for Oblivious Routing," Computer Architecture Letters, (http://www.cs.virginia.edu/~tcca/2002paps.html), 2002.