| 基于分支限界的关键路径求解算法 |
| |
| 引用本文： | 胡美群,夏银水,王伦耀.基于分支限界的关键路径求解算法[J].宁波大学学报(理工版),2011,24(2):37-41. |
| |
| 作者姓名： | 胡美群 夏银水 王伦耀 |
| |
| 作者单位： | 宁波大学信息科学与工程学院,浙江宁波,315211 |
| |
| 基金项目： | 国家自然科学基金(60871022); 浙江省自然科学基金(Y1080654); 浙江省大学生新苗计划 |
| |
| 摘 要： | 提出一种基于分支限界的关键路径求解算法,将电路拓扑结构表示成有向带权网（WOEN）,寻找汇点,使节点到汇点的最大路径时延为该节点分支限界的最小限值,剪去违反分支限界最小限值的局部非关键路径的连接边以化简WOEN.新算法采取节点最大时延链表的存储结构,使得WOEN的存储空间、关键路径计算空间以及计算结果的存储空间共享同一存储空间.算法用C语言实现,并在ISCAS标准电路上加以测试.结果表明：新算法比现有算法所需的存储空间更小,求解关键路径的速度更快.
|
| 关 键 词： | 关键路径 分支限界 算法 时延 集成电路 |
Critical Path Algorithm Based on Branch-and-bound |
| |
| HU Mei-qun,XIA Yin-shui,WANG Lun-yao.Critical Path Algorithm Based on Branch-and-bound[J].Journal of Ningbo University(Natural Science and Engineering Edition),2011,24(2):37-41. |
| |
| Authors: | HU Mei-qun XIA Yin-shui WANG Lun-yao |
| |
| Institution: | HU Mei-qun,XIA Yin-shui,WANG Lun-yao(Faculty of Information Science and Technology,Ningbo University,Ningbo 315211,China) |
| |
| Abstract: | 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 t... |
| |
| Keywords: | critical path branch-and-bound algorithm delay VLSI |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
