基于遗传算法的两端线网布线方法.pdf

江汉石油学院学报 年 月 第 卷 第 期 2003 3 25 1 Journal of Jianghan Petroleum Institute Mar .2003 VOI .25 NO . 1 · · 1 基于遗传算法的两端线网布线方法 张红民 （江汉石油学院计算机科学系，湖北 荆州434023） 徐 宁 （江汉石油学院计算机科学系，湖北 荆州434023；电子科技大学光电子技术系，四川 成都610054 ） ［摘要］对于给定的布线平面，基于遗传算法的两端线网布线方法首先根据障碍情况对布线平面进行网格 化，然后对网格进行编号，用一系列网格序号的有序排列来表示两端点的布线路径，以多条布线路径组 成的群体作为优化有哪些信誉好的足球投注网站基础，最后采用遗传算法对此群体进行遗传操作，得到两端线网的最短路径。 ［关键词］遗传算法；布线；网格化；最短路径 ［中图分类号］ ［文献标识码］ ［文章编号］ （ ） TN702 A 1000 9752 2003 01 0105 03 两端线网的布线问题，可看成是在一有网格的平面中求两端点之间的绕障碍的最短路径。在超大规 模集成电路 （ ）布线设计中，金属布线层上的电路元件、已经布好的互连线、甚至待连接的电路端 VLSI 点都可看作是障碍，如何绕过这些障碍找到互连的路径或对今后布线最有利的路径，并达到总线长及时 延的最小化，是人们要解决的问题。对于解决绕障碍寻找目标路径布线问题，目前已经有了一些算法， ［ ］ 如迷宫算法、线探索法、平面扫描法、图论方案法、计算几何法、波前端法以及动态有哪些信誉好的足球投注网站法等 1 ~ 5 ，但 ［］ 这些方法都有一定的优缺点。为此提出了基于遗传算法6 的两端线网布线方法，为解决这类布线问题提 出了一种新的思路。实验结果表明，在参数选择适当的情况下，能很快的找到最短路径。 1 布线空间的网格化建模 两端线网的布线区域用二维平面表示。布线时，在布线区域内的障碍物的位置和大小是已知的，在 布线过程中，障碍物的位置和大小不发生变化。 将布线区域进行二维网格划分，网格的划分以障碍物的边、角作水平线和垂直线，这样就可以得到 布线区域的不均匀网格。若某一网格范围内不含障碍物，称此网格为自由网格；反之，则称为障碍网 格。自由网格和障碍网格均可表示为网格块的集成。 网格的标识采用序号法。如图 所示，以网格阵左上角为坐 1 标原点，水平向右为 轴正方向，垂直向下为 轴正方向，每一网 X Y 格区间对应坐标轴上的一个序号。任一网格均可用 轴、 轴序号 X Y （，）唯一标识，这样就构成了 维的矩阵，矩阵元素的值为 x y X X Y 该网格的中心坐标（图中黑影区表示障碍网格）。采用序号法可以 节省空间，表述简洁明了，并且便于进行遗传算子的操作。在对路 径质量进行评价时，则要将序号转换成真实坐标，这样便于计算路 径长度及检验路径的可行性。 2 两端线网布线的遗传算法 图 布线区域网格划分 1 2 . 1 个体编码 以两端线网在布线区域中的一条无障碍路径作为一个个体。如图 所示，由两端线网的源点 沿图