月计算机集成制造系统

第１２卷第９期计算机集成制造系统Ｖｏｌ．１２Ｎｏ．９２００６年９月ＣｏｍｐｕｔｅｒＩｎｔｅｇｒａｔｅｄＭａｎｕｆａｃｔｕｒｉｎｇＳｙｓｔｅｍｓＳｅｐ．２００６文章编号：１００６－５９１１（２００６）０９－１４５９－０７收稿日期：２００６－０３－２４；修订日期：２００６－０７－１２。Ｒｅｃｅｉｖｅｄ２４Ｍａｒ．２００６；ａｃｃｅｐｔｅｄ１２Ｊｕｌｙ２００６．作者简介：石文兰（１９６５－），女，河北正定人，河北工业职业技术学院信息工程与自动化系讲师，主要从事计算机控制技术、计算机辅助设计和电气自动化等的研究。Ｅ－ｍａｉｌ：[e-mail]。面向芯片计算机集成的时钟树构建石文兰１，南国芳２，李俊婷１（１．河北工业职业技术学院信息工程与自动化系，河北　石家庄　０５００９１；２．天津大学系统工程研究所，天津　３０００７２）摘　要：阐述了芯片的版图设计中形成时钟二叉树的多级遗传算法，从理论上说明了该遗传算法的求解思路、编码方式、适应度函数、遗传算子的设计等。重点讨论了节点合并策略和单节点二叉树的形成。提出了时钟二叉树的多级模型，并设计了基于多级遗传算法的时钟二叉树形成算法。用该算法对随机测试例子和标准标杆测试例子的测试中发现，与传统的启发式算法相比，多级遗传算法能产生更好的测试结果。关键词：二叉树；时钟布线；遗传算法；多级模型中图分类号：ＴＰ３　　　　文献标识码：Ａ犆狅狀狊狋狉狌犮狋犻狅狀狅犳犮犾狅犮犽狋狉犲犲狅狉犻犲狀狋犲犱狋狅犮狅犿狆狌狋犲狉犻狀狋犲犵狉犪狋犻狅狀狅犳犮犺犻狆犛犎犐犠犲狀－犾犪狀１，犖犃犖犌狌狅－犳犪狀犵２，犔犐犑狌狀－狋犻狀犵１（１．Ｄｅｐ．ｏｆＩｎｆｏ．Ｅｎｇ．＆Ａｕｔｏｍａｔｉｚａｔｉｏｎ，ＨｅｂｅｉＩｎｓｔ．ｏｆＶｏｃａｔｉｏｎ＆Ｔｅｃｈ．，Ｓｈｉｊｉａｚｈｕａｎｇ　０５００９１，Ｃｈｉｎａ；２．Ｉｎｓｔ．ｏｆＳｙｓｔｅｍｓＥｎｇ．，ＴｉａｎｊｉｎＵｎｉｖ．，Ｔｉａｎｊｉｎ　３０００７２，Ｃｈｉｎａ）犃犫狊狋狉犪犮狋：Ａｋｉｎｄｏｆｍｕｌｔｉ－ｌｅｖｅｌｍｏｄｅｌｏｆｃｌｏｃｋｂｉｎａｒｙｔｒｅｅａｎｄｉｔｓｃｏｎｓｔｒｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｏｆｃｌｏｃｋｓｉｇｎａｌｂａｓｅｄｏｎｍｕｌｔｉ－ｌｅｖｅｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｗｅｒｅｐｒｏｐｏｓｅｄ．Ｒｅｓｏｌｕｔｉｏｎｍｅｔｈｏｄｓ，ｆｉｔｎｅｓｓｆｕｎｃｔｉｏｎａｎｄｄｅｓｉｇｎｏｆｇｅｎｅｔｉｃｏｐｅｒａｔｏｒｏｆｔｈｅｐｒｏｐｏｓｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｗｅｒｅｔｈｅｏｒｅｔｉｃａｌｌｙｅｘｐａｔｉａｔｅｄ．Ｎｏｄｅｍｅｒｇｅｓｔｒａｔｅｇｙａｎｄｆｏｒｍａｔｉｏｎｏｆｓｉｎｇｌｅｎｏｄｅｂｉｎａｒｙｔｒｅｅｗｅｒｅｄｉｓｃｕｓｓｅｄｉｎｐａｒｔｉｃｕｌａｒ．Ｆｒｏｍｔｈｅｒｅｓｕｌｔｓｏｆｒａｎｄｏｍｔｅｓｔｃａｓｅｓａｎｄｓｔａｎｄａｒｄｂｅｎｃｈｍａｒｋｔｅｓｔｃａｓｅｓｂｙｔｈｉｓａｌｇｏｒｉｔｈｍ，ｉｔｃｏｕｌｄｂｅｃｏｎｃｌｕｄｅｄｔｈａｔｍｕｌｔｉ－ｌｅｖｅｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｃｏｕｌｄｐｒｏｄｕｃｅｍｕｃｈｂｅｔｔｅｒｔｅｓｔｒｅｓｕｌｔｓｃｏｍｐａｒｅｄｗｉｔｈｔｒａｄｉｔｉｏｎａｌｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｓ．犓犲狔狑狅狉犱狊：ｂｉｎａｒｙｔｒｅｅ；ｃｌｏｃｋｒｏｕｔｉｎｇ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｍｕｌｔｉ－ｌｅｖｅｌｍｏｄｅｌ０　引言版图设计是芯片制造的一个重要阶段，该阶段也可称为逻辑设计的计算机版图集成。布局布线是版图集成的重要任务，而时钟线网的布线是芯片能够正常工作的重要保证，是布线阶段需要优先考虑的线网，因为从时钟网的时钟源点到各个时钟端点的实际路径长度决定了时钟的最大频率。由于时钟布线是全局性的，其连线一般很长，在超大规模集成电路中，连线引起的时延占整个芯片时延的７０％以上，时钟布线要保证连线长度最小。同时，在一个系统中，每个需要时钟的作用单元与时钟源点相连，但时钟信号并不能同时到达所有的作用单元，一般会产生时钟偏差。为保证系统高效无误地工作，必须保证时钟偏差最小。时钟偏差为时钟源点到时钟端点的最大延时，优化时钟偏差能动态缩减系统的时钟周期，提高系统的时间性能。式（１）［１］为计算时钟信号网的时钟周期计算式：狋狆≥狋犱＋狋狊犽犲狑＋狋狊狌＋狋犱狊。（１）计算机集成制造系统第１２卷其中，狋狆为系统的时钟周期，狋犱为组合逻辑电路部分的最长路径延迟，狋狊犽犲狑为时钟偏差，狋狊狌为同步元件的启动时间（假定为沿触发），狋犱狊为同步元件信号传播延时。狋犱＝狋犱＿ｉｎｔ犲狉犮狅狀狀犲犱＋狋犱＿犵犪狋犲狊。（２）式中，狋犱＿ｉｎｔ犲狉犮狅狀狀犲犱是与组合逻辑电路的最长路径内部连接相关的延时，狋犱＿犵犪狋犲狊为组合逻辑电路门延时。随着集成电路制造工艺的不断发展及门电路的开关速度不断提高，狋狊狌，狋犱狊及狋犱＿犵犪狋犲狊大大减小，由此可见，减小时钟偏差狋狊犽犲狑成为目前集成电路设计过程中一个很重要的因素。１　问题的描述在Ｍａｎｈａｔｔａｎ平面上，给定时钟端点位置的集合犛＝｛狊１，狊２，…，狊狀｝犚２，同时给出一个时钟源点狊０及其位置。布线拓扑犌为狀个节点的二叉树，狀个节点为犛中狀个时钟端点。将布线拓扑犌映射为一个时钟树犜犌（犛），其中每一节点狏∈犌映射为Ｍａｎｈａｔｔａｎ平面上的一个位置犾（狏），该节点通过边犲狏与它的父节点相连，边犲狏的值代表连线长度，表示为｜犲狏｜。树犜犌（犛）的布线长度表示为ｃｏｓ狋（犜），为每一个边长度之和。如狋（狌，狏）代表任意两个节点狌，狏之间的信号延迟，则整个时钟树的偏差表示为：狊犽犲狑（犜）＝ｍａｘ狊犻，狊犼∈犛｜狋（狊０，狊犻）－狋（狊０，狊犼）｜。（３）因本文采用的算法在理论上可以实现零偏差，故目标函数表示为ｃｏｓ狋（犜）＝∑犲狏∈犜狘犲狏狘。（４）　　计算信号延时采用路径长度延时（ｐａｔｈｌｅｎｇｔｈｄｅｌａｙ）模型，对于任意两个节点狌，狏∈犌，且节点狌为节点狏的祖节点，狆犪狋犺（狌，狏）表示拓扑犌中从节点狌至节点狏的惟一路径，从节点狌至节点狏的信号延时为该路径上每一个边的长度｜犲狑｜的总和：狋（狌，狏）＝∑犲狑∈狆犪狋犺（狌，狏）狘犲狑狘。（５）　　近年来，很多专家学者对零偏差时钟布线问题进行了研究，启发式方法在时钟偏差布线中得到了很好的应用，其中Ｈ树结构应用较为广泛，尤其是针对阵列单元设计。文献［２］和文献［３］提出的均值和中值法（ＭｅｔｈｏｄｓｏｆＭｅａｎｓａｎｄＭｅｄｉａｎｓ，ＭＭＭ）通过将时钟端点集不断地划分为两个相等子集的方式建立时钟网的拓扑结构；文献［４］对ＭＭＭ算法进行了改进，提出了自底向上的几何匹配方法来建立时钟二叉树，这种方法比ＭＭＭ方法节省了５％～７％的线长；文献［５］将上述方法进行改进，得出了基于Ｅｌｍｏｒｅ延时模型［６］下的时钟二叉树，达到了时钟零偏差，该方法自底向上不断将两个零偏差子树进行合并直至一棵完整的树；ＤＭＥ（ｄｅｆｅｒｅｄｍｅｒｇｅｄｅｍｂｅｄｄｉｎｇ）算法［７］同样是用于生成时钟二叉树的拓扑生成算法，不仅能够实现零偏差，而且所需线长大大缩短。此后ＤＭＥ算法得到了很广泛的应用，并进行了很多改进［８－９］。２　多级遗传算法用于时钟二叉树形成遗传算法［１０－１２］是一种全局优化算法，对ＮＰ问题的求解效果尤为明显。由于时钟布线问题中输入条件为时钟源点的位置及各时钟端点的位置，也就是说时钟二叉树的根节点和叶节点位置是明确的，而需要解决其他的内部节点及其位置，以使整个二叉树的连线最短且保证时钟源点至各时钟端点的延时偏差为零。首先，二叉树是自下而上的多级结构，其形成是先从底层叶节点开始，逐级形成各内部节点，并得到内部节点的详细位置，直到根节点。这样每一级的优化过程都采用遗传算法，虽然在计算时间（时间复杂性）上有所增加，但却能改善整个时钟网络的性能，大幅度减少连接线长。随着计算机技术的发展，这种时间复杂性的增加对计算带来的影响将越来越小，而时钟网络的优化对芯片性能的改善却显得越来越重要。２１　算法的设计原则假设已知时钟源点狊０及其坐标（狓０，狔０）、各时钟端点狊犻（１≤犻≤狀）及其坐标（狓犻，狔犻），算法的主要目的是在满足约束条件的情况下，对时钟二叉树中的每一个内部节点确定其坐标及其所有节点的拓扑关系，再利用传统布线策略实现时钟网的布线。在该遗传算法中，不考虑绕线和各节点的位置冲突，利用点与点间的实际距离近似表示总体线长。算法的基本思想是自下而上逐级实现，级与级之间遵循下列原则：（１）按照遗传算法的基本操作确定出每级的节点序列，依次两两节点合并，利用合并算法确定合并点，由此确定出这一级的拓扑关系和内部节点位置坐标。　　（２）上一级的输出作为下一级的输入，即上一级０６４１第９期石文兰等：面向芯片计算机集成的时钟树构建确定的各内部节点作为下一级的叶节点，重新执行遗传策略，在上一级的基础上确定出新的拓扑结构和合并点的坐标。　　（３）每一级的优化目标函数均为该级连接线的长度，它是适应值的倒数。（４）合并点的确定满足零偏差。上述原则是为了实现多级遗传算法构造时钟二叉树的过程而考虑的，同时设计了一种基于上述原则下的遗传算法解决框架，该框架下，可以根据需要设计适应度函数和选择、交叉、变异等遗传算子。２２　编码、算子及适应度函数设计用遗传算法［１３］生成时钟二叉树是一个多级的过程，每一级都采用相同的遗传策略，包括选择、交叉、变异、适应度函数等，其他控制参数可能不同。时钟二叉树的遗传算法生成的思想是将问题转化为函数优化问题，这一问题的关键在于设计出能够真实反映时钟信号零偏差的适应度函数、是否便于操作的遗传算法编码、简单有效的遗传算子、算法的整体结构等。现分别讨论如下。２．２．１　编码问题的输入为狀个时钟端点｛狊１，狊２，…，狊狀｝，因此考虑第１级编码采用整数编码，即先对狀个时钟端点进行编号｛１，２，…，狀｝，染色体串的表示即为狀个整数的随机排列。根据二叉树的特点，需要对时钟端点进行两两合并，并确定出合并的两个节点排列序号及合并点的位置坐标。如果第１级为狀＝２犽个节点，可以得到犽个合并点，将犽个合并点作为第１级的各时钟端点进行编号｛１，２，…，犽｝，染色体长度是第１级的一半。重复上述过程，直到某级染色体个数只有两个时，算法终止，这两个节点即为二叉树中根节点的两个直接子节点。具体操作如图１所示。２．２．２　适应度函数遗传算法将问题空间表示成染色体位串空间，为了执行适者生存的原则，必须对个体位串的适应性进行评价。时钟布线问题要求时钟偏差最小。在线长模型下，如果采用合适的二叉树构建方法，理论上可以实现零偏差，本节所述的时钟二叉树构建策略是基于多级遗传算法的，希望达到的目标为时钟树的所有连线长度最短，理论上能否实现零偏差主要取决于自下而上的节点合并策略（详见节点合并策略部分）。在自下而上的每一级二叉树构成过程中，希望每一级中涉及到的连线总长度最短。将二叉树按照自下而上进行严格分级（如图２），共分为犿级，其中｛犲１，犲２，犲３，犲４｝为第１级涉及到的连线，｛犲５，犲６｝为第２级涉及到的连线，｛犲７｝为第３级中的边。对于第犻级形成过程，需要将第犻级的各个节点两两合并，即增加了线长，设该级中共有狉对节点相连，即增加了狉个线段的长度，每对线段长度表示为｜犲犼｜（１≤犼≤狉），增加的连线总长为犾犻＝∑狉犼＝１狘犲犼狘，１≤犼≤狉，１≤犻≤犿。（６）其中，犾犻表示第犻层（１≤犻≤犿）增加的连线长度。为使整个二叉树的连线长度也能达到最小，采用的方法是每一级的连线长度都实现最小。从全局的角度出发，总的连线长度实现全局最优较为困难，但每一级利用遗传算法优化连线长度是很容易实现的。对于第犻级，希望犾犻越小越好，因此该级（层）遗传算法中采用的适应度函数可以表示为犳＝犺犾犻＝犺∑狉犼＝１狘犲犼狘，１≤犼≤狉，１≤犻≤犿。（７）这里，犳表示适应度函数，犺为一个正的常数，根据具体时钟网络的情况而定，这里取犺＝１００。２．２．３　选择按比例的适应度分配是利用比例于各个个体适应度的概率决定其子孙遗留的可能性，若某个个体为犻，其适应