An Incremental Algorithm for Non-Slicing Floorplan Based on Corner Block List Representation  

基于角模块布图表示的增量式布图规划算法(英文)

作　　者：杨柳[1] 马昱春[1] 洪先龙[1] 董社勤[1] 周强[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《Journal of Semiconductors》2005年第12期2335-2343,共9页半导体学报（英文版）

基　　金：国家自然科学基金(批准号:90407005,60473126);Intel公司3D布图规划和布局资助项目~~

摘　　要：We present a novel incremental algorithm for non-slicing floorplans based on the corner block list representation. The horizontal and vertical adjacency graphs are derived from the packing of the initial floorplanning results. Based on the critical path and the accumulated slack distances we define,we choose the best position for insertion and do a series of operations incrementally, such as deleting modules, adding modules, and resizing modules quickly. This incremental floorplanning algorithm has a very high speed less than 1μm,which is one of the most important measures in this research. The algorithm preserves the original good performances on area and wire length. It can also supply other tools with good physical estimates for area, wire length, and other performance guidelines.提出了一种基于CBL布图表示的新的增量式布图规划算法.该算法能很好地解决包括不可二划分结构在内的布图规划问题.针对现有增量式的一些需求,算法给出了相应的高速解决方案.在已有的初始布局的基础上,基于CBL表示方法建立水平约束和垂直约束图,利用图中关键路径和各模块之间的累加的距离松弛量进行增量式操作.对于新模块的插入,在力求面积最小,线长最短和移动模块数目最少的目标指引下能快速地找到最佳位置作为插入点,高效地完成相关操作,算法的时间复杂性仅为O(n).通过对一组来自工业界的设计实例的测试结果表明,该算法在保证芯片的面积、线长等性能不降低甚至有所改善的情况下,运行速度相当快,仅在μs量级,满足了工业界对增量式布图规划算法在速度上的首要要求,同时保证了基本性能的稳定.

关 键 词：incremental floorplanning corner block list adjacency graph balance node 

分 类 号：TN402[电子电信—微电子学与固体电子学]