电源线/地线网络开路电阻单故障分析方法

随着集成电路工艺进入纳米时代,供电电压波动严重影响电路性能.制造中通孔对位不准,及运行中铜导线电迁移现象.都会在电源线/地线网络(P/G网)中产生大量潜在的开路故障,并使供电电压发生明显波动.为了在测试中对大量的开路故障进行快速测试.迫切需要提高故障分析的算法效率.为此,首次提出了单故障连续过松弛算法(SD-SOR),对发生单开路电阻故障的P/G网节点电压分布进行快速分析.基于无故障P.G网节点电压分布,SD-SORR对开路电阻周围受故障影响比较大的少数节点进行松弛计算.与传统的全局SOR方法相比,SD-SOR具有如下3个优点:1)局部松弛.由于电路中只有一个电阻口发生开路故障.SD-SOR不是采用全局电路节点的顺序松弛方法,而是采用从故障q所连的节点不断向周围节点进行松弛的波状松弛方法,当某些节点的IR电压降变化小于一个极小的设定值时.这些节点就不再向外进行松弛计算.2)高效.与传统的全局SOR方法相比.SD-SOR不仅参与松弛的节点非常少.而且松弛次数也有明显减少.3)高精度.与传统的全局SOR方法相比,由于距离故障比较远,电路中绝大多数节点电压变化非常小,所以SD-SOR只需对距离故障比较近的节点进行松弛计算,就能够保持较高的分析精度.大量的实验数据表明:与预条件全局SOR求解方法相比,SD-SOR在保持较高精度(误差小于0.95%)的前提下,速度可以提高57倍.     

局部松弛电路理论及其在电热分析中的应用

在复杂度日益增高的高性能集成电路设计中,高效的性能分析是一项重要的设计内容,其中由电源线/地线网络(P/G)分析与芯片热分析构成的电热分析则是目前研究的热点问题.针对电热分析方程所具有的大规模稀疏(电导或热导)系数矩阵,根据该系数矩阵所具有的对称正定严格对角占优等特性,本文从理论上证明了电热分析具有局部性,在相同的截断误差限松弛结束条件下,局部松弛和全局松弛具有相同的松弛精度.基于局部松弛理论,本文提出了一个高效实用的局部过松弛(SOR)算法(LSOR2),并在文章最后将其用于如下的3个具体的电热分析问题研究:(1)P/G网中的过压降点电压变化统计分析;(2)3D热分析中的过热点温度变化统计分析;(3)单开路故障下的P/G网快速分析.实验数据表明:与全局SOR算法相比,在保证精度的前提下,LSOR2算法可以将电热分析的求解速度提高1-2个数量级.     

片上P/G网求解算法及其GPU上的并行化

为了得到片上电源线/地线网络(P/G网)快速而准确的求解算法,根据结构化供电网的局部性效应,重新分析了连续过松弛迭代法(SOR)和变向隐含迭代法(ADI)在P/G网中的求解效率及并行性,提出了利于GPU加速的并行算法:G_RBSOR和G_ADI.它们均采用规则的数据结构,以利于GPU并行读写数据,并采用合并归约来并行计算迭代结束标志位.为了避免GPU计算的数据冲突,G_RBSOR算法采用棋盘格方式对电路节点进行红黑分类,并对红黑节点进行交错松弛.实验结果表明,在不损失精度的前提下,与各自对应的CPU串行算法相比,G_RBSOR和G_ADI算法均取得了超过50倍的加速效果;与高效的P/G分析串行求解算法ICCG相比,也取得了超过5倍的加速效果.     

利于GPU计算具有线性并行度的P/G网SOR求解算法

近年来电子设计自动化(EDA)研究人员尝试利用图形处理器(graphic processing unit,GPU)提供的高性能计算能力对IC参数分析进行加速研究.为了利用GPU进行电源线/地线网络(power/ground network,P/G网)快速分析,设计了一种基于经典的连续过松弛(successive over-relaxation,SOR)算法的高效P/G网分析并行算法.基于GPU并行计算加速原理,此算法进行了如下改进:1)采用红-黑次序的松弛策略.将所有的节点分为红黑两类,红色节点的所有邻点只有黑色节点、黑色节点的所有邻点只有红色节点,红色节点与黑色节点交替松弛,保证了GPU并行计算中的数据一致性.对于具有N个节点的P/G网而言,一次红色节点或黑色节点松弛可以同时对N/2个节点进行松弛操作,即理论上可以同时启动N/2个并行线程.2)优化数据结构.实现了对数据空间的合并访问,以保证对GPU全局存储空间的最优访问.3)在共享存储器内通过并行归约对松弛标记进行快速统计,同时利用zero-copy技术进行松弛标记的快速拷贝,以快速决定是否继续松弛.大量的实验结果表明:与单线程的CPU程序相比,此算法的加速倍数随GPU所提供物理线程的数目增加而线性增加,可以获得最大242倍的加速效果,是目前EDA研究领域中加速效果最好的GPU算法.     

直角多边形布图区域内的二次布局算法

提出了一种直角多边形布图区域内的基于动态划分的二次布局算法——DPRR．通过在传统的二次布局算法中引入一种新的圆盘划分和分布约束生成策略,解决了直角多边形布图区域里的单元布局问题,并且由于该算法在迭代优化过程中动态地划分电路并生成分布约束,且不限制单元在布图区域的不同部分间自由移动,所以它可以在一定程度上避免优化过程中出现的“局部最优”,从而达到更高的布局质量．对一些电路实例的测试和比较结果也证明DPRR是一种高效优良的布局算法,并且它十分适用于解决非矩形的直角多边形布图区域内的标准单元布局问题．     

基于部分随机行走的电源线/地线(P/G)网络快速求解方法

介绍一种基于随机行走方法与松弛迭代(SOR)算法相结合的快速电源网络求解方法，它先将P／G网分为若干块，然后用简化的随机行走方法求取电路块边界结点的电压，最后采用松弛迭代算法求出电路块内部结点的电压．同时还给出了一种电路块从对角顶点向中央求解的策略，并将此方法推广到采用RLC瞬态网络的求解．大量的实验数据表明，受限于P／G网供电PAD的数目较少这一现实，随机行走方法的效率比较低，在此情形下，该方法比随机行走方法快20倍．     

一种考虑集中约束的平面布图规划算法

在超大规模集成电路(VLSI)物理设计中,将更多约束实现放在更高的设计阶段考虑可以有效的加速设计收敛,减少设计时间.文中针对宏模块平面布图规划中约束的实现方法进行了分析和研究,基于B tree表示方法提出一种考虑集中约束(clustering constraints)的平面布图规划算法,针对布图规划中集中约束的实现取得了较好效果.     

基于Single—Sequence布图规划线长约束问题的研究

布图规划是VLSI设计中非常重要的步骤。Single—Sequenc是一种非常有用的表示布图的编码方法。在实际的布图规划中,由于线长对芯片性能有较大的影响,因此为了使芯片的整体性能达到最优,考虑线长因素,使线长尽可能短。该论文提出了在用模拟退火算法寻求最优布图的同时,通过对算法加以改进,考虑线长约束条件,有效地解决了布图规划的线长约束问题。     

一种考虑电压岛边界约束的多电压布图算法

多电压设计(multiple supply voltage,MSV)是降低SoC功耗的有效方法之一.为便于电压岛供电引脚的放置,提出了一种考虑电压岛边界约束的多电压布图算法.首先,基于切分树表示的布图解特点,提出一种边界检查算法快速确定所有模块的边界信息.其次,以优化功耗为目标采用改进动态规划方法进行多电压分配并构建电压岛.最后,以模拟退火算法作为搜索引擎对芯片的面积、线长和功耗进行协同优化.为减少SA迭代次数,采用了一个两阶段的降温策略.对GSRC电路的实验结果表明,该算法可获得满足边界约束的多电压布图,且和不考虑边界约束时相比,仅在功耗上平均增加5.2％.     

门阵列布局与全局布线合并算法

本文提出了一种门阵列的布局与全局布线的合并算法(简称合并算法)。合并算法将布局和全局布线两过程合为一体,在布局的过程中考虑全局布线,同时利用布线信息指导布局,从而有效地利用了布局和全局布线信息,以较少的代价获得全局优化结果。合并算法成功地克服了传统的布局和全局布线分阶段设计的布图设计模式所固有的缺点。     

基于Single-Sequence布图规划边界约束问题的研究

布图规划是VLSI设计中非常重要的步骤.在计算机辅助设计中,布图被表示成编码以使其容易被计算机处理.Single-Sequence就是一种非常有用的表示布图的编码方法.一个布图中,一些模块如输入输出模块,必须放置在芯片的边界处,这种限制被称为边界约束.本论文提出了用模拟退火算法寻求最优布圈的方法,有效地解决了布图规划的边界约束问题.     

VLSI布局结构表示研究进展

超大规模集成电路技术的迅猛发展迫切需要高性能CAD工具——电子设计自动化软件工具的支持．布局是布图设计中一个极为重要的环节．目前,在深亚微米、超深亚微米工艺下的超大规模、甚大规模集成电路设计中,布局结果的好坏直接影响整个布图设计,因此如何高效地表示布局结构,从而提高布局质量成为布图设计中的一个国际上的研究热点．文中介绍并分析了当前国内外比较流行的布局结构的表示方法研究工作的进展情况．     

求解约束优化问题的改进自适应mu约束处理技术

针对当前的约束处理技术存在易陷入局部最优解、难以满足等式约束和多控制参数的问题,在mu约束处理技术的基础上,以梯度下降法和多目标拥挤距离为理论依据,设计反映种群约束违反度分布信息的omega参数,它可以自适应地调节约束违反度阈值mu的松弛进而有效地解决约束问题.此外,改进了mu阈值比较准则以提高种群的多样性.经对CEC2017的标准约束优化问题(Constraint optimization problems,COP)进行求解,并与其他先进算法相比较,结果表明,改进的mu约束处理技术能够高效地处理含等式约束的COP.     

供电网工况参数SCADA系统设计

建立供电网工况参数数据采集和监控系统(SCADA),对于保证供电网的供电质量具有重要的意义.供电网工况参数主要有电压,电流、功率、功率因数等参数.本文设计的供电网工况参数SCADA系统在设计中采用了鼎升力创公司生产的电量采集模块R-8073N,监控软件采用Delphi 7设计.     

电缆虚拟布线中的物理特性分析与布局设计技术

针对机电产品中电缆布局设计中没有考虑物理特性导致电缆取样长度不准确的问题,提出了虚拟环境中基于物理特性的电缆布局设计方法.首先使用非均匀三次B样条曲线拟合电缆中心线,并考虑电缆的弯曲半径,使电缆在拐角处的转弯半径符合其物理特性;然后采用能量优化造型法得到电缆调整过程中的静态位姿,并利用定长约束下搜索算法对求解结果进行优化;最后提出利用局部曲率约束算法控制电缆的弯曲变形,使电缆布局时更符合其弯曲特性.由于该方法考虑了柔性电缆的物理特性,提高了电缆布局结果形态的真实性和取样长度的准确性.最后设计并开发了基于物理特性的电缆布局设计原型系统,并通过实例验证了文中算法的可行性.     

EDA软件中的布局优化算法分析及其改进

在深亚微米、超深亚微米工艺水平下的超大规模集成电路设计需要高性能的EDA(电子设计自动化,ElectricalDesignAutomation)软件的支持。与物理设计相关的布图设计中,布局设计是一个极为重要的环节。该文以FPGA(现场可编程门电路,FieldProgrammableGateArray)为例,分析和介绍了EDA中的布局算法,然后利用遗传模拟退火算法对原算法提出了改进,并在文章中介绍了改进后的算法。     

基于新约束图模型的布图规划和布局算法

布图规划和布局构形的表示是基于随机优化方法的布图规划和布局算法的核心问题.针对Non-slicing结构的布图规划和布局,提出了一种新的基于约束图表示的模型.基于该模型及其性质,可以得到近似O(n)时间复杂度的有效的布局算法.通过引入变形网格的假设,得到了一种新的更加精确的Non-Slicing结构的表示模型:梯形网格模型.其空间复杂度为n(3+lg[n]),时间复杂度为O(n),解空间规模为n!2^3n-7.已经证明,梯形网格模型可以表示所有的Slicing结构的布局,同时又可以有效地表示Non-Slicing结构的布局,而时间复杂度与Slicing表示相同.实验结果表明,该表示优于刚刚发表的O-tree模型.梯形网格模型是一种拓扑模型,而O-tree的表示依赖于模块的尺寸,因而梯形网格能更有效地处理含有软模块的的布图规划问题.     

供电网工况参数SCADA系统设计

建立供电网工况参数数据采集和监控系统(SCADA),对于保证供电网的供电质量具有重要的意义。供电网工况参数主要有电压、电流、功率、功率因数等参数。本文设计的供电网工况参数SCADA系统在设计中采用了鼎升力创公司生产的电量采集模块R-8073N,监控软件采用Delphi7设计。     

基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法

Steiner最小树是超大规模集成电路中布线阶段的最佳模型,进一步考虑能够有效防止信号失真的电压转换速率(Slew)约束这一个更为贴近实际芯片设计模型和更具线长优化能力的X结构,首次提出基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法.首先,为了避免频繁的Slew约束计算,提出了高效的预处理策略,并且提出一种能够有效考虑Slew约束的针对性的惩罚机制.其次,为了能够有效求解该离散问题,基于遗传算子重新设计了粒子群优化算法的离散更新机制,并提出一种更适合遗传算子的引脚对编码方式.然后,为了进一步优化布线树的长度,提出一种有效的精炼策略.最终,提出一种混合修正策略以完全满足Slew约束.实验表明,所提算法可完全满足电压转换速率约束并取得同类工作中最佳的布线结果.     

一种基于SLP的异构NoC布图优化算法

随着超大规模集成电路的飞速发展,越来越多的IP核被集成到片上网络(Network-on-Chip,NoC)上,而片上网络是一种以通信为中心的片上互连结构,与传统总线型片上系统(System on Chip,SoC)相比具有低功耗、高宽带的显著优势。笔者将工业工程中系统布局设计(Systematic Layout Planning,SLP)方法与遗传算法相结合,提出一种系统布图优化算法。相对于传统的布图算法,提出的系统布图优化算法不仅具有更优的搜索能力,而且可定性与定量地优化布图方案,为片上网络布图规划提供了一种全新思路。实验结果表明,随着IP核之间平均通信量的增加功耗降低幅度逐渐减小,当IP核之间的平均核通信量在1 000 Mb/s以内时,总功耗平均降低了40.51%。