全芯片互连线功耗最优的布局阶段缓冲器规划方法

摘要

全芯片互连线功耗最优化的布局阶段缓冲器规划方法属于互连线设计优化技术领域，其特征在于，含有以下步骤：读入模块信息及互连线信息，建立电路的逻辑拓扑，边状态初始化为1，计算模块间互连线的时间松弛量，计算逻辑拓扑图中各边权重，利用预流推进方法得到逻辑拓扑图的最大割集，对该割集中的每条边分配时间松弛量，对于每一段互连线，根据时间松弛量分配结果，计算所需要的缓冲器尺寸和个数，以及电路消耗的总互连线功耗。本发明在不影响电路延时性能的前提下，降低了互连线总功耗，具有很高的执行效率，具有工业应用价值。

主权项

1.全芯片互连线功耗最优化的缓冲器规划方法，其特征在于，所述方法是在计算机中依次按以下步骤实现的：步骤(1).初始化设置功耗计算用的工艺参数：电源电压V_DD、时钟频率f_clk、单位尺寸缓冲器漏电流I_offn、单位尺寸缓冲器短路电路I_short，设置缓冲器的相关参数：负载电容C_L、驱动输出电阻R_d、单位尺寸缓冲器输出电阻r_s、单位尺寸缓冲器输入电容c_o、单位尺寸缓冲器输出电容c_p，设置互连线的相关参数：单位长度线电容c，单位长度线电阻r，设置功耗-时间松弛分段线性模型的相关参数：各分段区间的起始位置a_i，终止位置b_i，单位长度互连线最优延时表示线性区间斜率的模型参数m_i、n_i，以及互连线临界长度L_crit，其中功耗-时间松弛分段线性模型为：$\mathrm{\Delta P}(\alpha ,L,\mathrm{slack})=\left\{\begin{array}{cc}0& (L<=L_{\mathrm{crit}})\\ \alpha (m_{i}L+n_i\mathrm{slack})& (L>L_{\mathrm{crit}},f=\frac{\mathrm{slack}}{L·{\left(\frac{\tau }{l}\right)}_{\mathrm{opt}}}\in [a_i,b_i))\end{array}\right.$其中slack是时间松弛量，α代表信号翻转概率，L是互连线长度；互连线临界长度L_crit按下式得到：$L_{\mathrm{crit}}=2\sqrt{\frac{{2r}_s(c_0+c_p)}{\mathrm{rc}}};$步骤(2).从模块描述文件读入模块及线网信息：步骤(2.1).读入模块四角坐标，并根据此模块的四角坐标计算模块的宽、高，以及模块对应引线端的坐标；步骤(2.2).读入所选模块的时延信息；步骤(2.3).读入线网信息，记录模块的互联信息及输入输出关系，并按下式计算互连线的长度L以及初始时延：设：互连线引线端的坐标为(x₁，y₁)，(x₂，y₂)，则：互连线的长度L为：L＝|x₁-x₂|+|y₁-y₂|，设：互连线的初始延时d_Linit为$d_{\mathrm{Linit}}=2\sqrt{r_s{c}_0\mathrm{rc}}(1+\sqrt{\frac{1}{2}(1+\frac{c_p}{c_0})})*L;$步骤(3).根据步骤(2.2)的模块信息和互连信息，构造用以表示电路连接关系的有向无环图作为电路的逻辑拓扑图，图中的节点表示模块，而边表示模块之间的连线，并增加一个虚拟输入节点作为原有所有输入节点的输入，同时，增加一个虚拟输出节点作为原有所有输出节点的输出，虚拟节点的本征延时均记为0；步骤(4).按以下步骤迭代分配时间松弛量：步骤(4.1).初始设置所建有向无环图中各边的状态量为1；步骤(4.2).按以下公式计算各互连线间的时间松弛量：$\left\{\begin{array}{c}a\left(v\right)=\underset{u\in \mathrm{FI}\left(v\right)}{\max }(a\left(u\right)+d\left(u\right)+d(u,v))\\ r\left(v\right)=\underset{u\in \mathrm{FO}\left(v\right)}{\min }(r\left(u\right)-d\left(v\right)-d(v,u))\\ \mathrm{slack}(u,v)=r\left(v\right)-d\left(u\right)-a\left(u\right)-d(u,v)\end{array}\right.$其中：a(v)为信号实际到达模块v的时间，单位ns，a(u)为信号实际到达模块u的时间，单位ns，d(v)为信号通过模块v的本征延时，单位ns，d(u)为信号通过模块u的本征延时，单位ns，d(u，v)为信号通过模块v，u之间的互连线的延时，单位ns，r(v)为信号要求到达模块v的时间，单位ns，r(u)为信号要求到达模块u的时间，单位ns，slack(u，v)为模块v，u之间的互连线的时间松弛量，单位nsFI(v)为模块v的所有输入模块的集合，FO(v)为模块v的所有输出模块的集合，此处设：信号实际到达虚拟输入模块的时间为0，信号要求到达虚拟输出模块的时间为信号实际到达该模块的时间；步骤(4.3).对于时间松弛量为0的互连线，将该互连线的状态量置为0，一旦所有互连线的状态量均为0，迭代过程结束；步骤(4.4).按下式计算出所建电路的逻辑拓扑图中各边的权重w：$w=\frac{\mathrm{d\Delta P}(\alpha ,L,\mathrm{slack})}{d\left(\mathrm{slack}\right)}$即w是ΔP(α，L，slack)对slack的偏导数；步骤(4.5).利用预流推进方法得到逻辑拓扑图的最大割集，对此割集中的每条边按以下步骤分配时间松弛量：步骤(4.5.1).当互连线中不插入缓冲器时，该互连线有最大延时d_Lmax：$d_{L\max }=\frac{1}{2}{\mathrm{rcL}}^2+(R_{d}c+{\mathrm{rC}}_L)L+R_d{C}_L,$其中：R_d为驱动输出电阻(Ω)，C_L为负载电容(fF)，且处于状态i的互连线的延时有一个上限约束d_Li：d_Li＝d_Linit(1+f_i)，f_i是功耗-时间松弛分段线性模型中对应线性区间的右端点取值，d_Lmin是步骤2中得到的互连线的初始延时；设：当前状态下每条边当前的延时为d_Lcurrent，slack为步骤4.2中得到的模块之间互连线的时间松弛量，则：该边的延时应当更新为d_Lupdated；d_Lupdated＝min((d_Lcurrent+slack)，d_Lmax，d_Li)；步骤(4.5.2).若d_Lupdated被赋值为d_Lcurrent+slack或者d_Lmax，则该互连线状态量改写为0，该互连线不能再分配时间松弛量；步骤(4.5.3).若d_Lupdated被赋值为d_Li，则该互连线状态量在原有基础上加1；步骤(4.6).对于每一段互连线，根据时间松弛量分配结果计算所需要的缓冲器的尺寸s和个数N并输出，其公式如下：$\frac{k_1(c_p+c_0)}{l}+\frac{k_2}{l}+k_3(1+f){\left(\frac{\tau }{l}\right)}_{\mathrm{opt}}-[\frac{k_{1}s(c_p+c_0)}{l^2}+\frac{k_{2}s}{l^2}]\frac{\mathrm{dl}}{\mathrm{ds}}=0$$\frac{1}{l}{r}_s(c_p+c_0)+\frac{r_s}{s}c+{\mathrm{rsc}}_0+\frac{1}{2}\mathrm{rcl}-(1+f){\left(\frac{\tau }{l}\right)}_{\mathrm{opt}}=0$$[\frac{1}{2}\mathrm{rc}-\frac{r_s(c_p+c_0)}{l^2}]\frac{\mathrm{dl}}{\mathrm{ds}}+{\mathrm{rc}}_0-\frac{r_{s}c}{s^2}=0$其中，$k_1={\mathrm{\alpha V}}_{\mathrm{DD}}^2{f}_{\mathrm{clk}},$$k_2=\frac{3}{2}{V}_{\mathrm{DD}}{I}_{\mathrm{offn}},$k₃＝ln3·αV_DDI_shortf_clk，其中，s为缓冲器尺寸，即单位缓冲器大小的倍数，L为互连线长度，um，α为信号翻转概率，V_DD为电源电压，V，f_clk为工作频率，GHz，l为缓冲器间距，um，c_o为单位缓冲器输入电容，fF，c为单位长度线电容，fF/um，c_p为单位缓冲器输出电容，fF，I_offn为单位缓冲器漏电电流，uA，I_short为单位缓冲器短路电流，uA，f为时间惩罚，用实际延时超出最优延时的百分比(％)表示，为单位长度互连线最优延时，ns，设定值；缓冲器的个数N按照下式求得：表示向下取整步骤(4.7).由设定每一段互连线的功耗，计算该电路整体互连线功耗。