使用Ford-Fulkerson算法研究输入排队调度

• 作者: 法拉
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: Ford-Fulkerson 算法 匹配 调度
• 年，卷（期）: 2005,（9）
• 所属期刊栏目: 学术探讨
• 页码范围: 79-81,110
• 页数: 4页
• 分类号: TP391.9
• 字数: 3164字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2005.09.026

摘要

Ford-Fulkerson算法是图论中求解网络最大流的经典算法之一.输入排队Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量.因而在调度算法理论研究中把应用了二部图最大匹配的Maximumsize Matching(MSM)和Maximum weight Matching(MwM)算法作为目前各种调度算法性能评价标准.论文介绍了如何使用Ford-Fulkerson算法求解二部图的最大匹配,并且应用算法于输入排队调度算法仿真中,得出对应典型算法MSM和MWM的性能仿真曲线,从而为进一步研究调度算法打下理论基础.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	法拉	北京航空航天大学计算机学院软件开发环境国家重点实验室	3	9	2.0	3.0