This paper presents a timing-driven global routing algorithm based on coarse pin assignment, block reshaping, and positioning for VLSI building block layout. As opposed to conventional approaches, we combine pin assignment and global routing problems into one problem. The proposed algorithm determines global routes, coarse pin assignments, and block shapes and positions so as to minimize the chip area and total wire length of nets under the given timing constraints. It is based on an iterative improvement paradigm and performs rip-up and rerouting, block reshaping, and positioning in the manner of simulated evolution taking shapes of soft blocks and routing congestion into consideration until the solution is not further improved. The Elmore delay model is adopted for the interconnection delay model. Experimental results show the effectiveness of the proposed algorithm.

In this paper, we present a hierarchical technique for simultaneous pin assignment and global routing during floorplanning based on the minimum cost maximum integer flow algorithm with several heuristic cost functions. Furthermore, our algorithm handles feedthrough pins and equi-potential pins taking into account global routes. Our algorithm allows various user specified constraints such as pre-specified pin positions, wiring paths, wiring widths and critical nets. Experimental results including Xerox floorplanning benchmark have shown the effectiveness of the heuristics.

Reducing switching noise is a key point in increasing signal transmission capability. This noise is related to the pin assignment of connectors and the inner layer structure of the printed circuit board (PCB). This paper presents and evaluates experimental results on the relationships between pin assignment, the number of the signal outputs, and switching noise. It shows that calculated and experimental results agree well if we assume that the distribution of return current, causing switching noise in a connector, does not uniformly decrease with increases in the number of ground pins. We also assume that the effective number of ground pins is related to the number of signal pins even if there are more ground pins than there are signal pins.

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.