Parallel Algorithms for VLSI Layout.

Abstract

Efficient automatic layout tools are clearly essential for designing complex VLSI systems. Recent efforts have been directed toward developing parallel algorithms to handle the different subproblems involved in the layout phase. Some of these algorithms have been shown to offer significant speed-ups over the sequential ones. In this chapter, basic parallel techniques that have been found to be effective for handling problems arising in the layout phase are reviewed. In particular, parallel algorithms for problems arising in paffitioning, placement and routing are discussed. The algorithms used to handle these problems can be classified into two broad categories: iterative or direct. The iterative techniques such as simulated annealing and the Kernighan-Lin algorithm are very effective for partitioning and placment. The direct methods seem to be dominant in routing. These methods and some new methods are discussed in the general context of parallel processing. Efficient algorithms for the shared-memory model and for distributed-memory multiprocessors such as the hypercube are described. In addition, several special-purpose hardware for placement and routing are also outlined and their merits discussed.