OVERVIEW

The increased importance of interconnect delay on VLSI circuit performance has spurred rapid progress in algorithms for large-scale global placement. The new algorithms often generalize previously studied heuristics or embed them within a hierarchical framework, either top-down recursive partitioning or multilevel (a.k.a. multiscale) optimization. This chapter presents a brief tutorial on the multilevel approach and describes some leading contemporary multiscale algorithms for large-scale global placement.

Multiscale methods have emerged as a means of generating scalable solutions to many diverse mathematical problems in the gigascale range. However, multiscale methods for partial differential equations (PDEs) [1,2] are not readily transferred to large-scale combinatorial optimization problems like placement. Lack of continuity presents one obstacle; myriad local extrema present another. Lack of a natural grid structure presents a challenge as well. Although there has been progress in the so-called algebraic multigrid (AMG) PDE solvers over general, unstructured graphs, extensions of these methods to hypergraphs are not generally available.

Hierarchical levels of abstraction are indispensable in the design of gigascale complex systems, but hierarchies must properly represent physical relationships, viz., interconnects, among constituent parts. The flexibility of the multiscale heuristic provides the opportunity both to merge previously distinct phases in the design flow and to simultaneously model very diverse, heterogeneous kinds of objectives and constraints. Adaptability to complex formulations of standard objectives and constraints such as timing (Chapter 21) [3,4], routability (Chapter 22) [5 7], and power (Chapter 22) [8] is a demonstrated core attribute of the multilevel...