一种基于 CRPR 的最大时钟偏差计算与定位算法

一种基于 CRPR 的最大时钟偏差计算与定位算法

谢丁，朱春 

摘要：在超大规模集成电路中，不计其数的寄存器等基本时序单元通过时钟信号的控制以稳定的步调捕获和发送信号，支撑电路正确地运行。时钟树的设计和分析成为物理综合和静态时序分析中的关键环节，影响时序收敛的速度和最终的性能。提出一种基于 CRPR 的算法，能够精确和快速地定位最大时钟偏差，帮助物理综合优化程序或者设计者实现快速时序收敛。此算法的复杂度为 O(n)，即与基本时序器件的数量成线性关系。完成计算的同时定位最大偏差，以极低的成本反馈时序分析结果。

关键词：集成电路设计，静态时序分析，时钟树，CRPR，时序分析。

中图分类号：TN402；TP333   文章编号：1674-2583(2020)05-0028-03

DOI：10.19339/j.issn.1674-2583.2020.05.009

中文引用格式：谢丁，朱春.一种基于CRPR的最大时钟偏差计算与定位算法`J`.集成电路应用, 2020, 37(05):28-30.

A Fast Algorithm of Calculating and Locating Max Clock Skew Based on CRPR
XIE Ding, ZHU Chun

Abstract — In VLSI, tremendous amount of registers and other sequential elements are controlled by clock signals to launch and capture normal digital signals at given pace, making it elementary for a chip to function as expected. Clock tree synthesis and optimization plays a critical role in the physical synthesis and static timing analysis (STA), timing closure and circuit performance are bounded by the quality. This paper presents a CRPR based algorithm, fast and accurate, on calculating and locating how much and where is the worst clock skew, which will favor the timing closure. This algorithm exposes O(n) complexity, linear to the number of sequential cells, with significantly low costs.

Index Terms — IC design, STA, clock tree, CRPR, timing closure.

0  引言 

在数字集成电路`1`的不同设计阶段（例如逻辑综合、布局、布线等）需要对电路内部路径进行延迟计算，进而指导优化。静态时序分析`2`是对数字电路的时序性能进行计算、评估的一种分析流程，该流程不需要通过输入激励的方式进行仿真，而是采用遍历的方式考量所有的时序路径，获取既定条件可能的最坏和最好情况，在电路时序快速、准确的测量中扮演了重要角色。

时钟树`3`是由许多缓冲单元以及它们之间的互连线网搭建而成的树状结构。信号从时钟源点传播到寄存器的过程中，经过多级缓冲器。所经过的缓冲器数目根据寄存器的物理位置不同而体现出差别，进而导致信号到达各个寄存器的延时不对等，这种不对等即为时钟偏差`4`。时钟偏差过大，原本属于数据路径上的时序裕量将可能被吞噬，导致时序不能满足设计要求，电路不能正常工作。

在超大规模集成电路中，时钟偏差是不可避免的，在设计过程中要不断定位超出设计目标的时钟偏差并相应对时钟网络进行优化，将时钟偏差控制在合理范围以内，平衡时钟信号到达所有寄存器的延时。因此如果能够精确和快速地定位最大时钟偏差，将能极大地提高电路物理综合阶段的优化效率，从而加快目标设计的时序收敛。

1  CRPR 技术

由于晶圆物理特性、集成电路制造、芯片工作环境的差异，同一电路单元（如缓冲器）在不同芯片、不同工况、不同位置的延时将会出现一定程度的偏差。

通常，元器件时序库的供应商会提供同一器件在各种测试条件下观察到的最快和最慢延时，这种最快和最慢延时确定了延时的变化范围，而对于时钟网络最大偏差的分析，也将在此范围内展开。

如图 1 所示，时钟驱动两个寄存器 DFF1、DFF2，DFF1 发送数据，DFF2 接收数据。对于典型的 setup 时序检查，采用最悲观策略分析时，计算时钟源到 DFF1 的时钟路径延时采取最慢延时（max path）累加，即缓冲器 A、B、C 的最坏延时；计算时钟源到 DFF2 的时钟路径延时采取最快延时（min path）累加，即缓冲器 A、B、D、E 的最快延时。由于 max path 与 min path 共享缓冲器 A 和 B，在同一时刻下，缓冲器 A 和 B 的延时只有一种可能，不可能出现延时差别。因此，悲观策略计算 DFF1/DFF2 的时钟偏差在缓冲器 A 和 B 上出现了过分悲观裕量，此悲观裕量在任意物理条件下都不会发生，可能导致过设计（over design），增加了时序目标收敛的难度，应该在算法中加以消除。

Clock Reconvergence Pessimism Removal`5`（CRPR），即消除时钟共享路径上的过悲观因素。以图 1 为例，DDF1 与 DFF2 之间的真实时钟偏差应该发生在从最近共享节点（common point， B 的输出端）开始的两条不同时钟路径，即 C 和 D+E 之间的两条路径。A+B 为 DFF1 与 DFF2 的时钟共享路径，共享路径的延时不参与时钟偏差的计算。

2  线性遍历时钟树

  2.1 时钟树

时钟树中每个节点有且只有一个父节点。因此，共享路径只可能存在于从时钟源开始的前面一部分，并且共享路径的起点必为根节点。此外，通过 CRPR 技术的介绍，我们可以得出结论：共享路径不是绝对的，讨论共享路径需要先明确两个寄存器或者时钟路径终端。如图 2 所示，A 为时钟源，D/E/G/H/J/K 为时钟路径终端，B/C/F/I 为缓冲器。D 和 E 的共享路径为 A-B-C，它们之间的时钟偏差只需要计算以 C 为根节点的子树上的偏差。D 和 H 的共享路径为 A-B，他们之间的时钟偏差只需要计算以 B 为根节点的子树上的偏差。D 和 K 之间无共享路径，他们的时钟偏差发生在整个时钟树上。因此，时钟偏差的计算可能发生在整个时钟树的任意子树上（时钟树本身也是特殊子树）。

  2.2 偏差计算

为了摒弃共享路径的影响，我们创新性地采用先自顶向下，再逐步回升的方法，只用一次遍历即可得出整个时钟树的最大时钟偏差，同时能够得到对应最大时钟偏差的所有寄存器对。为了使整个算法更具有普适性，我们假设时钟树中任意边的延时大于或者等于零，并且最大时钟偏差可能发生于时钟树中任何子树上。算法流程如图 3 所示。

从时钟树的根节点出发，获取根节点的所有子节点，而每个子节点又是以自身为起点的子树的根节点，由此出发遍历各自的子树，逐渐深入到最低层的子树。由于叶子节点的子树即其本身，其时钟偏差为零，当算法行进到时钟树的叶子节点，即将控制返回到父节点。当且仅当节点本身所有的子树全部遍历完成以后，才会跳回父节点进一步处理兄弟节点的子树。如此层层往上回溯，并最终归结于根节点，整个时钟树的遍历因此而完成。同时，每个节点遍历完成时都需要将本节点自身子树的最大时钟偏差写入整个时钟网络对应的时钟偏差查找表中。

由时钟树的固有特性可以得出：任意两个子树的时钟偏差互不干扰。因此，算法在逐步回升的过程中记录下除叶节点以外节点的时钟偏差（如果当前节点只有一个子节点则不记录时钟偏差），同时将当前节点所有下游路径的最大和最小延时返回给父节点。节点的时钟偏差具体计算方式如图 4 所示。

A 为 B/C/D 的父节点，我们分别先后完成以 B/C/D 为根节点的子树的时钟偏差计算，将 B/C/D 的时钟偏差写入查找表，同时将各自子树的最大和最小延时返回给父节点 A，分别为 minB/maxB，minC/maxC，minD/maxD。AB/AC/AD 边分别拥有最大和最小延时，分别累加到子树的最大和最小延时上，得到 A 的 3 个子树的最大和最小延时，分别为 minAB/maxAB，minAC/maxAC，minAD/maxAD。因此，以 A 为根节点的子树的最大延时为 maxAB，maxAC，maxAD 中的最大者，最小延时为 minAB，minAC，minAD 中的最小者。

maxA＝MAX{maxAB，maxAC，maxAD} （1）

minA＝MIN{minAB，minAC，minAD} （2）

求得最大和最小延时值，获得式（3）。

skewA＝maxＡ－minA （3）

同时记录最大和最小延时对应的子树名称。如果最大延时来自子树 B，最小延时来自子树 C，那么最大时钟偏差来自子树 B 和子树 C 之间的时钟偏差。如果 A 只有一个子节点 B，那么 A 子树的时钟偏差与 B 子树的时钟偏差相同，但需要注意 A 子树的最大和最小延时和 B 子树的可能有所区别，此区别由 AB 边导致，因此依然需要将 A 子树的最大和最小延时传递给A的父节点。

  2.3 偏差记录

当算法回到整个时钟树的根节点，所有的时钟偏差已经计算完成，并如 2.1 节所述各子树的最大时钟偏差已存入统一的查找表中。此处我们设计了两级查找表，第一级查找表（Skew Table）提供最大时钟偏差到相应节点对的映射，第二级查找表（Node Table）提供该节点对所在子树中贡献最大时钟偏差的最大延时与最小延时的节点集合，如图 5 所示。

接着，首先对 Skew Table 进行一次性的，按照时钟偏差值从大到小的整体排序。排序完成以后，存在于查找表表头的所有具有相同时钟偏差的节点即为具有最大时钟偏差的节点。时钟偏差是针对时钟树的终点而言的，因此最终的报告必须体现为时钟终点的引脚对，而 Node Table 中存储的最大、最小延时节点集合是此节点的直接子节点集合，并非叶子节点集合。因此，需要从这些中间节点出发，逐级递归获取下游子树的最大、最小延时节点，最终收集到叶节点的集合。

  2.4 整体流程

图 6 展示了整个时钟偏差分析以及得出最终结果的整体流程。获取电路设计中的时钟网络并完成时钟树的构造是整个算法的准备阶段。时钟树的边对应时钟网络中缓冲器之间的连接关系或者缓冲器内部的连通关系，因此从时序库文件提取相应的延时数据并标注到时钟树的边上。下一步骤是整个方法的核心：采用递归的基本方法，从时钟树的根节点开始遍历整个时钟树的节点，中间不断计算每个节点子树的时钟偏差以及贡献此时钟偏差的直接子节点集合，将数据记录在统一的查找表内。当整个时钟树的遍历完成以后，对查找表进行排序，依次获得最大时钟偏差的节点并输出对应的寄存器引脚对。

3  结语：实验结果

本文提出的算法已集成在安路公司自主研发的 FPGA 全流程软件系统 Tang Dynasty（TD）中，作为时钟树分析引擎的核心算法，能在计算最大时钟偏差的同时准确定位最大时钟偏差发生的位置，其运行报告如图 7 所示。

除了生成最终报告供设计人员参考分析之外，更重要的是该算法能够在布局布线阶段提供迅速准确的反馈，提高物理综合优化算法收敛的效率，并为有用偏斜（usefulskew）等进阶优化提供了操作空间。我们挑选了若干真实的工业设计在安路公司最新的 TD4.9 软件上进行测试（处理器：Intel Xeon Gold 6242@2.8 GHz，操作系统：Red hat 6.8）。实验结果如表 1 所示，可以看到该算法的运行时间均小于 1 s，并且与电路规模成线性关系，算法复杂度确为 O(n)，体现出超高的效率。

参考文献

`1` Jan M.Rabaey,Anantha Chandrakasan, Borivoje Nikolic.Digital Integrated Circuits:A Design Perspective,second edition`M`.Pearson,2003.

`2` J.Bhasker,Rakesh Chadha.Static Timing Analysis for Nanometer Designs:A Practical Approach`M`.Springer,2009.

`3` Andrew B.Kahng,Jens Lienig,Igor L. Markov,Jin Hu.VLSI Physical Design:From Graph Partitioning to Timing Closure`M`. Springer,2011.

`4` Ivan S.Kourtev,Eby G.Friedman,Baris Taskin.Timing Optimization Through Clock Skew Scheduling`M`.Springer,2012.

`5` Jindrich Zejda,Paul Frain.General framework for removal of clock network pessimism`C`.IEEE/ACM International Conference on Computer Aided Design, 2002.

===========================