【作者】 庄昌文；

【导师】 虞厥邦； 黄劲；

【作者基本信息】 电子科技大学 ， 电路与系统， 2001， 博士

【摘要】 我们首次将蚁群（ACS-Ant Colony System）算法应用到大规模集成电路的物理设计中，具体实现了一个开关盒布线算法，取得了较遗传算法、模拟退火等算法为优的结果。开关盒布线问题是物理设计后期的一个NP-完全问题，因为它最终决定线网的实际走线，对整个布图过程起着至关重要的作用。此前，ACS算法已成功地运用到TSP问题和计算机通信等领域中，受此算法的启发，我们在ACS协同学习的基础上融进了协同工作的机制，得到一个增强了的ACS（IACS），并应用到了开关盒布线中。在开关盒布线中，各蚁群在各自线网引脚的牵引下，在停等机制的协调下，能有效地避免它们在争用布线区域中引起的冲突，使算法能快速将各线网布通，同时优化了线长和通孔数。 我们运用JAVA语言实现了一个采用Agent技术的并行布线系统。由于计算机网络（尤其是Internet和Intranet）已逐渐成为各行各业计算机应用的基础设施，高效地利用网络中的计算资源是所有算法设计者提高算法性能的一个有力途径，本文结合计算机界热门的Agent技术，运用JAVA语言，采用C/S模式，在局域网上实现了一个并行布线系统，实验结果表明，算法有着很高的加速比。由于JAVA的跨平台特性，使并行系统可以平滑地移植到异构的Internet环境中。该系统的设计思想和结构同样可以运用到其它需要充分利用网络计算资源的系统中，具有很高的实用价值。 我们首次在总体布线过程中同时考虑串扰和时延。通过采用一种广泛使用的互连线时延模型和一种简单的串扰计算模型，我们尝试了在总体布线过程中 电子科技大学博士论文；超大规模集成电路若千布线算法研究同时考虑时延和串扰的方案。我们的具体作法是：将串扰和时延变换为通道容量表示，将问题转换为变通道容量的Steiner树问题，用一个Steiner树算法分别对名线网进行初始布线，若有线网违反串扰或时延约束，则采用拆线重布的方法来修正，拆线重布中采用A旷nt技术。实验结果表明，我们的算法是可行的。 乳们将蚁群算法首次应用到多层布线的通孔最小化问题中。在高性能和高密度的芯片设计中，多层布线是经常出现的。为了优化多种设计目标如线长最短、面积最小、考虑时延和串扰等问题，人们往往在布线之后采用一些特别算法，对初始布线结果进行优化。多层布线的通孔最小化算法便是在保持线网的拓扑结构不变的情况下，为各线网的网段分配合适的布线层，使得最后布线结果中的通孔数最少。本文中我们提出了一种基于蚁群系统（ACS）的多层通孔最小化算法。首先K层布线的CYM问题被转化为一个交叠图，图中每个结点中有K个隧道，这样为各网段分层的问题转化为穿越各结点的隧道而形成的一条路径的问题。结合ACS的基本思想，各蚂蚁通过互相学习，能够搜寻到使最后布线结果中通孔数得到优化的一条路径。实验结果表明该算法是可行的。 我们设计了一个基于Web的布线设计环境XLAYDEN，在该环境中，系统能够将用户的设计任务自动公布在Internet上，由多人共同设计完成；系统能够可靠地保存用户的数据，能够为用户提供多种设计工具，并且XLAYDEN能够自动利用网上的计算资源，提高系统的计算性能。通过系统原型的实验，表明设计是基本可行的，并且具有很好的伸缩性和移植性。更多还原

【Abstract】 In chapter 3, Ant Colony System (ACS) algorithm is first used in the physical design of VLSI circuit to implement a switchbox router that has lowered time complexity compared with SA (Simulated Anneal) and GA (genetic Algorithm). Since the final routing is determined by the detail routing, switchbox routing problem that is NP-Complete plays an important role in the whole process of layout. The ACS algorithm that has been applied to TSP and computer communication successfully was intensified by cooperative working mechanism, which led to an Intensified Ant Colony System (IACS). Then based on IACS, we implemented a switchbox router in which ants attracted by pins and coordinated by stop-to-wait mechanism can avoid routing conflict affectively and route all nets quickly while optimize total wire length and vias. In chapter 4, a parallel router is implemented. As computer networks (especially Internet and Jntranet) become the infrastructure of application, it is a powerful approach for designers to improve the performance of their algorithms to use computing resources efficiently in the network. By using oriented agent technique, we implemented a parallel switchbox router based on C/S model and written in Java in a local area network. In the algorithm, there are three kinds of agents that deal with routing a net, routing a switchbox, and iteration respectively. The experiments show that the router has a high speed-up ratio. Because Java is independent of the platforiii, the parallel router can be ported into Internet gracefully. The design method and architecture of this router can be used in other systems that make use of network computing resources in the network. III In chapter 5, a global router considering crosstalk and delay is implemented in which a general delay model and a simple crosstalk model are used. In order to reduce the complexity of the problem, we map the crosstalk and delay constraints into path capacity, and then the algorithm just considers the wue routing to inee~ the path capacity constraints. If there are some nets that are not routed successfully, some nets will be rip-up and rerouted according to a modified maze algorithm. The experiments show that our global router is feasible. In chapter 6 ACS algorithm is used to resolve the Constrained Via Minimization problem in multi-layer routing. For advanced integrated circuits (IC) design, four to six routing layers ate commonly used in high-performance and high-density design. In order to design a router that can simultaneously optimize many different design objectives, such as wire length, area, delay, crosstalk, etc, certain post-layout optimization techniques can help the routers to meet various design constraints and produce better routing results. The constrained via minimization preserves the wire length and topologies and reassigns wire segments to appropriate 1ay~rs to minimize the number of vias. In chapter 6, a via minimization algorithm for multi-layer routing based on ACS is implemented. The via minimization problem is mapped into a cross-segment graph, in which each node has K tunnels, where K is the number of layers. In the algorithm, there are many ants that will pass all ruxies separately to get a layer assignment soluton. An ant chooses a tunnel to pass through when it visits a node. The tunnel an ant passed indicates the layer the wire segment should be assigned to. By the cooperative learning mechanism, ants can get a更多还原