匈牙利算法在输入排队调度仿真中的应用研究

Application of Hungary Algorithm to Simulation of Input-queued Scheduling

匈牙利算法是图论中完成二分图匹配的经典算法之一。输入排队的Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的。因而在调度算法理论研究中应用了二分图最大匹配的MaximumSizeMatching(MSM)和MaximumWeightMatching(MWM)算法成为各种调度算法性能的评价标准。文中介绍了匈牙利算法在输入排队调度算法仿真中的应用,并且得出相应典型算法的性能仿真曲线,从而为进一步研究调度算法打下理论基础。

Hungary algorithm is a classical one to solve bipartite graph matching problem. Inputqueued crossbar scheduling algorithms are designed to match input ports to output ports of a switch as many as possible. So,maximum size matching (MSM) and maximum weight matching (MWM),which are basing on bipartite graph matching,become the criteria of various scheduling algorithms theoretically. In this paper,Hungary algorithm is successfully applied to the simulation of scheduling algorithms,which produces accurate simulation results. It is the theoretical foundation to do further research on scheduling algorithms. 