轻量化FPGA布线路径搜索算法EI北大核心CSCD

针对FPGA布线耗时较长的问题,提出一种基于最优节点预测的轻量化FPGA布线路径搜索算法.该算法通过预测最优布线资源节点,在搜索最优布线路径时只对最优节点进行详细计算、分析,无须搜索其他节点,从而提高搜索速度;当轻量化搜索失败时,以全局最优节点为源点重新进行轻量化搜索,提高全局搜索能力;在寻找全局最优节点时,只对可能出现在最优路径上的次优节点进行详细计算分析,减少无效计算.使用VTR标准电路对所提算法和VPR 8.0进行测试,并从布线所需时间和结果质量2个方面进行比较.实验结果表明,与VPR 8.0中布线路径搜索算法相比,所提算法在保证布线结果质量基本不变的情况下,将搜索的布线资源节点数量减少41.8%,可节省31.3%的运行时间.     

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

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

迷宫最短路径问题新算法

提出了求解迷宫最短路径问题的新算法,该算法抛弃了经典算法(深度优先搜索和广度优先搜索)中繁杂低效的递归、回溯思想。通过合理的变换,将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试,显示出该算法易于理解、易于编程、时间空间复杂度低等优点。     

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

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

门阵列布局与全局布线合并算法

本文提出了一种门阵列的布局与全局布线的合并算法(简称合并算法)。合并算法将布局和全局布线两过程合为一体,在布局的过程中考虑全局布线,同时利用布线信息指导布局,从而有效地利用了布局和全局布线信息,以较少的代价获得全局优化结果。合并算法成功地克服了传统的布局和全局布线分阶段设计的布图设计模式所固有的缺点。     

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

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

基于RRT*的母线布线路径规划算法

针对母线布线设计繁杂,低效,耗时成本高的问题。对工程中母线布线设计的约束与优化目标进行了研究总结,提出了一种基于快速扩展随机树算法(RRT*)的母线布线路径规划算法。在传统的RRT*算法的基础上,通过引入中间点（corner点）的方式改变已生成路径到随机点的扩展方式,使生成路径符合母线的走向限制,实现了初始路径的生成。同时在初始路径生成过程中采取贪心的优化策略,获得弯头数量最少且满足约束的路径。仿真结果表明,相较于传统的RRT*路径规划算法,本文提出的算法可以很好的满足母线的各项布线要求,为母线的自动布线问题提供了一个新方法。     

确定区域详细布线算法

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

基于动态离散势场的迷宫机器人路径规划

针对未知环境下的机器人迷宫求解问题,提出一种动态离散势场路径规划算法。为提高路径优化性能,采用引入边界节点的栅格法建立模型,在各栅格的边界节点处定义障碍物状态和势场的数值大小,通过计算可连通相邻节点的累计代价值完成势场的构造。为提高寻优速度,随着环境信息的更新动态改变势场分布,沿势场下降最快方向获得实时重规划路径,引导机器人向目标运动,通过预规划路径的访问状态判断路径是否收敛,避免无用栅格的扩展。仿真实验结果表明,应用该算法可使机器人在复杂未知的迷宫环境中快速、高效地规划出一条折线少、转折角度小的优化路径。     

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

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

网络中最短距离的递归算法

提出了在搜索过程中采用标记最短距离,调用递归函数用回溯搜索法求解网络最短距离的算法。该算法可以方便地求解复杂网络或复杂迷宫的通道与最短距离问题,在求解结果中给出从起点到网络通道上任意点的路径标识和最短距离值等信息,在无向加权图的最短路径求解中,显示出比Dijkstra方法小的时间复杂度。该算法克服了传统回溯法求解复杂迷宫时被时间复杂度和空间复杂度困扰的难题,显示出良好的应用前景。     

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

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

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

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

电路布线问题求解的改进算法

常用的解决电路布线问题的算法的时间和空间的复杂度都是O(n2)。这里n为一块电路板的上端(或下端)接线柱的个数。现给出一种时间复杂度为O(nlogn)的新算法。改进了传统的算法。     

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

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

注水法求解迷宫最优路径

根据灌溉系统的工作原理,提出注水法算法应用于求解迷宫最优路径问题.设定迷宫为一个灌溉系统,水从迷宫的入口注入,通过迷宫的通路水从迷宫的出口流出.从入口注入的水沿通路流向各个方向,在通路的各个位置记忆水流到达的时间.当迷宫出口有水流到达时,从出口到入口根据记录在通路上的时间逐步减小的原则逆向寻找入口就可找到迷宫的所有最优路径.该算法的空间复杂度和时间复杂度同迷宫的规模成线性关系.实验结果显示该算法是一种求解迷宫问题的有效算法.     

Dijkstra算法的一种高效率实现

Dijkstm提出单源点最短路径算法即计算一个节点到其他所有节点的最短路径.算法结构过于复杂且效率较低.采用最小堆对Dijkstra最短路径算法进行优化,优化后的算法比起经典算法在时间复杂度和空间复杂度上都有明显的提高.     

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

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

复杂环境下基于贝叶斯决策的机器人路径规划

提出了一种基于贝叶斯决策的机器人路径规划蚂蚁算法,该算法在路径节点选择方式上采用贝叶斯模型,通过后验概率对候选节点进行评估,解决了用传统蚂蚁算法进行路径规划时容易陷入局部最优的问题。仿真实验表明,机器人应用该算法可在复杂障碍环境下快速规划出一条全局优化避障路径。     

DW最短路径算法及在逻辑图自动布线中的应用

提出了基于Dijkstra最短路径算法的动态权值最短路径算法，并对该算法提出了优化措施。基于优化的最短路径算法，在芯片分析软件中实现了逻辑图中的两点间自动布线的功能，并在此基础上实现了拖动元件过程中的重布线功能。该算法能够在尽量减少布线交叉和转角的基础上减少布线长度，使得逻辑图清晰易读，提高了芯片反向工程后端电路分析的效率。