法律状态公告日
法律状态信息
法律状态
2023-03-17
未缴年费专利权终止 IPC(主分类):G06F17/50 专利号:ZL2012101052165 申请日:20120411 授权公告日:20131211
专利权的终止
2013-12-11
授权
授权
2012-10-17
实质审查的生效 IPC(主分类):G06F17/50 申请日:20120411
实质审查的生效
2012-08-29
公开
公开
技术领域
本发明涉及一种集成电路设计中基于随机行走的电容参数提取计算方法,属于集成电路计算机辅助设计技术领域。
背景技术
集成电路的设计流程中首先要提出功能描述,然后经过逻辑设计、版图设计得到描述半导体工艺尺寸、结构的版图。这时需要进行“版图验证”,即通过计算机软件模拟等来验证上述设计是否能达到当初设定的要求。如果满足要求,就可进行下一步的生产制造等;否则要返回逻辑设计等进行必要的修正。重复这个迭代过程,直到版图验证表明设计确实能够满足要求为止。在版图验证中,一个重要的环节称为“寄生参数提取”。
随着电路制造技术的发展,随着电路规模的不断增大,和特征尺寸的不断缩小,当今很多芯片含有几千万乃至上亿个器件。不过,现今互连线的寄生效应对电路的延时影响已经超越了器件级别。而对于影响时延的电感,电容等参数以往简单估计甚至直接忽略的做法已经很难达到足够的精度要求,需要对其进行的准确的提取计算,只有这样才能进行正确的电路模拟与验证。随着工业界对计算精度的要求越来越高,互连线之间的电容参数提取研究需要使用三维电容提取,即三维场求解器来进行精确求解。此类场求解器的计算往往是耗时的,对其算法的优化与加速研究意义很大。
集成电路电容参数提取场求解器中,随机行走电容提取算法是一种现在比较流行的计算方法。本申请人曾经在第十七届国际会议Asia and South Pacific Design Automation Conference 2012(以下简称ASP-DAC 2012)的论文“Fast Floating Random Walk Algorithm for Capacitance Extraction with Numerical Characterization of Green′s Function”中,公开了一种加速该方法用于求解先进集成电路多介质工艺下电容参数提取。其中提出了一种在给定集成电路工艺的条件下,预计算随机行走算法中需要的数据信息,如增加两层介质层转移区域的转移概率分布,以及相应权重分布数据,并应用于随机行走算法中,解决了目前同类算法在多层介质情况下计算速率较慢或者消耗内存较大的问题。通过观察发现,该算法以及其他相似算法,对随机行走算法中涉及的蒙特卡洛过程中使用的权重以及采样方法并没有进一步优化,导致了算法效率不高。
发明内容
本发明的目的是提出一种集成电路设计中基于随机行走的电容参数提取计算方法,针对未经过优化的权重数值以及采样的问题,给出一种通过重要性采样的思想进行预处理权重数值以及相应采样概率,并应用于随机行走算法,提高对集成电路在电容参数提取计算效率。
本发明方法提出的集成电路设计中基于随机行走的电容参数提取计算方法,包括以下步骤:
(1)设定集成电路中的相邻两个介质层的交界面的介电常数组合为(ε-,ε+)s,其中s=1,2,...,m,m为介电常数组合的种类,ε-为交界面的上层介质的介电常数,ε+为交界面的下层介质的介电常数,注:ε-=ε+的时候就是单介质情况;
(2)设在集成电路介质中建立一个立方体转移区域模型,将立方体的每个棱长划分为n段,介质交界面位于该立方体纵向高度的j/n处,其中j需要分别取值1,2,...,n-1。这里要求的只是立方体表面共有6n2个网格,而这在之后将以一个向量的形式表示面上所有元素的数值,所以需要根据一定规则编好号,并记录所有元素相对于转移区域的位置偏移量为x方向为offx[i],y方向为offy[i],z方向为offz[i],i=1,2,...,6n2;
坐标偏移的使用方法:为了方便说明转移区域的形式以及之后随机行走中使用的随机行走点在集成电路版图上实际坐标的计算,用图3这个二维作为示意图,三维的形式可以做相应的类比。因为是二维,只考虑x和z方向坐标,图3中左下角的28所指的线段为起始的边界线段,此时n为7,顺时针对边界上的线段进行顺序编号,那么24所指的线段的编号就是6。设x方向的偏移量为offx[6]=0,z方向的偏移量为offz[6]=6/n。当随机行走的中心点(如图3的点26),和转移区域中介质交界面(如图3的27所指)在2/n处,那么就记录此时转移区域在集成电路版图中实际的棱长L,和左下角的实际坐标(MinX,MinZ),通过X=MinX+offx[6]·L,Z=MinZ+offz[6]·L。那么(X,Z)就是图3中24所指线段,即边界元素6所对应的实际坐标。
现在需要的是求解转移概率密度向量:根据(a)静电场电势拉普拉斯方程:
(b)交界面电势连续条件:
φ+=φ-
以及(c)电位移连续条件:
以有限数值差分形式建立一个求解立方体转移区域表面6n2个网格的电势与立方体转移区域中心点电势关系的矩阵:
其中E11是满足上述拉普拉斯方程的立方体转移区域内任意两个立方体单元之间的电势关系系数,E12是满足拉普拉斯方程的立方体转移区域内任意一个立方体单元与任意一个表面网格之间的电势关系系数,E13是满足拉普拉斯方程的立方体转移区域中介质交界面与任意一个立方体单元之间的电势关系系数,E31和D33分别是同时满足上述交界面电势连续条件和电位移连续条件的立方体转移区域中介质交界面与任意一个立方体单元之间的电势关系系数,I2是单位对角矩阵,用于使立方体转移区域表面网格上的电势φB等于一个中间变量fB,φF是立方体转移区域介质交界面上的电势,φI是立方体转移区域中立方体单元的电势;
设k是转移区域中心点所在立方体转移区域中立方体单元的编号,ek是一个用于提取立方体转移区域中心点电势的向量,在该向量的k位置的数值为1,其余数值均是0,
则φI表达成:
消去边界条件fB,得到立方体转移区域表面6n2个网格的电势与中心点电势关系的格林函数数值解Pk,并将该格林函数数值解Pk作为集成电路中立方体转移区域的初始转移概率概率向量:
(3)使梯度算子作用于上述初始转移概率向量Pk,得到集成电路中立方体转移区域的 初始权重数值向量如下:
其中 是向量,其中元素
i=1,n,n2,k是转移区域中心点所在立方体转移区域中立方体单元的编号,h为立方体转移区域中相邻两个立方体单元的中心间距;
(4)采用重要性采样原理,根据上述初始权重数值向量,计算得到集成电路中立方体转移区域的权重数值向量KX,KY,KZ:
根据得到的权重数值向量Kx,对上述集成电路中立方体转移区域的初始转移概率密度向量Pk进行调整,得到转移概率密度向量
上述转移概率密度向量需要转换为转移积累分布向量,才能用于随机行走时随机取点的概率判断。
转换方法是:设一转移概率密度向量为P,那么P[i]是该向量的第i个元素。i从2到6n2, P[i]=P[i]+P[i-1],这样就形成了转移积累分布向量 同样处理Pk。
(5)重复(1)~(4),得到集成电路中各立方体转移区域的转移概率向量以及与该转移概率相对应的权重数值向量,将集成电路中各立方体转移区域的初始转移积累分布向量Pk,转移积累分布向量 以及与转移积累分布向量相对应的权重数值向量KX,KY,KZ存入一个数据库中;
(6)设定一个求解精度q,读取描述集成电路的版图,并从上述数据库中读取与该集成电路版图相对应的初始转移概率向量、转移概率向量以及权重数值向量,设置随机行走路径计数器,初始化时,设M为1,设与集成电路中U个导体电容数值对应的数组A[i]=B[i]=0,i为与导体电容数值对应的数组序号,i=1,2,...,U,设与主导体电容数值对应的数组序号为1;
(7)在集成电路版图中建立一个高斯面,高斯面内包括目标主导体,如图2的11;
(8)从高斯面上任取一个随机行走起始点T1,以该点为中心,构建一个不包括任何导体且至多包含两层介质的随机行走立方体转移区域,并记录区域棱长L,左下角点在空间中的坐标(MinX,MinY,MinZ);
(9)从步骤(6)的初始转移积累分布向量、转移积累分布向量以及权重数值向量中检索到与随机行走立方体转移区域相匹配的转移积累分布向量和权重数值向量;判断T1所处于高斯面的法向与那个坐标轴平行,如果与X平行,则令 同理,与Y平行,
(10)生成一个0~1之间的随机数R,将该随机数按照一定查找算法与步骤(9)的转移积累分布向量P中进行比较,若随机数R满足P[i]≤R<P[i+1],进行步骤(11),若没有达到此关系,继续比较,直到R满足P[i]≤R<P[i+1],进行步骤(11);
(11)判定随机行走将走向i所标记的网格位置,根据上述步骤(2)的偏移量计算出T2所在集成电路版图中的实际坐标(MinX+offx[i]×L,MinY+offy[i]×L,MinZ+offz[i]×L),并计算权重数值W=K/L,其中,L为随机行走立方体转移区域棱长,K为权重数值向量,并判断方向T2是否在高斯面之外,若是则W=-W,不是既保持W不 变;
(12)对随机行走点T2进行判断,若随机行走点T2在导体上(如图2中的19),则进行步骤(13),若随机行走点T2不在任何导体上,则以随机行走点T2为中心重新构建一个不包括任何导体且至多包含两层介质的随机行走立方体转移区域,并记录区域棱长L,左下角点在空间中的坐标(MinX,MinY,MinZ),从步骤(6)的初始转移积累分布向量、转移积累分布向量以及权重数值向量中检索出对应的初始转移概率P=Pk;重新生成一个0~1之间的随机数R,用于替代步骤(10)的随机数,将该随机数与步骤(9)的转移积累分布向量P中进行比较,若随机数R不满足P[i]≤R<P[i+1],继续比较,直到随机数R满足P[i]≤R<P[i+1],随机行走将走向i所标记的网格位置,根据步骤(2)的偏移量更新T2所在集成电路版图中的实际坐标(MinX+offx[i]×L,MinY+offy[i]×L,MinZ+offz[i]×L),重复本步骤,直到T2属于一个导体;
(13)设随机行走点T2在导体Cj上,这样就结束了一条随机行走路径,将上述权重数值Wi加入数组A[j],即A[j]=A[j]+W,使权重的平方W2加入数组B[j],即B[j]=B[j]+W2,利用下列式子 进行判断,若不等式成立,则达到求解精度q,并使A[j]=A[j]/M,j=1,2,...,U。进行步骤(14),若不等式不成立,则设M=M+1,返回步骤(8);
(14)结束。
本发明提出的集成电路设计中基于随机行走的电容参数提取计算方法,其优点是,由于方法中采用了重要性采样对原始权重的预处理,使得产生的权重数值较为统一,且取样概率趋向对高斯面积分贡献较大的地方。所以本发明的电容参数提取计算方法计算效率较高,缩短了集成电路的设计周期。
附图说明
图1是集成电路的层间结构示意图。
图2是随机行走电容提取算法示意图,其中仅画出了一条随机行走路径。
图3是转移区域的2维纵向截面图。
图1~图3中,1是介质层1,介质层2,3是介质层3,4是介质层4,5是底部导体,6是介质层6,7是介质层7,8是介质层8,9是介质层9,10是位于介质层7的长导线,11是位于介质层7的长导线,12是位于介质层7的长导线,13是位于介质层8的短导线,14是位于介质层6的短导线,16是高斯面上的随机行走点(一条路径的起始点),17是16生产的漫步点,18是17生产的漫步点,19是击中导体的漫步点,20是16形成的转移区域,21是17形成的转移区域,22是18形成的转移区域,23是这条路径的轨迹,24是转移区域的边界元,25是转移区域差分格点,26是转移区域的中心点,27是介质面处在的位置,28是转移区域的边界元。
具体实施方式
本发明的建库以及重要性采样处理已用MATLAB编程实现,FRW已用C++语言编程实现,可以在Intel工作站上的LINUX操作系统及PC机的Linux操作系统上运行。下面结合一个具体实施例说明含重要性采样建库过程方法的电容提取过程,以图1为实施例子,在长导线10、11、12的地方各放置一个长导线,在长导线13和14的地方分别放置19根短导线,与长导线10、11、12的方向成水平面内交叉。
(1)设定集成电路中的相邻两个介质层的交界面的介电常数组合为(ε-=2.6,ε+=5),n=5(为了便于版面书写,设n=5已知,为了保证精度,根据经验n通常设为31),进行计算,
(2)设在集成电路介质中建立一个立方体转移区域模型,将立方体的每个棱长划分为n段,介质交界面位于该立方体纵向高度的j/n处,其中j=1,2,...,n-1,此时立方体中共有n3个立方体单元。要求得只是立方体表面共有6n2个网格,而这在之后将以一个向量的形式表示面上所有元素的数值,所以需要根据一定规则编好号,并记录所有元素相对与转移区域的位置偏移量offx[i],offy[i],offz[i],i=1,2,...,6n2。
根据(a)静电场电势拉普拉斯方程:
(b)交界面电势连续条件:
φ+=φ-
以及(c)电位移连续条件:
以有限数值差分形式建立一个求解立方体转移区域表面6n2个网格的电势与立方体转移区域中心点电势关系的矩阵:
其中E11是满足上述拉普拉斯方程的立方体转移区域内任意两个立方体单元之间的电势关系系数,E12是满足拉普拉斯方程的立方体转移区域内任意一个立方体单元与任意一个表面网格之间的电势关系系数,E13是满足拉普拉斯方程的立方体转移区域中介质交界面与任意一个立方体单元之间的电势关系系数,E31和D33分别是同时满足上述交界面电势连续条件和电位移连续条件的立方体转移区域中介质交界面与任意一个立方体单元之间的电势关系系数,I2是单位对角矩阵,用于使立方体转移区域表面网格上的电势φB等于一个中间变量fB,φF是立方体转移区域介质交界面上的电势,φI是立方体转移区域中立方体单元的电势,
设k是转移区域中心点所在立方体转移区域中立方体单元的编号,ek是一个用于提取立方体转移区域中心点电势的向量,在该向量的k位置的数值为1,其余数值均是0,
则φI表达成:
消去边界条件fB,得到立方体转移区域表面6n2个网格的电势与中心点电势关系的格林函数数值解Pk,并将该格林函数数值解Pk作为集成电路中立方体转移区域的初始转移概率密度向量:
(3)使梯度算子作用于上述初始转移概率密度向量Pk,
其中 是向量,其中元素
其中i=1,n,n2,k是转移区域中心点所在立方体转移区域中立方体单元的编号,h为立方体转移区域中相邻两个立方体单元的中心间距,将上述计算结果作为集成电路中立方体转移区域的初始权重数值向量,
如:当k=2时候,选择z方向向上为正方向,顶面权重分布
某个侧面权重的分布为
(4)采用重要性采样原理,根据上述初始权重数值向量,计算得到集成电路中立方体转移区域的权重数值KX,KY,KZ
根据得到的权重数值向量Kx,对上述集成电路中立方体转移区域的初始转移概率密度向量Pk进行调整,得到转移概率密度向量
相应的(3),顶面重要性采样转移概率分布为
对应(3)的第二个表,侧面重要性采样转移概率的分布为
将转移密度向量 和初始转移密度向量Pk转化为转移积累分布向量。
(5)重复(1)-(4),因为这个例子只有1组介质配置(2.6,5),已经计算,就无需在重复。已经得到需要的集成电路中各立方体转移区域的转移概率向量以及与该转移概率相对应的权重数值向量,将集成电路中各立方体转移区域的初始转移积累分布向量Pk、转移积累分布向量 以及与转移概率向量相对应的权重数值向量KX,KY,KZ存入一个数据库中,
(6)设定一个求解精度q,读取描述集成电路的版图,并从上述数据库中读取与该集成电路版图相对应的初始转移积累分布向量、转移积累分布向量以及权重数值向量,设随机行走路径计数器M为1,初始化与U个导体电容数值对应的数组A[i]=B[i]=0,i=1,2,...,U,主导体的数组序号为1。
(7)在集成电路版图中建立一个高斯面,如图2的15,高斯面内包括目标主导体,如图2的11。
(8)从高斯面上任取一个随机行走起始点T1,如图2的16,以该点为中心,构建一个不包括任何导体且至多包含两层介质的随机行走立方体转移区域,如图2的20,并记录区域棱长L,左下角点在空间中的坐标(MinX,MinY,MinZ)。
(9)从步骤(6)的初始转移积累分布向量、转移积累分布向量以及权重数值向量中检索到与随机行走立方体转移区域相匹配的转移积累分布向量和权重数值向量,判断T1所处于高斯面的法向与那个坐标轴平行,如果与X平行,则令 K=Kx,同理,与Y平 行, K=Ky,与Z平行, K=Kz。
(10)生成一个0~1之间的随机数R,将该随机数按照一定查找算法与步骤(9)的转移概率向量P中进行比较,若随机数R满足P[i]≤R<P[i+1],进行步骤(11),若没有达到此关系,继续比较,直到R满足P[i]≤R<P[i+1],进行步骤(11)。
(11)判定随机行走将走向i所标记的网格位置,根据上述步骤(2)的偏移量计算出T2所在集成电路版图中的实际坐标(MinX+offx[i]×L,MinY+offy[i]×L,MinZ+offz[i]×L),并计算权重数值W=K/L,其中,L为随机行走立方体转移区域棱长,K为权重数值向量,并判断方向T2是否在高斯面之外,若是则W=-W,不是既保持W不变。
(12)对随机行走点T2(如图2的17,18)进行判断,若随机行走点T2在导体上(如图2中的19),则进行步骤(13),若随机行走点T2不在任何导体上(如图2的10,11,12),则以随机行走点T2为中心重新构建一个不包括任何导体(如图2考虑导体10,11,12,13,在图1里则还需要考虑14,15)且至多包含两层介质(如图2考虑的介质是2,3,6,7,8,在图1则是1到9)的随机行走立方体转移区域(如图2的20,21),并记录区域棱长L,左下角点在空间中的坐标(MinX,MinY,MinZ),从步骤(6)的初始转移积累分布向量、转移积累分布向量以及权重数值向量中检索出对应的初始转移概率P=Pk;重新生成一个0~1之间的随机数R,用于替代步骤(10)的随机数,将该随机数与步骤(9)的转移积累分布向量P中进行比较,若随机数R不满足P[i]≤R<P[i+1],继续比较,直到随机数R满足P[i]≤R<P[i+1],随机行走将走向i所标记的网格位置,根据步骤(2)的偏移量更新T2所在集成电路版图中的实际坐标(MinX+offx[i]×L,MinY+offy[i]×L,MinZ+offz[i]×L),重复本步骤,直到T2属于一个导体。
(13)设随机行走点T2在导体Cj上如图2的13,这样就结束了一条随机行走路径,如图2的23,将上述权重数值Wi加入数组A[j],即A[j]=A[j]+W,使权重的平方W2加入数组B[j],即B[j]=B[j]+W2,利用下列式子 进行判断,若不等式成立,则达到求解精度q,并使A[j]=A[j]/M,j=1,2,...,U。进行步骤(14),若不等式不成立,则设M=M+1,返回步骤(8)。
(14)结束。
机译: 半导体集成电路设计方法和程序,半导体集成电路设计支持方法和程序以及布线寄生电容计算方法和程序
机译: 用于集成电路设计中的功能操作测试的随机代码生成,涉及为分配给指令类型的预定义控制值生成随机权重,以将其包括在随机代码中
机译: 集成电路设计的电参数提取