Algorithm-hardware codesign of fast parallel round-robin arbiters
As a basic building block of a switch scheduler, a fast and fair arbiter is critical to the efficiency of the scheduler, which is the key to the performance of a high-speed switch or router. In this paper, we propose a parallel round-robin arbiter (PRRA) based on a simple binary search algorithm, which is specially designed for hardware implementation. We prove that our PRRA achieves round-robin fairness under all input patterns. We further propose an improved (IPRRA) design that reduces the timing of PRRA significantly. Simulation results with TSMC .18mum standard cell library show that PRRA and IPRRA can meet the timing requirement of a terabit 256 times 256 switch. Both PRRA and IPRRA are much faster and simpler than the programmable priority encoder (PPE), a well-known round-robin arbiter design. We also introduce an additional design which combines PRRA and IPRRA and provides trade-offs in gate delay, wire delay, and circuit area. With the binary tree structure and high performance, our designs are scalable for large N and useful for implementing schedulers for high-speed switches and routers.
Algorithm design and analysis; Binary trees; Circuits; Delay; Hardware; Libraries; Round robin; Switches; Timing; Wire
Controls and Control Theory | Electrical and Computer Engineering | Electrical and Electronics | Signal Processing | Systems and Communications
Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.
Zheng, S. Q.,
Algorithm-hardware codesign of fast parallel round-robin arbiters.
IEEE Transactions on Parallel and Distributed Systems, 18