基于分支限界的关键路径求解算法  

Critical Path Algorithm Based on Branch-and-bound

作　　者：胡美群[1] 夏银水[1] 王伦耀[1] 

机构地区：[1]宁波大学信息科学与工程学院,浙江宁波315211

出　　处：《宁波大学学报（理工版）》2011年第2期37-41,共5页Journal of Ningbo University：Natural Science and Engineering Edition

基　　金：国家自然科学基金(60871022);浙江省自然科学基金(Y1080654);浙江省大学生新苗计划

摘　　要：提出一种基于分支限界的关键路径求解算法,将电路拓扑结构表示成有向带权网(WOEN),寻找汇点,使节点到汇点的最大路径时延为该节点分支限界的最小限值,剪去违反分支限界最小限值的局部非关键路径的连接边以化简WOEN.新算法采取节点最大时延链表的存储结构,使得WOEN的存储空间、关键路径计算空间以及计算结果的存储空间共享同一存储空间.算法用C语言实现,并在ISCAS标准电路上加以测试.结果表明:新算法比现有算法所需的存储空间更小,求解关键路径的速度更快.A novel algorithm for finding critical paths based on branch-and-bound is proposed. By employing Weight On Edge Network （WOEN）, those edges of the WOEN in non-critical paths will be removed during the evaluation thus at last one of the critical paths will be detected. Memory saving is implemented by storing the simplified WOEN, computing space and computing results in the shared memory. The algorithm is implemented in C and tested under ISCAS standard benchmarks. The proposed algorithm needs less memory and less time than those previously published algorithms.

关 键 词：关键路径 分支限界 算法 时延 集成电路 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]