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

小 型 微 型 计 算 机 系 统 Journal of Chinese Computer Systems 2011 年 10 月 第 10 期 Vol. 32 No． 10 2011 一种利用图建模的宏模块合法化算法 鑫1，2 ，闫海霞1 ，钱 旭2 ，吕勇强3 ，刁 屹1 ，周 强1 吴 1 ( 清华大学 计算机科学与技术系，北京 100084) 2 ( 中国矿业大学 机电与信息工程学院，北京 100083) 3 ( 清华大学 信息技术研究院，北京 100084) E-mail: groovy87@ 163． com 摘 要: 提出一种基于有向限制图的宏模块合法化算法，将宏模块合法化问题抽象为图的问题． 该算法建立水平和垂直方向两 张有向图，把每个宏模块抽象为两张图中的结点，把两个模块之间的位置关系抽象为图中的边，从而把二维问题转化成两个一 维问题，大大降低问题的复杂度． 实验证明，该算法可以有效地消除宏模块之间的重叠，并且有效控制了所有宏模块的位移距离． 关 键 词: 宏模块; 合法化; 有向限制图; 布局 中图分类号: TP393 文献标识码:A 文 章 编 号:1000-1220(2011)10-1933-04 Macro-modules Legalization Algorithm Modeled by Gragh WU Xin1，2 ，YAN Hai-xia1 ，QIAN Xu2 ，LV Yong -qiang3 ，DIAO Yi1 ，ZHOU Qiang1 1 ( Department of Computer Science ＆ Technology，Tsinghua University，Beijing 100084，China) 2 ( School of Mechanical Electronic ＆ Information Engineer，China University of Mining ＆ Technology，Beijing 100083，China) 3 ( Research Institute of Information Technology，Tsinghua University，Beijing 100084，China) Abstract: In this paper，w e propose a directed constraint graphic based algorithm to legalize the macros． It creates tw o directed graphs，the horizontal one and the vertical one． Each macro is abstracted as a node in each graph，and the position relationship of ev- ery 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． Key words: macro ; legalization; directed constraint graph; placement 模块合法化算法，与其他算法最大的区别和本文的贡献在于: ( 1) 宏模块合法化以所有宏模块受到的扰动之和最小为 目标，并在此约束条件下消除所有宏模块之间的重叠． ( 2) 把二维问题转化为两个一维问题，并把宏模块合法 化问题抽象为解决图问题，从而降低了算法的复杂度． 1 引 言 随着集成电路技术的发展，芯片上集成的单元数目越来 越多，系统也越来越复杂; 在实际设计中，芯片上可能需要预 先放置诸如 ROM ，RAM ，PLA 等宏模块，于是产生了混合模 式布局问题［1，11］． 在混合模式详细布局中，宏模块面积比较大，通常是标准 单元的几十倍甚至上百倍; 高度通常是单行高度的整数倍． 这 些特性使得宏模块很难和标准单元同时用相同的算法进行布 局． 所以，研究出高效快速的混合模式布局算法显得尤为重要． 宏模块与标准单元的不同使得混合模式布局算法通常采 用分阶段布局的策略: 首先，不考虑标准单元的存在，用某些 特定的算法消除所有宏模块之间的重叠; 当宏模块合法化完 成后把它们作为固定模块