基于新约束图模型的布图规划和布局算法(英文)

A Non-Slicing Floorplanning and Placement Algorithm Using a New Constraint Graph Based Model

布图规划和布局构形的表示是基于随机优化方法的布图规划和布局算法的核心问题 .针对 Non- slicing结构的布图规划和布局 ,提出了一种新的基于约束图表示的模型 .基于该模型及其性质 ,可以得到近似 O(n)时间复杂度的有效的布局算法 .通过引入变形网格的假设 ,得到了一种新的更加精确的 Non- Slicing结构的表示模型 :梯形网格模型 .其空间复杂度为 n(3+ lg[n]) ,时间复杂度为 O(n) ,解空间规模为 n!2 3 n-7.已经证明 ,梯形网格模型可以表示所有的 Slicing结构的布局 ,同时又可以有效地表示 Non- Slicing结构的布局 ,而时间复杂度与 Slicing表示相同 .实验结果表明 ,该表示优于刚刚发表的 O- tree模型 .梯形网格模型是一种拓扑模型 ,而 O- tree的表示依赖于模块的尺寸 。

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 . We name the new representation as Stairway Grid (SG) model. It needs n(3+) bits for a placement of n rectangular blocks. The solution space of SG is n!2 3n-7 . For a SG representation, it takes only O(n) time to transform it to its corresponding placement. It had been proved that all slicing structures could be represented by SG . And SG model also can represent non slicing structure. Experimental results on SG model demonstrated that it is a concise and effective representation of non slicing structure.