摘要: 布图规划和布局是布图设计流程中较早的阶段，其完成的质量对最终芯片的面积和性能有很大影响，随着工艺的发展，布图规划问题已经从单纯的面积和线长优化发展成为多目标多约束的问题。尤其在深亚微米工艺设计中，IP模块的广泛使用和新的封装工艺的使用使得集成电路器件并不局限于矩形的模块，如数据电路模块（Data Path Block）由于其相互关联的控制关系使其具有特殊的形状（L/T型），这使得电路设计中需要考虑L/T型模块的处理。基于角模块序列（CBL）布图规划表示方法，本文提出了处理多边形模块L/T形模块的崭新思路，将L/T形模块的布图规划问题转化为子模块的对齐-相邻约束问题，并能够在线性运算复杂度下实现对已有序列的判断和修正，从而保证了L/T多边形模块在最终布图结果中保持原有构形。本文提出的多边形模块处理方法，能够对L/T形模块进行快速有效的布局，保持其多边形构形，不仅可以处理二划分结构，同时也可以处理非二划分结构的布图结果。通过对L/T形模块的划分，将多边形布图问题转化为模块之间的相邻-对齐约束，并根据角模块序列的特征，提出了相邻-对齐关系的充分条件，根据该充分条件对角模块序列进行扫描，即可找到角模块序列所对应的布图中存在的相邻-对齐关系，并且设计子模块的组合过程和子模块的对齐操作来维持布图规划中L/T形模块的整体形状。从而在进行布图摆放得到布图结果之前，即可以对L/T模块的子模块的位置进行修正，尽可能保证子模块之间的相对关系，提高布图搜索效率，避免对不合理解的搜索。在模块交换过程中，由于约束情况的复杂性，仍然有可能存在不可修复的约束条件，因此引入了空模块的方法。实验结果表明，空模块的引入不仅提高了布图的效率而且为模块交换提供更多可能位置。根据相邻对齐约束的特性，本文中设计了相应的惩罚函数项，能够合理有效的衡量布图结果中的约束满足情况，并且控制其优化搜索过程，保证最终解的合理性。为了进一步的提高芯片利用率，加速搜索收敛过程，针对布图结果的优化问题，我们将模块的软化以及L/T形模块的旋转和翻转操作嵌入到优化过程中，与以往多边形模块布图算法相比，其实验结果和效率上都具有一定优势。本文提出的多边形模块的布图规划算法，能够保持最终布图结果中多边形模块的原有形状而并不发生重叠，该算法可以进一步扩展，用于解决面向互连规划的布图规划问题。