一个多层VLSI/PCB布线通孔最小化的神经网络方法

本文提出了一个基于Ｈｏｐｆｉｅｌｄ网络的ＶＬＳＩ／ＰＣＢ多层布线中的有约束通孔最小化方法。在线段交叠图模型的基础上，提出了相邻矩阵，交叠矩阵，定层矩阵等概念，利用换位矩阵，将问题映射为相应的神经网络，并构造了该问题的能量函数，从而解决了多层布线的分层及通孔最小化问题，新算法还解决了多层布线分层的管脚约束和相邻约束问题。     

一个可处理多种约束的多层布线通孔最少化算法

本文分析了常用的VLSI多层布线图模型线段－相交图SCG的局限性,提出了对SCG模型的修正,并基于该模型用模拟退火算法来解决通孔最少化问题,算法可以处理严格和非严格分层的布线,并考虑了许多物理约束的处理方法.实验证明算法可以较大程度地减少通孔.     

一种基于神经网络的多层通孔最小化方法

在多层布线的线段－相交图模型基础上，利用Ｈｏｐｆｉｅｌｄ人工神经网络理论，通过反通孔数目这个优化目标与Ｈｏｐｆｉｅｌ网络能量函烽相联系的方法来解决多层布线通孔最小化问题。算法考虑了许多来自实际的约束。     

一个VLSI三层布线通孔最少化的启发式算法

该文在三层布线的线段-相交图模型基础上,提出了一个启发式算法来解决VLSI三层布线通孔最少化问题,该算法通过总体优化和局部优化两个阶段对三层布线进行通孔优化。算法考虑了实际约束的处理方法,并进行大量的布线实例验证。     

性能驱动的多层布线有约束分层及其神经网络求解方法

介绍了性能驱动多层布线有约束分层的思想,给出了相应的形式化描述,提出了一种神经网络求解算法．算法以通孔最少为优化目标,以通孔能够连接任意两层之间的线段、不同线网的线段不能在同一层上相交和一线网的通孔不能在它所穿过的层上与其它线网相交为约束条件．算法通过换位矩阵把问题映射为神经网络,并建立了问题的能量函数,再用均场退火方程迭代求解．每条线段只能分配到一层上的约束用神经元归一化的方法处理．另外,算法不仅还能够考虑线网的时延关键性,以进一步减少系统时间延迟,而且还可以防止相互串扰的线网分在同一层上．     

一种用于三层布线的分层算法

随着VLSI/LSI技术的发展,多层布线已能够实现。互连网络的分层问题就是要使得互连网络所需的通孔数最少。在通孔最小化问题中,如果布图拓扑逻辑已给出,这类问题被称为受限的通孔最小化(CVM)问题。本文针对三层布线中的CVM问题提出了一种分层算法,使得布图所需的通孔数最小化。应用此算法能获得比文献中所述更少的通孔数。     

设计规则驱动的多层布线算法

迷宫算法是集成电路两端线网优化布线问题的经典算法。多层布线受复杂版图设计规则约束．简单直接应用迷宫布线算法，或者无法获得优化的结果，或者无法满足设计规则。文章分析了迷宫算法特性与局限．提出基于群组图的多层迷宫算法，圆满地解决了上述问题。     

一个基于人工神经网络的通孔最少化方法

本文在布线的相交图模型基础上,利用离散型的Hopfield网络解决了相交图的最大切割问题,从而解决了双层布线的分层及通孔最少化问题。新算法考虑了许多来自实际问题的约束,并对大量的布线实例进行了验证。     

超平面概略布线算法的研究

本文提出体现多层布线内在本质约束的新模型：超平面布图模型及超平面概略布线算法．该算法以全新的逆向删冗策略成功地解决了布线线序问题，使线网布线真正达到并行处理；基于总体分析方法，以布线层数和通孔最少为目标，通过动态地分析线网间相互位置关系，全局考虑地释放各线网占据的不合理布线资源，使布线过程避免了迭代，以较高处理效率获得高精度的解．     

超平面布线

本文大胆打破了传统通道模型的束缚,建立了一个能更好体现多层布线内在本质约束的新模型：超平面布图模型,在该模型下提出了超平面布线算法。该算法以全新的逆向删冗策略成功地解决了布线线序的问题,使线网布线真正达到了并行处理。算法遵循了王守觉先生关于总体分析的方法作为解决超平面布线问题的指导思想,以布线层数最少化和通孔最少化为目标,通过动态地分析线网间的相互位置关系,全局考虑去释放各线网占据的不合理布线资源     

Three-step pin assignment algorithm for building block layout

A new pin assignment algorithm is proposed which can be used in floorplanning and building block layout to minimise the total wiring length and channel area while satisfying the minimum distance constraint among pin positions on the block boundary. This algorithm can be used in floorplanning in which block shapes are iteratively modified by the channel density obtained as a result of global routing. The proposed pin assignment algorithm occurs in three steps: approximate pin assignment, global routing and detailed pin assignment. Experimental results were obtained using MCNC placement and floorplanning benchmark examples.<>     

基于蚁群算法的自适应QoS路由优化

Internet网络规模的迅速增长和网络技术的不断完善，使得如何在满足QoS（quality of service）要求下进行路由选择成为路由算法研究的重要方向。提出了一种多约束条件下的自适应蚁群算法，该算法基于目标函数的信息素分配策略来自适应地调整蚂蚁的搜索行为，使多约束QoS路由优化问题得到了很好的解决。     

Routing and wavelength assignment of scheduled lightpath demands

We present algorithms that compute the routing and wavelength assignment (RWA) for scheduled lightpath demands in a wavelength-switching mesh network without wavelength conversion functionality. Scheduled lightpath demands are connection demands for which the setup and teardown times are known in advance. We formulate separately the routing problem and the wavelength assignment problem as spatio-temporal combinatorial optimization problems. For the former, we propose a branch and bound algorithm for exact resolution and an alternative tabu search algorithm for approximate resolution. A generalized graph coloring approach is used to solve the wavelength assignment problem. We compared the proposed algorithms to an RWA algorithm that sequentially computes the route and wavelength assignment for the scheduled lightpath demands.     

A Tabu search algorithm for static routing and wavelength assignment problem

Static routing and wavelength assignment (RWA) is usually formulated as an optimization problem with the objective of minimizing wavelength usage (MWU). Existing solution methodologies for the MWU problem are usually based on a two-step approach, where routing and wavelength assignment are done independently. Though this approach can reduce computational cost, the optimality of the solution is compromised. We propose a novel tabu search (TS) algorithm, which considers routing and wavelength assignment jointly without increasing the computational complexity. The performance of the proposed TS algorithm is compared with the integer linear programming (ILP) method, which is known to solve the MWU to optimality. The results for both small and large networks show that our proposed TS algorithm works almost as well as the ILP solution and is much more computationally efficient.     

Solving the routing and wavelength assignment problem in WDM networks for future planning - [Topics in optical communications]

In this article we define and analyze the routing and wavelength assignment problem by applying a virtual topology for both the optical network and the light paths. We introduce our developed algorithm to solve offline RWA problem. First the light path requests are constrained to repeated uniform distributed traffic. The reason is that this constraint permits us to study and analyze the behavior of the RWA problem. In addition, this constraint could be used as a benchmark to compare different algorithms. Then we relax the requests constraint to be non-uniform traffic. We show that the maximum number of assigned wavelengths depends on the number of traversed links, not on the shortest path length. Theorems are derived with proof to justify our algorithm. The effect of adding supplementary links to the WDM optical network is also explained to show how this approach could be used in the future planning for online operation. Finally, the result shows significant different in the number of wavelengths used compared to a recent backbone implemented network.     

Hierarchical channel router

The channel routing problem is a special case of the wire routing problem when interconnections have to be performed within a rectangular strip having no obstructions, between terminals located on opposite sides of the rectangle.We present here a new channel routing algorithm, based on reduction of the problem to the case of a (2 × n) grid and on consistent utilization of a ‘divide-and-conquer’ approach. For the current implementation of the algorithm, the running time is proportional to N 1 n log(m) where N is the number of nets, n the length of the channel (number of columns) and m the width of the channel (number of tracks).Traditional technological restrictions are assumed, i.e., net terminals are located on vertical grid lines, two wiring layers are available for interconnections — one layer is used exclusively for vertical segments, another for horizontal and vias are introduced for each layer change.This algorithm consistently outperforms several known routers in quality of wiring. We tested the algorithm on several benchmark problems. One of them — Deutsch's ‘difficult example’ — was routed with only 19 horizontal wiring tracks (the absolute minimum for this case), whereas all other known routers required 20 or more tracks.     

基于强化学习的光传送网路由波长优化

针对光传送网中动态业务的路由和波长问题,提出一种基于强化学习的深度路由波长分配算法DeepRWA。算法基于软件定义网络架构,通过强化学习灵活地调整控制光传送网,实现光网络路由波长分配策略优化。针对路由选择问题,结合链路上的波长使用情况,使用A3C算法选择合适的路由,使得阻塞率最小;针对波长分配问题,使用首次命中算法选择波长。考虑阻塞率、资源利用率、策略熵、价值损失、运行时间及收敛速度等多个指标,利用14节点NSFNET网络拓扑仿真实验。结果表明:当信道中包含18个波长时,与传统KSP-FF算法相比,所提出的路由波长分配算法的阻塞率降低了0.06,资源利用率提高了0.02,但运行时间有增加;在波长数超过45以后,与传统KSP-FF算法相比,所提算法保持阻塞率和资源利用率的同时,运行时间开始降低;当信道中包含波长数为58时,与传统KSP-FF算法相比,所提算法运行时间减少了0.07 ms。由此可见,提出的算法使路由选择和波长分配得到了优化。     

Layer assignment for printed circuit boards and integrated circuits

The layer assignment problem arises in printed circuit board (PCB) and integrated circuit (IC) design. It involves the assignment of interconnect wiring to various planes of a PCB or to various layers of interconnect wires in an IC. This paper reviews basic techniques for layer assignment in both PCBs and ICs. Two types of layer assignment are considered: (1) constrained layer assignment in which routing of interconnections is given and the objective is to assign wires to specific layers, and (2) unconstrained, or topological, layer assignment, in which both the physical routing of interconnections and assignment of the wires to layers is sought. Various objective functions, such as via minimization and minimization of signal delays through interconnect lines are discussed     

QoS aware traffic grooming and integrated routing on IP over WDM networks

In this article, we consider traffic grooming and integrated routing in IP over WDM networks. The challenges of this problem come from jointly considering traffic grooming, IP routing, and lightpath routing and wavelength assignment (RWA). Due to the high bandwidth of optical fiber, there exists a mismatch between the capacity needed by an IP flow and that provided by a single lightpath. Traffic grooming is therefore used to increase the network utilization by aggregating multiple IP flows in a single lightpath. However, traffic grooming incurs additional delays that might violate Quality-of-Service (QoS) requirements of IP users. In this work, the tradeoff between traffic grooming and IP QoS routing is well-formulated as a mixed integer and linear optimization problem, in which the revenue from successfully provisioning IP paths is to be maximized. Problem constraints include IP QoS, routing, optical RWA, and the WDM network capacity. We propose a novel Lagrangean relaxation (LGR) algorithm to perform constraint relaxation and derive a set of subproblems. The Lagrangean multipliers are used in the proposed algorithm to obtain a solution in consideration of grooming advantage and resource constraints simultaneously. Through numerical experiments and comparisons between the proposed algorithm and a two-phase approach, LGR outperforms the two-phase approach under all experimental cases. In particular, the improvement ratio becomes even more significant when the ratio of IP flow to the wavelength capacity is smaller.