Name
Abstract | ||
|---|---|---|
A key issue for high integration circuit design in the semiconductor industry are power constraints that stem from the need for heat removal and reliability or battery lifetime limitations. As the power consumption depends heavily on the capacitances between adjacent wires, determining the optimal ordering and spacing of parallel wires is an important issue in the design of low power chips. As it turns out, optimal wire spacing is a convex optimization problem, whereas the optimal wire ordering is combinatorial in nature, containing (a special class of) the Minimum Hamilton Path problem. While the latter is $${\mathcal{NP}}$$-hard in general, the present paper provides an $${\mathcal{O}{(N \log N)}}$$algorithm that solves the coupled ordering and spacing problem for N parallel wires to optimality. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s10107-008-0231-z | Math. Program. |
Keywords | Field | DocType |
spacing problem,power constraint,optimal wire placement · convex programming · combinatorial optimization · hamilton path,n parallel wire,low power chip,convex optimization problem,optimal wire spacing,optimal wire,low power semiconductor design,power consumption,minimum hamilton path problem,adjacent wire,integrated circuit design,convex optimization,convex programming,combinatorial optimization,chip | Discrete mathematics,Binary logarithm,Capacitance,Hamiltonian path,Circuit design,Combinatorial optimization,Battery (electricity),Convex optimization,Energy consumption,Mathematics | Journal |
Volume | Issue | ISSN |
121 | 2 | 1436-4646 |
Citations | PageRank | References |
1 | 0.36 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Gritzmann | 1 | 412 | 46.93 |
| Michael Ritter | 2 | 7 | 1.25 |
| Paul Zuber | 3 | 6 | 1.19 |