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

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

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

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

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

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

消除拥挤的多层总体布线新流程

提出一种在布线前进行层分配的总体布线算法,基于一个多层布线的新流程,使用包含线网所有端点的边界盒来估计线网拥挤度,并基于拥挤度均匀的目标把线网分配到不同层对上.该算法已经实现并进行了测试,实验结果证明了其有效性.     

一种通孔最小化的三层通道布线算法

本文提出的连通孔最小化的三层通道布线算法,根据线网的接点位置建立线网分层图,并对此图进行三着色,确定出初始布线集和分拆线网集,通过引进线网次序图、压缩空段长度、填充原则和逐步排障法等,将初始布线集和拆网集的线网分配到相应的走线道上.实现线网的互连.本算法已用PASCAL语言编程,并在XT/286机上实现.结果表明,该算法不仅使通孔数大大减少,而且有些例子的走线道数也较一般布线法少.     

GHz零时滞时钟树物理布图的虚拟通道布线算法

随着集成电路技术的发展和GHz频率的应用需求，已有的基于线长或RC延迟模型的时钟树布图算法已不能适用．针对GHz频率宏模块中时钟树的平面布图，依据流水线技术，提出一种虚拟通道布线算法；根据时钟树的拓扑结构，分别进行粗略布线和虚拟通道内的布线调整，完成时钟树的平面布线．该算法在开发软件原型ClockStar中得以应用．     

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

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

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

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

一种分级布线方案的设计与实现

本文从分层与布线关系的角度出发,分析了传统布线方式的不足之处,提出了一种多层印制板自动布线的分级布线方案。     

基于延迟合并嵌入的带障碍的时钟树布线算法

提出一种在带障碍情况下,基于延迟合并嵌入方法的时钟树构建算法,并在时钟树构造过程中引入了轨迹图以保证布线可以绕过障碍．该算法以已知障碍为布线约束,首先自底向上计算时钟树内部节点的可能位置,然后自顶向下确定每个节点的确切位置．实验结果表明,该算法能够正确、有效地实现有障碍存在时的时钟树布线,线长优化率超过7％．     

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

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

Priority-Based Routing Resource Assignment Considering Crosstalk

Crosstalk has become one of the most critical concerns in very deep sub-micron era. This paper deals with the problem of crosstalk mitigation at both methodological and algorithmic levels. Noting that intermediate operations between global routing and detailed routing are very effective in crosstalk estimation and reduction, the authors propose to incorporate several intermediate steps that are separated in traditional design flow into an integrated routing resource assignment stage, so that the operations could easily cooperate to fully exert their power on crosstalk reduction. An efficient priority-based heuristic algorithm is developed, which works slice by slice. Crosstalk avoidance, and many other aspects that are critical in routing practice including congestion, vias, layer preference, etc., are taken into account. A track reservation strategy is adopted in the algorithm framework to compensate the undesired effects caused by sequential routing. Experimental results on a series of ISPD98 and industrial benchmarks show that the proposed approach is able to reduce capacitive crosstalk by about 70% on average without compromising completion ratio compared with a previously reported graph based algorithm, demonstrating the advantages of the approach.     

基于量子遗传算法的QoS路由算法

多约束的QoS路由问题是NP完全问题.量子遗传算法是基于量子计算理论的新遗传算法,具有种群多样性、收敛速度快和全局寻优的特点.将量子遗传算法引入多约束QoS路由计算,提出了一种基于量子遗传算法的QoS路由算法,给出了算法实现的方法和具体流程.实验结果表明,通过该算法得到的QoS路由不但能满足QoS约束要求,同时可以均衡链路负载,减少路由拥塞.     

拥挤度驱动的总体布线层分配算法

针对多层布线问题，提出以拥挤度为驱动目标，完成布线资源的合理分配，同时达到布线层资源占用少和通孔数少等优化目标的层分配算法．首先采用启发式方法获得初始分配方案，然后通过模拟退火技术优化分配结果，最后采用试探策略优化层资源占用．工业实验数据表明，该算法能够实现线网层合理分配，获得满足拥挤度的优化解．     

基于隶属云蚁群算法的长链型无线传感器网络路由优化

针对用于监测系统的长链树状无线传感器网络数据传输的实时性和高可靠性等要求,并考虑到近汇聚节点处易形成"漏斗"等问题,本文提出用基于云模型的多蚁群算法对无线传感器网络路由进行跨层优化的设计思想。算法通过种群间信息素的相互作用并行地完成路径的搜索并及时对信息素进行更新,在搜索的过程中把节点的时延、跳数、负载及分组成功率作为路径的启发值,利用多规则云发生器对更新策略中的信息素残留系数和信息素强度进行自适应调整。仿真结果表明,该路由算法能够保证无线传感器网络具有很强的实时性、可靠性及鲁棒性,实现了网络的负载平衡及拥塞控制机制。     

印制板布线的最佳路径快速通道分配算法

针对目前面向线网布线方法的某些不足,本文提出一种具有整体布线思想的最佳路径快速通道分配方法:对给定的线网按照一定的走线模式,根据代价函数,求出其最佳通道分配。它尤其适用于对连线长度有严格要求的超高速电路的布线问题。     

Bi-LCQ: A low-weight clustering-based Q-learning approach for NoCs

Network congestion has a negative impact on the performance of on-chip networks due to the increased packet latency. Many congestion-aware routing algorithms have been developed to alleviate traffic congestion over the network. In this paper, we propose a congestion-aware routing algorithm based on the Q-learning approach for avoiding congested areas in the network. By using the learning method, local and global congestion information of the network is provided for each switch. This information can be dynamically updated, when a switch receives a packet. However, Q-learning approach suffers from high area overhead in NoCs due to the need for a large routing table in each switch. In order to reduce the area overhead, we also present a clustering approach that decreases the number of routing tables by the factor of 4. Results show that the proposed approach achieves a significant performance improvement over the traditional Q-learning, C-routing, DBAR and Dynamic XY algorithms.     

Fuzzy-based Adaptive Routing Algorithm for Networks-on-Chip

In this paper, we propose two adaptive routing algorithms to alleviate congestion in the network. In the first algorithm, the routing decision is assisted by the number of occupied buffer slots at the corresponding input buffer of the next router and the congestion level of that router. Although this algorithm performs better than the conventional method, DyXY, in some cases the proposed algorithm leads to non-optimal decisions. Fuzzy controllers compensate for ambiguities in the data by giving a level of confidence rather than declaring the data simply true or false. To make a better routing decision, we propose an adaptive routing algorithm based on fuzzy logic for Networks-on-chip where the routing path is determined based on the current condition of the network. The proposed algorithm avoids congestion by distributing traffic over the routers that are less congested or have a spare capacity. The output of the fuzzy controller is the congestion level, so that at each router, the neighboring router with the lowest congestion value is chosen for routing a packet. To evaluate the proposed routing method, we use two multimedia applications and two synthetic traffic profiles. The experimental results show that the fuzzy-based routing scheme improves the performance over the DyXY routing algorithm by up to 25% with a negligible hardware overhead.