Algorithm-hardware Codesign of Fast Parallel Round-robin Arbiters

Authors

S. Q. Zheng, The University of Texas at DallasFollow
Mei Yang, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

1-2007

Publication Title

IEEE Transactions on Parallel and Distributed Systems

Volume

18

First page number:

84

Last page number:

95

Abstract

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.

Keywords

Algorithm design and analysis; Binary trees; Circuits; Delay; Hardware; Libraries; Round robin; Switches; Timing; Wire

Disciplines

Controls and Control Theory | Electrical and Computer Engineering | Electrical and Electronics | Signal Processing | Systems and Communications

Language

English

Permissions

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.

Repository Citation

Zheng, S. Q., Yang, M. (2007). Algorithm-hardware Codesign of Fast Parallel Round-robin Arbiters. IEEE Transactions on Parallel and Distributed Systems, 18 84-95.