性能驱动总体布线算法3.PDFVIP

　第 19 卷第 2 期　　　　　　　　　半　导　体　学　报　　　　　　　 . 19, . 2　 V o l N o 　1998 年 2 月　　　　　　 　　　　　　 . , 1998　 CH IN ESE JOU RNAL O F SEM ICONDU CTOR S Feb SERR: 基于模拟进化技术的 性能驱动总体布线算法 杨昌玲　　　严晓浪 (杭州电子工业学院CAD 所　杭州　310007) 摘要　本文结合BBL 布图模式, 以提高整个芯片的时间性能为目标, 提出了关于总体布线的 ( ) ( ) 基于模拟进化 SE 技术的拆线与重布线算法 简称为 SERR 算法 . SERR 算法对传统的顺序 布线算法进行了改进, 运用概率准则选择线网进行拆除与重布, 具有绕开局部优化点、得到全 局优化解的能力. 实验证明, SERR 算法能够较好地达到优化整个芯片的连线延时性能的目 标. : 7410 , 5120 EEACC D 1　引言 总体布线是 IC 布图中继布局之后的又一重要阶段, 它是基于全局的考虑, 把所有的线 网合理地分配到各个布线通道中去, 完成所有线网的拓扑布线. 目前, 总体布线算法从其布线顺序来分, 可分为顺序布线与并行布线两大类. 其中并行 布线算法是对所有线网同时布线, 但并行算法很难实现, 甚至对于 2端点的线网也没有一 [ 1 ] 个有效的多项式时间算法 ; 而许多基于整数规划的同时布线算法虽然能够从整体上对所 有线网进行同时布线, 但是这些算法也比较复杂, 而且对于单个的线网来讲, 其结果也许并 [ 9～ 11 ] 不优化 . 顺序布线方法是对所有线网依次进行布线, 该方法对于布线顺序十分敏感, 因 为先布线的线网很可能会影响其他线网的布线; 但是, 顺序布线适用于各种布图模式与工艺 [ 1 ] 条件下布线, 所以, 其应用最为广泛 . 顺序布线方法的基本思想是: 一般地, 根据线网的平面位置关系, 或边界盒的大小, 或端 点个数排序, 或线网的延时纺束, 赋予线网一定的权值, 根据线网依权值大小的顺序对线网 　 电科院预研项目 杨昌玲　女, 1969 年出生, 博士研究生, 研究方向为集成电路计算机辅助设计 严晓浪　男, 1946 年出生, 教授, 主要从事集成电路设计自动化方面的科研和教学工作 收到,定稿 152 　　　　　　　　　　　　　　　半　导　体　学　报　 19 卷 [ 2, 5 ] 依次进行布线 . 当进一步布线已不可行时, 通常采用一个改善的方法, 这就是拆线与重布 线技术( ) , 也就是将妨碍其他线网布线的导线折开并重新布线, 以保证 R ip up and R erou te [ 2, 5 ] 其他线网的布线顺利进 . 上述总体布线方法的特点是: 第一, 布线、拆线与重布线的过程都是按照线网的关键值 ( ) (