Towards Faster and Better Analytical Placements
Abstract
In this thesis, we explore ways to improve the current state of the art
in analytical VLSI standard cell placement techniques. We present a
convex formulation of the placement problem which can be made
arbitrarily close to a linear wire length model. An interior point
method (IPM) for solving this convex problem is presented which
utilizes a preconditioned version of the conjugate gradient squared
(CGS) iterative method. Preconditioners are computed using a drop
tolerance incomplete $LDL^T$ factorization. Both the IPM and the
iterative method have been implemented in parallel in a shared memory
environment. Moderate speedups are achieved on two and four processor
symmetric multiprocessor workstations. The parallel implementation
often requires fewer CGS and IPM iterations due to very slight
numerical differences in the vector computations. The limiting factor
is memory-to-CPU bandwidth and the inability to bind slave threads to a
particular processor.
Fetch the entire document in postscript format.
Mark Frazer -- mjfrazer@gmail.com