王小港[1]2001年在《遗传算法在VLSI设计自动化中的应用研究》文中研究指明遗传算法不仅仅是一种单纯的优化算法，而是一种以进化思想为基础的一般方法，对于复杂问题的解决是一个有力工具。遗传算法是概率性全局收敛的，具有并行性搜索、全局性优化、算法设计简单、操作性强、效率高以及不依赖于问题的模型等特性。近些年来遗传算法作为一种自适应启发式概率性迭代式全局搜索算法，在许多方面得到了应用。 本文在详细分析了遗传算法的原理的基础上，着重研究了VLSI的划分、布局、布线、测试生成以及测试集的极小化等优化问题，并设计了相应的遗传算法。论文的主要工作和创新有： 1．简单回顾了遗传算法的发展历程，并介绍了遗传算法的最新发展。对遗传算法的选择、交叉、变异等遗传算子进行了讨论，给出了遗传算法的结构以及遗传算法设计的重点，详细阐述了遗传算法的积木块理论，模式定理和NFL（No Free Lunch）原理。 2．分析了VLSI电路划分的性质和特点，提出了基于遗传算法的VLSI电路的划分方法，设计了适用于电路划分的遗传算法，该算法不仅可以完成电路的二划分和K划分问题，还能对有面积约束的多目标电路划分问题进行优化，得到了比较满意的结果。 3．研究了布局和布图规划问题，提出了一种新的基于遗传算法的VLSI布图规划方法。在染色体的表达中，对软模块的不同形状和硬模块的布局方向进行了编码，并设计了有效的启发式解码方法进行解码。算法能完成对布局面积和模块连线总长度同时进行优化的多目标优化问题，其结果优于现有算法。 4．研究了多层通道布线问题，提出了一种基于通孔数最小化的多层通道布线算法。算法采用非预留层模型，首先根据线网之间的位置关系利用遗传算法将各线网合理地分配到对应的布线层中去，然后利用遗传算法得到相关有线层中线网的最佳布线顺序向量，最后根据得到的顺序向量利用“沉积法”将各线网布于合理的通道上。该算法克服了传统通孔优化算法中原始布线对优化结果的不利影响，使通孔的优化达到很好的效果，其结果优于已有算法。 5．讨论了组合逻辑电路的故障诊断的方法，故障的类型。并在详细分析伪穷举算法的基础上，给出了基于遗传算法的适用于伪穷举算法的分块算法（DGP-GA）和着色方法（MCR-GA）。可以大大减少电路完全测试所需的测试矢量的数目，对加速测试过程和减小测试代价有积极的意义。 6．讨论了测试集的优化问题，通过对编码方式的讨论，评估函数的设计，分别给出了面向测试矢量的测试集优化遗传算法和面向故障的测试集优化算法，较好的解决了测试矢量集最小化问题。
孙宁[2]2006年在《人工免疫优化算法及其应用研究》文中提出优化问题大量存在于科学研究和工程应用中的各个领域,进行最优化方法的研究具有重要的理论意义和实用价值。传统优化方法存在着种种不足,在当今大规模生产中的应用受到限制。多学科的交叉研究为解决优化问题提供了新的思路,以生物智能或自然现象为基础的新型智能优化算法在研究与应用中表现出优异的性能,现代智能算法也成为人工智能领域一个新的研究热点。人工免疫优化算法是模仿生物免疫系统功能的一种智能方法,提供了类似生物免疫系统的噪声忍耐、无教师学习、自组织、记忆等进化学习机理,为解决复杂的分布式问题提供了新的方案,相比其它智能优化算法具有寻优成功率高、个体多样性好的特点。本文在分析人工免疫优化算法原理与特点并对比人工免疫优化算法与其它智能优化算法的基础上,总结人工免疫优化算法存在的不足,进行算法改进研究以增强算法的寻优搜索能力,并将改进算法应用于数字系统设计和故障诊断中的两个实际问题,验证算法的有效性和实用价值。本文的主要研究内容和成果如下:1.分析基本人工免疫优化算法变异算子搜索能力的不足,将多变异率的改进二进制编码变异策略引入人工免疫算法,并利用混沌模型实现算法个体编码中高有效位部分和低有效位部分的自适应设定,提出了基于混沌序列的多变异率人工免疫算法。仿真结果验证了改进算法具有更好的全局搜索性能和更快的收敛速度。2.研究基本人工免疫优化算法的局部搜索机制,针对其缺乏信息交换、个体社会性不好的缺点,为基本人工免疫优化算法的局部搜索引入信息交换的手段,并提出了算法参数的动态更新机制和自适应更新机制,实现了参数自适应更新的引导型人工免疫算法。仿真结果表明,采用参数更新机制的引导型人工免疫算法不仅有效地加快了算法的收敛速度,而且可以使算法以较大概率在预先指定的迭代次数范围内收敛,更具实用价值。3.在研究离散微粒群算法原理的基础上,讨论应用离散微粒群算法作为人工免疫优化算法局部搜索算子的实现方法,提出了离散微粒群算法与人工免疫优化算法综合应用的混合优化算法。仿真结果表明,实现的混合算法不仅大大减少了算法收敛所需的迭代次数,而且可以有效地提高算法的寻优
符宁[3]2002年在《用于VLSI布局的计算智能方法研究》文中进行了进一步梳理作为电子信息产业发展的核心和基础，集成电路技术正迅速地向着更高集成度、超小型化、高性能、高可靠性的方向发展，在VLSI设计流程中，物理设计是既关键又复杂的一步，而布局又是物理设计中最重要的一步，布局的诸多问题都是NP完全问题，需要启发式算法来求解。随着VLSI集成度的迅猛提高，寻求有效的优化算法应用于布局问题，以提高布局质量和速度已成为当务之急。 本文主要研究用于解决VLSI布局问题的计算智能方法，在总结概括了当前主要的布局优化算法的基础上，引入了禁忌搜索算法和模糊禁忌搜索算法，并用于求解VLSI布局问题。 禁忌搜索算法是一种可广泛用于各种优化问题的思想框架。许多文献也都证明它在时间和性能上扰于其他一些算法，在诸多组合优化领域中显示出了强大的寻优能力，并以其较高的求解质量和效率得到人们越来越多的青睐。本文将其引入，用以解决VLSI门阵列布局问题，与遗传算法比较，在求解质量和速度上都取得了优于遗传算法的结果。 然而，禁忌搜索算法的求解性能严重地依赖于算法的一些参数，它们又大都在算法运行中起着指导算法前进的作用。这些参数都是凭经验选取的，而且这些参数在算法运行过程中始终保持不变，这样的策略在很多情况下都不是很有效。因此，我们发展了一种新的算法——模糊禁忌搜索，它引入一个模糊系统来控制禁忌搜索算法的参数取值。在针对VLSI门阵列布局问题的应用中，用当前解的优劣程度和非优化迭代的次数来控制邻域的产生，计算机仿真结果表明该算法具有很好的寻优性能。
高久顼[4]2017年在《VLSI物理设计中的约束传播性研究》文中研究表明随着复杂的半导体技术的快速发展,电路集成度不断提高,芯片内晶体管的数目日益增多。在超大规模集成电路(VLSI)设计中,一片芯片上能够集成多达十几亿甚至几十亿个晶体管,因此集成电路的设计也越来越困难。物理设计是与产品直接相关的一个设计过程,在VLSI设计中有着重要的作用,分为电路划分、布图规划、布局及布线等阶段。物理设计的好坏,直接影响着设计周期长短,成本高低以及质量高低。本文首先介绍了电路划分的数学模型以及KL算法、FM算法、hMetis算法,布图规划/布局的数学模型以及模拟退火算法和遗传算法,布线的数学模型以及串行布线和拆线重布算法,然后介绍了约束的表示方法以及方向约束、边界约束和邻接约束的定义。本文是对约束的传播方法进行研究,提出VLSI物理设计中约束的传播性研究。首先通过MD5算法将数字签名转化为电路约束。然后将得到的约束通过约束嵌入算法添加到电路文件中,分析约束在不同阶段对线长的影响。其次使用约束提取算法对布线后的电路文件进行约束提取,并与原始约束进行比较,分析约束能够在物理设计过程中传播的概率。最后对电路进行优化,并对优化后的电路的线长和约束的改变率进行分析。通过约束对VLSI物理设计中布局阶段和布线阶段的影响,研究约束的传播过程。实验结果表明,在布局阶段和布线阶段,嵌入约束后电路的半周长(HPWL)和线长(WL)都增加,并且对于大部分电路而言,嵌入约束个数多的电路的HPWL和WL都较长。不同的约束对HPWL和WL影响也不相同,其中,边界约束对WL有着非常大的影响。对嵌入约束的电路进行优化后,电路的HPWL和WL有一定程度上的减少,但是线长的减少是以牺牲约束为代价的。在优化前,约束能够在布局布线中传播的概率为100%,而优化后,概率降为50%。
李康[5]2009年在《VLSI物理设计中布局及有约束的布局优化》文中研究表明随着微电子技术的高速发展,VLSI的集成度急剧增加,特征尺寸迅速下降至深亚微米甚至纳米级,导致VLSI物理设计阶段的任务更重,难度更大。布图规划和布局是VLSI物理设计中的早期阶段,其结果不但直接影响VLSI的整体设计质量,而且会对后续的布线设计产生决定性的影响。因而,布图规划和布局已成为VLSI设计的关键问题之一。本文在分析影响VLSI布图规划和布局相关因素的基础上,从布图规划及布局的表示法、布局算法中所采用的数据结构、布图规划的结构分析以及模块放置的优化方法等方面,对布局算法的优化、有约束的布图规划和布局、布线优化和标准单元模式布局等问题作了一些探索性研究,主要工作和取得的成果概括如下:1.在布局算法上,详细研究了布局算法中所采用的辅助数据结构和模块放置方法对算法运行效率的影响,提出了角轮廓结构(Corner-Contour)数据结构,证明其从左至右阶梯下降的重要特性,并结合O-tree和Single-Sequence(简称SS)表示法编码各自的特性,简化并优化了基于这两种表示法的布局算法;提出凹轮廓(Concave- Contour)数据结构,并用其实现有固定外框约束的布局;在布局算法中考虑矩形外框对布局的影响,以矩形外框对角线为准线引导模块放置,加快了布局算法的收敛;利用边界约束条件,在不执行模块放置程序的条件下快速评价布局编码,以缩小搜索范围,加快布局算法的收敛。2.在有约束的布局方面,详细研究了SS表示法的编码特性,提出并证明了基于该表示法的边界约束的充要条件,给出了边界约束条件的数字串表达式并用算法实现。对SS表示法边界约束条件的研究进一步完善了这种新式表示法。3.在布线优化方面,详细研究了SS表示法与对应布图规划之间的关系,提出基于该表示法的边界约束对布图规划进行分层结构分析、通过引导模块放置以优化布线结构的方法,不但使SS编码对应的布图规划图形结构更加清晰,而且实现了布局对布线的指导作用和基于布线优化的布局;基于B*-tree编码,用插入虚拟模块的方法实现了紧致型布局中任意模块对的连通,解决了布线中局部模块布通性的问题。4.在标准单元布局方面,从全新的角度考虑标准单元布局的优化问题,提出了标准单元方式下的布局表示法-Ordered Single Chain Tree(简称OSCT)。OSCT表示法编码以数字串编码形式表示标准单元布局的拓扑结构,易于实现标准单元布局的边界约束和布线优化,并能够借助现代随机优化算法对标准单元布局进行更大范围的、更加精确的优化计算。
李静[6]2004年在《电源/地线线网的拓扑优化设计及进化蚁群算法在VLSI多端线网绕障布线中的应用》文中认为在VLSI布局布线中,电源网和地线网络的设计非常重要。电源和地线网布线方法的可适应性及优化结果,都将影响整个芯片的电性能和面积的优化。目前,在设计灵活的BBL布图模式下,对于电源、地线线网的拓扑设计而言,虽然已有一些研究结果出现,但基于噪声分布和可靠性约束的性能拓扑优化仍少有论述。实际上,若在拓扑优化阶段没有考虑相关性能约束,就不免有些“先天不足”,即不能充分利用现有条件实现电路性能上的进一步提高。在本文中,我们基于对噪声均匀分布及芯片内模块工作可靠性的客观分析,提出了一种考虑了以上性能并能对电源网、地网拓扑同时进行优化设计的改进算法。实验结果证明在布线面积增量不大的情况下,该算法可获得较好的噪声均匀分布及模块工作可靠特性。另外,随着VLSI的工艺向超深亚微米的推进,物理设计中的布线问题(无论是非NP问题、NP完全问题和NP困难问题),由于问题规模的急剧增大,都迫切需要更有效的优化算法解决方案。在本文中,我们在本教研室原来研究的基础上,就物理设计中BBL模式下典型的多端线网绕障碍布线问题,提出了一种基于生物仿生特性的蚁群算法,通过选择适当的图模型表述,该算法可采用蚁群任务调度策略,模仿蚁群的协同学习机制,来求解多端线网绕障碍的布线问题,并能给出较优的解。同样,我们给出实例证明算法的有效性。
刘和周[7]2003年在《改进的进化蚁群算法在超深亚微米VLSI电路绕障布线问题中的应用》文中指出自从IC诞生以来，IC芯片的发展基本上遵循了摩尔定律，目前已经突破100nm大关，相应的系统规模的扩大，使得IC物理设计中的很多困难日益NP问题日益棘手。此外IC本身的物理设计能力一直落后同时代的制造工艺能力，于是就造成了下面的这种局面：现有EDA工具难以应付复杂度呈指数增长的诸多VLSI物理设计难题，也缺乏对深亚微米工艺下一系列新问题（如：功率危机、复杂度危机和互连线危机）的考虑。另一方面，在计算智能领域，各种优化技术的蓬勃发展，为解决非NP和NP复杂度的问题提供了方法和启示。本文正是在这样的背景下，基于四川省科技厅基金项目，研究计算智能方法在深亚微米工艺下性能驱动VLSI生产工序中关键环节——物理设计中的应用。在目前IC的工艺条件下，很多VLSI的物理设计中的布线问题（无论是非NP问题、NP完全问题和NP困难问题），由于问题规模的急剧增大，都迫切需要更有效的优化方法来解决。本文我们首先就物理设计中BBL模式下典型的两端绕障碍布线问题，提出了解决不同条件下实际问题的两种模型，即非均匀网格和无网格的两种模型，使问题的复杂度大大下降。然后，介绍了一种兼具生物仿生特性的蚁群和遗传算法特点的进化蚁群算法，并对该算法模仿蚁群的协同学习机制，以及遗传算法的优秀群体中的个体之间信息交换的策略进行了阐述，接着探讨了该算法在总体布线和斯坦纳树问题中的应用。接下来把该算法用于解决两端绕障碍的布局布线问题，同时给出了实验仿真以及在此基础上分析的结果。最后还探讨了两端绕障碍布线问题的模型在多端线网布线问题、总体布线问题以及最小费用问题中应用的可行性问题。
李坤龙[8]2016年在《布图规划约束对VLSI设计性能的影响》文中进行了进一步梳理随着现代芯片工艺技术的飞速发展,片上系统(SoC:System-on-Chip)设计已成为主流,单一芯片所包含的模块越来越多,设计呈现出复杂性。通过SoC的设计方法,降低了芯片的设计成本,优化了芯片面积,大大提高了芯片的整体性能。物理设计在超大规模集成电路中起着至关重要的作用,目前的VLSI(Very large Scale Integration)物理设计中广泛采用层次化的分级设计方法,一般分为划分、布图规划、布局及布线等阶段。布图规划是VLSI电路物理设计中的重要的一环,尤其是在片上系统设计中,布图规划的好坏往往对布局、布线的结果甚至最终芯片的性能有很大的影响。本文介绍了超大规模集成电路物理设计中各个阶段的相关算法,包括划分算法、布图规划表示法、布局算法以及布线算法,并且对布图规划约束做了简单的介绍,其中包括对齐约束、邻接约束、预置约束、边界约束和聚类约束,提出了布图规划约束嵌入算法。通过对IBM-HB+Benchmark嵌入布图规划约束,研究了布图规划约束对VLSI物理设计中各个阶段的影响。前置嵌入布图规划约束的实验表明,嵌入约束后芯片设计面积、布线长和空白占比有一定程度上的减少,运行时间基本维持不变。对布局阶段的对比结果分析可知,嵌入约束造成了电路中半周长和算法运行时间一定程度的增加;在布线阶段的对比结果分析可知,嵌入约束造成了线长和运行时间明显的增加。后置嵌入布图规划约束的实验表明,嵌入不同的约束对物理设计的布局和布线影响不同,并且嵌入约束的模块比例不同对电路设计性能的影响也是不同的,随着嵌入约束模块比例的增加,半周长也有一定程度的增加。
杨波[9]2004年在《VLSI电路非曼哈顿布局和改进蚁群算法的初步研究》文中研究指明随着VLSI电路中互连线特征尺寸的不断减小(Intel和AMD在2003年都已经推出了采用0.09微米工艺的处理器),许多电子/电路问题变得非常突出,例如电路连线之间的噪声串扰、电迁移、电路发热、连线延迟等等。而电路连线延迟和发热是其中影响较大的问题,它们可能会制约整个VLSI芯片的工作速度。因此,连线延迟将成为电路延时的主要部份,线间串扰也将成为影响电路信号完整性的重要因素,在深亚微米电路设计中连线本身也不能再当作集总参量处理。不言而喻,随着深亚微米工艺的发展,集成电路设计将从以器件为中心的设计模式,逐步过渡到器件和连线并重,和以互连为中心的设计模式。为了解决这些问题,国内外研究人员提出了很多的改良方法,但这些方法一直建立在水平/垂直的布线模式(即所谓的Manhattan模式)上。如Sunil P. Khatri等提出的GSVS串扰消除布线模型[3]。该模型的核心思想就是将传输高频信号的线路之间用电源线或地线进行分隔。这种方法确实能对比较关键的线网起到一定的保护作用,比如时钟树线网。但很明显的弊端就是它将导致连线过长,芯片面积增大。2001年,Cadence、TOSHIBA、ARM、Applied Materials等涵盖了IC工具、设计、生产的着名厂商组建了推动所谓的X结构发展的开放论坛(X- Initiative Open Forum ,XIOF),提出了称为X结构的非曼哈顿IC布线模式。它在允许采用传统的水平/垂直的布线方式的同时,还允许采用45°对角布线。与传统的曼哈顿布线方式相比,新的X结构布线方式可以将连线总长缩短超过20%,将通孔(via)数减少30%以上。很显然,由于连线延迟与连线长度、通孔数目成正比,<WP=5>采用X结构可望有效的降低连线延迟。同样由于连线总长的减少,芯片的总面积也会相应减少,而性能有10%的提高,功耗降低了20%。虽然X结构在下一代纳米级IC领域有可观的应用前景,但是到目前为止,研究开发人员主要关注的方向依然只是X结构的布线方面。例如,ATMC实现的第一块90纳米的X结构芯片实际上只是在布线的金属层上增加了两个方向(即45度和135度)的布线层,并不是一块完全的X结构IC。在电路模块层以及开始的几个布线层仍然是曼哈顿结构,只是在最后的两到叁层金属上才用X结构。显然,要完全利用非曼哈顿结构来提高VLSI芯片的性能,还有很多障碍要克服。比如无网格的非曼哈顿布线模式、任意方向的布线模式、X结构的布图布局规划、X结构的布局数据结构几何表示方法等等。基于上述理由,本文尝试对非曼哈顿的VLSI布局做初步的研究,并提出了一种用以表示非曼哈顿布局的表示方法和与之对应的布局算法,在理论上证明了布局的表示法与布局存在的对应关系, 同时应用遗传算法来迭代改善非曼哈顿布局,以实验证明了该非曼哈顿布局的表示方法和布局算法的正确性与有效性。同时,本文围绕绕障布线问题,提出了一种新的增强蚁群算法(EACS), 通过启发蚂蚁的一种有效策略,加快了基本蚁群算法的求解速度。并提出了一种配合增强蚁群算法解的冗余消除算法(PEAK-CUT 算法),通过对EACS算法解作适当的后处理,达到了使该算法快速收敛的目的。
张徐亮[10]2001年在《一种动态数据结构——池及其在VLSI电路布局设计中的应用》文中研究说明本文提出一个新的数据结构概念——动态数据结构。基于这个概念，本文实现了一种新的数据结构——池及其在一维和二维时的情况。本文同时对这种新的数据结构在VLSI电路布局设计中的应用和在打印机任务调度中的应用进行了研究。 本文的主要贡献概括如下： 1.本文讨论了各种计算机应用中的动态数据处理要求，之后提出了动 态数据结构的概念。根据这一新概念，本文建议了一种新的数据结 构——池，它能对数据进行动态处理（例如，数据的表示，查找， 合并，排序和存储等等）。 2.本文研究了一维池和二维池的实现，对一维池和二维池的顺序存 取、基于周期机制和基于触发机制的动态秩序维持程序进行了研 究，并定义了一维池和二维池的基本运算。 3.本文成功地将池和遗传算法相结合，形成改进的基于池的遗传算法 （PGA），以作为池的一种灵活应用。然后，将基于池的遗传算法 （PGA）用于解决门阵列布局设计。对门阵列布局算例的计算机仿 搞要 真结果表明使用基于池的遗传算法汀GA）能够获得比传统遗传算 法（GA）更好的结果。 4．本文将快速进化规划算法（FEP）用于同样的门阵列布局算例，也 取得了满意的结果。 5．为减小通道布线中线网间的串扰，本文提出一个基于扰动的算法。 我们将此算法运用到若干benchlnn例子上去，并和已知的一些结 果进行了比较，结果表明我们建议的基于扰动的算法能够获得比文 甲 献p7习21更优的性能。 动态数据结构一池是一种普适的工具，可以用来解决其他计算机科学领域中的问题，比如进程管理、并行计算中的任务分配等。作为一个具体的应用，本文将二维池应用到打印机任务调度中，仿真结果表明算法能解决繁重的计算机排队打印问题。
参考文献：
[1]. 遗传算法在VLSI设计自动化中的应用研究[D]. 王小港. 中国科学院上海冶金研究所. 2001
[2]. 人工免疫优化算法及其应用研究[D]. 孙宁. 哈尔滨工业大学. 2006
[3]. 用于VLSI布局的计算智能方法研究[D]. 符宁. 电子科技大学. 2002
[4]. VLSI物理设计中的约束传播性研究[D]. 高久顼. 青岛理工大学. 2017
[5]. VLSI物理设计中布局及有约束的布局优化[D]. 李康. 电子科技大学. 2009
[6]. 电源/地线线网的拓扑优化设计及进化蚁群算法在VLSI多端线网绕障布线中的应用[D]. 李静. 电子科技大学. 2004
[7]. 改进的进化蚁群算法在超深亚微米VLSI电路绕障布线问题中的应用[D]. 刘和周. 电子科技大学. 2003
[8]. 布图规划约束对VLSI设计性能的影响[D]. 李坤龙. 青岛理工大学. 2016
[9]. VLSI电路非曼哈顿布局和改进蚁群算法的初步研究[D]. 杨波. 电子科技大学. 2004
[10]. 一种动态数据结构——池及其在VLSI电路布局设计中的应用[D]. 张徐亮. 电子科技大学. 2001