The relative window method provides quantitative crosstalk delay degradation for the post-layout timing analysis in deep sub-micron VLSI design. However, to the best of our knowledge, the relative window method has not been applied to the crosstalk minimization in gridded channel routing problem. Most conventional crosstalk optimizers only use the coupling length to estimate the crosstalk. In this paper, we present a post-layout timing driven crosstalk optimizer based on the relative window method. According to the relative signal arrival time and the coupling length, we define a delay degradation graph to describe the crosstalks between nets in a routing solution. Our optimization goal is to maximize the time slack by iteratively improving the delay degradation graph without increasing the channel height. Benchmark data consistently show that our post-layout timing driven crosstalk optimizer can further improve the routing solution obtained by a conventional crosstalk optimizer.

A digital neural network approach is presented for the multilayer channel routing problem with the objective of crosstalk minimization in this paper. As VLSI fabrication technology advances, the reduction of crosstalk between interconnection wires on a chip has gained important consideration in VLSI design, because of the closer interwire spacing and the circuit operation at higher frequencies. Our neural network is composed of N M L digital neurons with one-bit output and seven-bit input for the N-net-M-track-2L-layer problem using a set of integer parameters, which is greatly suitable for the implementaion on digital technology. The digital neural network directly seeks a routing solution of satisfying the routing constraint and the crosstalk constraint simultaneously. The heuristic methods are effectively introduced to improve the convergence property. The performance is evaluated through solving 10 benchmark problems including Deutsch difficult example in 2-10 layers. Among the existing neural networks, the digital neural network first achieves the lower bound solution in terms of the number of tracks in any instance. Through extensive simulation runs, it provides the best maximum crosstalks of nets for valid routing solutions of the benchmark problems in multilayer channels.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we propose a modified genetic channel router. We adopt the compatible crossover operator and newly designed compatible mutation operator in order to search solution space more effectively, where vertical constraints are integrated. By carefully selected fitness function forms and optimized genetic parameters, the current version speeds up benchmarks on average about 5.83 times faster than that of our previous version. Moreover the total convergence to optimal solutions for benchmarks can be always obtained.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we describe the implementation of genetic algorithms for channel routing problems and identify the key points which are essential to making full use of the population of potential solutions, that is one of the characteristics of genetic algorithms. Three efficient crossover techniques which can be divided further into 13 kinds of crossover operators have been compared. We also extend our previous work with ability to deal with dogleg case by simply splitting multi-terminal nets into a series of 2-terminal subnets. It routes the Deutsch's difficult example with 21 tracks without any detours.

This paper presents a linear time optimal algorithm to a channel pin assignment problem for hierarchical building-block layout design. The channel pin assignment problem is to determine positions of the pins of nets on the top and the bottom sides of a channel, which are partitioned into several intervals, and the pins are permutable within their associated intervals. The channel pin assignment problem has been shown NP-hard in general. We present a linear time optimal algorithm for an important special case of the problem, in which there is at most one pin of a net within each interval in the channel. The proposed algorithm is optimal in a sense that it can minimize both the channel density and the total wire length of the channel. We also disscuss how to apply our algorithm to the pin assignment in the L-shaped and staircase channels. Experimental results indicate that substantial reduction in both channel density and estimated total wire length can be obtained by permuting pins in each interval. Combining the proposed algorithm with a conventional channel router, results of channel routing also achieve large amount of reduction of the number of tracks, total wire length, and the number of vias.

Evolution programs have been shown to be very useful in a variety of search and optimization problems, however, until now, there has been little attempt to apply evolution programs to channel routing problem. In this paper, we present an exolution program and identify the key points which are essential to successfully applying evolution programs to channel routing problem. We also indicate how integrating heuristic information related to the problem under consideration helps in convergence on final solutions and illustrate the validity of out approach by providing experimental results obtained for the benchmark tests. compared with the optimal solutions.

A layout system for mixed analog/digital standard cell LSI's is described. The system includes interactive floorplan and placement features and automatic global and channel router. In mixed analog/digital circuits, crosstalk noise causes chip performance degradation. Thus, the proposed global routing algorithm routes analog nets in areas that are free of digital nets as much as possible. The number of line crossovers, especially for analog nets, is minimized by both global and detailed routers, because these crossovers are the dominant factors in the crosstalk noise. Double width lines can be used to avoid unexpected voltage drops caused by parasitic resistances. A postprocess automatically puts up shield lines for very noise sensitive wirings to improve the S/N ratio. Experimental results show that the proposed algorithms are effective in reducing the number of crossovers and redundant vias.