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

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

自动布局布线程序

功述描述了用于规划芯片的自动布局布线程序。其特点是在单元电路版图实现之前进行布局布线以及布线是在单元内部进行，不存在专门的布线通道。这种布图模式，以多端网连接模型作为布局布线的连接模型，并以布线均匀作为主要的目标函数。 整个程序模块分为矩阵网格规划和布局，总体布线，端口分配三部分。在布局中采用最小切割算法。初始布线以布线均匀，连线长度最短为目标，并采用一个基于布线均匀的“重心“算法。通过再布线和通     

面向区域布线的层次式PB角勾链版图数据结构

无网格区域布线具有存储量小、布通率较高、易实现混合设计规划布线并可解决串扰问题等优点,无网格区域布线算法中,找到路径后对底层图数据库的修改时间在整个算法运行时间中占很大比例,因此,操作简便、快捷的版图数据结构对于网格区域布线算法非常重要,目前无网格区域布线算法中应用最广泛的版图数据结构是矩形勾链,其点查找和模块插入操作的复杂度均匀Ｏ（Ｎ＾１／２）,文中提出一种新型的结合了Ｂｉｎ结构与梯形角勾链结构     

考虑布线资源松弛的X结构Steiner最小树算法

为了进一步考虑X结构,并充分利用障碍内可用布线资源,文中提出考虑布线资源松弛的X结构Steiner最小树算法.为了能够求解离散问题,在粒子的更新操作中引入交叉算子和变异算子.通过构建查找表,为整个算法流程提供快速的信息查询.提出角点选取策略,通过引入一些障碍角点,使粒子满足约束.最后构建精炼策略,进一步提高最终布线树的质量.实验表明,文中算法充分利用障碍内可用布线资源,有效缩短总布线长度,取得较佳的总布线长度.     

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

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

用于高效布线的拓扑变换

本文介绍一种独特的以拓扑为基础的非最短距离布线算法。这种算法既提供最大的布通率,又提供最小的通路使用率。算法以印刷电路(PC)布线问题有效子集的拓扑变换为基础:一条宽通道包含双列直插式封装(DIP)的整个行及里面的所有线路。变换不必考虑布线时详细的通道形式。布线问题被转换成一种网格的排列。排列与回找相结合,产生高效的布线算法。回找是在平面上进行的。     

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

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

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

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

DrPlace:基于深度学习的可布线性驱动布局算法

在集成电路物理设计的布局阶段,针对基于深度学习的布局算法结果可布线性较差的问题,在开源的DREAMPlace算法的基础上提出并实现了一种基于深度学习的可布线性驱动布局算法DrPlace.算法模型在总体上设计并实现了布局器的整体框架,集成了基于深度学习的可布线性驱动总体布局、可布线性驱动的合法化和详细布局.总体布局过程中,在目标函数中加入了引脚密度函数,并实现了基于GPU的引脚密度的关键内核.在ISPD2011和DAC 2012布局实例上的实验结果表明,该算法与DREAMPlace相比在可布线性上获得了提升,且在运行时间、线长和可布线性方面均优于传统的可布线性驱动布局算法.     

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

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

交互式逻辑图布线算法及其在VLAB中的应用

本文以交互式虚拟实验室VLAB的设计和实现为背景，解决了逻辑图交互绘制过程中各个逻辑图元的布线连接问题，在遵照逻辑图布线基本原则的基础上，提出由自动布线、通道扩展和布线优化三部分联合构成的交互式逻辑图布线算法，并对试验结果进行了评价。     

WDM网络中支持多优先级动态业务的路由算法

路由问题始终是WDM网络中的一个核心问题。基于多优先级动态业务,对不同等级的业务设置不同的瓶颈门限,产生不同的禁用链路集,当一个连接请求到达时,根据其优先级在网络中将相应的禁用链路删去,在剩余网络中寻求最优路由,从而获得一种新的路由算法——链路限制法。算法能缓解通信链路中的“瓶颈”,同时保证高优先级的连接请求具有较好的传输指标。     

二维网格中基于最小通路区的自适应和最小容错路由算法

网格结构是并行与分布式处理中最流行的一种网络拓扑结构。在存在故障的情况下，如何设计具有最优性的容错路由算法一直是研究的热，点问题。本文研究了采用故障块模型的二维网格的最小路由问题，提出存在最小通路的一个充分必要条件。基于最小通路区（RMP）的概念，提出一种自适应的最小容错路由算法。如果源节点和目的节点之间存在最小通路区，则在最小通路区中进行自适应最小容错路由；反之，则采用多阶段最小容错路由。主要思想就是在存在故障的情况下，尽量保证路由算法能走最短路径。因为只要求知道每个节点的局部信息，故算法是分布式的。     

Routing in Polygons Without Rectilinearly Visible Corners

In this paper we present an algorithm for the routing problem in a routing region which is bordered by a simple polygonal line, such that there are no rectilinearly visible corners. The routing problem consists in finding pairwise edge-disjoint paths in the grid for the nets connecting some given pairs of boundary vertices. Whenever a solution exists our algorithm finds it in time O(U log²U), where U is the size of the boundary. This is a generalization of the algorithm for rectangle routing by Mehlhorn and Preparata (1986, J. Assoc. Comput. Mach.33, 60-85), which up to now has been the only method with sublinear running time in respect of the routing area.     

A MANET accessing Internet routing algorithm based on dynamic gateway adaptive selection

Based on the study on communication situation of mobile ad hoc network (MANET) accessing Internet and taking the gateway important function of accessing network into account, a MANET accessing Internet routing algorithm based on dynamic gateway adaptive selection (MRBDAS) is presented. It considers candidate gateways’ connecting degree, load degree, residual energy, and movement rate synthetically and uses the idea of group decision-making method for reference. The algorithm employs the methods of multipaths and query localization technique based on old path information to maintain routing adaptively. Compared with the existing accessing routing algorithm based on dynamic gateway, the algorithm demonstrates in its simulations that by bringing dynamic gateways colony function, the MRBDAS can improve network throughput, reduce average transmission delay of data packets and routing overhead, and prolong accessing network life. The validity of MRBDAS has been proven.     

A MANET accessing Internet routing algorithm based on dynamic gateway adaptive selection

Based on the study on communication situation of mobile ad hoc network (MANET) accessing Internet and taking the gateway important function of accessing network into account, a MANET accessing Internet routing algorithm based on dynamic gateway adaptive selection (MRBDAS) is presented. It considers candidate gateways’ connecting degree, load degree, residual energy, and movement rate synthetically and uses the idea of group decision-making method for reference. The algorithm employs the methods of multipaths and query localization technique based on old path information to maintain routing adaptively. Compared with the existing accessing routing algorithm based on dynamic gateway, the algorithm demonstrates in its simulations that by bringing dynamic gateways colony function, the MRBDAS can improve network throughput, reduce average transmission delay of data packets and routing overhead, and prolong accessing network life. The validity of MRBDAS has been proven.     

移动传感器网络中基于概率分布的动态的低冗余路由算法

受到节点移动、有限的存储空间及能量等因素的影响,容延迟移动传感器网络在将数据汇聚至Sink过程中伴随着较高的丢包率与数据冗余,传统的确定性路由机制难以应用。对此,利用节点在一定数量时间槽内与Sink点连通的概率分布,提出了一种动态的、分布式的路由算法。该算法充分利用了节点的移动性,使网络在保持低冗余的同时,具有较高的数据送达率。实验结果表明,在节点数多、移动速度快、节点传输距离大的网络中,该算法更具优势。     

An Adaptive Routing Algorithm for WK-Recursive Topologies

This paper presents an easy and straightforward routing algorithm for WK-recursive topologies. The algorithm, based on adaptive routing, takes advantage of the geometric properties of such topologies. Once a source node S and destination node D have been determined for a message communication, they characterize, at some level l, two virtual nodes and that respectively contain S but not D and D but not S. Such virtual nodes characterize other (where is the node degree for a fixed topology) virtual nodes of the same level that contain neither S nor D. Consequently, it is possible to locate triangles whose vertices are these virtual nodes with property to share the same path, called the self-routing path, directly connecting to . When the self-routing path is unavailable to transmit a message from S to D because of deadlock, fault, and congestion conditions, the routing strategy can follow what we call the triangle rule to deliver it. The proposed communication scheme has the advantage that 1) it is the same for all three conditions; 2) each node of a WK-recursive network, to transmit messages, does not require any information about their presence or location. Furthermore, this routing algorithm is able to tolerate up to faulty links. Received: July 19, 1998; revised May 17, 1999     

基于参考能量的无线传感器网络连通支配集算法研究

无线传感器网络中通常利用连通支配集形成虚拟骨干网以进行分层次的路由.现有算法所得到的连通支配集或者只适用于图的连通度比较大的情况,或者没有考虑支配节点的能量等特性.本文设计了一种基于参考能量的连通支配集构造算法,在考虑支配节点的剩余能量的基础上生成连通支配集,使获得的连通支配集不仅适合于各种连通度的拓扑情况,而且具有更好的能量性能.     

一种有效的簇集主干点P2P网络结构模型

文中提出一种有效的簇集主干点P2P网络结构模型，克服了非结构化P2P系统中存在的扩展性不好和搜索效率不高的问题。该模型根据拓扑优先级把对等点聚类成簇形层级结构，从CN中选出GN充当簇的中心和服务提供者，实现定位查询和信息交互。为了衡量由主干点组成的骨干网的路由，文中设计了一种适用于应用级广播协议的路由算法。实验利用Java平台和仿真工具模拟实时网络环境，比较层级结构结合主干点骨干协议的系统模型和Gnuteua系统的代价。实验结果证明这种层级结构的簇集P2P模型，加上骨干网协议支持，在系统性能和可扩展性上带来了明显地提升，并可在大范围非结构化的P2P环境中得到应用推广。