| 摘要: |
| 布图规划和布局构形的表示是基于随机优化方法的布图规划和布局算法的核心问题.针对Non-slicing结构的布图规划和布局,提出了一种新的基于约束图表示的模型.基于该模型及其性质,可以得到近似O(n)时间复杂度的有效的布局算法.通过引入变形网格的假设,得到了一种新的更加精确的Non-Slicing结构的表示模型:梯形网格模型.其空间复杂度为n(3+lg[n]),时间复杂度为O(n),解空间规模为n!23n-7.已经证明,梯形网格模型可以表示所有的Slicing结构的布局,同时又可以有效地表示Non-Slicing结构的布局,而时间复杂度与Slicing表示相同.实验结果表明,该表示优于刚刚发表的O-tree模型.梯形网格模型是一种拓扑模型,而O-tree的表示依赖于模块的尺寸,因而梯形网格能更有效地处理含有软模块的的布图规划问题. |
| 关键词: 积木块布图 布局 布图规划 Non-Slicing结构 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.60076016 (国家自然科学基金); the National Grant Fundamental Research 973 Program of China under Grant No.G1998030411 (国家重点基础研究973发展规划) |
|
| A Non-Slicing Floorplanning and Placement Algorithm Using a New Constraint Graph Based Model |
|
DONG She qin,HONG Xian long,HUANG Gang,GU Jun
|
| Abstract: |
| To use a stochastic optimization algorithm to search an optimum placement, the representation of the configuration of a placement is the most important and fundamental issue. A new Constraint Graph based representation SL was devised in the paper to represent the non slicing structure of placement. A nearly O(n) placement algorithm can be designed over the SL representation. With the assumption of the meta grid, we can derive a new concise representation for non slicing structures from SL representation.With assumption of the meta-grid,we can derive a new concise representation for non-slicing structures from SL.We name the new representation as Stairway Grid(SG)model.It needs n(2「lg n」)bits fora placement of nrectangular blocks.The solution space of SGrepresentation,it takes onlyO(n)time to transform it to its corresponding placement.It had been proved that all slicing structures could be represented by SG.And SGmodel also can represent non-slicing structure.Experimental results on SG model demonstrated that it is a concise and effective representation of non-slicing structure. |
| Key words: building block layout placement foorplanning non slicing structure |
