一种电压岛的多供电引脚分配方法

摘要

本发明公开了一种电压岛的多供电引脚分配方法，首先根据电压岛的物理信息，基于电压岛所包含的电路宏模块的坐标信息，采用Kmeans汇聚算法将其划分成个                                                个簇，然后针对所有簇中的电路宏模块归属进行微调，使得各个簇的功耗密度大致相等，最后根据电流密度的大小给电路宏模块连接的弹簧分配不同的劲度系数，确定弹簧系统的能量均衡点位置并完成每个簇所包含电路宏模块的供电引脚分配，重复上述过程可完成所有电压岛所需数目的多供电引脚分配；本发明方法能快速有效的优化芯片上电压岛电源网络节点的电压降。从而丰富了芯片电压岛的供电引脚分配的自动设计优化方法，又降低了设计成本。通过实例验证，本发明的方法得到的电源网络电压降能得到有效降低。

主权项

一种电压岛的多供电引脚分配方法，其特征在于包括以下步骤：步骤①：定义电压岛为工作在同一工作电压下且占据连续二维物理空间的电路宏模块组成的区域，芯片由若干电压岛组成；计算机读入和分析用户提供的电压岛信息、电路宏模块的物理坐标信息、供电引脚位置信息、每个电压岛所需的供电引脚个数信息；步骤②：定义电压岛K_island中所包含的电路宏模块集合为B，芯片的可用供电引脚集合为P，电压岛K_island中电路宏模块的总个数为|B|，对于每一个电路宏模块b_p∈B，根据电路宏模块物理坐标信息可确定b_p中心点坐标定义电压岛K_island所需的供电引脚个数为n_island；步骤③：采用Kmeans聚类算法将电压岛K_island中所包含的电路宏模块划分成n_island个簇，具体步骤如下：首先在电压岛K_island所占据的二维空间中随机产生n_island个初始中心点，坐标分别为然后分别计算每个电路宏模块b_p的中心点到n_island个初始中心点的欧几里得距离，即${\mathrm{dist}}_{pq}=\sqrt{{(x_{b_p}-x_{c_q})}^2+{(y_{b_p}-y_{c_q})}^2},p\in [1,|B\left|\right],q\in [1,n_{island}]---\left(1\right)$假定电路宏模块b_p的中心点到第q个初始中心点的欧几里得距离最小，则标记该电路宏模块b_p为q，即电路宏模块b_p当前被划分到第q个簇；步骤④：更新n_island个簇的初始中心点坐标，更新的初始中心点坐标为第q个簇中包含的所有电路宏模块坐标的平均值；分别计算n_island个簇中所有电路宏模块的中心点坐标到更新后的初始中心点坐标的均方误差之和，并计算相邻迭代次数中得出的均方误差之和的变化量Δ；若Δ>0.001，则重复步骤③～④，否则停止迭代，输出划分的n_island个簇的信息；步骤⑤：计算n_island个簇的平均面积；对于n_island个簇，对其包含的电路宏模块归属进行微调，使得每个簇的面积与平均面积的差值小于15％，具体步骤如下：步骤⑤‑1：将n_island个簇按照面积大小进行降序排列，得到簇1，簇2，…，簇n_island，计算簇i(1≤i≤n_island‑1)中所有电路宏模块到簇j(i≤j≤n_island)中心点的欧几里得距离，若簇i中的电路宏模块b_p到簇j中心点的欧几里得距离最小，则将电路宏模块b_p移至簇j中；步骤⑤‑2：更新n_island个簇的初始中心点坐标，更新的初始中心点坐标为第q个簇中包含的所有电路宏模块坐标的平均值；步骤⑤‑3：若每个簇的面积与平均面积的差值大于或等于15％，则重复步骤⑤‑1～⑤‑2，否则停止迭代，输出划分的n_island个簇的信息；步骤⑥：对于n_island个簇，针对每个簇中所包含的每一个电路宏模块b_p，假设以电路宏模块b_p的中心点为固定点，该固定点与一个零长度，劲度系数为k_bi的弹簧的一端连接，并将每个簇中所有与电路宏模块所连接的弹簧的另一端互相连接在一起，所有的弹簧组成了弹簧系统；计算出弹簧系统的能量均衡点e的坐标(x_e,y_e)；若一个簇中所有电路宏模块中具有最小面积的电路宏模块的面积值为A₀，电路宏模块b_p的面积值为则$k_{b_p}=A_{b_p}/A_0---\left(2\right)$能量均衡点e到各电路宏模块中心点所引起的弹簧拉力可分解为在水平方向的分力和垂直方向的分力其中能量均衡点e的坐标可通过公式(5)和(6)求解得到：寻找出一个供电引脚p_j∈P，使得p_j到能量均衡点e的曼哈顿距离最小，即最小，p_j即为其所属簇的供电引脚分配的位置；依次为每个簇分配供电引脚，完成电压岛K_island所需的n_island个供电引脚的分配，对于已分配的供电引脚，将其从可用供电引脚集合P中移除，以避免供电引脚的重复分配；步骤⑦：重复步骤③～⑥完成芯片中所有电压岛的供电引脚分配。