Research

Large-Scale Chip Placement by Grid Warping

Group Members: Suzanne Fowler, James D. Ma, Zhong Xiu

Grid-warping is a new placement algorithm based on a strikingly simple idea: rather than move the gates to optimize their location, we elastically deform a model of the 2-d chip surface on which the gates have been roughly placed, “stretching” it until the gates arrange themselves to our liking. Put simply: we move the grid, not the gutes. Deforming the elastic grid is a surprisingly simple, low-dimensional nonlinear optimization, and augments a traditional quadratic formulation. A range of prototype implementations of the idea — WARP1, WARP2, WARP3 — perform very competitively with the best of peer placement techniques.

Key Papers/Talks

  • Zhong Xiu, James D. Ma, Suzanne Fowler, Rob A. Rutenbar, “Large-scale placement by grid-warping,” Proc. ACM/IEEE 41st Design Automation Conference, June 2004. (Best Paper Nominee.) pdf
  • Z. Xiu, D.A. Papa, P. Chong, C. Albrecht, A, Kuehlmann, R.A. Rutenbar, I.L. Markov, “Early research experience with OpenAccess gear: an open source development environment for physical design,” Proc. ACM International Symposium on Physical Design (ISPD05), April 2005. pdf
  • Zhong Xiu, Rob A. Rutenbar, “Timing-driven placement by grid-warping,” Proc. ACM/IEEE 42nd Design Automation Conference, June 2005. pdf
  • Zhong Xiu, Rob A. Rutenbar, , “Mixed-size placement with fixed macrocells using grid-warping,” Proceedings of the 2007 ACM International Symposium on Physical Design (ISPD07), April 2007. pdf

Copyright © 2015 Rob A. Rutenbar. All Rights Reserved. Site designed by Academic Web Pages