层次式FPGA快速可布性布线算法

提出了一种针对层次式结构FPGA的快速拆线重布布线算法.利用历史拆线信息衡量拆线区域的可布性、可重布性及拆线影响力,形成独特的资源竞争解决机制;在禁忌搜索框架下选取禁忌拆线点、拆线路径与拆线线网,并在禁忌策略的指导下解决资源冲突,提高拆线有效性与速度.文中算法分为初始布线阶段与拆线重布2个阶段.在布线过程中,针对层次式结构引入简洁实用的布线线序.实验结果表明,该算法中的拆线机制可以有效地减少拆线数目,显著提高了运行速度.     

基于多阶段拆线重布的总体布线算法

超大规模集成电路总体布线是集成电路物理设计的关键环节之一,对芯片的可布线性、线长、通孔数等性能指标有重大影响.针对拆线重布方法容易陷入局部最优解的问题,提出一种基于多阶段拆线重布的总体布线算法.该算法根据不同布线阶段对最小化溢出值和最小化线长这两个目标的侧重点不同,通过构造不同的布线代价函数、确定不同的布线顺序、选取不同的布线模型及布线算法对线网进行拆线重布,使得基于多阶段拆线重布的总体布线算法可以有效地跳出局部最优解,快速地提高布线质量.采用ISPD08总体布线竞赛中的标准测试例子集的实验结果表明,与NTUgr,NTHU-Route2.0和NCTU-GR2.0相比,所提出的总体布线算法在平均总溢出方面分别减少了1.4%,2.4%和21.5%,在平均运行时间方面分别快了10.4倍,1.6倍和1.3倍.     

确定区域详细布线算法

提出了一种确定区域的详细布线算法,它能对不同设计模式进行布线。该算法能适用于任意多层布线情况,并且支持不同布线层具有的不同工艺参数,在构造布线树时,考虑芯片当前的走线拥挤度,使布线比较平均,并加快了算法运行速度、改善了布线质量,在连接两点线网时,构造基于二维迷宫布线结果的分层图,提出了一种对分层图的启发式染色算示来进行布线层分配,大大提高算法布线速度,采用拆线重布的方法来处理布线失败的线网。     

基于PathFinder和拆线-重布的FPGA时序布线算法

为了解决当前FPGA布线算法的绕线问题,进一步减少关键路径的延时,提出一种混合PathFinder和拆线-重布的FPGA时序布线算法.在PathFinder时序算法整体布线布通之后,拆掉一些影响关键路径延时的线网路径,再对这些拆掉的线网采用PathFinder算法进行增量布线;在重布的过程中,通过为关键连接和其他连接采用差别化的关键度来专门优化关键连接的路径,从而减少整个关键路径的延时.实验结果表明,与VPR时序驱动布线算法相比,该算法能平均减少12.97%的关键路径延时,而运行时间仅增加了4.87%.     

门阵列和标准单元布图中一种有效的走线道分配算法*

本文提出了一种用于门阵列和标准单元版图自动设计中的走线道分配算法一FARM，它连接总体布线和通道布线．算法目标是使通道的最大密度最小，同时考虑减小线网长度和通孔数．FARM由两部分组成：多行走线道分配和单行走线道分配它已用c语言在DE(：工作站和sun工作站上实现，并已用于我们开发的双层CMOS门阵列布图系统MALS3中．实验例子表明，它与Timborwolf 5.6的结果相当或更好．     

基于布通率的FPGA装箱算法

提出一种基于FPGA布通率的装箱算法.选择连接因子最小的节点作为种子节点;采用基于布通率的启发式函数来选择最合适的逻辑单元(LE)装箱到可配置逻辑单元(CLB)内部.可以同时减少装箱后CLB之间的线网数和CLB引脚的外部使用率,从而减少布线所需的通道数.该算法和已有算法相比较,线网数和布线通道数都减少约30%. 算法的时间复杂度仍然是线性的.     

带有引线端预处理的区域布线算法

提出一种带有引线端优化处理的多层区域布线算法,能处理端点障碍在区域内任意分布的大量布线问题,首先将多端线网划分为二端子线网,并在此基础上根据二端子线网之间的相对位置关系进行分类;然后对每个类型的二端子线网,采用双向迷宫和朝向目标的深度优先搜索策略依次布线;最后通过拆线-重布策略来解决布线冲突．在进行布线搜索之前,对引线端映射到网格点上这一过程引入了一种有效的优化预处理机制,采用二分图中多目标约束寻找最佳匹配的思想和策略来解决引线端优化映射问题．测试并比较了有／无这种优化处理的2种情况,实验结果表明,该算法有效地改善了网格映射的精度和准确性,可缩短线长和提高布通率．     

门阵列和标准单元布图中一种有效的走线道分配算法

本提出了一种用于门阵列和标准单元图自动设计中的走线道分配算法－ＦＡＲＭ，它连接总体布张和通道布线，算法目标是使通道的最大密度最小，同时考虑减小线网长度和通孔数。ＦＡＲＭ同两部分组成，多行走线道分配和单行走线分配。它已用Ｃ语言在ＤＥＣ工作站和Ｓｕｎ工作上实现，并已用于我们开发的双层ＣＭＯＳ门阵布图系统ＭＡＬＳ３中，实验例子表明，它与ＴｉｍｂｏｒＷｏｌｆ５．６的结果相当或更好。     

非默认规则线技术下基于多策略的时延驱动层分配算法

层分配作为超大规模集成电路物理设计中的关键环节,在决定布线方案的时延起到非常重要作用.为了优化集成电路的时延性能,现有的层分配工作通常注重优化互连时延和通孔数量,但要么未考虑到对线网中时序关键段的分配问题,要么对线网段的时序关键性的表示不够合理,最终使得算法的时延优化不够理想.为此,本文提出一种非默认规则线技术下基于多策略的时延驱动层分配算法,主要包含4种关键策略:(1)提出轨道数感知的层选择策略,增强层分配器为线网段选择合适布线层的能力;(2)提出多指标驱动的初始线网排序策略,综合考虑线长、信号接收器数和可布线轨道资源等多个指标为线网确定层分配优先级,从而获得高质量的初始层分配结果;(3)提出线网段调整策略,通过重绕线网,将时序关键段调整至上层布线层,优化线网时延;(4)提出线网段时延优化策略,对存在溢出线网进行拆线重绕,从而可同时优化时延和溢出数.实验结果表明,本文提出的算法相比于现有的层分配算法能够在时延和通孔数两个指标上均取得最佳,并且保证不产生溢出.     

一种考虑可制造性的高性能多层布线算法

本文采用改进的“V”字型布线流程,提出了一个考虑可制造性的多层布线算法,通过粗化和细化两个阶段完成布线。粗化阶段进行资源估计,在“V”字型框架的最底层通过多商品流算法获得总体布线的粗略解;细化阶段通过基于图的Steiner树方法细化布线拓扑树。详细布线采用改进的非均匀网格图,通过考虑OPC的迷宫布线算法,提高设计的的可制造性。     

电路原理图中两边网格通道布线的类贪婪算法

贪婪算法是VLSI设计中通道布线的常用算法，在电路原理图的自动布图中，也会遇到通道布线的问题。但传统的贪婪算法着重于使通道面积最小化，不能满足原理图中对布线结果有序化的要求。提出类贪婪算法，在原贪婪算法的基础上，通过修改处理规则，使得布线结果更加整齐有序，便于阅读，同时也保留了原算法简洁的优点。     

随机图的邻点可区别VI-均匀全染色算法

邻点可区别[VI]-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类（点或边）的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别[VI]-均匀全色数。提出了一种针对随机图的邻点可区别[VI]-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别[VI]-均匀全色数。     

串扰最小化的网格模式下的双层通道布线

超深亚微米IC设计中互连线的串扰情况与详细布线方案和信号波形密切相关。基于这一事实，在网格模式下的通道布线算法中建立了最小化串扰的目标函数。提出获得最小化串扰布线方案的方法。与以往算法不同的是，本方法将相邻平行线间信号跳变的方式和频度作为目标函数中的影响因子。可以更准确地估计出布线区内串扰总和的大小。并且通过构造布线生成树的方法求得精简的布线方案。有效地减少了求解具有最小串扰的布线方案的计算量。     

一种新的与线网顺序无关的随机优化总体布线算法

针对目前总体布线中仍然存在的3个关键问题;布线结果受布线顺序的影响、总体布线图中拥挤区域的不可预见性、线网连接式样受到算法的限制等,该文提出了一种新的不受线网顺序影响的总体布线算法,并实现了相应的总体布线器RINO－Router。该算法采用随机优化方法来保 证先后被拆线重布的线网有相同的通过拥挤区域的机会,并能得到GRG边的拥挤度估计值;采用高效的Steiner树改造算法构造避开拥挤区域的布线树,采用典型电路实例进行了测试,并将布线结果与基于多商品流算法的总体布线器Matula-Router进行了对比。结果表明,RINO－Router能够在短得多的运行时间内求得质量与Matula-Router相近的总体布线解。     

基于极坐标测量的圆度误差评定算法

提出一种利用极坐标测量数据求解圆度误差的网格搜索算法,其原理是在最小二乘圆心周围按一定规则布置一系列的极坐标网格点,依次以各网格点为理想圆心计算所有测点的半径值,通过比较这些半径值,实现最小区域法、最小外接圆法和最大内接圆法的圆度误差精确评定。详细叙述了算法求解圆度误差的过程和步骤,给出了数学计算公式及程序流程图。试验结果表明,该算法可有效、正确地评定圆度误差。     

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

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

自动修复短时序违反路径的FPGA布线算法

为了解决寄存器保持时间不满足而引起的短路径问题, 提出一种自动修复短时序违反路径的FPGA布线算法。在VPR时序布线算法整体布线布通之后, 调用短路径时序分析来获取违反短时序约束的布线连接, 然后通过修改代价函数, 对每条违反短时序约束的连接进行增量布线, 使每条连接的路径延时尽可能达到满足短时序约束所需的延时。实验结果表明, 本算法与VPR时序驱动布线算法相比, 能够平均修复94. 7%的短时序违反路径, 而运行时间仅增加了6. 8%。     

多电压SoC引线压焊供电引脚分配及电源网络拓扑优化

针对较大电压降易导致电压岛内电路宏模块供电不足,引起电路失效的问题,基于引线压焊技术封装芯片,提出一种面向多电压技术的电压岛供电引脚分配及电源网络拓扑优化方法.首先根据电压岛的物理布图信息,采用弹簧模型确定电压岛供电引脚位置实现电压降优化;然后通过建立稠密的虚拟电源网络,利用增量式方法完成电源网络的拓扑优化.通过对GSRC标准电路测试的实验结果表明,与固定供电引脚方法相比,文中提出的供电引脚分配方法平均降低电压降26.1%;而电源网络拓扑优化方法产生的非规则网络,使得电源网络布线面积较规则电源网络的布线面积平均降低84.5%.     

一种基于图的平面点集Delaunay三角剖分算法

本文提出了一种基于图的平面点集Ｄｅｌａｕｎａｙ三角剖分算法。该算法首先求出平面点集的欧几里得最小生成树，然后逐次加入一边构造三角形网格，最后按最小内角最大的三角化准则，通过局部变换，得到平面点集的Ｄｅｌａｕｎａｙ三角剖分。本文同时阐述了它的对偶图；平面点集的Ｖｏｒｏｎｏｉ图的概念和性质。     

电缆网电路图自动布图算法的研究与系统实现

针对电缆网电路图的自动生成问题,在借鉴传统电路原理图自动布图的行列布局与通道布线思想的基础上,同时结合电缆网电路图的特点,提出了先位号行定位,再点号列定位的自动布局算法,并在两相邻位号间形成的行通道与相邻点号间形成的列通道间进行通道布线。算法成功应用于自主研发的电缆网电路图自动布图系统。系统能够根据电缆网表中的元器件连接信息,自动生成逻辑功能正确且布图美观规范的电缆网电路图,系统已被多个航天研究所在火箭、导弹的电缆网设计工作中采用,显著提高了电缆网设计工作的自动化程度。