A comparative study of arbitration algorithms for the Alpha 21364 pipelined router
Authors:
Open Access
- 1 October 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 30 (5) , 223-234
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.Keywords
This publication has 26 references indexed in Scilit:
- The Alpha 21364 network architectureIEEE Micro, 2002
- Efficient randomized algorithms for input-queued switch schedulingIEEE Micro, 2002
- Asim: a performance model frameworkComputer, 2002
- The Sun Fireplane InterconnectIEEE Micro, 2002
- An implementable parallel scheduler for input-queued switchesIEEE Micro, 2002
- The iSLIP scheduling algorithm for input-queued switchesIEEE/ACM Transactions on Networking, 1999
- Symmetric crossbar arbiters for VLSI communication switchesIEEE Transactions on Parallel and Distributed Systems, 1993
- A new theory of deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1993
- The use of feedback in multiprocessors and its application to tree saturation controlIEEE Transactions on Parallel and Distributed Systems, 1990
- Analysis of interconnection networks with different arbiter designsJournal of Parallel and Distributed Computing, 1987