弹性自适应二端布线算法研究及实现

军事通信指挥中很重要的环节是大量通信组织图表的绘制,目前借助计算机软件进行数字化制图处于研制与发展中,其重点与难点在于自动布线算法的设计和实现.由此在系统开发中首次提出了弹性自适应二端布线算法,主要对布线点的自适应选择、寻路算法优化、布线版图美化几个方面进行研究与实践.从而解决了自动布线过程中布通率低、布线速度慢的技术难题,大大提高通信制图的自动化程度.     

确定区域详细布线算法

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

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

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

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

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

基于线网分类的模拟电路自动布线器

提出一种基于线网分类的模拟电路自动布线方法,并设计实现了一种基于线网分类的模拟电路布线器NCARouter．基于模拟电路性能要求,布线器中的线网被分为关键线网、普通线网和电源／地线网3种类型．同时,模拟电路的性能约束被转化为线网的属性描述,包括几何约束（如对称）、电学约束（如匹配）、寄生参数描述等．此外,针对不同类型的线网,该布线器使用了不同的布线算法,以满足总体性能约束．实验结果表明,该布线器不仅能很好地完成布线,还能确保满足模拟电路各种性能要求．     

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

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

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

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

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

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

端到端时间约束的实时任务动态调度算法

在单处理机系统中,由于计算高优先级任务抢占的时间相对比较简单,所以单处理机调度理论取得了长足的进步.提出一个端到端时间约束的实时任务调度算法,当实时任务到达系统时,算法为任务的每个子任务在相应的处理机上预约一定的计算资源,把端到端的多处理机调度问题转换成单处理机调度问题,从而可以利用单处理机调度理论判定实时任务的可调度性.实验表明,该算法明显地提高了CPU利用率和任务接收率.     

一类电路布线问题的分支限界算法

分支限界策略对很多实际问题是重要和有效的。论文首先提出了一类电路布线问题,然后给出了解决该问题的分支限界算法并分析了所给出算法的复杂度。实验结果验证了所提出方法的有效性。     

交换超立方网中的最短路径路由算法

针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法.利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为O(s+t)2).理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径.     

优化的多媒体流多播选路的试探算法

在网络实时应用如远程教育、视频会议等系统中,对多播多媒体流的每一个流,不仅有严格的端到端时延限制,还有网络带宽的约束。网络在满足应用服务请求的同时,还应尽可能地降低资源的消耗。因此需要研究优化网络资源利用的多媒体流多播路由算法。论文采用优化的试探方法解决多播路由多媒体流分发问题。实验结果表明优化后的算法,与已有算法比较起来,使客户端接收视频流的满意度提高5%～8%,链路带宽节余8%～20%。     

一种带有可控阈值参数的分簇路由优化算法

针对传感网中大量冗余数据导致通信频繁中断的问题,提出一种带有可控阈值参数的分簇路由优化算法。引入蚁群算法中的适应度函数和启发式函数,使得下一跳簇首节点的选择更具针对性,实现网络路由树的建立与事件域节点的分布式成簇。利用可控阈值参数和变异系数对网络路由所选最短路径进行优化,保证节点能量消耗较低的同时全网延时最小,并通过全局信息素的更新策略抑制长链路的产生,以均衡全网能量并延长网络生存周期。实验结果表明,该算法与DMOA和MTTA算法在抑制网络能量消耗和延长网络生存周期方面进行对比,其性能指标平均提升了13.72%和12.06%。     

降低路由开销的ZigBee路由算法研究

ZigBee技术是为无线传感器网络技术设计的一项新兴的低成本、低功耗的短距离无线通信技术。在分析ZigBee路由机制的基础上,针对控制分组的传输范围和转发方向提出降低路由开销的改进方案,并与原算法进行仿真分析。     

OHChord:基于优化路由表和路由热点的Chord改进

在P2P系统和网格计算中如何高效定位所需资源是目前的一个研究热点。Chord是一种基于DHT技术的结构化P2P路由协议,具有完全分布式、负载均衡、可用性及可扩展性好等特点。但其路由表结构具有一定的冗余信息,定位效率不高。本文提出基于优化路由表和路由热点的OHChord算法,一方面优化Chord路由表,除去冗余信息,另一方面为Chord中每个节点增加热点路由表。与标准Chord和P_Chord相比,OHChord提高了查询效率。     

基于Dijkstra策略的QoS路由多目标算法

对网络拓扑结构和QoS路由指标进行了形式化分析，提出了一种QoS路由数学模型．通过建立QoS路由综合评价指标，基于Dijkstra策略，给出了一种QoS路由多目标算法(Multi—object QOS Routing Algorithm Based on Dijk—stra Strategy：MOQRAD)．仿真研究表明该算法在满足业务连接QoS需求的同时，网络负载分布均衡，提高了网络的吞吐量，较好地改善了网络的性能．     

移动自组网的单向链路优化路由算法AODVUD

移动自组织网络路由协议多是基于双向链路提出,而单向链路在实用环境下普遍存在,严重影响着网络性能.本文在路由发现、双向链路感知和路由维护等方面对AODV路由算法进行改进,提出了一种基于单向链路的优化路由算法AOD-VUD.仿真实验表明该算法显著改善了报文端到端传榆率,相对于现有按需路由算法AODV和AODVUU有较显著的优势.     

一种带软时间窗的物流配送路径优化遗传算法

本文在建立物流配送路径优化问题模型的基础上,采用最佳保留的轮盘赌复制法、最大保留交叉法、交叉率和变异率自适应调整等技术,设计了基于自然数编码的遗传算法,并进行了实验计算。结果表明,用该算法进行带软时间窗的非满载车辆调度优化问题,可以方便有效地求得满意解。     

多约束QoS动态多播路由算法

YAM和QoSMIC是支持QoS动态多播路由算法,允许多播组成员动态地加入/退出,同时为接收方提供多个可选择的多播接入路径,以满足不同应用的QoS需求。该文在分析这些算法的基础上,研讨了具有延迟、延迟抖动、带宽和代价等多约束QoS的多播路由问题,描述了一种适应于研究QoS多播路由的网络模型,提出了一种具有多约束QoS的动态多播路由算法(MQDMR),MQDMR试图有效地减少生成多约束QoS的多播树的开销。在MQDMR中,一个多播组成员能动态地加入/退出一个多播会晤,且不干扰现有的多播树。仿真实验结果表明,MQDMR比YAM和QoSMIC具有较小的延时和较少的代价。