一种利用图建模的宏模块合法化算法

Macro-modules′ Legalization Algorithm Modeled by Gragh

提出一种基于有向限制图的宏模块合法化算法,将宏模块合法化问题抽象为图的问题.该算法建立水平和垂直方向两张有向图,把每个宏模块抽象为两张图中的结点,把两个模块之间的位置关系抽象为图中的边,从而把二维问题转化成两个一维问题,大大降低问题的复杂度.实验证明,该算法可以有效地消除宏模块之间的重叠,并且有效控制了所有宏模块的位移距离.

In this paper,we propose a directed constraint graphic based algorithm to legalize the macros.It creates two directed graphs,the horizontal one and the vertical one.Each macro is abstracted as a node in each graph,and the position relationship of every pair of macros is abstracted as edges in graphs.This algorithm abstracts the macro legalization problem to a graphic problem,and greatly reduces the complexity of the problem.Experiments show that the algorithm can be very effective.