一种混合高度单元电路布局合法化问题的加速方法及装置

本发明公开了一种混合高度单元电路布局合法化问题的加速方法及装置，所述方法包括：将单元分配到最近的满足轨道约束的行，对每一行的单元按照非降的顺序确定单位顺序；对混高单元进行预处理，保证所有多行高的子单元的x‑坐标相等；将混高合法化问题转化为线性互补问题后，针对系数矩阵M的特殊结构，提出了新的分裂格式，并选取适当的正对角阵，提出SMMS算法；引入松弛参数，提出松弛移位模基矩阵分裂迭代算法RSMMS，并对算法进行了收敛性分析；采用Tetris‑like方法处理不合法的单元，依次检查每一行单元的合法性，对于不合法的单元，将其放置到最近的满足轨道约束的空闲位置。本发明能对单元坐标进行动态调整,进而加速求解，更快的完成混高单元合法化过程。