• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 15
    • 下载费用:30 金币  

    重庆时时彩新手群: 面向集成电路互连电容提取的线网高斯面采样方法及系统.pdf

    关 键 词:
    面向 集成电路 互连 电容 提取 线网高斯面 采样 方法 系统
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201410016439.3

    申请日:

    2014.01.14

    公开号:

    CN103793557A

    公开日:

    2014.05.14

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):G06F 17/50申请日:20140114|||公开
    IPC分类号: G06F17/50 主分类号: G06F17/50
    申请人: 清华大学
    发明人: 喻文健; 张超
    地址: 100084 北京100084-82信箱
    优先权:
    专利代理机构: 深圳市鼎言知识产权代理有限公司 44311 代理人: 徐丽昕
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410016439.3

    授权公告号:

    ||||||

    法律状态公告日:

    2016.08.17|||2014.06.11|||2014.05.14

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    一种面向集成电路互连电容提取的线网高斯面采样方法及系统,针对包含超过一块导体的线网,实现在包围该线网的高斯面上进行随机行走采样的过程,该方法并不真正在几何上构造线网高斯面,而是在组成线网各个导体块的高斯面的合集上进行随机采样,然后通过拒绝采样(rejection?sampling)达到直接在线网高斯面上采样的效果。相比于通过几何运算求出所有块高斯面的包络、从而得到线网高斯面的方法,本发明运算简单、效率高,且能适应基于方差约减的快速随机行走方法。避免了通过复杂的三维几何运算求所有块高斯面的包络,效率高且易于实现。

    权利要求书

    权利要求书
    1.  一种面向集成电路互连电容提取的线网高斯面采样方法,应用于计算装置中,其特征在于,该方法包括:
    选择步骤一,生成一个0~1之间的均匀分布随机数R1,根据随机数R1及积累面积向量M选择块高斯面Gk,所述块高斯面Gk为导体块Bk的高斯面,所述导体块Bk为线网的一个导体块,所述线网包括Nb个导体块Bi,所述线网对应的三维形体是所述导体块Bi的并集,所述线网的每个导体块Bi对应一个块高斯面Gi,其中i=1,2,...,,Nb,Nb表示所述线网所包括的导体块的数量;
    选择步骤二,在块高斯面Gk上按均匀分布随机选取一点r;
    检查步骤,依次检查点r与其他块高斯面Gi的关系以丢弃了没有落在线网高斯面上的采样点,并获得nc的取值,其中i=1,2,...,Nb,i≠k,nc表示的是若r点落在线网高斯面上,则r点同时在nc个块高斯面上;
    生成步骤一,生成一个0~1之间的均匀分布随机数R2;
    判断步骤一,判断R2是否大于1/nc,当R2大于1/nc,返回执行选择步骤一;
    生成步骤二,当R2不大于1/nc时,生成一个0~1之间的均匀分布随机数R3;
    判断步骤二,判断R3是否大于p(r)/U,当R3大于p(r)/U,返回执行选择步骤一;
    获取步骤,当R3不大于p(r)/U,得到点r是所述线网的高斯面上的有效采样点,其中p(r)为所述线网的高斯面上的采样概率密度函数。

    2.  如权利要求1所述的面向集成电路互连电容提取的线网高斯面采样方法,其特征在于,Gi包含Bi,且Gi不与所述线网以外的其它导体相交,计算出每个Gi的面积Si,构造积累面积向量M,其第i个分量为:i=1,2,...,Nb,M[0]=0,向量M的最后一个元素M[Nb]为所有Gi的面积总和。

    3.  如权利要求1所述的面向集成电路互连电容提取的线网高斯面采样方法,其特征在于,所述检查步骤包括:
    (a)设置nc的初始值及循环变量i的初始值;
    (b)判断i的取值是否大于Nb,当i的取值大于Nb时,执行所述生成步骤一;
    (c)当i的取值不大于Nb时,检查i的取值是否等于k,当i的取值是等于k时,执行(h);
    (d)当i的取值不等于k时,判断点r是否落在Gi包围的空间内部,当点r落在Gi包围的空间内部时,返回执行所述选择步骤一;
    (e)当r没有落在Gi包围的空间内部时,判断点r是否在Gi的表面,当点r不在Gi的表面时,执行(h);
    (f)当点r在Gi的表面时,判断在r处Gi的外法向与Gk的外法向方向是否相同,当在r处Gi的外法向与Gk的外法向方向不相同时,返回执行所述选择步骤一;
    (g)当在r处Gi的外法向与Gk的外法向方向相同时,将nc的取值加1;
    (h)将i的取值自动加一,即i=i+1。

    4.  如权利要求1所述的面向集成电路互连电容提取的线网高斯面采样方法,其特征在于,所述U为预先设置的一个常数值,其不小于函数p(r)的最大值。

    5.  一种面向集成电路互连电容提取的线网高斯面采样系统,运行于计算装置中,其特征在于,该系统包括:
    选择???,用于生成一个0~1之间的均匀分布随机数R1,根据随机数R1及积累面积向量M选择块高斯面Gk,所述块高斯面Gk为导体块Bk的高斯面,所述导体块Bk为所述线网的一个导体块,所述线网包括Nb个导体块Bi,所述线网对应的三维形体是所述导体块Bi的并集,所述线网的每个导体块Bi对应一个块高斯面Gi,其中i=1,2,...,,Nb,Nb表示所述线网所包括的导体块的数量;
    所述选择???,用于在块高斯面Gk上按均匀分布随机选取一点r;
    检查???,用于依次检查点r与其他块高斯面Gi的关系以丢弃了没有落在线网高斯面上的采样点,并获得nc的取值,其中i=1,2,...,Nb,i≠k,nc表示的是若r点落在线网高斯面上,则r点同时在nc个块高斯面上;
    生成???,用于生成一个0~1之间的均匀分布随机数R2;
    判断???,用于判断R2是否大于1/nc,当R2大于1/nc,所述选择??樯梢桓?~1之间的均匀分布随机数R1;
    所述生成???,用于当R2不大于1/nc时,生成一个0~1之间的均匀分布随机数R3;
    所述判断???,用于判断R3是否大于p(r)/U,当R3大于p(r)/U,所述选择??樯梢桓?~1之间的均匀分布随机数R1;
    获取???,用于当R3不大于p(r)/U,得到点r是所述线网的高斯面上的有效采样点,其中p(r)为所述线网的高斯面上的采样概率密度函数。

    6.  如权利要求5所述的面向集成电路互连电容提取的线网高斯面采样系统,其特征在于,Gi包含Bi,且Gi不与所述线网以外的其它导体相交,计算出每个Gi的面积Si,构造积累面积向量M,其第i个分量为:i=1,2,...,Nb,M[0]=0,向量M的最后一个元素M[Nb]为所有Gi的面积总和。

    7.  如权利要求5所述的面向集成电路互连电容提取的线网高斯面采样系统,其特征在于,所述检查??榫咛逵糜冢?BR>(a)设置nc的初始值及循环变量i的初始值;
    (b)判断i的取值是否大于Nb,当i的取值大于Nb时,执行所述生成???,生成一个0~1之间的均匀分布随机数R2;
    (c)当i的取值不大于Nb时,检查i的取值是否等于k,当i的取值是等于k时,执行(h);
    (d)当i的取值不等于k时,判断点r是否落在Gi包围的空间内部,当点r落在Gi包围的空间内部时,执行所述选择???,生成一个0~1之间的均匀分布随机数R1;
    (e)当r没有落在Gi包围的空间内部时,判断点r是否在Gi的表面,当点r不在Gi的表面时,执行(h);
    (f)当点r在Gi的表面时,判断在r处Gi的外法向与Gk的外法向方向是否相同,当在r处Gi的外法向与Gk的外法向方向不相同时,执行所述选择???,生成一个0~1之间的均匀分布随机数R1;
    (g)当在r处Gi的外法向与Gk的外法向方向相同时,将nc的取值加1;
    (h)将i的取值自动加一,即i=i+1。

    8.  如权利要求5所述的面向集成电路互连电容提取的线网高斯面采样系统,其特征在于,所述U为预先设置的一个常数值,其不小于函数p(r)的最大值。

    说明书

    说明书面向集成电路互连电容提取的线网高斯面采样方法及系统
    技术领域
    本发明涉及超大规模集成电路(Very Large Scale Integrated circuits,VLSI)物理设计与验证领域,是面向集成电路互连电容提取的线网高斯面采样方法及系统。
    背景技术
    集成电路的设计流程中首先要提出功能描述,然后经过逻辑设计、版图设计得到描述半导体工艺尺寸、结构的版图,最后进行版图验证,即通过计算机软件模拟来验证上述设计是否满足要求。若满足要求,则进行下一步的生产制造。否则,若不满足要求,则返回逻辑设计、版图设计进行必要的修正。在版图验证中,一个重要的环节是“互连寄生参数提取”。
    随着集成电路制造技术的发展,电路规模不断增大、特征尺寸不断缩小,当今很多芯片已含有一千万乃至更多个器件。然而,集成电路中互连线的寄生效应造成互连线对电路延时的影响已超过了器件对电路延时的影响。因此,需要对互连线的电容、电阻等参数进行准确的计算,以保证电路模拟与验证的正确有效性。为了提高计算精度,互连线之间的电容参数提取需要使用三维提取方法,即利用三维场求解器进行求解。场求解器的计算往往耗时较多,对其算法的优化与加速研究意义很大。
    在集成电路电容参数提取的场求解器方法中,随机行走电容提取算法是一种比较流行的方法。该方法不同于常规的有限差分法、有限元法和边界元法,它无需要求解线性方程组,计算中的主要步骤是在空间中随机取点(其得到一系列点的过程被形象地称为“随机行走”)。如图1所示,每次随机行走都从围绕导体的高斯面上开始,然后以当前点为中心构造一个最大、不与导体相交的立方体(称为“转移立方体”),下一 次取点则随机地落在转移立方体的表面(如图1中的S(1)和S(2))。这个过程重复进行,直到随机取点的位置达到导体表面,此时结束一次随机行走。要计算某一导体(例如图1中的导体i)与其他所有导体之间的电容值,需要进行至少上万次的随机行走。
    申请人2013年在国际期刊IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems上发表的论文“RWCap:A floating random walk solver for3-D capacitance extraction of VLSI interconnects”(第3期)和“Efficient space management techniques for large-scale interconnect capacitance extraction with floating random walks”(第10期)中,公开了一种基于方差约减的快速随机行走方法和一种空间管理技术。前者通过重要性采样(importance sampling)和分层采样(stratified sampling)技术改变在高斯面及转移立方体表面进行随机采样所需的概率分布,从而减少计算电容值所用的权值序列的方差,使得在相同准确度要求下随机行走的次数较少数倍,达到提高计算速度的目的。后者包括根据所计算三维结构中导体块的几何信息(位置与尺寸)建立的空间管理数据结构,使用它可以在随机行走电容提取过程中快速地判断距离当前行走位置最近的导体,从而加快转移立方体的构造以及整体计算速度。
    虽然已有的工作能加快随机行走电容提取算法的计算速度,但它们都只能计算单个分离导体块(三维空间的单个长方体)与其他导体之间的电容。在实际的集成电路互连线结构中,多块导体相连接形成一条信号通路(一般称为“线网”),需要计算整条线网与其他导体之间的电容(称为“线网电容提取”),然后才能分析信号在该线网上传递时的延迟时间。图2显示了集成电路电容提取问题中考虑的一个三维互连结构,其中包括单个的三维导体块,也包括多块导体依次连接形成的线网。
    为了进行线网电容提取,需要首先构造一个包围线网的高斯面,并在它上面进行随机取点(即“采样”)。然而,一个线网在z方向上可能跨越多层,包括数十个导体块,如何构造一个包围线网整体的高斯面、并在其上进行取点成为一个难题。
    发明内容
    鉴于以上内容,有必要提供一种面向集成电路互连电容提取的线网高斯面采样方法及系统,其运算简单、效率高,且能适应基于方差约减的快速随机行走方法,避免了通过复杂的三维几何运算求所有块高斯面的包络,效率高且易于实现。
    一种面向集成电路互连电容提取的线网高斯面采样方法,应用于计算装置中,该方法包括:选择步骤一,生成一个0~1之间的均匀分布随机数R1,根据随机数R1及积累面积向量M选择块高斯面Gk,所述块高斯面Gk为导体块Bk的高斯面,所述导体块Bk为所述线网的一个导体块,所述线网包括Nb个导体块Bi,所述线网对应的三维形体是所述导体块Bi的并集,A的每个导体块Bi对应一个块高斯面Gi,其中i=1,2,...,,Nb,Nb表示所述线网所包括的导体块的数量;选择步骤二,在块高斯面Gk上按均匀分布随机选取一点r;检查步骤,依次检查点r与其他块高斯面Gi的关系以丢弃了没有落在线网高斯面上的采样点,并获得nc的取值,其中i=1,2,...,Nb,i≠k,nc表示的是若r点落在线网高斯面上,则r点同时在nc个块高斯面上;生成步骤一,生成一个0~1之间的均匀分布随机数R2;判断步骤一,判断R2是否大于1/nc,当R2大于1/nc,返回执行选择步骤一;生成步骤二,当R2不大于1/nc时,生成一个0~1之间的均匀分布随机数R3;判断步骤二,判断R3是否大于p(r)/U,当R3大于p(r)/U,返回执行选择步骤一;获取步骤,当R3不大于p(r)/U,得到点r是所述线网的高斯面上的有效采样点,其中p(r)为所述线网的高斯面上的采样概率密度函数。
    一种面向集成电路互连电容提取的线网高斯面采样系统,运行于计算装置中,该系统包括:选择???,用于生成一个0~1之间的均匀分布随机数R1,根据随机数R1及积累面积向量M选择块高斯面Gk,所述块高斯面Gk为导体块Bk的高斯面,所述导体块Bk为所述线网的一个导体块,所述线网包括Nb个导体块Bi,所述线网对应的三维形体是所述导体块Bi的并集,所述线网的每个导体块Bi对应一个块高斯面Gi,其中i=1,2,...,,Nb,Nb表示所述线网所包括的导体块的数量;所述选择???,用于在块高斯面Gk上按均匀分布随机选取一点r;检查 ???,用于依次检查点r与其他块高斯面Gi的关系以丢弃了没有落在线网高斯面上的采样点,并获得nc的取值,其中i=1,2,...,Nb,i≠k,nc表示的是若r点落在线网高斯面上,则r点同时在nc个块高斯面上;生成???,用于生成一个0~1之间的均匀分布随机数R2;判断???,用于判断R2是否大于1/nc,当R2大于1/nc,所述选择??樯梢桓?~1之间的均匀分布随机数R1;所述生成???,用于当R2不大于1/nc时,生成一个0~1之间的均匀分布随机数R3;所述判断???,用于判断R3是否大于p(r)/U,当R3大于p(r)/U,所述选择??樯梢桓?~1之间的均匀分布随机数R1;获取???,用于当R3不大于p(r)/U,得到点r是所述线网的高斯面上的有效采样点,其中p(r)为所述线网的高斯面上的采样概率密度函数。
    相较于现有技术,本发明面向集成电路线网电容提取的虚拟高斯面采样方法及系统,特别针对包含超过一块导体的线网,实现在包围该线网的高斯面(称为“线网高斯面”)上进行随机行走采样的过程。该方法并不真正在几何上构造线网高斯面,而是在组成线网各个导体块的高斯面(称为“块高斯面”)的合集上进行随机采样,然后通过拒绝采样(rejection sampling)达到直接在线网高斯面上采样的效果。相比于通过几何运算求出所有块高斯面的包络、从而得到线网高斯面的方法,本发明运算简单、效率高,且能适应基于方差约减的快速随机行走方法。避免了通过复杂的三维几何运算求所有块高斯面的包络,效率高且易于实现。
    附图说明
    图1是随机行走电容提取过程的二维示意图。
    图2是集中电路互连电容提取中考虑的三维导体块与线网。
    图3是本发明面向集成电路互连电容提取的线网高斯面采样系统较佳实施例的运行环境示意图。
    图4是本发明本发明面向集成电路互连电容提取的线网高斯面采样系统较佳实施例的功能??橥?。
    图5是本发明面向集成电路互连电容提取的线网高斯面采样方法较佳实施例的流程图。
    图6是一个包括三块导体的线网的侧视图。
    主要元件符号说明

    如下具体实施方式将结合上述附图进一步说明本发明。
    具体实施方式
    参阅图3所示,是本发明面向集成电路互连电容提取的线网高斯面采样系统较佳实施例的运行环境示意图。所述面向集成电路互连电容提取的线网高斯面采样系统10运行于计算装置1中。该计算装置1还包括存储设备11及处理设备12。所述存储设备11存储集成电路版图,该集成电路版图描述集成电路的导体(包括主导体与环境导体)在空间的分布情况。所述处理设备12包括CPU(Central Processing Unit,中央处理器)及GPU(Graphic Processing Unit,图形处理器)等。
    所述存储设备11还存储预先建立的格林函数库和权值向量。所述格林函数库描述随机行走过程中转移区域的转移概率分布,所述权值向量存储行走起始点对应的权值。所述格林函数库可以描述单一介质转移区域的转移概率分布,用于提取单一介质条件下集成电路电容参数。所述格林函数库还可以描述多层介质转移区域的转移概率分布,用于提取 多层介质条件下集成电路电容参数。格林函数库与权值向量的建立方法可参考申请人在第十七届国际会议Asia and South Pacific Design Automation Conference2012发表的论文“Fast Floating Random Walk Algorithm for Capacitance Extraction with Numerical Characterization of Green's Function”(以下称ASP-DAC2012)。所述存储设备11还存储面向集成电路互连电容提取的线网高斯面采样系统10的程序代码及运行过程中所需的数据。所述处理设备12执行面向集成电路互连电容提取的线网高斯面采样系统10的程序代码,以快速计算集成电路中主导体与每个环境导体之间电容参数。
    假设本发明的线网为A,线网A包括Nb个导体块Bi,(i=1,2,...,Nb),A对应的三维形体是所述导体块Bi,(i=1,2,...,Nb)的并集。假设对A的每个导体块Bi,已建立了Bi的高斯面Gi(块高斯面)行随机采样的方法。假设所考虑的Gi包含Bi,且Gi不与线网A以外的其它导体相交。同时计算出每个Gi的面积Si,构造积累面积向量M,其第i个分量为:i=1,2,...,Nb,而M[0]=0,注意,向量M的最后一个元素M[Nb]为所有Gi的面积总和。
    在线网A的高斯面上按采样概率密度函数p(r)进行随机采点,r表示点的位置。并且预先设置U为不小于函数p(r)的最大值的某个常数值,则获得一个采样点的具体流程在图5详述。
    参阅图4所示,是本发明面向集成电路互连电容提取的线网高斯面采样系统较佳实施例的功能??橥?。面向集成电路互连电容提取的线网高斯面采样系统10包括选择???00、检查???01、生成???02、判断???03及获取???04。图5将对功能???00-104进行详细描述。
    参阅图5所示,是本发明面向集成电路互连电容提取的线网高斯面采样方法较佳实施例的流程图。
    步骤S701,选择???00生成一个0~1之间的均匀分布随机数R1,根据随机数R1及积累面积向量M选择块高斯面Gk。
    在本实施例中,选择???00按查找算法将R1与积累面积向量M的元素进行比较,如果R1满足M[k-1]≤R1·M[Nb]<M[k],则表示根据各个块高斯面的面积随机选中了Gk。
    步骤S702,选择???00在块高斯面Gk上按均匀分布随机选取一点r。
    后续步骤S703至步骤S710为检查???01依次检查点r与其他块高斯面Gi,(i=1,2,...,Nb,i≠k)的关系以丢弃了没有落在线网高斯面上的采样点,并获得nc的取值,nc的意义是:若r点落在线网高斯面上,则r点同时在nc个块高斯面上。具体过程如下:
    步骤S703,检查???01设置nc的初始值及循环变量i的初始值,nc的意义是:若r点落在线网高斯面上,则r点同时在nc个块高斯面上。在本实施例中,nc的初始值为1,i的初始值为1。循环变量i是为了使检查???01依次检查点r与其他块高斯面Gi,(i=1,2,...,Nb,i≠k)的关系。这样每个循环变量i对应一个高斯面Gi。
    步骤S704,检查???01判断i的取值是否大于Nb,Nb表示线网A所包括的导体块的数量,即Bi,(i=1,2,...,Nb)。当i的取值大于Nb时,执行步骤S711;当i的取值不大于Nb时,执行步骤S705。
    步骤S705,检查???01检查i的取值是否等于k。当i的取值是等于k时,执行步骤S710,i的取值自动加一,即i=i+1,然后返回执行步骤S704,直至使Nb个块高斯面(除Gk外)与点r的关系都被检查;当i的取值不等于k时,执行步骤S706。
    步骤S706,检查???01判断点r是否落在Gi包围的空间内部。当点r落在Gi包围的空间内部时,返回执行步骤S701;当r没有落在Gi包围的空间内部时,执行步骤S707。
    步骤S707,检查???01判断点r是否在Gi的表面。当点r在Gi的表面时,执行步骤S708;当点r不在Gi的表面时,执行步骤S710,i的取值自动加一,即i=i+1,然后返回执行步骤S704,直至使Nb个块高斯面(除Gk外)与点r的关系都被检查。
    步骤S708,检查???01判断在r处Gi的外法向与Gk的外法向方向是否相同。当在r处Gi的外法向与Gk的外法向方向相同时,执行 步骤S709;当在r处Gi的外法向与Gk的外法向方向不相同时,返回执行步骤S701。
    步骤S709,检查???01将nc的取值加1。
    步骤S710,检查???01将i的取值自动加一,即i=i+1。
    步骤S711,生成???02生成一个0~1之间的均匀分布随机数R2。
    步骤S712,判断???03判断R2是否大于1/nc。当R2大于1/nc时,返回执行步骤S701;当R2不大于1/nc时,执行步骤S713。
    步骤S713,生成???02生成一个0~1之间的均匀分布随机数R3。
    步骤S714,判断???03判断R3是否大于p(r)/U。当R3大于p(r)/U时,返回执行步骤S701;当R3不大于p(r)/U时,执行步骤S715。
    步骤S715,获取???04得到点r是线网A的高斯面上的有效采样点,该流程结束。
    在上述步骤S701中产生了一个随机数R1,应注意的是每执行一次步骤S701,都会产生一个不同的随机数R1。在步骤步骤S711及步骤S713中也是类似的情况。
    上述步骤S703~S710丢弃了没有落在线网高斯面上的采样点,步骤S711~S714则根据随机采样规则对落在线网高斯面上的点做进一步筛选。下面用一个二维示意图说明这些丢弃和筛选规则。如图6显示了一个含3块导体的线网的侧视图,并用虚线画出了它们各自的块高斯面G1,G2,G3,块高斯面上的点P1,P2,P3都落在线网高斯面上,而点P4,P5并非落在线网高斯面上,其中P4在G3所包围的空间内(通过步骤S706来判断),而P5同时在G1和G3的表面,但G1和G3在P5点处的外法向方向相反(通过步骤S707及步骤S708步来判断),因此P4,P5都不在线网高斯面上。对于P1,P2,P3来说,P3在G1和G2的表面,其对应的nc=2,通过步骤S712可知应按50%的概率接受P3,P1,P2只在一个块高斯面上,因此通过步骤S712可知可按100%的概率接受P1,P2。接下来考虑到要进行的高斯面采样并不一定是均匀采 样,因此还需根据采样概率密度函数p(r)通过步骤S714对P1,P2和P3点做进一步的筛选,才能使最终得到的采样点在线网高斯面上满足概率密度分布p(r)。
    本发明使用C语言编程实现。在使用Linux操作系统的工作站上运行。利用本发明“面向集成电路互连电容提取的线网高斯面采样方法”的基于随机行走方法进行线网电容提取的算法如下:
    基于随机行走方法进行线网电容提取的算法的输入为描述集成电路中线网的导体几何结构,需提取电容的线网编号j,随机行走算法终止条件。输出为线网j与其他导体块(或线网)i的耦合电容Cji,
    算法1基于随机行走方法的线网电容提取流程包括如下步骤:
    1:载入随机行走所需的格林函数库和权值向量;
    2:根据导体分布情况生成空间管理数据,以便于步骤9中的转移立方体能快速地构造;
    3:对线网j的每个导体块构造其块高斯面;
    4:设置电容初值:设置随机行走次数初值npath:=0;
    5:重复执行第6步至第13步;
    6:npath:=npath+1;
    7:在线网j的高斯面上随机取点r(0),以r(0)为中心生成转移立方体,然后在该立方体表面按照格林函数库所表示的概率分布随机取点r(1),在载入的权值向量的帮助下计算r(1)相应的权值ω;
    8:While随机点r(1)不在导体表面do
    9:以r(1)为中心构造最大、不与导体相交的转移立方体;
    10:按照格林函数库所表示的概率分布在转移立方体上随机取一点,将该随机点赋值给r(1);
    11:End
    12:若r(1)在导体i的表面,则Cji:=Cji+ω;
    13:直到满足终止条件
    14:Cji:=Cji/npath,
    上述算法1的第1步,格林函数库可以描述单一介质转移区域的转移概率分布,用于提取单一介质条件下集成电路电容参数,还可以描述多层介质转移区域的转移概率分布,用于提取多层介质条件下集成电路电容参数。格林函数库与权值向量的建立方法可参考发明人2013年在国际期刊IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems上发表的论文“RWCap:A floating random walk solver for3-D capacitance extraction of VLSI interconnects”。
    算法1的第2步,具体做法可参考发明人2013年在国际期刊IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems上发表的论文“Efficient space management techniques for large-scale interconnect capacitance extraction with floating random walks”,以及提交的发明专利申请201310388975.1。
    算法1的第3步是本发明的一个创新点,即不对线网整体真正构造高斯面,或者说不真正构造线网高斯面。
    算法1的第7步包含本发明的重点,其“在线网j的高斯面上随机取点r(0)”便是使用本发明面向集成电路互连电容提取的线网高斯面采样方法(即步骤S701至S715)获得线网高斯面上采样点的方法。
    算法1的其他步骤都是现有技术,与进行单个导体的电容提取算法一样,细节可参见发明人2013年在国际期刊IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems上发表的论文“RWCap:A floating random walk solver for3-D capacitance extraction of VLSI interconnects”。
    本发明面向集成电路线网电容提取的虚拟高斯面采样方法及系统,特别针对包含超过一块导体的线网,实现在包围该线网的高斯面(称为“线网高斯面”)上进行随机行走采样的过程。该方法并不真正在几何上构造线网高斯面,而是在组成线网各个导体块的高斯面(称为“块高斯面”)的合集上进行随机采样,然后通过拒绝采样(rejection sampling)达到直接在线网高斯面上采样的效果。相比于通过几何运算求出所有块高斯面的包络、从而得到线网高斯面的方法,本方法运算简 单、效率高,且能适应基于方差约减的快速随机行走方法。避免了通过复杂的三维几何运算求所有块高斯面的包络,效率高且易于实现。

    关于本文
    本文标题:面向集成电路互连电容提取的线网高斯面采样方法及系统.pdf
    链接地址://www.4mum.com.cn/p-6185434.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 快三全能必中计划软件怎么注册 王者传奇官网下载 金沙棋牌最新官方下载 飞艇7码滚雪球在线计划 澳洲幸运5的规律 西洋棋棋子样子 上海时时乐乐 开心农场小游戏种菜下载 7星彩预测 pk10计划软件手机版 千里马计划软件ios 甘肃十一选五开奖号码 抖音的赚钱规则 235棋牌游戏中心下载 众发娱乐可以赚钱吗 陕西快乐10开奖走势图