刘燚灵[1]2003年在《基于序列对的禁忌搜索算法在VLSI BBL布局中的应用》文中进行了进一步梳理当前集电路产业已经突破100nm工艺大关，基于90纳米工艺的CPU处理器将于今年内推出，整个产业向深亚微米工艺不断推进。现有EDA工具却明显滞后于芯片加工能力，在有效处理超深亚微米物理效应和高效仿真验证高复杂度集成方面亟待提高和改善。与此同时，基于计算智能思想的各种优化方法不断涌现，为解决VLSI物理设计中的NP-困难问题提供了新的思路和启迪。由此，基于四川省科技厅基金项目——《计算智能在超大规模集成电路物理设计中的应用》，本文对计算智能算法中的禁忌搜索算法在VLSI电路芯片布局设计中的应用进行了一些研究。基于BBL模式的优点和目前对其研究发展的不充分，本文将当前主流之一的布局表征——序列对与禁忌搜索算法相结合，研究了其在BBL布局中的应用。采取实验与理论分析并重的方式，具体针对本文方法，构造初始布局并对一些尚在讨论中的禁忌搜索算法的重要参数进行了研究和确定。通过仿真并与其它计算智能方法相比较，证明了此方法的有效性。同时还对本文方法的一些特性（优化侧重、收敛性与小概率事件的关系等）进行了实验和分析。文中还提出了个人对禁忌搜索算法思想框架的一点改进意见。
徐宁[2]2002年在《用于VLSI物理设计的计算智能算法研究及应用》文中研究表明大规模集成电路设计正向深亚微米工艺不断推进，已经突破100nm大关。现有EDA工具难以应付复杂度呈指数增长的诸多VLSI设计难题，也缺乏对深亚微米工艺下一系列新问题的考虑。VLSI物理设计中的布局、总体布线和详细布线是典型的NP问题，计算智能方法为解决NP复杂度的大规模问题展示了广阔前景，因此研究各种计算智能算法求解这类问题，对于满足深亚微米工艺下高性能物理设计中的诸多要求是十分重要的。本文工作正是在这样的背景下，基于中国博士后基金，结合四川省科技厅的应用基础项目 《计算智能在超大规模集成电路物理设计中的应用》，对计算智能算法及其在VLSI物理设计中的应用，展开了一些研究工作。本文完成的主要工作如下：1） 首次将分形技术引入到VLSI物理设计中，提出了一种崭新的布局线长估计方法，它与传统的线长估计方法比较，估计结果更接近于实际线长。计算机仿真结果表明它是一种实用且有效的线长估计方法。2） 首次将禁忌搜索算法与结群技术相结合，并将其分别应用于门阵列布局和BBL布局中，计算机模拟结果表明该算法鲁棒性强、有效，适应性广，适用于大规模门阵列布局和BBL布局问题，3） 分别用神经网络技术、遗传算法和蚁群算法对两端线网布线问题进行了研究，并对结果进行了分析比较。在不同布线阶段，分别采用上述方法，可大大提高两端线网布线效率。4） 提出了一种基于均场退火的通道布线算法，并与基于Hopfield 神经网络的通道算法进行了比较，结果表明在得到较好布线结果的情况下，其求解优化时间大大降低
李煜[3]2005年在《改进的O-TREE表示法在求解带总线约束的VLSI电路BBL布局问题中的应用》文中进行了进一步梳理随着系统芯片(SOC)设计方法和知识产权(IP)模块技术在集成电路设计中的不断发展和应用,布图规划(Floorplanning)和布局日渐成为超大规模集成(VLSI)电路与系统物理设计的关键环节。布图规划的主要目标是在满足用户约束条件的前提下确定芯片上模块的最佳形状、位置以及模块的引线端位置,使得芯片的面积以及模块之间的互连线总长最小。由于布图规划设计是芯片物理设计的第一个步骤,其结果将影响芯片的最终性能。人们一直在寻求有效的优化算法以应用于布局问题,通过正确的策略我们可以很好地解决布局问题,同时减少算法的复杂度,缩短整个实现的时间。本文正是在这样的背景下,基于四川省科技厅基金项目,面对VLSI 电路物理设计中的关键环节,针对BBL 模式下的带约束布局问题,展开了一些研究工作。本文主要研究如何来求解在超大规模集成电路布局中,具有预定义坐标结群约束模块的布局问题(简称PCA 问题),研究途径是采用O-TREE 的编码表示方法和模拟退火的算法。目前,存在一些成功的算法来解决PCA 问题。然而,它们的算法有些很复杂,有些很耗时。在这篇文章里,我们提了一种新的布局算法来解决这个问题,该算法是基于O-Tree 结构,旨在减少总的运行时间且简便。通过对MCNC 的基准例子ami33 和ami49 上的仿真实验表明:与参考文献[32]中提出方法所得的结果相比,我们的新算法是可行的并且很有效。它不仅使芯片面积利用率得到改善,而且节约了一半以上的设计计算时间开销。本文还考虑到算法是否受模块规模大小的影响,为此我们进行了电路模块扩张的实验验证。针对ami33 基准例,实验模块被扩展到了65 个,实验结果表明我们的算法是很有效、鲁棒的,并且运行很快。
徐宁, 洪先龙, 董社勤[4]2004年在《BBL布局算法研究》文中研究指明针对不可二划分结构的布局问题 ,在序列对的基础上 ,结合结群技术 ,利用禁忌搜索算法 ,以芯片面积和连线总长作为优化目标求解BBL布局问题 用两个规模较大的MCNC标准例子进行了测试 ,并与其他文献中的结果进行了比较 实验结果表明 ,文中算法是十分有效的
梁多勇[5]2009年在《超大规模集成电路的布局算法研究》文中研究说明超大规模集成电路的物理设计是VLSI设计中重要的一环,也是较为复杂的一步。由于其复杂性,一般又把它分成划分,布图规划,布局,布线,压缩等若干子步骤。其中,布局问题是一个NP完全问题,一般采用启发式算法解决。目前,超大规模集成电路布局算法得到深入而广泛的研究,出现了许多较为有效的优化算法。本文的研究工作主要处于布图规划和布局设计阶段。首先,深入探讨了布局的各种表示方法,并对比了各种表示方法的优缺点。最后选择了序列对(Sequence Pair, SP)作为主要的研究基础。除此之外,还深入研究了模拟退火算法,并且提出了基于序列对的布局算法。为了得到更好更稳健的布局算法,本文在已有的权重模型基础上,改善了模块的移动方式。最后,对benchmark电路的数据进行了大量的仿真实验。实验结果表明,本文的算法是有效的,稳健的。除此之外,通过与研究小组的成员合作,将本算法与划分算法,详细布局算法等集成了一个简单的电路布局系统。
刘志[6]2004年在《基于LFF原则的BBL布局研究及应用》文中指出超大规模集成电路技术的迅猛发展得到了高性能计算机辅助设计工具——电子设计自动化软件的支持，同时也促进了电子设计自动化软件业的发展。与物理设计相关的计算机辅助设计技术称为布图设计，而布局是布图设计中的一个极为重要的环节，其主要目标是在满足用户约束条件的前提下确定芯片上模块的最佳形状、位置以及模块的引线端位置，最小化芯片面积和模块之间的互连线总长。 目前，在深亚微米、超深亚微米工艺下的超大规模、甚大规模集成电路设计中，布局结果的好坏直接影响整个布图设计，因此如何高效地表示布局结构，从而提高布局质量成为布图设计中的一个国际研究热点。本文正是在这样的背景下，基于四川省科技厅基金项目，对VLSI物理设计中的关键环节——布局，展开了一些研究工作。 本文概括地介绍了布局结构表示研究的进展。针对不可二划分的BBL布局问题，近年来国内外涌现出如：CBL，BSG，SP，O-tree等优秀的布局结构表示方法，但它们在解空间的大小、编码的费用、编码与和局之间的转换时间等方面各有差异。同时阐述了从人们日常生活中积累出的LFF原则，即尽量先用完更受限制的资源，而尽量后用更“一般”的资源，以便有更多的机会满足匹配来解决问题。然后运用LFF原则解决具有邻接约束的模块和L／T型模块的BBL布局问题。 作者在解决上述布局问题中主要工作如下： 1．提出了针对多边模块的有向图编码表示法的概念； 2．基于LFF原则，结合有向图编码表示法，针对以上的特殊的布局问题设计了ALFF布局算法； 3．编程实现A_LFF布局算法，并且测试实例的计算机仿真证明有向图编码表示法和A_LFF布局算法是有效的。
陆生勋, 姜国均, 陈文勇[7]1989年在《BBL布局的V-H树》文中指出本文首先定义一种有序有色的出树,称为V-H树。用该树描述BBL布局中的slicing结群。然后提出两种产生V-H树的递归构造法:一种是利用整数划分和迭代的方法,另一种是先分类再根据若干定理递归。最后讨论几种特殊树和BBL布局的关系。
陈锦珠[8]2011年在《适用于求解VLSI布图规划问题的多目标PSO算法研究》文中研究表明集成电路对经济和社会的发展起极大的推动作用，在提升国家综合实力上具有重要战略意义。布图规划是集成电路物理设计的一个重要过程，对芯片的成本，性能等方面起着决定作用，它通常需要满足多个设计目标且一些子问题已经被证明是NP完全或NP难问题。随着集成电路发展至超大规模及甚大规模集成电路，布图规划的难度也在不断加大，单靠传统手工方法来完成已不可能，必须借助电子设计自动化技术。粒子群优化算法是一种简单有效的群智能算法，具有良好的全局寻优能力。本文针对超大规模集成电路布图规划中的BBL布图问题，以粒子群优化为算法框架，围绕问题中的的编码和多目标优化等进行研究和分析，提出一种求解布图规划多目标优化问题的方法。主要研究内容如下：(1)采用智能算法解决布图规划问题首先需确定一种合适的布图表示方式。针对积木块布图模式和粒子群算法，采用了两种常见的布图表示方式，并相应地对粒子的更新方式进行重新定义，构造了两个离散粒子群优化算法，最后通过实验进行测试和分析，挑选较为合适的一种编码进行后继研究。(2)针对传统布图规划方法的不足和缺陷，以布图面积和互连线长为优化目标，在粒子群优化算法的基础上引入Pareto概念及其他多目标优化策略，提出了一种求解布图规划问题的多目标粒子优化算法。(3)协同进化算法比传统的进化算法更具优越性，通过对协同进化论及其多目标算法的研究和分析，在已有的多目标粒子群优化算法中引入协同进化的思想对其进行进一步改进，实验结果表明改进后的算法具有更好的性能。
张博[9]2007年在《BBL布局结构及算法研究》文中研究说明作为电子信息产业发展的核心和基础,集成电路技术正迅速向着更高集成度,超小型化,高性能、高可靠性的方向发展。随着系统芯片(SOC)设计方法和知识产权(IP)模块技术在集成电路设计中的不断发展和应用,布图规划和布局日渐成为超大规模集成(VLSI)电路与系统物理设计的关键环节。布图规划和布局的主要目标是在满足用户约束条件的前提下确定芯片上模块的最佳形状、位置以及模块的引线端位置,使得芯片的面积以及模块之间的互连线总长最小。由于布图规划和布局是芯片物理设计的第一个重要步骤,其结果将影响芯片的最终性能。在VLSI设计流程中,物理设计是既关键又复杂的一步,而布局又是物理设计中最重要的一步,布局的诸多问题都是NP完全问题,需要启发式算法来求解。随着VLSI集成度的迅猛提高,寻求有效的优化算法应用于布局问题,以提高布局质量和速度已成为当务之急;同时如何高效地表示布局结构,从而提高布局质量成为物理设计中的一个国际研究热点。本文正是在这样的背景下,对VLSI物理设计中的关键环节——布局,展开了一些研究工作。本文概括地介绍了布局结构表示研究的进展。针对不可二划分的BBL布局问题,近年来国内外涌现出如:CBL、BSG、SP、O-tree等优秀的布局结构表示方法,但它们在解空间的大小、编码的费用、编码与布局之间的转换时间等方面各有差异。本文提出了一种求解VLSI布局问题的启发式算法。该算法通过设计模块的优先顺序进行合理的布局,再辅助于边界矩形来减少边界浪费,对于模块布局放置的多个可能位置进行比较,并将其放置在优先度最高的适当区域。同时本文阐述了一种布局表示方法,在这种表示方法中尽量先用更受限制的资源,而尽量后用“一般”的资源,一般有更多机会满足匹配来解决问题。
霍明旭[10]2005年在《基于序列对的集成电路版图布局算法研究》文中研究表明集成电路版图(Layout)设计或物理设计(Physical Design)是VLSI设计中重要的一环，也是最费时的一步。由于布图的复杂性，整个布图过程往往分成划分、布图规划、布局、总体布线、详细布线和压缩等若干步骤，每一步骤完成布图的一部分工作。本文目前所做的研究处于布图规划和布局设计阶段。本文综述了各种布图表示方法，并对比各种方法的优缺点，在此基础上选取序列对(Sequence Pair，SP)作为主要的研究基础。以模拟退火算法作为程序框架，实现了多种布局方法，其中提出了一种增量式的布局算法，该算法原理简单、通用，可用于任何的实现框架之中，在优化效果和运行时间上都具有一定的优势。文中还实现了两个流行的用于搜索的数据结构：平衡二叉搜索树和优先级队列，并且把它们用在基于SP的版图布局中以加快运行速度。对一个给定的布局产生期序列对在很多情况下也是必须的，本文提出了一种快速的序列对的产生方法和相应的一个简便的算法。该算法性能优越，实现简单，并利用它证明了对于n个模块组成的布局，若模块之间的几何关系只有水平和垂直两种，任何的P~*-admissible的表示方法，其解空间的大小必须是(n!)2。最后开发并应用了一个版图的显示程序，该程序可以利用多屏显示技术以方便版图信息的显示。
参考文献：
[1]. 基于序列对的禁忌搜索算法在VLSI BBL布局中的应用[D]. 刘燚灵. 电子科技大学. 2003
[2]. 用于VLSI物理设计的计算智能算法研究及应用[D]. 徐宁. 电子科技大学. 2002
[3]. 改进的O-TREE表示法在求解带总线约束的VLSI电路BBL布局问题中的应用[D]. 李煜. 电子科技大学. 2005
[4]. BBL布局算法研究[J]. 徐宁, 洪先龙, 董社勤. 计算机辅助设计与图形学学报. 2004
[5]. 超大规模集成电路的布局算法研究[D]. 梁多勇. 西安电子科技大学. 2009
[6]. 基于LFF原则的BBL布局研究及应用[D]. 刘志. 电子科技大学. 2004
[7]. BBL布局的V-H树[J]. 陆生勋, 姜国均, 陈文勇. 杭州大学学报(自然科学版). 1989
[8]. 适用于求解VLSI布图规划问题的多目标PSO算法研究[D]. 陈锦珠. 福州大学. 2011
[9]. BBL布局结构及算法研究[D]. 张博. 电子科技大学. 2007
[10]. 基于序列对的集成电路版图布局算法研究[D]. 霍明旭. 浙江大学. 2005
标签：无线电电子学论文; 禁忌搜索算法论文; 智能算法论文; 序列模式论文; 集成电路论文; 算法论文; 四川省科技厅论文; 芯片论文;