Incremental Placement for Structured ASICs using the Transportation Problem


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.


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)