Design and implementation of an acyclic stable matching scheduler

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² and n respectively, making it feasible to implement the scheduler at high speed with current CMOS technologies.