Provably Fast and Near-Optimum Gate Sizing
| Autor: | Siad Daboul, Nicolai Hahnle, Ulrike Schorr, Stephan Held |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
Polynomial Heuristic Computer science Multiplicative function 0211 other engineering and technologies Regular polygon 02 engineering and technology Computer Graphics and Computer-Aided Design 020202 computer hardware & architecture symbols.namesake Lagrangian relaxation 0202 electrical engineering electronic engineering information engineering symbols Electrical and Electronic Engineering Routing (electronic design automation) Software 021106 design practice & management |
| Zdroj: | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 37:3163-3176 |
| ISSN: | 1937-4151 0278-0070 |
| DOI: | 10.1109/tcad.2018.2801231 |
| Popis: | We present a new approach for the cell selection problem based on a resource sharing formulation, which is a specialization of Lagrangian relaxation with multiplicative weight updates. For the convex continuous gate sizing problem, we can prove fast polynomial running times. This theoretical result also gives some justification to previous heuristic multiplicative weight update methods. For the discrete cell selection problem, where voltage thresholds can also be chosen, we employ the new algorithm heuristically and achieve superior results on industrial benchmarks compared with one of the previously best known algorithms, and competitive results on the ISPD 2013 benchmarks. Finally, we demonstrate how the approach can be parallelized effectively achieving speed-ups of up to 16. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|