Design and implementation of an acyclic stable matching scheduler
Enyue Lu, Mei Yang, Yi Zhang, S. Q. Zheng · 2004
Applications of stable matching in switch scheduling have been proposed. However, the classical GS (Gale and Shapley) stable matching algorithm is infeasible for high-speed implementation due to its high complexity. Instead, acyclic stable matching algorithms have been shown useful in implementing scheduling for high-speed switches/routers. We model the acyclic stable matching problem as the dominating set problem for a rooted dependency graph, and propose a parallel algorithm for finding the dominating set in O(n log n) time. We design and implement a scheduler based on the proposed algorithm in hardware. Simulation results show that the number of 2-input NAND gates and the timing of our design are proportional to n/sup 2/ and n respectively, making it feasible to implement the scheduler at high speed with current CMOS technologies.