一种考虑空间关联工艺偏差的统计静态时序分析方法

喻 伟杨海钢刘 洋黄 娟蔡博睿陈 锐

①(中国科学院电子学研究所 北京 100190)

②(中国科学院大学 北京 100086)

一种考虑空间关联工艺偏差的统计静态时序分析方法

喻 伟①②杨海钢*①刘 洋①黄 娟①蔡博睿①陈 锐①②

①(中国科学院电子学研究所 北京 100190)

②(中国科学院大学 北京 100086)

为了准确评估工艺参数偏差对电路延时的影响，该文提出一种考虑空间关联工艺偏差的统计静态时序分析方法。该方法采用一种考虑非高斯分布工艺参数的二阶延时模型，通过引入临时变量，将2维非线性模型降阶为1维线性模型；再通过计算到达时间的紧密度概率、均值、二阶矩、方差及敏感度系数，完成了非线性非高斯延时表达式的求和、求极大值操作。经ISCAS89电路集测试表明，与蒙特卡洛仿真(MC)相比，该方法对应延时分布的均值、标准差、5%延时点及95%延时点的平均相对误差分别为0.81%, -0.72%, 2.23%及-0.05%，而运行时间仅为蒙特卡洛仿真的0.21%，证明该方法具有较高的准确度和较快的运行速度。

集成电路；统计静态时序分析；空间关联；非高斯非线性；工艺偏差；延时模型

1 引言

随着集成电路工艺的特征尺寸缩小到纳米尺度，工艺参数偏差的影响变得越来越显著。这些工艺偏差导致了芯片电气参数随机变化，并给电路的时序评估带来极大挑战。为了解决工艺偏差带来的影响，传统的静态时序分析(Static Timing Analysis, STA)，通过在不同的工艺角下执行时序裕量检查，来实现电路的时序评估。然而，随着工艺参数偏差源的增多，需要考虑的工艺角数量随之增多，基于多工艺角的STA变得越来越费时；而且由于片内逻辑门不同位置的工艺参数存在空间关联，多工艺角STA也没有考虑到这些关联统计信息，从而使得评估结果过于悲观。在利用这些悲观结果指导时序优化时，将会造成严重的资源浪费，并影响到电路功耗、面积等其他性能参数的评估。

因此，与传统多工艺角STA相比，统计静态时序分析(Statistical Static Timing Analysis, SSTA)显得更为可靠。SSTA的处理对象为延时的概率分布函数(Probability Distribution Function, PDF)和累计分布函数(Cumulative Distribution Function, CDF)，换句话说，SSTA利用工艺参数偏差的统计信息来评估最终延时的统计分布。尽管影响SSTA延时变化的因素很多[1-9]，但随着工艺尺寸的不断缩小，在深亚微米尺度下工艺参数偏差仍然是影响延时变化的最大因素。考虑工艺参数偏差的SSTA方法虽不是最新的研究热点，但在算法分析方面还是为国内的研究开展提供了方向；而且从目前SSTA EDA工具的开发经验来看，考虑工艺参数偏差的SSTA方法显得更切实际。

考虑工艺偏差的SSTA方法大致可以分为两类：一类是基于路径的方法[6]，这类方法通常先利用传统的STA方法找到一定数量的关键路径，然后再采用基于路径的分析流程来运行参数化SSTA，由于需要遍历一定数量的路径，其时间代价往往较高；另一类是基于块的方法[7-9]，这类方法通常先采用基于项目评估技术[10](Program Evaluation and Review Technique, PERT)的拓扑技术遍历时序图，然后再完成从输入到输出的延时分布传递，由于不需逐个遍历路径，其时间代价相对较小。从区分工艺参数分布和延时依赖关系的角度看，这些基于块的SSTA方法大致又可以分为4类：(1)线性高斯SSTA，在这类方法中，研究人员将工艺参数假设为高斯分布，在利用主元分析(Principle Component Analysis, PCA)技术[11]把那些空间关联高斯变量转换为彼此独立高斯变量后，将延时表示为独立高斯变量的一阶线性表达式，如文献[7]，这类方法忽略了工艺参数的非高斯分布形式和延时变量的非线性表示方式，因而是一种不完备的SSTA分析方法；(2)非线性高斯SSTA：在这类方法中，研究人员仍将工艺参数假设为高斯分布，在利用PCA技术进行变量转换后，将延时表示为独立高斯变量的非线性表达式，特别是二阶表达式，如文献[8]，由于这类方法同样忽略了工艺参数的非高斯分布形式，所以也是一种不完备的SSTA分析方法；(3)线性非高斯SSTA：在这类方法中，研究人员不再将工艺参数局限于高斯分布，可以是任意非高斯分布，在利用独立元分析(Independent Component Analysis, ICA)技术[12]把那些空间关联非高斯变量转换为彼此独立非高斯变量后，将延时表示为工艺参数的一阶线性表达式，如文献[9]。由于这类方法也忽略了延时变量的非线性表示方式，同样是一种不完备的SSTA分析方法；(4)非线性非高斯SSTA：这类方法是其他3类方法的综合，工艺参数既能满足任意分布，延时又可以是工艺参数的非线性表达式，因此是一种更通用更完备的方法。

基于以上分析，本文提出了一种基于块的考虑空间关联非高斯分布工艺偏差的非线性统计静态时序分析方法。这种方法首先假设了芯片内不同位置的工艺参数存在空间关联性，使其更加符合实际情况；然后将工艺参数假设为高斯分布和非高斯分布并存的情形，并将延时表示为工艺参数的二阶表达式；最后利用降阶方法将非线性延时模型降阶为线性延时模型，通过计算延时的紧密度概率、均值、二阶矩、方差及敏感度系数，完成非线性非高斯延时表达式的求和及求极大值操作。本文方法避免了前文方法中工艺参数的不完备表达，改进了延时变量的建模方法，并提高了SSTA分析的完整性和准确性。

2 工艺参数的空间关联与电路延时的非高斯非线性属性

2.1 SSTA中的工艺参数空间关联

为了探究芯片内逻辑门不同位置工艺参数之间的空间关联性，本文借鉴了文献[7]提出的方格树模型，如图1所示。在此模型中，芯片被抽象为一个多层次的方格树，在树的第i层，芯片被划分为2i×2i个方格。这种树形结构在不同层次的方格间形成一种等级关系，若较高层的一个方格和较低层的某些方格共享面积，那么较高层的这个方格就被称为父方格，较低层的方格则被称为子方格。对于同一个方格内的不同逻辑门，它们具有相同的工艺参数敏感度，如顶层内的所有逻辑门就具有相同的工艺参数敏感度；对于不同方格内的不同逻辑门，其工艺参数的空间关联性由它们的父方格所决定。

图1 工艺参数空间关联的方格模型示意图

在每一个方格内，本文用一个单独的随机变量表示一个工艺参数，最底层方格内的逻辑门工艺参数是由其自身方格内的工艺参数和所有父方格内的工艺参数共同决定的。例如在图1(a)中，方格[0,1]为[1,1]的父方格，方格[1,1]为[2,1]的父方格，那么方格[2,1]内的逻辑门沟道长度L(2,1)就可以表示为如式(1)与物理位置相关的参数化表达式：

其中，L0为沟道长度本征值，ΔL2,1, ΔL1,1, ΔL1,0分别表示方格[2,1], [1,1], [1,0]内的沟道长度偏差。

不同方格内工艺参数的空间关联程度是由其共同的父方格所决定的，例如方格[2,1], [2,2]及[2,16]内的逻辑门沟道长度分别可以表示为

在式(2)中，方格[2,1]和[2,2]共享两个父方格(ΔL1,1,ΔL0,1)，而方格[2,1]和[2,16]只共享一个父方格(ΔL0,1)。因此，与方格[2,1]和[2,16]对应空间关联程度相比，方格[2,1]和[2,2]之间的工艺参数空间关联程度更高，这也表明两个逻辑门离得越近，其工艺参数空间关联程度越高，逻辑门的工艺参数变化越具有相似性。

另外需要指出的是：(1)空间关联仅局限于同一种工艺参数，不同的工艺参数之间彼此独立，例如方格[2,1]内的沟道长度仅与其它方格内的沟道长度存在关联，而和其它诸如栅氧化层厚度、半导体掺杂浓度等工艺参数没有关系；(2)对于一个3层的方格树，在表示最底层两个方格内任一工艺参数的关联关系时，需要一个16×16的协方差矩阵；(3)对于顶层方格，由于它是所有其它方格的父方格，所以它可以用来表示片外工艺参数偏差，而片内工艺参数偏差则可由其它层次的方格来表示，这样本文方格模型就可以表示所有的片内偏差和片外偏差。

2.2 SSTA中的非高斯非线性

随着工艺尺寸的减小，电路延时呈现出越来越多的非高斯属性。实际分析时，一些工艺参数往往会极大地偏离高斯分布，如互连线的金属宽度会呈现出非对称的概率分布，半导体掺杂浓度会呈现出泊松分布等；同时由于片内空间邻近效应的存在，这些非高斯分布工艺参数彼此空间关联，若依据传统的SSTA方法将这些工艺参数表示为高斯分布，则很可能会导致电路延时的PDF严重偏离实际情形。

随着工艺尺寸的减小，电路延时也呈现出越来越多的非线性属性。因为逻辑门延时和互连线延时往往是工艺参数的参数化表达式，当工艺参数偏差较小时，一阶泰勒展开式足够精确；然而随着工艺参数偏差的增大，一阶线性表达式已不再适用，延时表达更多地呈现非线性特征。另外，对于基于块的SSTA方法，在时序图上传递延时分布时，执行了两个基本操作：求和、求极大值。求和一般适用于单输入逻辑单元，如反相器、缓冲器和互连线等，若输入信号到达时间和单输入逻辑单元延时都服从高斯分布，那么输出信号到达时间也是一个高斯分布，所以求和操作是一个线性操作；求极大值一般适用于多输入逻辑单元，如与门、或门等，即使两个随机变量A, B相互独立且满足高斯分布，其极大值仍为非高斯分布，所以求极大值操作是一个非线性操作。同时还需要指出的是，在求解延时偏斜时，需要计算其三阶矩，如果延时为一阶线性表达，那么其三阶矩则为零，这与实际非高斯分布随机变量对应延时偏斜非零的事实相矛盾，所以在计算延时偏斜时，也有必要将延时表示为非线性表达式，如二阶表达式等。

针对SSTA中工艺参数的空间关联性及延时表达的非高斯非线性，本文提出一种改进的空间关联统计静态时序分析(Correlated Statistical Static Timing Analysis, CSSTA)方法，从而将这两个问题考虑进来。

3 CSSTA算法流程

本文CSSTA算法流程如图2所示。首先根据前文的非高斯非线性分析，将影响延时分布的工艺参数划分为高斯参数和非高斯参数两部分，将空间关联的高斯分布(非高斯分布)工艺参数转化为一组彼此独立的高斯分布(非高斯分布)随机变量，并将延时表示为这组独立随机变量的二阶非线性模型；然后基于二阶非高斯非线性模型，采用基于PERT的延时分布拓扑传递方法，针对时序图上的每一个节点执行求和操作(sum)和求极大值操作(max)，以期获得节点到达时间的参数化表达式，并通过计算节点到达时间的紧密度概率、均值、二阶矩、方差及敏感度系数，得到参数化延时表达式的近似拟合；最后根据参数化延时表达式的具体形式，通过匹配工艺参数的k阶矩，得到经由PCA (ICA)转化后的独立随机变量的矩，并根据这些独立随机变量的矩和延时变量非线性模型，得到延时变量的矩，从而利用延时变量的矩和概率提取流程算法，生成延时变量的PDF。

3.1 基于工艺参数偏差的延时建模

图2 CSSTA算法流程图

为了描述工艺参数偏差对电路延时的非线性影响，本文采用基于截断的泰勒展开多项式，将一阶线性表达式扩展为二阶延时模型：

其中，D为对应逻辑门延时或输入端到达时间的随机变量，d0为D的本征值，xi为空间关联工艺参数高斯变量，yj为空间关联工艺参数非高斯变量，z为空间独立工艺参数随机变量；,分别为第i个高斯分布工艺参数的一阶、二阶敏感度系数，,分别为第j个非高斯分布工艺参数的一阶、二阶敏感度系数，e为随机变量z的敏感度系数；n和m分别为空间关联高斯分布和非高斯分布工艺参数的个数。

考虑到正交变换的处理流程，将D表示为工艺参数的向量表达式：

其中x=(x1,x2,…,xn)T为空间关联高斯分布工艺参数向量，y=(y1,y2,…,ym)T为空间关联非高斯分布工艺参数向量；p′=(,,…,)为一阶项x的敏感度系数向量，q′=(,…,)为一阶项y的敏感度系数向量，p′为n×n对角矩阵，其对角线系数为二阶项x的敏感度系数，q′为m×m对角矩阵，其对角线系数为二阶项y的敏感度系数。

接着，运用PCA (ICA)技术，将空间关联的高斯分布工艺参数向量x(空间关联的非高斯分布工艺参数向量y)转换为彼此独立的高斯分布工艺参数向量X(彼此独立的非高斯分布工艺参数向量Y)，将D进一步表示为

其中，X为转换后的高斯分布工艺参数向量，Y为转换后的非高斯分布工艺参数向量；P′=(,…,)为一阶项X的敏感度系数向量，Q′=(,…,)为一阶项Y的敏感度系数向量，P′为n×n对角矩阵，其对角线系数为二阶项X的敏感度系数，Q′为m×m对角矩阵，其对角线系数为二阶项Y的敏感度系数。需要注意的是，对于空间独立随机变量z，根据中心极限定理(不同独立随机变量的叠加满足高斯分布)，可以将z转换为一个均值为0，方差为1的标准正态分布变量Z,Z～N(0,1)，同时所有的Xi,Yj也满足均值为0,-1≤Xi≤1, -1≤Yj≤1。

3.2 非线性非高斯延时的统计操作

参数化基于块的SSTA方法通常将电路抽象为一个统计时序图G=(N,E,ns,nf)。其中，N为节点集合，E为边集合，ns为源节点，nf为终节点。从源节点到终节点传递延时分布时，通过执行求和或求极大值操作，就可以依次求出节点到达时间的概率分布(参数化表达式)，如图3所示。

图3 统计时序图中求和、求极大值操作及延时分布传递

3.2.1 求和 因为求和操作是一个线性操作，所以求和结果应该与输入到达时间及门延时具有相同的表达式。参考式(5)，考虑两个非线性非高斯延时表达式A和B：

求和结果C=A+B可以表示为

其中

3.2.2 求极大值 因为求极大值是一个非线性操作，所以为了获取max(A,B)的近似估计，本文借鉴了线性高斯SSTA[7]中的处理方法。本文算法通过引入临时变量，将2维非线性模型降阶为1维线性模型；然后在此1维线性模型的基础上，通过计算max(A, B)的紧密度概率、均值、二阶矩及方差，获得了max(A,B)的近似表达。

观察式(6)，将其中的随机变量表达式分解为4部分：线性高斯部分、非线性高斯部分、线性非高斯部分及非线性非高斯部分；令X为线性高斯随机变iL量，XiN为非线性高斯随机变量，YjL为线性非高斯随机变量，YjN为非线性非高斯随机变量，则式(5)可表示为

其中，h(XiN,YjL,YjN)为一个临时变量，它代表了线性高斯部分以外的随机变量表达式。

假设非线性高斯部分、线性非高斯部分及非线性非高斯部分是固定的，那么临时变量h(XiN,YjL, YjN)也将固定，将h(XiN,YjL,YjN)和d0当作一个整体，重写式(9)为

式(11)可以看作为一个本征值为d0+h(XiN,YjL,YjN)的一阶线性表达式，再次考虑两个用式(11)表示的A和B：

于是，当XiN,YjL及YjN固定时，max(A,B)的临时紧密度概率TA,cond、临时均值μC,cond及临时二阶矩m2C,cond就可以表示为XiN,YjL及YjN的函数。

同时，由于XiL的概率分布可以简单地等效为XiN,YjL及YjN的联合概率分布：

在用d0A+hA(XiN,YjL,YjN)和d0B+hB(XiN,YjL, YjN)替换掉线性高斯延时表达式中的d0A和d0B后，将临时紧密度概率、临时均值及临时二阶矩在联合概率分布的随机变量参数空间内积分，就可以计算出max(A,B)的正式紧密度概率TA、正式均值μC、正式二阶矩m2C及正式方差。

在获得max(A,B)的紧密度概率、均值及二阶矩之后，就可以利用Cappr来近似估计max(A,B)。因为系数是和Pi′B的线性组合，系数hC是hA和hB的线性组合，所以可以将Cappr视为一阶线性情形

令Cappr的方差为var(Cappr)，则Cappr的相关参数为

为了突出本文非线性非高斯延时表达式与传统线性高斯延时表达式求极大值操作的对比结果，图4给出了包含两个随机变量的max(A,B)近似示意图，其中图4(a)为线性高斯情形，图4(b)为本文非线性非高斯情形。在图4(b)中，虚曲线分别为非线性表达式A, B，弯折实曲线为准确的max(A,B)，光滑实曲线为近似的Cappr。可以看出，光滑实曲线Cappr和弯折实曲线max(A,B)具有较高的拟合度，证明本文参数化表达式的近似拟合结果具有一定的合理性。若把各个随机变量从1维扩展到多维，这种图示方法仍然适用，只不过图中曲线变成了曲面。

3.3 基于矩匹配的延时评估

在计算延时或到达时间的PDF(CDF)时，本文采用了文献[13]提出的概率提取流程算法(Asymptotic Probability Extraction, APEX)。算法首先将一个随机变量的二阶矩作为输入，采用渐进波形评估技术来匹配这个随机变量的2M阶矩，从而生成一个M阶的线性无关系统；接着利用这个M阶线性无关系统的冲激响应(阶跃响应)来近似拟合随机变量的PDF (CDF)。

图4 max(A,B)的准确表达与近似表达示意图

本文以一个简单的例子解释基于矩匹配的PDF评估方法。假设w, l为空间关联高斯分布(非高斯分布)随机变量，且w和l相互独立。令= p·w+q·l ，其中=D-μ，经PCA, ICA转换后，=P·W+Q·L ，其中W, L为高斯分布(非高斯分布)彼此独立随机变量，那么的k阶矩就可以用式(18)的二项展开式表示。

因为W和L的所有i阶矩可按文献[9]所提方法求得，所以根据式(18)计算得到的2M矩后，利用M阶线性无关系统的冲激响应即可近似拟合的实际PDF。

式(19)中，ri, ρi为M阶线性无关系统的极数。对于式(5)所示延时表达，其共有2m+2n+2项，只要延时表达式中这2m+2n+2个随机变量是统计独立的，那么就可以应用以上方法评估延时变量的PDF。

4 本文算法复杂度分析

如果将PCA正交转换、ICA矩阵生成及独立随机变量矩计算过程等当作一次性的预处理，那么本文SSTA流程的计算复杂度仅包含了时序图拓扑遍历中的求和及求极大值操作。若非高斯独立随机变量的数量为n，高斯独立随机变量的数量为m，则求和操作的时间复杂度为O(n+m)；同时，若用于评估各个随机变量的矩的阶数为2M，则求极大值操作的时间复杂度即为O(M(n+m))。实际操作中，因为M是有上界的，所以求极大值操作的时间复杂度也可以看作为O(n+m)。对于一个含有G个逻辑门的应用电路，因为其各个门的扇入个数有界，则基本操作的总体时间复杂度就为O((n+m)·G)。假设延时建模时片内方格数量为g，因为m, n与方格数量g成正比，O(m)=O(n)=O(m+n)=O(g )，那么本文基于空间关联工艺偏差的SSTA总体时间复杂度就可以表示为O(g·G)。

5 实验结果

基于美国明尼苏达州立大学的MinnSSTA开源框架[7]，本文在Windows平台下采用C++语言实现了所提算法。实验的硬件平台为：CPU 3.6 GHz，内存1.0 GB。算法所用测试电路来自于ISCAS89测试集[14]，之所以选择ISCAS89，是因为：(1)学术界广泛承认并使用；(2)ISCAS89测试集中两个锁存器之间的组合模块非常有利于本文CSSTA的基本操作和延时评估。本文利用文献[11]提出的方法实现了高斯变量的PCA转换，利用FastICA软件包[15]实现了非高斯变量的ICA转换，同时对每个工艺参数，生成5000个随机样本。

在本文实验中，工艺参数既有空间关联也有空间独立，既有高斯分布也有非高斯分布。对于逻辑门工艺参数，只考虑逻辑门长度Lg，逻辑门宽度Wg，栅氧化层厚度Tox及半导体掺杂浓度Na；对于互连线工艺参数，在每一金属层l，只考虑金属互连线宽度Wint,l，金属互连线厚度Tint,l及金属高度HILD,l；令Lg,Wg,Tox,Wint,l,Tint,l及HILD,l为空间关联的工艺参数，令Na为空间独立的工艺参数。基于方格模型，本文将各个方格内逻辑门的Lg,Wg及Tox表示为高斯分布，其参数取值范围为[μ-3·σ,μ+3 ·σ]；将各个方格内互连线的Wint,l,Tint,l及HILD,l表示为非高斯分布(如均匀分布)，其参数取值范围为[μ-3·σ,μ+3·σ]；将Na表示为泊松分布。各个参数的均值和3倍/3倍标准差取值如表1所示，其中μ为各个工艺参数的均值；3σ(片间/片内)为工艺参数Lg,Wg及Tox的3倍片间/片内标准差；3σ(片间/片内)为工艺参数Wint,l,Tint,l及HILD,l的3倍片间/片内标准差；nmos/pmos为工艺参数Na对应n/p型栅氧化管。

表1 本文实验所用工艺参数

在分析工艺参数的空间关联性时，需要知道逻辑门和互连线的物理位置信息，为此本文首先用UCLA大学的开源布局工具Capo[16]进行初始布局，然后再执行全局布线。依据不同的电路单元数，本文将芯片划分为不同数量的方格，使得每个方格内的逻辑门或互连线段数量不超过100个。为简化分析，本文忽略掉输入信号斜率、输出信号负载及路径耦合噪声对延时模型的影响，从而将逻辑门和互连线延时表示为工艺参数的二阶泰勒展开式。

为了验证空间关联SSTA(CSSTA)的精确性，本文基于相同的方格模型运行了蒙特卡洛仿真(MC)。MC是MinnSSTA中的一段源代码程序，为平衡精度和时间开销，本文设置了10000次迭代，在每一次迭代时，程序首先随机选择一组工艺参数，通过更新这组工艺参数对应的引脚电容，计算时序图上各条边的电阻电容参数(RC)，来获得各条边的延时；然后再采用PERT拓扑方法，通过传递延时参数，以获得最终的路径总延时。MC的10000次迭代产生了10000个随机的路径延时结果，通过统计这些结果的最大值、最小值、平均值及方差信息，即可得到仿真的统计信息。另外，在计算边的RC参数和延时变量时，本文使用到了矩阵分解，为此MC调用了MTALAB的数学计算源文件，限于篇幅，具体细节不再赘述。表2为本文CSSTA和MC的对比结果，其中#C, #G分别为测试集中各个电路对应的单元数和方格数。对于每个ISCAS89测试电路，表中列出了两种方法对应的均值u(ps)，标准差sd(ps), 5%概率点5%Pt和95%概率点95%Pt (ps,5%Pt定义为存在一个延时值，使得p(x≤5%Pt) =5%；95%Pt定义为存在一个延时值，使得p(x≤95%Pt)=95%)及运行时间t(s)。从表2可以看出，两种方法的结果非常相近，均值、标准差、5%Pt及95%Pt的平均相对误差分别只有0.81%, -0.72%, 2.23%及-0.05%。这表明本文CSSTA具有相当高的精确度，足以匹配真实的延时分布。对于电路s38417，图5给出了两种方法下的延时PDF和CDF对比结果，其中三角块线为考虑空间关联且假设工艺参数同时服从高斯分布和非高斯分布的CSSTA结果，方块线为相同方格模型下的MC结果，从图中也可以看出，两种方法对应的曲线具有较高的匹配度。另外，从表2也可以看出，虽然本文CSSTA采用了ICA和PCA转换技术，但其运行时间相对于MC仍要小很多，除了电路s27的运行时间约为MC运行时间的1.29%外，其它电路的运行时间几乎为MC运行时间的千分之几；特别是对于电路s35932，本文CSSTA运行时间为10.65 s，而MC却需要超过7 h。因此，根据表2可以计算出，本文9组电路的CSSTA平均运行时间约为MC平均运行时间的0.21%。

为了验证SSTA非线性非高斯建模的合理性，本文与文献[9]中的结果进行了比较，比较的对象为相对MC的偏离误差。在文献[9]中，作者虽然也将部分工艺参数假设为非高斯分布，但其延时依赖关系却是线性的。表3给出了本文方法与文献[9]方法的对比结果，表中没有列出运行时间结果，这是因为：(1)表3关注的重点是两种方法的精确程度；(2)两种方法的运行时间相对MC都要小很多。从表3可以看出，若以MC为比较基准，本文方法的均值、标准差、5%Pt及95%Pt的平均相对误差更小，这表明本文方法相比文献[9]更为精确。

表2 本文空间关联SSTA(CSSTA)方法与蒙特卡洛(Monte Carlo, MC)仿真的对比结果

图5 电路s38417在空间关联SSTA与MC方法下的延时PDF, CDF对比结果

表3 本文空间关联SSTA方法与文献[9]方法的对比结果

6 结束语

本文提出了一种考虑空间关联工艺偏差的统计静态时序分析方法。该方法首先分析了芯片内不同位置工艺参数之间的空间关联性，并提出了一种考虑非高斯分布工艺参数的二阶延时模型；然后通过执行非线性非高斯延时表达式的求和、求极大值操作，实现了延时变量的PDF评估。ISCAS89实验结果验证了本文SSTA方法的准确性和快速性。

[1] Tang Q, Rodriguez J, Zjajo A, et al.. Statistical transistorlevel timing analysis using a direct random differential equation solver[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(2): 210-223.

[2] Shi B and Srivastava A. Thermal stress aware 3D-IC statistical static timing analysis[C]. Proceedings of the 23rd ACM International Conference on Great Lakes Symposium on VLSI, Paris, France, 2013: 281-286.

[3] Li B, Chen N, Xu Y, et al.. On timing model extraction and hierarchical statistical timing analysis[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32(3): 367-380.

[4] Zhang Xiao-lin, Ye Jing, Hu Yu, et al.. Capturing post-silicon variation by layout-aware path-delay testing[C]. Proceedings of IEEE/EDAA Design, Automation & Test in Europe, Grenoble, France, 2013: 288-291.

[5] Wagner M and Wunderlich H. Efficient variation-aware statistical dynamic timing analysis for delay test applications [C]. Proceedings of IEEE/EDAA Design, Automation & Test in Europe, Grenoble, France, 2013: 276-281.

[6] Amin C, Menezes N, Killpack K, et al.. Statistical static timing analysis: how simple can we get?[C]. Proceedings of IEEE/ACM Design Automation Conference, San Diego, USA, 2005: 652-657.

[7] Chang H and Sapatnekar S. Statistical timing analysis considering spatial correlations using a single PERT-like traversal[C]. Proceedings of IEEE/ACM International Conference on Computer Aided Design, San Jose, USA, 2003: 621-625.

[8] Zhan Y, Strojwas A, Li X, et al.. Correlation-aware statistical timing analysis with non-Gaussian delay distributions[C]. Proceedings of IEEE/ACM Design Automation Conference, San Diego, USA, 2005: 77-82.

[9] Singh J and Sapatnekar S. A scalable statistical static timing analyzer incorporating correlated non-Gaussian and Gaussian parameter variations[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(1): 160-173.

[10] Kirkpatrick T and Clark N. PERT as an aid to logic design[J]. IBM Journal of Research and Development, 1966, 10(2):135-141.

[11] Morrison D. Multivariate Statistical Methods[M]. 2nd Edition, New York: McGraw-Hill, 1976: 170-179.

[12] Tony B. An ICA page-papers, code, demos and links[OL]. http://cnl.salk.edu/～tony/ica.html. 1996.11.

[13] Li X, Le J, Gopalakrishnan P, et al.. Asymptotic probability extraction for non-normal distributions of circuit performance[C]. Proceedings of IEEE/ACM International Conference on Computer Aided Design, San Jose, USA, 2004: 2-9.

[14] Brglez F, Bryan D, and Kozminski K. Combinational profiles of sequential benchmark circuits[C]. Proceeding of IEEE International Symposium on Circuits and Systems, Portland, USA, 1989: 1929-1943.

[15] Juha K. Independent component analysis and blind source separation[OL]. http://research.ics.aalto.fi/ica/fastica/. 2011. 2.

[16] Andrew C. Wire length-driven standard-cell placement[OL]. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/Placement/. 2000.6.

喻 伟： 男，1986年生，博士生，研究方向为大规模集成电路设计自动化技术.

杨海钢： 男，1960年生，研究员，博士生导师，研究方向为高速可编程逻辑芯片设计技术、数模混合信号SOC设计技术.

刘 洋： 男，1983年生，博士，助理研究员，研究方向为大规模集成电路设计自动化技术.

黄 娟： 女，1983年生，博士，助理研究员，研究方向为大规模集成电路设计自动化技术.

蔡博睿： 男，1988年生，研究实习员，研究方向为大规模集成电路设计自动化技术.

陈 锐： 男，1986年生，博士生，研究方向为粗粒度可重构阵列结构方面的研究.

A Statistical Static Timing Analysis Incorporating Process Variations with Spatial Correlations

Yu Wei①②Yang Hai-gang①Liu Yang①Huang Juan①Cai Bo-rui①Chen Rui①②

①(Institute of Electronics, Chinese Academy of Sciences, Beijing 100190, China)
②(University of Chinese Academy of Sciences, Beijing 100086, China)

To evaluate effects of process variations on circuit delay accurately, this study proposes a Statistical Static Timing Analysis (SSTA) which incorporates process variations with spatial correlations. The algorithm applies a second order delay model that taking into account the non-Gaussian parameters - by inducting the notion of ‘conditional variables’, the 2D non-linear delay model is translated into 1D linear one; and by computing the tightness probability, mean, variance, second-order moment and sensitivity coefficients of the circuit arrival time, the sum and max operations of non-linear and non-Gaussian delay expressions are implemented. For the ISCAS89 benchmark circuits, as compared to Monte Carlo (MC) simulation, the average errors of 0.81%, -0.72%, 2.23% and -0.05%, in the mean, variance, 5% and 95% quantile points of the circuit delay are obtained respectively for the proposed method. The runtime of the proposed method is about 0.21% of the value of Monte Carlo simulation. The experimental results prove that the high accuracy of the SSTA is reliable.

Integrated Circuit (IC); Statistical Static Timing Analysis (SSTA); Spatial correlations; Nongaussianity and non-linearity; Process variations; Delay model

TN402

A

1009-5896(2015)02-0468-09

10.11999/JEIT140295

2014-03-06收到，2014-06-09改回

国家科技重大专项(2013ZX03006004)和国家自然科学基金(61106033)资助课题

*通信作者：杨海钢 yanghg@mail.ie.ac.cn