Global placement by primal-dual Lagrange optimization

The “research highlights” paper in the June 2013 CACM was “SimPL: an algorithm for placing VLSI circuits” by Kim, Lee and Markov.

Typical state-of-the-art placers require over 100,000 lines of C++ code, but our self-contained implementation of SimPL uses fewer than 5000 lines. … Two placers based on the SimPL framework finished in top three at the ISPD 2011, DAC 2012, and ICCAD 2012 routability-driven placement contests organized by IBM Research.

They noticed a similarity to primal-dual optimization algorithms in which the constraints and the objective function are swapped until lower and upper bounds converge, and Kim and Markov generalized and extended SimPL to ComPLx for multilevel optimization.

Their ComPLx paper from DAC 2012 is available for free download HERE.

A key diff erence from analytical placement based on non-convex optimization is the emphasis on decomposing the original problem into a series of convex optimizations, which enables duality and accelerates convergence. Unlike prior works limited to a single interconnect model, our technique can be used with quadratic, log-sum-exp and other models.

Advertisements

Tell me (anonymous OK)

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s