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

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

考虑设计规则的引脚分配算法

详细布线是集成电路物理设计的关键步骤之一,引脚分配是影响详细布线质量和减少设计规则违反的关键因素,为此提出一种基于最小费用最大流的考虑设计规则的引脚分配算法.首先构建详细布线图和相应的网格图;然后在网格图上搜索布线区域内总费用最小的最大流,为所有线网的引脚同时分配pin点;在引脚分配的基础上提出一种拆线重布算法,针对引脚分配中不合理的pin点位置进行拆线重布,为其分配新的pin点,同时对设计规则违反从代价函数定义、拆线重布顺序、布线方式3个方面进行优化.实验结果表明,应用文中的引脚分配算法后,详细布线结果中的设计规则违反数平均减少了24%.     

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

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

基于整数规划的层次式FPGA布线算法

为了避免由于布线线序处理不当而导致无法布通的问题,提出一种基于整数规划的层次式FPGA布线算法.该算法使用一种全局优化处理的方式对布线问题进行求解,通过分析层次式FPGA的结构特点和整数规划的算法特点,导出了FPGA布线算法问题与整数规划之间的关系;然后具体描述了如何将FPGA布线问题转化成二进制整数规划问题及其相应的求解过程,其中利用层次式FPGA的结构特点对得到的整数规划问题进行简化.与可满足性布线算法进行实验比较的结果表明,文中算法具有求解速度更快、求解规模更大以及求解质量更高等方面的优势.     

确定区域详细布线算法

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

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

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

集成电路物理设计中的快速可布性评估算法

集成电路可布性评估在集成电路物理设计中针对布局结果进行有效的评估,作为对布局的反馈信息,并指导后续布线阶段的工作,避免了当后续布线无法完成时再回到前面布局阶段进行重新布局的被动局面,减少了物理设计的迭代周期.提出一种快速可布性评估算法,采用新的基于概率模型的估计算法,利用边界框进行拥挤度的预估,并在概率指导下进行实际布线.文中算法可以在很短的运行时间内对拥挤情况进行较为准确、客观的分析,线长较短.     

随程序规模动态调整的通道优化布线算法

针对常规层次型布图算法在大规模程序中布线混乱的缺点,借鉴Sugiyama层次布局算法,提出了一种随着程序规模动态调整的通道优化布线算法。通过将节点的通道数目与程序规模建立函数关系,以解决现有算法在布图时出现的线路重叠和效率低下的问题;在布图中结合广义张量平衡思想,以减少交叉并实现布图的美观性;并根据调用节点之间的相对位置关系,给出了相应的线路分配和申请策略,实现了布线的有序性。实践证明,该算法能够提高布图效率,有效地减少交叉,实现节点的有序布线和实现简单等优点。     

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

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

结合垂直通孔分配的层次式三维混合布局算法

采用层次式方法,分而治之,减小了电路的设计规模,非常适用于大规模的混合模式布局,并且在布局阶段结合了垂直通孔的分配问题.布局阶段的通孔分配问题不仅使得三维布局问题得以简化,而且为布线做好了准备,减少了后面的调整,是布线阶段垂直通孔分配问题的良好指导.提出了2种垂直通孔分配算法:比较精确的匈牙利近似算法;比较快速的邻域搜索方法.将这2种算法与层次式三维混合模式布局流程紧密结合,有效地解决了三维混合模式布局问题.     

自动机制设计中一种改进的混沌蚁群算法

针对自动机制设计计算复杂度会随具体问题规模的增大而呈指数增长等问题,提出了一种改进的混沌蚁群算法.在机制设计基础上,依据激励兼容和个人理性约束,分析了自动机制设计中的占优策略机制模型和贝叶斯-纳什均衡机制模型,并将改进的算法用于实现这2种机制模型.结果表明:该算法在公共货物配置问题上取得了较好的效果.     

基于围攻机制的改进鲸鱼优化算法

针对传统鲸鱼优化算法全局探索能力不足、收敛精度低、速度慢等问题,提出一种基于围攻机制的改进鲸鱼优化算法.首先,使用Tent混沌映射和非线性参数,使种群的分布更均匀,并且协调了鲸鱼优化算法的探索与开发能力;其次,考虑算法适应度在寻优中的重要作用,提出限制适应度控制和高斯检测机制;最后,结合哈里斯鹰优化算法的围攻机制,提升鲸鱼优化算法的全局探索和局部寻优的能力.将改进的算法与多种算法在13个可变维基准函数上进行仿真测试,结果表明,基于围攻机制的改进鲸鱼优化算法,在拥有较好鲁棒性和稳定性的同时,能够保证收敛精度与速度.     

一种无线传感器网络区域式服务发现机制研究

基于服务发现机制在无线传感器网络中的重要性及必要性,提出了一种区域式的服务发现机制模型.分析了对区域式无线传感器网络服务发现机制起支撑作用的分簇路由算法和数据融合算法,改进GAF算法形成了E-GAF算法,采用了感知器数据融合算法.通过仿真,从能量消耗等多方面论证E-GAF算法和感知器数据融合算法符合区域式服务发现机制的...     

机会网络下基于信任机制的改进Epidemic算法

针对 Epidemic 算法导致机会网络拥塞引发的路由可靠性问题,提出一种基于信任机制的改进Epidemic算法。通过构建节点之间的信任机制,提供具有足够可信度的节点作为消息的下一跳转发节点,使消息进行有限规模的泛洪传播。仿真实验结果和分析表明,改进后的Epidemic算法避免了泛洪机制引发的网络拥塞问题,并且在路由可靠性和传输性能上有一定的提高。     

任务调度问题机制设计

讨论分布环境中的算法问题,即网络上的计算机不执行给定的算法,而是执行最利于其主人工作的情况。作为这样的参与者即操纵算法的代理,算法设计者应事先确保代理的利益通过真实报告是最大的。引用了机制设计的概念,主要讨论了一个具有代表性的问题一任务调度问题。该问题不能通过标准的机制设计的方法去实现,因此,文中提出了几种特别方法,包括近似机制、随机机制以及验证机制。     

求解曲面距离问题的模拟退火遗传算法

提出计算曲面距离的统一方法——退火遗传算法。该算法将模拟退火算法和遗传算法相结合,解决了曲面之间的距离问题。该方法将工业中常用的曲面统一用参数形式表示,利用遗传算法求解曲面的距离问题。该方法通过引入模拟退火机制和人为地加入一定数目的特殊个体,大大增强了算法的爬山性能。     

A discrete electromagnetism-like mechanism for single machine total weighted tardiness problem with sequence-dependent setup times

Electromagnetism-like mechanism (EM) is a novel meta-heuristic, inspired by the attraction–repulsion mechanism of electromagnetic theory. There are very few applications of EM in scheduling problems. This paper presents a discrete EM (DEM) algorithm for minimizing the total weighted tardiness in a single-machine scheduling problem with sequence-dependent setup times. Unlike other discrete EM algorithms that use a random key method to deal with the discreteness, the proposed DEM algorithm employs a completely different approach, with an attraction–repulsion mechanism involving crossover and mutation operators. The proposed algorithm not only accomplishes the intention of an EM algorithm but also can be applied in other combinatorial optimization problems. To verify the algorithm, it is compared with a discrete differential evolution (DDE) algorithm, which is the best meta-heuristic for the considered problem. Computational experiments show that the performance of the proposed DEM algorithm is better than that of the DDE algorithm in most benchmark problem instances. Specifically, 30 out of 120 aggregated best-known solutions in the literature are further improved by the DEM algorithm, while other another 70 instances are solved to an equivalent degree.     

融合微平衡激活的小孔成像算术优化算法

为提高算术优化算法的全局勘探和局部开发性能,提出基于非线性小孔成像机理以及具有微调功能最优位置引导搜索策略的算术优化算法（IX-AOA）,自适应调整算术加速优化器因子是基于平衡算法勘探与开发目的一种纵向更新策略,通过双曲线性质调整算法勘探与开发时间分配,进而实现算法的自我更新机制,达到平衡算法勘探与开发的效果。在最优个体使用基于sigmoid激活函数的权重系数调整子代位置的搜索与开发的合理受控机理,达到丰富优质候选解的目标;引入非线性小孔成像原理改善搜索机制以优化候选解之间覆盖现象导致的寻优停滞局面,最后通过8个基准函数和部分CEC2014以及Wilcoxon秩和检测验证算法函数寻优的优越性。     

MADDPG算法经验优先抽取机制

针对多智能体深度确定性策略梯度算法(MADDPG)学习训练效率低、收敛速度慢的问题,研究MADDPG算法经验优先抽取机制,提出PES-MADDPG算法.首先,分析MADDPG算法的模型和训练方法;然后,改进多智能体经验缓存池,以策略评估函数误差和经验抽取训练频率为依据,设计优先级评估函数,以优先级作为抽取概率获取学习样本训练神经网络;最后,在合作导航和竞争对抗2类环境中进行6组对比实验,实验结果表明,经验优先抽取机制可提高MADDPG算法的训练速度,学习后的智能体具有更好的表现,同时对深度确定性策略梯度算法(DDPG)控制的多智能体训练具有一定的适用性.