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

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

一种基于通孔数最小化的多层通道布线算法

该文提出了一种基于通孔数量小化的多层通道布线算法，算法采用非预留层模，首先根据线网之间的位置关系利用模拟退火算法将各线网合理地分配到对应的布线层中去，然后利用遗传算法得到相关布线层中线网的最佳布线顺序向量，最的根据得到的顺序向量利用“沉积法”将各线网布于合理的通道上，该算法克服了传统通孔优化算法中原始布线对优化结果的不利影响，使通孔的优化达到很好的效果。     

一个基于无约束通孔优化的双层布线算法—FOREST

FOREST是一个立足于无约束通孔优化的新的布线算法,它从总体上将布线过程分为拓扑布线和物理布线两部分,并把两者视为相互联系的整体。作为一种启发式算法,它试图综合考虑布通率、布线空间、通孔数和连线总长等因素,算法打破横竖严格分层的限制,并允许不同层线段重叠,FOREST算法适用于一般的通道布线,特别是不规则边界的通道,一些实例的试算表明,FOREST算法具有较好的布线效果,尤其在减少通孔数上,取得了比较满意的结果。     

通道布线的神经网络优化算法

介绍通道布线的思想，给出相应的形式化描述，提出一种神经网络求解算法，该算法以总线长最短，轨道数最少为优化目标，以满足水平，垂直制约为约束条件，通过把问题映射为神经网络模型，建立了问题的能量函数，用均场退火方程迭代求解，实验结果是令人满意的。     

一种新的L－型通道区布线算法

本算法把Ｌ－通道区分成两个三边通道,从分析割值出发,确定Ｌ－型通过的初始宽度。为达到总体布线最优,采用迭代法和改进的“贪婪,算法,交替实现水平和垂直通道的布线。     

一种基于非严格预留层的双层通道布线算法

本文提出一种基于非严格预留层的双层通道布线算法，算法通过确定较好的布线顺序，在基本上不增加空间的情况下，有效地减少GP线与通孔。实验结果证明，该算法能得到较好的布线结果。     

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

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

一种在VLSI电路物理设计中减小串扰的优化算法

通过研究调整线段和线间距对串扰的影响,提出了一种在布线时通过采线段摄动和压缩线间距的措施来减小串扰的优化算法,计算机仿真结果表明,该算法能有效地减少芯片中的串扰,此外,可预期算法应用于布线区域不规则的情形。     

变形网格结构的快速评估算法

随着超大规模集成电路技术的进步，集成电路的复杂性在急剧增加。分级设计和IP(知识产权)重用技术变得极为重要。因此，面向宏模块布局的布图规划/布局技术在近10年来成为VLSI设计自动化领域的研究热点。即使简单的矩形放置问题(将n个矩形放置在一个平面的矩形区域内，目标是     

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

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

行路由PEA广度贪心调度映射算法

粗粒度可重构单元阵列硬件任务的贪心映射是可重构计算要解决的核心问题。不同的阵列具有不同的硬件约束条件,针对行路由粗粒度可重构单元阵列提出一种广度贪心映射算法BGMA（Breadth Greedy Mapping Algorithm）。该算法首先从第一个节点开始依次扫描,如果节点满足条件则将其映射到PEA上,当遇到不满足映射条件的节点时,该算法将跳过该节点继续寻找满足约束条件的节点进行映射,通过与广度不贪心映射算法BNGMA（Breadth No Greedy Mapping Algorithm）相比较,BGMA的[N1]平均减少了35.1%（PEA6×6）和54.8%（PEA8×8）,[N2]平均减少了35.6%（PEA6×6）和54.6%（PEA8×8）,[CCON]平均减少了15.7%（PEA6×6）和26.2%（PEA8×8）,[TTOTAL]平均减少了20.2%（PEA6×6）和32.1%（PEA8×8）。实验结果表明了贪心策略在映射算法中的重要性。     

基于路径探索的车载自组网贪婪路由算法

为了提高城市中车辆间信息的传输效率，实现车辆间的信息共享，针对目前车载自组网（VANET）中基于地理位置转发的多跳单播路由算法没有考虑城市场景的特殊性，不能很好地适应城市中车辆的高度动态性，使车辆之间的数据包可能在错误的路径上传播，造成丢包率较高、时延较长的问题，提出了一种新的基于路径探索的贪婪路由算法。首先，以数据包传输时延为标准，运用人工蜂群算法对数字地图规划出的多条路由路径进行探索。其次，优化数据包在车辆之间的多跳转发方式。仿真结果表明，与贪婪周边无状态路由（GPSR）协议和最大持续时间最小角的GPSR（MM-GPSR）改进算法比较，在最好情况下，所提算法的数据包到达率分别提高了13.81%和9.64%，而该算法的数据包平均端到端时延分别降低了61.91%和27.28%。     

Placement and routing for logic schematics

This paper deals with the automatic generation of logic schematics. Practical aims are the reduction of input effort, the efficient use of memory space and the development of tools for translating machine codes implemented in programmable binary control devices back to graphical representations. The emphasis lies on the determination of such sequences of logic units that result in a minimal number of line intersections. A new heuristic algorithm that decreases the intersection number successively is proposed. First results of computer experiments are presented.     

无线传感器网络中分段贪婪地理路由算法

针对基于地理位置的无线传感器网络路由中存在的路由空洞问题,提出一种新的路由模式:分段贪婪路由.在该模式中,整个路由过程被中间节点序列划分为若干段,在每一段上仅应用贪婪转发策略.为确定合适的中间节点,给出一种基于递归探测的方法,并以GPSR算法为基础探测路由构造了SGR算法.仿真实验表明,在存在不同类型、大小、数量路由空洞的网络环境中,SGR算法均能以较小的探测开销获得接近最优的路由路径,尤其是凹空洞存在的情况.     

A parallel routing algorithm on circulant networks employing the Hamiltonian circuit latin square

Double-loop [J. Bermond, F. Comellas, D. Hsu, Distributed Loop Computer Networks: A Survey, J. Parallel and Distributed Computing, Academic Press, 24 (1995) 2-10] and 2-circulant networks (2-CN) [J. Park, Cycle Embedding of Faulty Recursive Circulants, J. of Korea Info. Sci. Soc. 31 (2) (2004) 86-94] are widely used in the design and implementation of local area networks and parallel processing architectures. In this paper, we investigate the routing of a message on circulant networks, that is a key to the performance of this network. We would like to transmit 2k packets from a source node to a destination node simultaneously along paths on G(n; ±s₁, ±s₂, … , ±s_k), where the ith packet traverses along the ith path (1 ? i ? 2k). In order for all packets to arrive at the destination node quickly and securely, the ith path must be node-disjoint from all other paths. For construction of these paths, employing the Hamiltonian circuit latin square (HCLS), a special class of (n × n) matrices, we present O(n²) parallel routing algorithm on circulant networks.     

A generalized greedy routing algorithm for 2-connected graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent, which makes this scheme infeasible in some applications.The essence of the geometric routing is the following: When an origin vertex u wants to send a message to a destination vertex w, it forwards the message to a neighbor t, solely based on the location information of u,w and all neighbors of u. In the greedy routing scheme, the decision is based on decreasing distance. For this idea to work, however, the decision needs not be based on decreasing distance. As long as the decision is made locally, this scheme will work fine.In this paper, we introduce a version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance, a generalized greedy routing algorithm uses other criteria to determine routing paths, solely based on local information. We present simple generalized greedy routing algorithms based on st-coordinates (consisting of two integers between 0 and n−1), which are derived from an st-orientation of a 2-connected plane graph. We also generalize this result to arbitrary trees. Both algorithms are natural and simple to be implemented.     

基于虚拟坐标系统的无线网络地理路由算法

针对地理路由算法中的路由空洞问题,通过引入虚拟坐标的方式,提出了一种新颖的无线网络地理路由算法——双重贪婪算法(DGA)。根据网络的拓扑结构信息,DGA为每个节点分配虚拟坐标,在基于真实地理位置的贪婪算法遇到路由空洞时,以基于虚拟坐标系统的贪婪算法作为恢复机制,从而保证路由算法的收敛性。DGA克服了GPSR等传统地理路由算法只能适用于理想的单位圆图(UDG)的缺点,能够适用于更加真实的无线网络模型。仿真实验验证了DGA高效的路由性能及良好的扩展性。     

A parallel routing algorithm on recursive cube of rings networks employing Hamiltonian circuit Latin square

Recursive cube of rings (RCR) networks [Y. Sun, P. Cheung, X. Lin, Recursive cube of rings: a new topology for interconnection networks, IEEE Trans. Parallel Dist. Syst. 11 (3) (2000) 275-286] can be widely used in the design and implementation of parallel processing architectures. In this paper, we investigate the routing of a message on RCR networks, that is a key to the performance of this network. We would like to transmit k+1 packets from a source node to a destination node simultaneously along paths on RCR networks, the ith packet will traverse along the ith path (1?i?k+1). In order for all packets to arrive at a destination node quickly and securely, the ith path must be node-disjoint from all other paths. For construction of these paths, employing Hamiltonian circuit Latin square (HCLS), we present O(n²) parallel routing algorithm on RCR networks.     

基于QoS的单播源路由算法研究

保证服务质量的QoS路由是网络中解决QoS问题的一项关键技术,QoS路由的主要目标是为接入的业务选择满足服务质量要求的传输路径,同时保证全网资源的有效利用。围绕度量参数选择问题、寻路问题这两个方面,给出了一个基于源地址的单播QoS次优解路由算法,并对其正确性进行了证明。     

基于地理路由协议GPSR的研究和改进

分析了地理路由协议GPSR的特性,并针对GPSR协议在遇到空洞时,贪婪算法失效而出现的消耗过多能量的情况,提出了一种简易的能量改进策略,以减少由于GPSR协议中周围模式引起的过多的跳跃。基于这种策略,提出了一种改进的地理路由协议。在路由子集节点被动获得的局部网络信息的帮助下,此协议能裁减路由线路,以减少由GPSR的周围模式引起的很大一部分跳跃。