X结构下超大规模集成电路总体布线方法

摘要

本发明涉及一种X结构下超大规模集成电路总体布线方法，包括以下步骤：初始阶段，采用Steiner最小树方法将多端线网分解为多个两端线网，并对可连接的两端线网采用X结构边连接，即进行初始布线，得到近似的布线拥挤分布情况；主阶段，从所述近似的初始布线结果中选取最拥挤区域作为当前布线区域，为当前布线区域构建整数线性规划模型并求解；继而不断扩大布线区域并依次求解，直至布线区域扩张至整个芯片为止；后处理阶段，重新定义布线边代价，利用基于所述布线边代价的迷宫算法对尚未布通的两端线网进行布线，得到最终的总体布线结果。该方法有利于提高布线方案的质量，且易于实现，使用效果好。

主权项

一种X结构下超大规模集成电路总体布线方法，其特征在于，包括以下步骤：(1)初始阶段，采用Steiner最小树方法将多端线网分解为多个两端线网，并对可连接的两端线网采用X结构边连接，即进行初始布线，得到近似的布线拥挤分布情况；(2)主阶段，从所述近似的布线拥挤分布情况中选取最拥挤区域作为当前布线区域，为当前布线区域构建整数线性规划模型并求解；继而不断扩大布线区域并依次求解，直至布线区域扩张至整个芯片为止；(3)后处理阶段，重新定义布线边代价，利用基于所述布线边代价的迷宫算法对尚未布通的两端线网进行布线，得到最终的总体布线结果；在主阶段中，所述整数线性规划模型为：$MIN:\beta *({\alpha }_1*\underset{j=1}{\overset{t}{\Sigma }}{y}_j*{\mathrm{Wl}}_j+{\alpha }_2*std(cong\left(e_1,...,e_p\right)\left)\right)$$S.T.:\underset{y_j\in N_k}{\Sigma }{y}_j=1,k=1,2,...,n$$\beta =\left\{\begin{array}{ccc}1,& \begin{array}{cc}if& \underset{j=1}{\overset{1}{\Sigma }}{a}_{ij}{y}_j\le C\left(e_i\right)\end{array}& \forall e_i,i=1,2,...,p\\ 1,1^r,& else& \end{array}\right.$y_j∈{0,1},j＝1,2,···,t其中Wl_j表示候选解y_j的线长；std()表示所有边拥挤度的标准差；cong()表示e₁到e_p的拥挤度集合，α₁和α₂分别表示两个优化目标的权重大小；β表示惩罚项，用以对违反布线边容量约束的方案进行一定程度的惩罚；y_j表示候选解被选择与否，其取值为0或1，而表示对于同一线网N_k的候选解的取值之和为1，确保只有一个候选解被选取；n表示线网总数，e_i表示总体布线网格边，a_ij表示候选解j是否通过边e_i，C(e_i)表示边e_i的最大允许走线数，p表示总体布线网格边数，r表示违反约束的边数，t表示候选解的总数。