Parallel algorithms for VLSI routing

With the increase in the design complexity of VLSI systems, there is an ever increasing need for efficient design automation tools. Parallel processing could open up the way for substantially faster and cost-effective VLSI design tools. In this paper, we review some of the basic parallel algorithms that have been recently developed to handle problems arising in VLSI routing. We also include some results that have not appeared in the literature before. These results indicate that existing parallel algorithmic techniques can efficiently handle many VLSI routing problems. Our emphasis will be on outlining some of the basic parallel strategies with appropriate pointers to the literature for more details.