一种基于推迟合并策略的低功耗时钟树综合实现方法

1.本发明属于低功耗时钟技术领域，具体是指一种基于推迟合并策略的低功耗时钟树综合实现方法。


背景技术：

2.数字芯片设计中时钟是非常重要的一部分，时钟信号是数据传输的基准，它对于同步数字系统的功能、性能和稳定性起决定性作用，所以时钟信号的特性及其分配网络尤被人们关注。时钟信号在传递过程中会不断衰减，如果信号强度过弱，每个寄存器的时钟周期将无法同步，严重影响芯片的性能。我们通过插入缓冲器来增强时钟信号，使信号的转换时间缩短。同时，插入缓冲器还能减小延迟。时钟树综合的概念是指设计一个零时钟偏差的时钟树，并沿着设计的时钟路径自动插入缓冲器，以平衡所有时钟延迟并满足要求的时钟转换时间。时钟信号必须保证在最差的条件下，时序要求如时钟偏差(clockskew)，时钟转换时间(slew)能得到满足，否则对时钟信号任何不当的控制都可能导致紊乱情况，将错误的数据信号锁存到寄存器，从而导致系统功能的错误。今天的芯片设计中总动态功耗的30％甚至更多都是消耗在时钟网络上，因此降低时钟树的总功耗也是重要目标之一。所以设计一个高效的时钟树综合方法对整个芯片后端物理设计至关重要。
3.设计一个时钟树首先要设计时钟树的拓扑结构，而其质量受到时钟合并策略的影响，不同的合并策略产生的时钟树差别很大。传统的合并策略是优先合并曼哈顿距离最近的两棵子树，但当这两棵子树延迟相差很大时，合并后会增加蛇形走线。而过多的蛇行走线会增加互连线长，进而增加功耗。而且蛇行走线受到的工艺波动的影响很大，进而增加时钟延迟的不确定性，最后导致时钟偏差的增大。所以为了减少蛇形走线，我们在设计合并策略时不能只考虑曼哈顿距离，而是要考虑合并所需要的所有资源，在本发明中我们将资源定义为互连线电容和缓冲器电容之和。
4.我们通过插入缓冲器来满足时钟转换时间约束。传统的方法往往是在时钟树拓扑结构构造完之后再进行缓冲器插入，这容易导致时钟偏差的波动，进而影响整个时钟树的性能。所以本发明采用缓冲器插入与时钟树合并同时进行的算法，避免影响时钟偏差。
5.时钟源与时钟引脚之间需要用互连线连接。在时钟布线阶段，我们将布局阶段摆放好的宏单元等当作障碍物，互连线允许与障碍物重合，而缓冲器不允许与障碍重合，传统的做法是布线时完全避开障碍物，但这可能会增加线长，进而增加功耗。所以本发明设计了一种既能减少线长也能使缓冲器避开障碍的算法。


技术实现要素：

6.为解决上述现有难题，本发明提供了一种时钟树综合方法使用了推迟合并算法，在缓冲器插入算法中，使用自底向上的插入策略，最大程度避免了缓冲器对时钟偏差的影响，使用双向宽度优先搜索算法进行时钟避障布线的基于推迟合并策略的低功耗时钟树综合实现方法。
7.本发明采取的技术方案如下：本发明基于推迟合并策略的低功耗时钟树综合实现方法，包括如下步骤：
8.步骤1：本发明使用数据结构中的二叉树作为时钟树的基础结构，为了使根节点到叶子结点的时钟传播延时相等，本发明使用推迟合并算法(dme)构造时钟树，该算法在第一阶段采用自底向上的合并方式得到所有合并段(mergingsegment)，即所有可能的合并点位置，等到根节点位置确定后，第二阶段确定每个合并点的精确位置，这样可以使互连线长最短，功耗最低；
9.步骤2：在合并时，如果缓冲器与障碍物可能重合，就重新寻找合并段；
10.步骤3：为了满足时钟转换时间约束，且使延迟平衡不受插入的缓冲器影响，每合并完一对子树，生成对应的合并段之后，就在该层进行缓冲器插入操作，但此时并不确定缓冲器的具体位置，只确定缓冲器相互之间的距离，直到dme的第二阶段确定每个合并点最终的位置后，再确定缓冲器的具体位置。
11.进一步地，步骤1包含如下步骤：
12.步骤1.1，在寻找待合并的子树时(第一轮的子树为所有的触发器)，将所有子树构造一个德劳内三角剖分图。德劳内三角剖分可以将寻找最近邻的时间复杂度从o(n)降到o(nlogn)；
13.步骤1.2，对德劳内三角剖分图中每条边计算其权重，权重表示为该边对应的两个子树合并所需要的互连线电容与缓冲器电容之和；
14.步骤1.3，将所有边进行快速排序，找到权重最小的一条边，将该边对应的两个子树进行合并，生成对应的合并段，并将其作为新生成的树加入德劳内三角剖分图。
15.进一步地，步骤2包含如下步骤：
16.步骤2.2，将新生成的合并段与两个子树的合并段的边界构造一个矩形区域；
17.步骤2.3，如果该矩形区域与障碍物相交，就使用双向宽度优先搜索算法重新寻找合并段。
18.进一步地，步骤3包含如下步骤：
19.步骤3.1，缓冲器自身的延时与输出转换时间取决于其输入转换时间和负载电容，在本发明中，输入转换时间(inputslew)是预先指定的值，为了实得到缓冲器相对准确的延时和输出转换时间，使用ngspice仿真来建立缓冲器的延时和输出转换时间的查找表；
20.步骤3.2，人为给定一个距离值，根据peri模型计算时钟转换时间，如果存在时钟转换时间违例，间隔的距离将被调整为更小的值，直到满足时钟转换时间约束；
21.步骤3.3，改变缓冲器的尺寸，重复步骤3.2；
22.步骤3.4，在找到缓冲器所有的可行解之后，我们选择具有最小功耗的可行解；
23.步骤3.5，当该层的缓冲器确定后，由于缓冲器会影响到两个子树的传播延迟，所以将从两个子树的最后一个缓冲器开始重新计算合并段位置；
24.步骤3.6，不断向上层迭代直到时钟树的每一层合并完，且确定插入的缓冲器后，然后执行dme的第二阶段，确定每个合并点和缓冲器的具体位置，接着进行布线，将它们用互连线连接，最后输出时钟树综合生成的解。
25.采用上述结构本发明取得的有益效果如下：本方案提出的基于推迟合并策略的低功耗时钟树综合实现方法，时钟树综合算法保证了时钟树具有很小的时钟偏差，且精准的
缓冲器插入算法保证了时钟树具有较小的的功耗。本发明的时钟树综合算法应用在ispd09和ispd10的基准电路上对比了同类的设计方法，时钟偏差及总功耗显著减少。时钟树综合是后端物理设计的重要组成部分，如此一来非常有助于芯片最后的时序收敛及运行时的性能。
附图说明
26.图1为本发明的整体流程图；
27.图2为本发明新生成的合并段与两个子树的合并段构成的矩形区域，其中，图2(a)是新生成的合并段与两个子树的合并段构成的矩形区域，其中ms_a和ms_b是子树的合并段，ms_v是新生成的合并段；图2(b)是新生成的合并段与两个子树的合并段构成的矩形区域与障碍物有重叠部分示意图；
28.图3为本发明的双向宽度优先搜索算法示意图；
29.图4为本发明的缓冲器插入的示意图。
具体实施方式
30.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例；基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
31.本方案提出的基于推迟合并策略的低功耗时钟树综合实现方法，包括如下步骤：
32.步骤1：本发明使用数据结构中的二叉树作为时钟树的基础结构，为了使根节点到叶子结点的时钟传播延时相等，本发明使用推迟合并算法(dme)构造时钟树，该算法在第一阶段采用自底向上的合并方式得到所有合并段(mergingsegment)，即所有可能的合并点位置，等到根节点位置确定后，第二阶段确定每个合并点的精确位置，这样可以使互连线长最短，功耗最低；
33.步骤2：在合并时，如果缓冲器与障碍物可能重合，就重新寻找合并段；
34.步骤3：为了满足时钟转换时间约束，且使延迟平衡不受插入的缓冲器影响，每合并完一对子树，生成对应的合并段之后，就在该层进行缓冲器插入操作，但此时并不确定缓冲器的具体位置，只确定缓冲器相互之间的距离，直到dme的第二阶段确定每个合并点最终的位置后，再确定缓冲器的具体位置。
35.步骤1包含如下步骤：步骤1.1，在寻找待合并的子树时(第一轮的子树为所有的触发器)，将所有子树构造一个德劳内三角剖分图。德劳内三角剖分可以将寻找最近邻的时间复杂度从o(n)降到o(nlogn)；
36.步骤1.2，对德劳内三角剖分图中每条边计算其权重，权重表示为该边对应的两个子树合并所需要的互连线电容与缓冲器电容之和；
37.步骤1.3，将所有边进行快速排序，找到权重最小的一条边，将该边对应的两个子树进行合并，生成对应的合并段，并将其作为新生成的树加入德劳内三角剖分图。
38.步骤2包含如下步骤：步骤2.2，将新生成的合并段与两个子树的合并段的边界构造一个矩形区域；
39.步骤2.3，如果该矩形区域与障碍物相交，就使用双向宽度优先搜索算法重新寻找合并段。
40.步骤3包含如下步骤：步骤3.1，缓冲器自身的延时与输出转换时间取决于其输入转换时间和负载电容，在本发明中，输入转换时间(inputslew)是预先指定的值，为了实得到缓冲器相对准确的延时和输出转换时间，使用ngspice仿真来建立缓冲器的延时和输出转换时间的查找表；
41.步骤3.2，人为给定一个距离值，根据peri模型计算时钟转换时间，如果存在时钟转换时间违例，间隔的距离将被调整为更小的值，直到满足时钟转换时间约束；
42.步骤3.3，改变缓冲器的尺寸，重复步骤3.2；
43.步骤3.4，在找到缓冲器所有的可行解之后，我们选择具有最小功耗的可行解；
44.步骤3.5，当该层的缓冲器确定后，由于缓冲器会影响到两个子树的传播延迟，所以将从两个子树的最后一个缓冲器开始重新计算合并段位置；
45.步骤3.6，不断向上层迭代直到时钟树的每一层合并完，且确定插入的缓冲器后，然后执行dme的第二阶段，确定每个合并点和缓冲器的具体位置，接着进行布线，将它们用互连线连接，最后输出时钟树综合生成的解。
46.其中，输入数据为所有触发器的坐标信息及缓冲器库和导线库，约束为最大时钟转换时间和最大总电容，最终的目标是构造一个插入缓冲器后的时钟树，且该时钟树满足给定的约束条件。
47.在选择子树进行合并时，使用合并所需要电容作为成本函数，公式1-3用于计算所需电容。
48.cost(i，j)＝cl+c
buf
49.公式1
[0050][0051][0052]
其中c为单位长度的电容，r为单位长度的电阻，d1和d2分别为两棵子树的传播延迟，c1和c2分别为两棵子树的负载电容，d
min
为两棵子树的最小曼哈顿距离，d1为左子树到合并段的曼哈顿距离，c
buf
为合并所需要的缓冲器的电容。
[0053]
在进行缓冲器插入时，就有可能导致缓冲器与障碍物重合，所以要重新生成合并段。
[0054]
双向宽度优先搜索算法，将布线区域划分成m
×
n的网格，将两棵子树的合并段映射到网格上，然后各自同时进行宽度优先搜索，每向外搜索一圈，就要增加相应的延迟，最后相遇的那个点就是重新生成的合并段，如果两个子树的延迟不平衡，则延迟较低的子树对应的网格先搜索，直到两边的延迟相等，然后再同时搜索。
[0055]
缓冲器插入间隔的距离随缓冲器尺寸的变化而变化，尺寸大的缓冲器驱动能力更强，所以间隔的距离更大，由于第一个缓冲器驱动的子树可能不同，首先要确定第一个缓冲器的间隔距离，因为缓冲器的结构影响，只能看到其上游的负载电容，所以之后插入的缓冲器的间隔距离是一样的。
[0056]
需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。
[0057]
尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。

技术特征：
1.一种基于推迟合并策略的低功耗时钟树综合实现方法，其特征在于：包括如下步骤：步骤1：本发明使用数据结构中的二叉树作为时钟树的基础结构，为了使根节点到叶子结点的时钟传播延时相等，本发明使用推迟合并算法构造时钟树，该算法在第一阶段采用自底向上的合并方式得到所有合并段，即所有可能的合并点位置，等到根节点位置确定后，第二阶段确定每个合并点的精确位置，这样可以使互连线长最短，功耗最低；步骤2：在合并时，如果缓冲器与障碍物可能重合，就重新寻找合并段；步骤3：为了满足时钟转换时间约束，且使延迟平衡不受插入的缓冲器影响，每合并完一对子树，生成对应的合并段之后，就在该层进行缓冲器插入操作，但此时并不确定缓冲器的具体位置，只确定缓冲器相互之间的距离，直到dme的第二阶段确定每个合并点最终的位置后，再确定缓冲器的具体位置。2.根据权利要求1所述的一种基于推迟合并策略的低功耗时钟树综合实现方法，其特征在于：步骤1包含如下步骤：步骤1.1，在寻找待合并的子树时，将所有子树构造一个德劳内三角剖分图。德劳内三角剖分可以将寻找最近邻的时间复杂度从o(n)降到o(nlogn)；步骤1.2，对德劳内三角剖分图中每条边计算其权重，权重表示为该边对应的两个子树合并所需要的互连线电容与缓冲器电容之和；步骤1.3，将所有边进行快速排序，找到权重最小的一条边，将该边对应的两个子树进行合并，生成对应的合并段，并将其作为新生成的树加入德劳内三角剖分图。3.根据权利要求1所述的一种基于推迟合并策略的低功耗时钟树综合实现方法，其特征在于：步骤2包含如下步骤：步骤2.2，将新生成的合并段与两个子树的合并段的边界构造一个矩形区域；步骤2.3，如果该矩形区域与障碍物相交，就使用双向宽度优先搜索算法重新寻找合并段。4.根据权利要求1所述的一种基于推迟合并策略的低功耗时钟树综合实现方法，其特征在于：步骤3包含如下步骤：步骤3.1，缓冲器自身的延时与输出转换时间取决于其输入转换时间和负载电容，在本发明中，输入转换时间是预先指定的值，为了实得到缓冲器相对准确的延时和输出转换时间，使用ngspice仿真来建立缓冲器的延时和输出转换时间的查找表；步骤3.2，人为给定一个距离值，根据peri模型计算时钟转换时间，如果存在时钟转换时间违例，间隔的距离将被调整为更小的值，直到满足时钟转换时间约束；步骤3.3，改变缓冲器的尺寸，重复步骤3.2；步骤3.4，在找到缓冲器所有的可行解之后，我们选择具有最小功耗的可行解；步骤3.5，当该层的缓冲器确定后，由于缓冲器会影响到两个子树的传播延迟，所以将从两个子树的最后一个缓冲器开始重新计算合并段位置；步骤3.6，不断向上层迭代直到时钟树的每一层合并完，且确定插入的缓冲器后，然后执行dme的第二阶段，确定每个合并点和缓冲器的具体位置，接着进行布线，将它们用互连线连接，最后输出时钟树综合生成的解。5.根据权利要求1所述的一种基于推迟合并策略的低功耗时钟树综合实现方法，其特征在于：在选择子树进行合并时，使用合并所需要电容作为成本函数，公式1-3用于计算所
需电容。cost(i，j)＝cl+c
buf
公式1公式1其中c为单位长度的电容，r为单位长度的电阻，d1和d2分别为两棵子树的传播延迟，c1和c2分别为两棵子树的负载电容，d
min
为两棵子树的最小曼哈顿距离，d1为左子树到合并段的曼哈顿距离，c
buf
为合并所需要的缓冲器的电容。

技术总结
本发明公开了一种基于推迟合并策略的低功耗时钟树综合实现方法，包括如下步骤：输入、自底向上阶段、自顶向下阶段、输出。本发明属于低功耗时钟技术领域，具体是提供了一种时钟树综合方法使用了推迟合并算法，在缓冲器插入算法中，使用自底向上的插入策略，最大程度避免了缓冲器对时钟偏差的影响，使用双向宽度优先搜索算法进行时钟避障布线的基于推迟合并策略的低功耗时钟树综合实现方法。略的低功耗时钟树综合实现方法。略的低功耗时钟树综合实现方法。


技术研发人员：俞文心 丁劲皓 文茄汁
受保护的技术使用者：西南科技大学
技术研发日：2023.06.08
技术公布日：2023/9/20