启发式布线方法

Lee’s迷路法实质上就是广度优先搜索法,线探索法实质上就是深度优先搜索法,它们是图搜索的两种极端情况。本文按照Rubin策略提出一种新的布线方法——启发式布线方法,它在布线过程中的每一步给出一个启发值,由此来确定向什么方向走线,其效率比DFS和BFS要好得多。     

一种自适应多层无网格布线算法

为适应多布线层，采用非均匀网格图模型，引入了一种自适应迭代策略，将多层布线转化为多次两层布线来处理，既能适应任意布线层数，又大大减少了多层迷宫布线的搜索空间；针对非均匀网格图模型的特点，提出了优化的绕障长度的迷宫布线算法。实验数据显示算法具有较快的搜索速度和较好的布线质量。     

新型实用布线算法──L─M算法

本文提出新型布线算法，集李氏迷宫法与线搜索法的长处为一体，以饱和带法进行动态排序，以线搜索法确定借孔位置，然后用李氏法进行单层布线，获得最佳路径，从而达到线型好，布通率高的效果。     

基于边界扩张的点对点布线新算法

在超大规模集成电路设计中,全局布线是非常重要的步骤。工业界普遍采用经典的迷宫算法及其改进算法解决全局布线问题。随着工艺节点的减小,传统迷宫算法复杂度高的缺点越来越明显。针对传统迷宫算法的复杂度会随着布线规模的扩大而迅速增加的问题,借助于边界扩张的概念,提出一种新的点对点布线路径的搜索算法。摒弃了迷宫算法低效率的逐个节点扩张的思想,通过自由节点的定义对节点边界进行迅速扩张并不断地找到新的自由节点,直到找出路径或确定无解时结束。将该算法与经典的布线算法进行理论和实验比较,结果表明在大多数情况下该算法使用经典算法7%~14%的运行时间即可完成路径搜索。     

用于迷宫电脑鼠的一种迷宫补全算法

摘要：在IEEE电脑鼠走迷宫竞赛规则的基础上,介绍了一种基于对迷宫分析补全思想的路径规划算法。详细阐述了算法流程和实现过程,对搜索过程中的算法提出一种改进思想。实验表明,该算法可以提高电脑鼠的搜索效率,有效地减少迷宫搜索时间,提高竞赛成绩。     

迷宫算法的改进与动态实现

本文在对广度优先迷宫搜索算法和深度优先迷宫搜索算法进行了仔细比较与探讨之后,提出一种新的算法:目标优先法。即每次向下一个位置搜索时,按当前位置的各方向靠近目标点的距离去选择方向。使得搜索过程在较短时间内能够快速从入口向出口目标逼近。然后从数据输入输出,程序设计等方面讲述了这种带优先级的算法的实现。并将此算法用Java语言在JDK上实现其搜索过程的画面,模拟其算法实现过程。最后,将此算法与传统的广度优先和深度优先算法优缺点进行了综合比较。     

基于向心法则的电脑鼠走迷宫算法设计与优化

电脑鼠是一个集自主迷宫搜索、搜索完后最短路冲刺、传感与控制于一体的自主移动机器人系统.具体设计和实现了基于向心法则迷宫搜索算法,并对算法和迷宫搜索流程进行优化,实验证明优化后的算法,在保持原有算法高效的基础上具有更加好的局部效应,相比同类型的算法,优化后的向心法则是一种非常高效的迷宫搜索算法.     

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

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

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

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

基于UG的三维电气自动布线技术研究

对三维电气布线的方法和技术进行了深入的研究。针对传统布线过程存在的预处理成本高、操作繁琐、干涉检测维护难等问题,通过综合"迷宫法"、线搜索法"等搜索算法和路径干涉理论,提出了"按面自动布线"和"贴壁干涉自动调整"的方法。以UG为开发平台,实现了包括三维布线路径自动生成和路径干涉检查及自动调整在内的三维自动布线。并以UG布线实例验证了所提出的三维布线方法的有效性和实用性。     

一种减少重复搜索的FPGA快速布线算法

为了提高FPGA布线的运行速度,提出一种减少重复搜索的快速布线算法,该算法分为布通驱动布线算法和时序驱动布线算法.在布通驱动布线算法中,通过把线网的布线路径转换成连接的布线路径来判断每条连接的路径中是否存在拥塞节点,如果存在,保留其布线路径,否则重新进行搜索;时序驱动布线算法采用临界度判定机制来平衡运行速度和时序性能之间的比重.实验结果表明,与公认的VPR布线算法相比,布通驱动布线算法和时序驱动布线算法的运行时间分别平均减少了95.19%和28.98%,且时序驱动布线算法的关键路径延时减少了4.80%.     

蚁群算法用于VLSI布线的特性分析

本文重点在于研究在VLSI布线中采用蚁群算法的实用性和优越性。通过用MATLAB编程对蚁群算法和迷宫算法等算法的实现,得出蚁群算法在VLSI布线中的适用性不受布线结构的限制,而且在得出最优解方面有一定的优势。     

具有稀疏障碍的近似迷宫算法

本文中给出了一个在具有稀疏障碍的迷宫中寻找给定两个单元之间的最短路径的走迷宫算法,算法以“不改变方向”为预测条件,沿直线方向扩展。经大量的随机实验对比,结果证明本文中的算法大量地缩减了搜索范围,是一个高效的算法。     

基于机器视觉和A*算法的迷宫机器人路径规划

针对迷宫机器人路径规划问题,以机器视觉和A*算法为基础,提出了一种新的迷宫机器人全局路径规划方法。该方法利用区域阀值分割对迷宫机器人系统采集的图像进行分析,结合A*算法逆向搜索全局最优路径。仿真结果表明,该方法实现简单,在复杂的迷宫环境下能有效地实现迷宫机器人路径规划。     

基于AVR ATmega128的迷宫电脑鼠软件设计与实现

根据IEEE标准电脑鼠走迷宫的比赛需求,介绍了一个基于AVR ATmega128的电脑鼠软件算法的设计与实现,主要包括底层驱动算法和顶层软件算法两个部分。该电脑鼠实现了在迷宫内快速稳定的行走及对迷宫最优路径的搜索.电脑鼠迷宫竞赛有一定的难度,这是一种具有挑战性和趣味性的竞技比赛。Micromouse是一个涉及多个学科领域的理论与应用的综合性系统。     

一种基于迷宫算法的有效FPGA布线方法

在本篇论文中,我们介绍了在标准对称阵列（隔离岛状）现场可编程逻辑阵列结构下的一种基于迷宫布线算法的新型有效布线方法,Pathfinder.实验结果显示,相比普通的迷宫布线法,Pathfinder算法在布线时间上减少了90%.     

一种模拟集成电路布线中的contact,via定位算法

模拟电路布线通常采用无网格的布线模式,这就存在如何在整个布线平面中确定连线间的contact和via的位置的问题,文中提出了一种在任意曼哈顿多边形中求最大内接矩形的算法,该算法通过准确,快速地搜索出放置contact和via的空间,以提高整个布线的效果并降低布线过程在时间上的消耗。     

一种改进的伪布尔可满足性算法用于FPGA布线

为了避免伪布尔可满足性算法在布线过程中带来的增加转换成本的负面影响,提出了一种用于FPGA的新的布线算法,该算法结合了伪布尔可满足性算法与几何布线算法的优点。在布线过程中,先选用PathFinder这种几何布线方法对FPC}A进行布线,如果不能成功再采用伪布尔可满足性算法。并在布线流程中增加了静态对称破缺技术对伪布尔约束进行预处理,侦测并破缺其中的对称,从而达到减少搜索路径,消减成本的目的。初步的实验结果表明,这种混合布线方法可以显著减少运行时间,加速求解过程,并且对整体方案无不良影响。     

一种电脑鼠走迷宫算法的设计与实现

电脑鼠是一个自主移动机器人系统.电脑鼠的任务是到达迷宫中心的目标区域.电脑鼠在不知道迷宫的布局情况下,必须自己找出到达目标的最优路径.整个过程是一种自主搜索的过程.研究和实现了基于位差值的搜索算法和基于等高图的最优路径算法,并作出改进提高机器人完成任务的能力.     

确定区域详细布线算法

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