A Robust Modulus-Based Matrix Splitting Iteration Method for Mixed-Cell-Height Circuit Legalization
A Robust Modulus-Based Matrix Splitting Iteration Method for Mixed-Cell-Height Circuit Legalization
复制标题
DOI：
10.1145/3423326
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Jianli Chen;Ziran Zhu;Wen-xing Zhu;Yao-Wen Chang
中科院分区：
文献类型：
--
作者：
Jianli Chen;Ziran Zhu;Wen-xing Zhu;Yao-Wen Chang
现代电路通常包含不同行高的标准单元，以满足各种设计要求。更高的单元提供更大的驱动强度和更高的速度，但代价是更大的面积和功率。多行高度标准单元给布局设计带来了挑战性的问题，特别是异构单元结构的混合单元高度合法化问题。为了尊重全局布局中的良好单元位置，我们在本文中提出了一种鲁棒的基于模数的矩阵分裂迭代方法（RMMSIM）来解决混合单元高度合法化问题。我们提出的方法通过固定全局布局的单元排序并放宽右边界约束，首先将问题转换为等效线性互补问题（LCP），然后适当分割LCP中的矩阵，以便RMMSIM可以最优地求解LCP。 RMMSIM有效地探索了电路的稀疏特性，每次迭代仅需线性时间；因此，它可以非常有效地解决 QP。最后，非法单元的分配方案用于将这些单元与行上的放置位置对齐，并修复右边界外单元的放置（如果有）。实验结果表明了我们提出的算法的有效性和效率。此外，RMMSIM的收敛性和最优性得到了理论证明和实证验证。特别是，本文为需要高效解决大规模凸二次规划问题的各种优化问题提供了一种新的 RMMSIM 公式。
Modern circuits often contain standard cells of different row heights to meet various design requirements. Taller cells give larger drive strengths and higher speed at the cost of larger areas and power. Multi-row height standard cells incur challenging issues for layout designs, especially the mixed-cell-height legalization problem with heterogeneous cell structures. Honoring the good cell positions from global placement, we present in this article a robust modulus-based matrix splitting iteration method (RMMSIM) to solve the mixed-cell-height legalization problem. Fixing the cell ordering from global placement and relaxing the right-boundary constraints, our proposed method first converts the problem into an equivalent linear complementarity problem (LCP), and then properly splits the matrices in the LCP so that the RMMSIM can solve the LCP optimally. The RMMSIM effectively explores the sparse characteristic of a circuit, and takes only linear time per iteration; as a result, it can solve the QP very efficiently. Finally, an allocation scheme for illegal cells is used to align such cells to placement sites on rows and fix the placement of out-of-right-boundary cells, if any. Experimental results show the effectiveness and efficiency of our proposed algorithm. In addition, the RMMSIM convergence and optimality are theoretically proved and empirically validated. In particular, this article provides a new RMMSIM formulation for various optimization problems that require solving large-scale convex quadratic programming problems efficiently.