边界约束下的增量式布图规划算法.pdfVIP

清华大学学报(自然科学版)2007年第47卷第10期 33／40 !墨墨堕!QQQ二QQ§± CN 1685—1688 11一ZZZ3／NJ Univ(Sci1℃ch)，2007，V01．47，No．10 TsinghIla 边界约束下的增量式布图规划算法 杨柳，董社勤，洪先龙 (清华大学计算机科学与技术系，EDA实验室，北京100084) 摘要：快速地在局部范围内调整布圈已经成为一种设计 过增量式布图规划进行多次调整、分阶段去满足。其 需要。该文提出了一种二阶段法来实现边界约束下的增量式 次，在现有的很多高层次综合和物理设计结合的研 布图规划算法。根据已有布图规划建立松弛推移图，直观描 究中，增量式布图规划都成为一个不可或缺的阶段。 述各模块之问。空白区”和松弛量的情况，同时建立模块交 在片上系统(SoC)设计中，会出现大量IP模块；虽 换圈，记录所有具有形状相似特征的模块集合，基于这2个 然各IP模块间功能相互独立，但对芯片整体性能优 圈进行增量式布图规划。第1阶段，基于推移图和交换图调 化来说，它们之间有着一些约束指导。比如希望IP 整布图规划，使其满足边界约束。第2阶段，再次利用交换图 模块A上某些功能单元模块和IP模块B上的某些 进行互连性能优化。实验结果表明该算法在较短的时间里不 仅对原有布圈规划进行了有效调整满足了给定的所有的几 功能单元模块相邻，那么实现上会让IP模块A和B 何约束，而且还保证了芯片的面积和线长效果。 上的有相邻需求的这些功能单元模块都往边界上 关键词：超大规模集成电路}增量式布图规划，边界约束， 靠，这样以实现相邻。另外在设计中，希望插入的新 松弛推移圈，模块交换图 模块尽可能靠近供电区域，这种情况下就需要指定 边界模块进行布图。目前已有的边界约束算法，如文 47 中图分类号：TN 文献标识码：A 文章编号：1000_0054(2007)10一1685一04 [1，2]，多是在随机优化过程中进行，或是在一开始 布局中就判断执行约束，这样的做法大部分耗时比 较长，这对于要求高速微调的增量式布图规划问题 Incremental with floorplanningalgorithm 并不适用。文[3—5]提到了几种现有的增量式布图 constraints boundary 算法，但是并没有考虑任何带有几何约束的情况。据 YANGLiu，DONGSheqjn。HONGXianlo叼 作者所知，到目前为止还没有在增量式布图规划问 (EDA of scIen∞蚰d Labontory，De呻rtmentC帅puter 题中解决几何约束的相关研究。 mhnoIogy，T