Zhong Xiu
ABSTRACT
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 gates. Deforming the elastic grid is a surprisingly simple, low-dimensional nonlinear optimization, and augments a traditional quadratic formulation. A preliminary implementation, WARP1, is already competitive with most recently published placers, e.g., placements that average 4% better wirelength, 40% faster than GORDIAN-L-DOMINO.
- S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, 13 May 1983.Google Scholar
- R. S. Tsay, E. Kuh, C. P Hsu, "PROUD: A sea-of-gates placement algorithm," IEEE Design & Test of Computers, vol.5, Dec. 1988. Google ScholarDigital Library
- Kleinhans, G. Sigl, F. Johannes, and K. Antreich, "Gordian: VLSI placement by quadratic programming and slicing optimization," IEEE Trans. CAD, vol. 10, no.3, March 1991.Google Scholar
- K. Doll, F. M. Johannes, K. J. Antreich, "Iterative placement improvement by network flow methods," Proc. IEEE Trans. CAD, vol. 13, no. 10, Oct 1994.Google Scholar
- H. Eisenmann, F. M. Johannes, "Generic global placement and floor-planning," Proc ACM/IEEE DAC, June 1998. Google ScholarDigital Library
- J. Vygen, "Algorithms for large-scale flat placement," Proc ACM/IEEE DAC, June 1998. Google ScholarDigital Library
- G. Karypis, R. Agarwal, V. Kumar, S. Shekhar, "Multilevel hypergraph partitioning: Applications in VLSI design," Proc ACM/IEEE DAC, June 1997. Google ScholarDigital Library
- T. F. Chan, J. Cong, T. Kong, J. R. Shinner, "Multilevel optimization for large-scale circuit placement.," Proc. ACM/IEEE ICCAD, Nov. 2000. Google ScholarDigital Library
- T. F. Chan, J. Cong, T. Kong, J. R. Shinner, K. Sze, "An enhanced multilevel algorithm for circuit placement," Proc. ACM/IEEE ICCAD, Nov. 2003. Google ScholarDigital Library
- G. Sigl, K. Doll, F. M. Johannes, "Analytical placement: A linear or a quadratic objective function?" Proc ACM/IEEE DAC, June 1991. Google ScholarDigital Library
- S. M. Folwer, Placement by Grid Warping. Master's Thesis, ECE, Carnegie Mellon University, 2001.Google Scholar
- R. H. J. M. Otten, "Efficient floorplan optimization," Proc. IEEE ICCD, 1983.Google Scholar
- P. S. Heckbert, Fundamentals of Texture Mapping and Image Warping, Master's Thesis, EECS, U.C. Berkeley, UCB/CSD-89/516, 1989. Google ScholarDigital Library
- Z. Xiu, VLSI Component Placement by Grid Warping, Master's Thesis, ECE, Carnegie Mellon University, 2003.Google Scholar
- M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 1997. Google ScholarDigital Library
- W. H. Press, et al., Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, 1992. Google ScholarDigital Library
- C. J. Alpert, "The ISPD98 circuit benchmark suite," Proc. ACM ISPD, April 1998. Google ScholarDigital Library
- A. Caldwell, A. Kahng, I. Markov, "Can recursive bisection alone produce routable placements?" Proc. ACM/IEEE DAC, June 2000. Google ScholarDigital Library
- M. Wang, X. Yang, M. Sarrafzadeh, "Dragon 2000: Fast standard-cell placement for large circuits," Proc. ACM/IEEE ICCAD, Nov. 2000. Google ScholarDigital Library
- J. Cong, UCLA, private communication, Nov. 2003.Google Scholar
Index Terms
- Large-scale placement by grid-warping
Recommendations
Timing-driven placement by grid-warping
DAC '05: Proceedings of the 42nd annual Design Automation ConferenceGrid-warping is a recent placement strategy based on a novel physical analogy: rather than move the gates to optimize their location, it elastically deforms a model of the 2-D chip surface on which the gates have been coarsely placed via a standard ...
Mixed-size placement with fixed macrocells using grid-warping
ISPD '07: Proceedings of the 2007 international symposium on Physical designGrid-warping is a placement strategy based on a novel physical analogy: rather than move the gates to optimize their location, it elastically deforms a model of the 2-D chip surface on which the gates have been coarsely placed via a standard quadratic ...
An Effective Floorplan-Guided Placement Algorithm for Large-Scale Mixed-Size Designs
In this article we propose an effective algorithm flow to handle modern large-scale mixed-size placement, both with and without geometry constraints. The basic idea is to use floorplanning to guide the placement of objects at the global level. The flow ...
Comments