Incremental Placement for Structured ASICs using the Transportation Problem
Abstract
While physically driven synthesis techniques have proven
to be an effective method to meet tight timing constraints required
by a design, the incremental placement step during physically driven
synthesis has emerged as the primary bottleneck. As a solution, this
paper
introduces a scalable incremental placement algorithm based upon the
well known transportation problem. This method has an average speedup
of 2x and a 30% reduction in memory usage when compared against a
commercial incremental placer without any impact on area or speed of
the
final placed circuit. Furthermore, this method is scalable for
structured
ASICs.
Reference
Andrew C. Ling, Deshanand P. Singh, and Stephen D.Brown, "Incremental Placement for Structured ASICs using the Transportation Problem", in Proceedings of the 2007 International Conference of Very Large Scale Integration (VLSI-SoC), Atlanta, Georgia, USA, Oct 2007, pp. 172-177.
(Download Full Paper)