Efficient algorithms for VLSI placement and routing problems

This thesis is primarily concerned with routing problems in VLSI physical layout design. For both single-layer and over-the-cell wiring models, efficient channel routing algorithms are developed to minimize standard cost measures. In addition, we provide an empirical comparison of placement and global routing algorithms for FPGAs.; In the area of single-layer channel routing, this thesis considers three specific problems, namely the minimum separation, offset range, and optimal offset problems, in parallel computing models. For the minimum separation problem, we obtain {dollar}O({lcub}rm lg{rcub} N){dollar} time on a CREW PRAM or {dollar}O({lcub}{lcub}rm lg{rcub} Nover{lcub}rm lg lg{rcub} N{rcub}){dollar} time on a (common) CRCW PRAM, both with optimal work (processor-time product) of {dollar}O(N),{dollar} where N is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as only one side of the channel contains single-sided nets. For the optimal offset problem with single-sided nets on one side of the channel, we obtain time {dollar}O({lcub}rm lg{rcub} N {lcub}rm lg lg{rcub} N){dollar} on a CREW PRAM or {dollar}O({lcub}{lcub}rm lg{rcub} Nover{lcub}rm lg lg{rcub} N{rcub}){dollar} time on a CRCW PRAM with {dollar}O(N {lcub}rm lg lg{rcub} N){dollar} work. Not only does this improve on previous results for river routing, but we can obtain an even better time of {dollar}O(({lcub}rm lg lg{rcub} N)sp2){dollar} on the CRCW PRAM in the river routing context. In addition, wherever our results allow a channel boundary to contain single-sided nets, the results also apply when that boundary is ragged and N incorporates the number of bendpoints.; In the over-the-cell context, this thesis presents an efficient algorithm to reduce the channel density of a given channel. By choosing critical nets or subnets to route over the cells, our algorithm achieves better or equal channel density reduction with fewer tracks in the over-the-cell regions than previous works. In addition, this algorithm can easily be parallelized due to the independent nature of cost function computations for each interval.; The last part of this thesis shows the results of an empirical comparison of placement and global routing algorithms for FPGAs. We consider recently described algorithms that appear promising but that have not been compared on the same FPGA architecture and with the same benchmarks. We focus on a simultaneous placement and global routing scheme of Togawa et al. and what appears to be the leading scheme for sequential placement and routing embodied in the Vpr system of Betz. We compare the algorithms on two different FPGA architectures, using several benchmarks in each case.