Zhong Xiu Carnegie Mellon University

Large Scale Placement by Grid Warping

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. 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.

We also introduce a timing-driven grid-warping formulation that incorporates slack-sensitivity-based net weighting. Given inevitable concerns about wirelength and runtime degradation in any timing-driven scheme, we also incorporate a more efficient net model and an integrated local improvement ("rewarping") step. An implementation of these ideas, WARP2, can improve worst-case negative slack by 37% on average, with very modest increases in wirelength and runtime.

Bio:

Zhong Xiu received the B.S. degree from the Computer Science and Technology Department from Tsinghua University in 2001 and the M.S. degree in Electrical and Computer Engineering from Carnegie Mellon University in 2003. He is currently a Ph.D. candidate in the ECE Department at CMU with his advisor, Professor Rob A. Rutenbar. His research interests include computer aided design algorithms, physical design algorithms and computer architecture.