Sequential/Parallel Heuristic Algorithms For VLSI Standard Cell Placement
By Guangfa Lu, September 2004
Abstract:
With advanced sub-micron technologies, the exponentially
increasing number of transistors on a VLSI chip causes placement
within physical design automation to become more and more important
and consequently extremely complicated and time consuming.
This research addresses the placement for VLSI standard cell designs.
A number of heuristic optimization techniques for placement are
studied and implemented, in particular, local search, Tabu Search,
Simulated Annealing and Genetic Algorithm. The Tabu Search reduces
wire length on average by 52.4% while Simulated Annealing yields a
61% improvement on average. Furthermore, two parallel island-based
GA models are implemented on a loosely-coupled parallel computing
architecture to pursue better performance. With the synchronous
model, an average speedup of 6.2 was achieved by seven processors.
On the other hand, the asynchronous model achieved a 7.6 speedup.
The former obtained the speedups while maintaining equal or better
quality of solutions than a serial GA. In addition to the above
developed algorithms, preprocessing and postprocessing procedures
were analyzed and developed to further enhance solution quality.
