Programmable weighted arbiters for constructing switch schedulers

As the basic building block of a scheduler based on maximal weight matching algorithms, the design of a weighted arbiter is vital to the performance of the scheduler. All existing weighted arbiter designs are based on the binary comparator tree structure and consume O(bN) gates, where b is the number of bits needed to represent the weight. These designs are not desirable for implementing scheduling algorithms that require a large number of weighted arbiters. In light of the idea of radix sort, we propose a new weighted arbiter (WA) design and a programmable weighted arbiter (PWA) design, both with O(N) gates. Through simulations, we show that the proposed WA design achieves a significant improvement on area cost over existing WA designs. The proposed PWA design provides round-robin fairness for requests with the same weight. Both designs can be directly used to build schedulers based on maximal weight matching algorithms. They are also useful for other applications, such as the arbitration of a shared bus and control of real-time systems.