ABSTRACT
This chapter presents a brief tutorial on the multilevel approach and describes some leading contemporary multiscale algorithms for large-scale global placement. It introduces basic ideas and vocabulary and summarizes known basic principles of general multiscale algorithms for global optimization. The chapter also summarizes properties of leading contemporary multiscale placement algorithms and compares new practice to the known theory and identify likely areas of research opportunity. Iterative improvement at each level may employ various techniques—network flows, simulated annealing, nonlinear programming, force-directed models—provided that it can support incorporation of complex constraints appropriate to the modeling scale at the level. Multiscale methods originated as geometric multigrid methods in the context of uniformly discretized partial differential equations, where the resolution and regularity of the discretization make the notion of modeling scale obvious. Both the outcome of relaxation and the convergence rates of individual variables during relaxation can be used to guide the construction of interpolation or aggregation operators.
