求解VLSI电路划分问题的混合粒子群优化算法

电路划分是VLSI物理设计过程中的一个关键阶段.该问题本质上是一个NP困难的组合优化问题.针对该问题,提出了一种带FM策略的混合粒子群优化算法.引入遗传算法的两点交叉算子和随机两点交换变异算子,保证了粒子在位置更新后依然可行;为了提高算法的局部搜索能力,将具有较强局部搜索能力的FM策略融入算法的位置更新;设计了种群多样性变异策略,提高了种群多样性,避免了易陷入局部最优的缺陷.对ISCAS89标准测试电路的仿真实验结果表明,所构造的算法是有效的.

VLSI电路划分问题的分散搜索算法

电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.

基于概率增益的电路划分算法

该文提出了一种新的划分算法,算法中引入可变线网权重。由于超图(hypergraph)中的线网连接节点数一般多于两个,为了充分将线网增加的权重作用到与该线网相连的所有节点上去,线网增益采用了概率增益模型。该算法与原有算法相比较,可以有效地让电路的划分跳出局部最小,结果有较大的改进,特别是当电路规模比较大的时候,改进更明显。由于采用概率增益模型,出现浮点数,节点增益的存储采用了平衡二叉树(balanced binary tree),因此算法的速度相对于FM算法有所下降,但是时间复杂度仍然接近为线性复杂度,时间复杂度为O(P log2(n))(P为电路所有逻辑单元的引脚数之和,n为电路的逻辑单元数)。

电路划分问题的算法研究与计算机实现

在介绍电路划分问题的基础上,提出了一种基于宏单元的电路划分数学模型,同时给出了利用计算机解决该问题的遗传算法的设计和实现过程。将该实现方案用于对标杆电路划分进行测试,与传统的F-M划分算法相比,划分结果得到明显改善。

求解电路划分问题的混合式遗传算法

为了进一步降低超大规模集成电路设计的复杂性、增强图形可读性 ,提出了一种求解电路划分问题的混合式遗传算法。与传统遗传算法不同的是 ,该算法采用了顺序交叉和单元交换变异方式 ,同时对交叉概率和变异概率进行了优化设计。与K -L算法及传统遗传算法得出的结果比较 。

基于贪心随机自适应搜索的电路划分改进算法

为提高基于迭代改进的传统电路划分算法的划分质量,提出了一种基于贪心随机自适应搜索过程(greedyrandomized adaptive search procedure,GRASP)的电路划分改进算法.GRASP由构造阶段和局部搜索阶段组成,能够快速构造较好的初始划分.在其构造阶段引入启发式子集选择策略,并与高效搜索技术Path-Relinking相结合,在各个局部最优解之间建立路径,从而有效搜索了局部最优解空间.实验结果表明,该算法与基本GRASP相比,能在合理的时间范围内改进解的质量,获得更好的划分结果.在获得的最小划分上,改进程度最大达到33.3%;而在平均划分上,最大达到27.4%.

基于F-M算法的电路划分新方法

提出了一种基于F M算法的启发式电路划分新方法.首先对电路各单元进行聚类,将聚类结果作为算法的初始划分,为了得到更好的划分效果,在F M算法的每一次迭代过程中都引入了单元释放;同时对比例划分作了进一步的研究;最后将该方法应用于标杆电路的划分.实验结果表明,该方法与F M算法相比,划分结果得到了明显的改善.

电路划分问题的遗传算法求解

电路划分是VLSI设计中的一个重要过程,它是降低超大规模集成电路设计复杂性、增强图形可读性的有效方法,因此电路划分算法尤其重要。针对该问题,本文提出了两种基于不同编码方式的遗传算法,算法1采用0-1编码方式,算法2则为基于模块编号的整数编码方式,同时给出了相应的适应度函数及遗传算子设计。将两种算法用于标杆电路模型的求解,与传统的F-M电路划分算法相比,这两种算法得出的划分结果有明显改善,但时间效率有所下降;另外算法一在时间效率上优于算法2。

基于遗传算法的VLSI电路划分方法

电路划分是降低超大规模集成电路设计复杂性的有效方法。提出了一种基于遗传算法的电路划分算法,该算法不仅适用于电路的二划分和划分问题,而且可以满足划分对子集的大小和面积等多约束的要求。

一种新的VLSI电路划分算法

提出了一种新的基于遗传算法的电路划分算法 ,该算法不仅适用于电路的二划分和K划分问题 。

用神经网络求解性能驱动的电路划分问题

文中考虑一种以连线代价最小为目标的、以面积和时延为约束的、划分块与划分块之间有确定的拓扑关系的电路划分问题，提出了一个性能驱动电路划分的均场退火算法．算法通过换位矩阵把问题映射为神经网络，并建立了包含优化目标项、面积约束项和时延约束项的能量函数，再用均场退火方程迭代求解．每个单元只能分配到一个划分块的约束用神经元归一化的方法处理．算法已用ＶｉｓｕａｌＣ＋＋语言编程实现，实验结果表明这是一种有效的方法．另外，文中还讨论了人机结合的电路划分问题．

电路划分算法改进

为提高电路划分的质量,对KL电路划分算法运行的终止条件进行改进,给出相关的公式推导过程,使得算法找到同样的解节省1/2的程序运行时间。

启发式局部搜索算法在电路划分中的应用

本文研究一种启发式局部搜索算法Path-relinking在电路划分问题中的应用。Path-relinking技术能在两个解之间建立路径,并搜索路径上的改进解,从而改善划分结果。实验结果证明了该技术的可行性及有效性。

利用一个随机并行算法实现最佳电路划分

电路划分是ＶＬＳＩ布图中的ＮＰ完全问题之一。用传统方法解决这个问题时，很难找到最佳解。本文利用一个随机并行算法，通过将电路划分问题公式化，选择适当的退火策略与参数值而寻找一个代价函数的全局极值即可得到最佳结果。所用算法具有较低的时间和空间复杂性以及高度的并行性。

一种基于多级聚类的VLSI电路划分算法

超大规模集成电路(VLSI)划分问题,属于NP-难问题。结合了贪心随机自适应搜索过程(GRASP)和多级聚类方法的思想,提出了一种基于多级聚类的电路划分算法。算法采用贪心随机自适应的思想改进了多级划分方法中重边粗化聚类(HEM)方法。通过对ISPD98的18个标准测试样例的测试结果表明,该方法与著名的划分工具h Metis相比,划分质量有一定的提高,最多可以改进3%左右。

用Tabu Search解决基于结群的电路划分问题

电路划分是VLSI物理设计中最重要的步骤之一。本文提出了一种自底向上的结群策略,首先将具有高互连关系的电路模块进行结群,然后再将结群后的宏模块进行划分,用Tabu Search启发式算法进行求解,测试电路选择标准MCNC benchmarks,实验结果表明在解的质量相当情况下,运算时间较少。

一种新的基于晶体管级的电路划分算法

随着VLSI电路规模的不断增加,为实现电路并行仿真所做的电路划分算法的质量显得日益重要。鉴于现有算法未能同时保证均衡的分块间规模和最少的互联信号数目,该文提出了一种新的基于晶体管级的电路划分算法。该算法首先通过一个聚合过程对电路网表进行分割,得到一个比较好的初始分割;然后通过平衡分块间规模差异和进一步优化分块间互连线的数目,最终得到理想的电路划分结果。应用该电路划分算法对工业界的实际电路网表进行测试,结果表明:相比于目前普遍使用的COPART算法,该算法在分块间规模的均衡性方面平均改善了25%,在分块间的互联信号数目方面平均减少了18%。

一种基于点割的电路划分算法

文中提出了一种基于IG图（Intersection Graph）点割的电路划分算法,引入IG图模型,根据电路中信号网络间的交互关系构建IG图,直接对电路信号网络IG图进行最小点割划分,从而实现对电路单元（模块）的划分.该算法既有效地解决了电路超图与图之间转换的一致性问题,又实现了点割目标值与直接电路划分目标值的一致性,IG图点割集的大小即为真实电路划分的目标值.此外,通过给每个电路网络赋权重的方式构建带权重网络交互图,实现对电路网络划分的面积平衡进行近似控制,满足电路划分对面积平衡的特殊要求.采用MCNC提供的标准电路测试数据进行测试,实验结果表明,基于IG图点割的电路划分算法较基于网络超图HDN划分的K DualFM算法平均有3％～7.8％的提高;同时,基于IG图点割的随机优化算法ROP比基于超图划分的FM优化算法具有更强的全局优化能力,划分结果提高18％,比基于二部图匹配的点割优化算法提高36％,对较大规模数据划分优化效果更好.

基于Cell对称矩阵结构的电路划分方法

电路划分是超大规模集成电路自动化设计中的一个关键的阶段,同时也是NP-hard组合优化问题.文中基于结点移动的Fiduccia-Mattheyses(FM)算法提出新的cell对称矩阵数据结构,实现一种电路划分方法.首先使用对称矩阵数据结构存储结点和线网信息,然后利用简单的加减运算代替划分过程中结点增益的计算,最后简化原始算法中复杂的判断与计算完成对电路的划分.实验结果表明,与原始FM算法相比,在保证得到等价划分结果的情况下,该方法显著简化了实现过程,并且保持了线性复杂度;对电路实例进行划分,平均切边优化效果达到95.89%.

模糊人工神经网络方法在电路划分问题中的应用

本文把模糊集合论的知识应用于自组织人工神经网络,提出一个模糊人工神经网络算法.新算法克服了一般人工神经网络方法共同面临的学习时间长、对网络参数的敏感性弱点,广泛适用于一般的模式分类问题.对集成电路设计中电路划分问题的应用情况表明,新算法无论在网络学习的速度上还是划分结果上都优于Kohonen的自组织人工神经网络方法.