月计算机集成制造系统.pdf

《月计算机集成制造系统.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第１２卷第９期计算机集成制造系统Ｖｏｌ．１２Ｎｏ．９２００６年９月ＣｏｍｐｕｔｅｒＩｎｔｅｇｒａｔｅｄＭａｎｕｆａｃｔｕｒｉｎｇＳｙｓｔｅｍｓＳｅｐ．２００６文章编号：１００６－５９１１（２００６）０９－１４５９－０７面向芯片计算机集成的时钟树构建石文兰１，南国芳２，李俊婷１（１．河北工业职业技术学院信息工程与自动化系，河北石家庄０５００９１；２．天津大学系统工程研究所，天津３０００７２）摘要：阐述了芯片的版图设计中形成时钟二叉树的多级遗传算法，从理论上说明了该遗传算法的求解思路、编码方式、适应度函数、遗传算子的设计等。重点讨论了节点合并策略和单节点二叉树的形成。提出了时钟二叉树的

2、多级模型，并设计了基于多级遗传算法的时钟二叉树形成算法。用该算法对随机测试例子和标准标杆测试例子的测试中发现，与传统的启发式算法相比，多级遗传算法能产生更好的测试结果。关键词：二叉树；时钟布线；遗传算法；多级模型中图分类号：ＴＰ３文献标识码：Ａ犆狅狀狊狋狉狌犮狋犻狅狀狅犳犮犾狅犮犽狋狉犲犲狅狉犻犲狀狋犲犱狋狅犮狅犿狆狌狋犲狉犻狀狋犲犵狉犪狋犻狅狀狅犳犮犺犻狆１，犖犃犖犌狌狅－犳犪狀犵２，犔犐犑狌狀－狋犻狀犵１犛犎犐犠犲狀－犾犪狀（１．Ｄｅｐ．ｏｆＩｎｆｏ．Ｅｎｇ．＆Ａｕｔｏｍａｔｉｚａｔｉｏｎ，ＨｅｂｅｉＩｎｓｔ．ｏｆＶｏｃａｔｉｏｎ＆Ｔｅｃｈ．，Ｓｈｉｊｉａｚｈｕａｎｇ０５００９

3、１，Ｃｈｉｎａ；２．Ｉｎｓｔ．ｏｆＳｙｓｔｅｍｓＥｎｇ．，ＴｉａｎｊｉｎＵｎｉｖ．，Ｔｉａｎｊｉｎ３０００７２，Ｃｈｉｎａ）犃犫狊狋狉犪犮狋：Ａｋｉｎｄｏｆｍｕｌｔｉ－ｌｅｖｅｌｍｏｄｅｌｏｆｃｌｏｃｋｂｉｎａｒｙｔｒｅｅａｎｄｉｔｓｃｏｎｓｔｒｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｏｆｃｌｏｃｋｓｉｇｎａｌｂａｓｅｄｏｎｍｕｌｔｉ－ｌｅｖｅｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｗｅｒｅｐｒｏｐｏｓｅｄ．Ｒｅｓｏｌｕｔｉｏｎｍｅｔｈｏｄｓ，ｆｉｔｎｅｓｓｆｕｎｃｔｉｏｎａｎｄｄｅｓｉｇｎｏｆｇｅｎｅｔｉｃｏｐｅｒａｔｏｒｏｆｔｈｅｐｒｏｐｏｓｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｗｅｒｅｔｈｅｏ

4、ｒｅｔｉｃａｌｌｙｅｘｐａｔｉａｔｅｄ．Ｎｏｄｅｍｅｒｇｅｓｔｒａｔｅｇｙａｎｄｆｏｒｍａｔｉｏｎｏｆｓｉｎｇｌｅｎｏｄｅｂｉｎａｒｙｔｒｅｅｗｅｒｅｄｉｓｃｕｓｓｅｄｉｎｐａｒｔｉｃｕｌａｒ．Ｆｒｏｍｔｈｅｒｅｓｕｌｔｓｏｆｒａｎｄｏｍｔｅｓｔｃａｓｅｓａｎｄｓｔａｎｄａｒｄｂｅｎｃｈｍａｒｋｔｅｓｔｃａｓｅｓｂｙｔｈｉｓａｌｇｏｒｉｔｈｍ，ｉｔｃｏｕｌｄｂｅｃｏｎｃｌｕｄｅｄｔｈａｔｍｕｌｔｉ－ｌｅｖｅｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｃｏｕｌｄｐｒｏｄｕｃｅｍｕｃｈｂｅｔｔｅｒｔｅｓｔｒｅｓｕｌｔｓｃｏｍｐａｒｅｄｗｉｔｈｔｒａｄｉｔｉｏｎａｌｈｅｕｒｉｓｔｉｃａｌｇｏｒ

5、ｉｔｈｍｓ．犓犲狔狑狅狉犱狊：ｂｉｎａｒｙｔｒｅｅ；ｃｌｏｃｋｒｏｕｔｉｎｇ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｍｕｌｔｉ－ｌｅｖｅｌｍｏｄｅｌ上，时钟布线要保证连线长度最小。同时，在一个系０引言统中，每个需要时钟的作用单元与时钟源点相连，但版图设计是芯片制造的一个重要阶段，该阶段时钟信号并不能同时到达所有的作用单元，一般会也可称为逻辑设计的计算机版图集成。布局布线是产生时钟偏差。为保证系统高效无误地工作，必须版图集成的重要任务，而时钟线网的布线是芯片能保证时钟偏差最小。够正常工作的重要保证，是布线阶段需要优先考虑时钟偏差为时钟源点到时钟端点的最大延时，的线网，因为从时钟网的时钟源

6、点到各个时钟端点优化时钟偏差能动态缩减系统的时钟周期，提高系的实际路径长度决定了时钟的最大频率。由于时钟［１］统的时间性能。式（１）为计算时钟信号网的时钟布线是全局性的，其连线一般很长，在超大规模集成周期计算式：电路中，连线引起的时延占整个芯片时延的７０％以狋狆≥狋犱＋狋狊犽犲狑＋狋狊狌＋狋犱狊。（１）收稿日期：２００６－０３－２４；修订日期：２００６－０７－１２。Ｒｅｃｅｉｖｅｄ２４Ｍａｒ．２００６；ａｃｃｅｐｔｅｄ１２Ｊｕｌｙ２００６．作者简介：石文兰（１９６５－），女，河北正定人，河北工业职业技术学院信息工程与自动化系讲师，主要从事计算机控制技术、计算机辅助设计和电气自动化等

7、的研究。Ｅ－ｍａｉｌ：ｓｈｉｗｅｎｌａｎ＠１２６．ｃｏｍ。１４６０计算机集成制造系统第１２卷其中，狋为系统的时钟周期，狋为组合逻辑电路部分式建立时钟网的拓扑结构；文献［４］对ＭＭＭ算法狆犱的最长路径延迟，狋为时钟偏差，狋为同步元件的进行了改进，提出了自底向上的几何匹配方法来建狊犽犲狑狊狌启动时间（假定为沿触发），狋为同步元件信号传播立时钟二叉树，这种方法比ＭＭＭ方法节省了５％犱狊延时。～７％的线长；文献［５］将上述方法进行改进，得出了［６］狋犱＝狋犱＿ｉｎｔ犲狉犮狅狀