Research On Routing Algorithms For VLSI Circuits

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...