一种针对近阈值的鲁棒时钟树综合算法实现方法

摘要

本发明一种针对近阈值的鲁棒时钟树综合算法实现方法，包括如下步骤：步骤1，采用自顶向下的综合算法生成对称时钟树初始拓扑；步骤2，在已经生成的拓扑结构基础上完成缓冲器插入，把时钟偏差波动的近似估计模型应用于多种缓冲器尺寸的缓冲器插入过程，此过程以优化时钟偏差波动为目标，优化过程基于遗传算法实现。本发明的一种针对近阈值的鲁棒时钟树综合算法实现方法，本发明的时钟树综合算法把对称时钟树作为初始拓扑应用在近阈值下，保证了时钟树具有很小的时钟偏差。在缓冲器插入阶段，实现了面向缓冲器库的缓冲器插入算法，该过程实现从缓冲器库中选择最优的缓冲器插入策略，使得时钟树时钟偏差波动尽可能小。

说明书

技术领域

本发明属于集成电路物理设计中的电子设计自动化领域，是一种应用于低电压近阈值中集成电路时钟树设计的鲁棒性优化方法。

背景技术

在低功耗的集成电路设计中，近阈值设计具有最高的能效比。而时钟树在整个电路设计中的功耗占比基本在30％-40％。因此近阈值下的时钟树设计对低功耗设计的重要性不言而喻。

减小工艺波动对设计的影响是近阈值设计中最需要解决的问题，也是区分于常电压设计的一个点。在结构上，时钟树主要由时钟源、缓冲器、互联线和寄存器组成。由于近阈值下晶体管的阈值非常接近工作电压，制造过程中的晶体管模型参数波动会非常明显地影响缓冲器的时序，进而影响时钟树的偏差和最大转换时间。时钟树在近阈值下的时序波动制约了电路性能的进一步提升。因此，提高时钟树偏差的抗工艺波动能力可以让时钟树以更高的性能工作在近阈值下

发明内容

发明目的：本发明的目的在于解决上述现有技术中存在的问题，提供一种近阈值下鲁棒的时钟树综合算法，以让芯片在近阈值下以更高的性能工作，实现更好的功耗、性能、面积权衡。

技术方案：

一种针对近阈值的鲁棒时钟树综合算法实现方法，该算法包括如下步骤：

步骤1，采用自顶向下的综合算法生成对称时钟树初始拓扑；

步骤2，在已经生成的拓扑结构基础上完成缓冲器插入，把时钟偏差波动的近似估计模型应用于多种缓冲器尺寸的缓冲器插入过程，此过程以优化时钟偏差波动为目标，优化过程基于遗传算法实现。

进一步地，步骤1包含如下步骤：

步骤1.1，根据布局阶段得到的寄存器数量结果进行分支数规划，规划得到时钟树层次化的分支结构；

步骤1.2，根据分支数规划结果递归地采用切蛋糕式的分组方式依据是最大化寄存器分布的平衡性进行分组；

步骤1.3，根据分组结果依次自底向上地合并子节点得到父节点，父节点为其所有子节点的几何中心；

步骤1.4，采用蛇形走线的方式进行时钟树布线，连接所有寄存器和合并点，由此得到时钟树初始拓扑。

进一步地，步骤2具体为：

步骤2.1，针对多种缓冲器尺寸建立时钟偏差波动模型的近似估计模型，首先构建不同缓冲器尺寸之间延迟波动的相关系数矩阵，并把相关系数矩阵引入时钟树偏差波动的近似估计模型，将此模型作为优化指标；

步骤2.2，利用遗传算法优化时钟偏差波动模型，将缓冲器插入策略使用十进制量化、编码，以构建遗传算法中的染色体，初始化种群，并经过多代演化产生时钟偏差波动更小的个体。

进一步地，不同缓冲器尺寸之间延迟波动的相关系数矩阵获得方法如下：

步骤,2.11，在缓冲器库中任选两种尺寸的缓冲器，记尺寸1和尺寸2，两种尺寸的缓冲器级联，并称该结构为最小结构；

步骤2.12，级联N个最小结构，对得到的结构做蒙特卡洛仿真，并统计每个最小结构的延迟方差，最小结构中尺寸1缓冲器的延迟标准差和尺寸2缓冲器的延迟标准差，分别记为σ

步骤2.13，利用步骤2中得到的数据对相关系数模型

步骤2.14，重复步骤2.11-2.13，得到缓冲器库中不同缓冲器尺寸之间延迟波动的相关系数矩阵。

进一步地，通过遗传算法实现时钟偏差波动的优化过程步骤如下：首先把初始拓扑结构中的合并点作为缓冲器插入的候选点，并单独对单条时钟路径作为建模对象，即最小化时钟偏差波动，缓冲器插入的候选点可以不插缓冲器，也可以插入任意尺寸的缓冲器，对插入的缓冲器尺寸编码，不插缓冲器编码为0，插入最小尺寸的缓冲器编码为1，以此类推，一条时钟路径上的缓冲器插入方案用十进制的一组数据量化，将编码方案对应到染色体中，染色体的长度为缓冲器插入方案对应的编码长度，染色体的基因位为缓冲器插入方案中每个插入候选点插缓冲器的尺寸，遗传算法中种群演化结束条件是达到给定的繁衍代数。

有益效果：(1)本发明的时钟树综合算法把对称时钟树作为初始拓扑应用在近阈值下，保证了时钟树具有很小的时钟偏差。同时由于该综合算法是自顶向下的综合过程，没有递归的计算过程，综合过程非常快。

(2)本发明的时钟树综合算法中的缓冲器插入步骤是面向缓冲器库的，这种面向缓冲器库的插入方式一方面具有更强的泛化能力，另一方面这种相比于只使用一种缓冲器尺寸的缓冲器去做缓冲器插入有更大的优化空间。

(3)本发明的缓冲器插入过程基于改进后的时钟偏差波动模型作为优化对象，插入过程能够同时进行缓冲器缩放，优化过程通过遗传算法实现。

本发明的近阈值鲁棒的时钟树综合算法应用在opencores的5个基准电路上对比了同类的设计方法，时钟偏差波动平均减少了117％，缓冲器使用面积平均减少了72％，代价是互联线使用平均增加了107％。

附图说明

图1(a)为本发明产生一个不插缓冲器的时钟树初始拓扑的过程，图1(b)为本发明完成时钟树缓冲器插入过程；

图2为本发明的把遗传算法应用于缓冲器插入时的染色体编码策略。

具体实施方式

下面结合附图对本发明作进一步说明：

本发明把对称时钟树结构应用于近阈值的设计，保证较小的时钟偏差，同时，采用面向缓冲器库的缓冲器插入策略，插入过程中同时实现缓冲器尺寸缩放，尽可能减小缓冲器插入带来的时钟偏差波动。图1是本发明的整体流程图，整个流程以所有寄存器位置信息和时钟缓冲器库作为输入，并以最大转换时间和最大负载电容作为约束。整个流程的目标是构建一个对称的插好缓冲器的时钟树结构，该时钟树结构在近阈值下满足约束的条件下具有最小的时钟偏差波动。整个流程分为两个部分，如图1(a)和图1(b)所示，其中图1(a)是产生一个不插缓冲器的时钟树初始拓扑，图1(b)是完成时钟树缓冲器插入过程，这步决定了时钟树中的缓冲器级数和每一级中使用的缓冲器尺寸。

图1(a)拓扑生成阶段包含两个步骤，分别是分支数规划和树构建。分支数规划通过对寄存器数量N做因式分解得到分支级数和每一级分支的分支数。对于得到的分支数超过最大分支数约束的情况，需要引入虚拟寄存器，使得寄存器数量可以分解得到满足约束的分支数组合，比如想分解26，因式分解表达式为26＝2*13，但是如果最大分支约束只有5，那就要引入1个虚拟寄存器。这样因式分解表达式为27(26+1)＝3*3*3。树构建步骤是根据分支数规划的结果对寄存器做递归分组，得到层次化的分组结果。然后再获得每组分组的合并节点。这些合并节点作为后续缓冲器插入的候选点。

基于时钟树拓扑结构是对称的结构，图1(b)的缓冲器插入过程简化为单条时钟路径的缓冲器插入。本发明中缓冲器的插入位置假设是前面提到的插入候选点。候选点可以插缓冲器也可以不插缓冲器。基于这个假设，缓冲器插入优化过程中本发明以推导的时钟偏差模型公式作为优化目标，公式1-9用于评估对称时钟树的时钟偏差波动。

σ

Cl

CW

0＜m

Slout

Slout

其中，ρ(*,*)表示相关系数矩阵二维查找表，f

公式1是改进后的时钟偏差波动近似预估公式，适用于多缓冲器尺寸的时钟偏差波动优化，其中，σ表示时钟偏差的标准差，σ

这个优化过程采用现代优化算法中的遗传算法实现。在构建优化器时，首先对插入策略量化编码成染色体，量化策略如图2所示。在缓冲器插入问题中，染色体的长度是L，表示不插缓冲器的时钟树级数。染色体的基因位用十进制编码，范围在[0,B]之间，其中B是缓冲器库中最大尺寸缓冲器的编号。编码值为0代表当前级数的候选点没有插缓冲器；编码值为非0代表在当前级数候选点插入了相应尺寸的缓冲器。如图2所示的示例表示的缓冲器插入方案是在5级的时钟树拓扑结构中插入了3级缓冲器，其中第一级缓冲器插在第一级分支点处，使用的缓冲器尺寸编号为3；第二级缓冲器插在第二级分支点处，使用的缓冲器尺寸编号为3；第三级缓冲器插在第五级分支点处，使用的缓冲器尺寸编号为2。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。