Optimal wire ordering and spacing in low power semiconductor design
成果类型：
Article
署名作者：
Gritzmann, Peter; Ritter, Michael; Zuber, Paul
署名单位：
Technical University of Munich; Technical University of Munich
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-008-0231-z
发表日期：
2010
页码：
201-220
关键词：
摘要：
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 NP-hard in general, the present paper provides an O(N log N) algorithm that solves the coupled ordering and spacing problem for N parallel wires to optimality.