File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1687399.1687453
- Scopus: eid_2-s2.0-76349094451
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: The epsilon-approximation to discrete VT assignment for leakage power minimization
Title | The epsilon-approximation to discrete VT assignment for leakage power minimization |
---|---|
Authors | |
Keywords | Leakage power NP-complete VT assignment ε-Approximation |
Issue Date | 2009 |
Citation | IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, 2009, p. 281-287 How to Cite? |
Abstract | As VLSI technology reaches 45nm technology node, leakage power optimization has become a major design challenge. Threshold voltage (vt) assignment has been extensively studied, due to its effectiveness in leakage power reduction. In contrast to the efficiently solvable continuous vt assignment problem, the discrete vt assignment problem is known to be NP-hard. All of the existing techniques are heuristics without performance guarantee due to the NP-hardness nature of the problem. It is still not known whether there is any rigorous approximation algorithm for the discrete vt assignment problem. In this paper, the first ε-approximation algorithm is designed for the discrete vt assignment problem. The algorithm can ε-approximate the optimal vt assignment solution in (equation presented) time, where n is the size of the combinational circuit and m is the number of available threshold voltages per gate. It is based on an advanced potential function technique and an efficient dual decision core query technique. Our experiments on ISCAS'85 benchmark circuits demonstrate that the new algorithm always returns a solution with error bounded by ε even compared to the lower bound of the optimal solution. On average, it can approximate the optimal solution with 2.8% additional leakage power running in 51.3 seconds, while the integer linear programming technique is computationally prohibitive. Our algorithm also significantly outperforms the heuristic in [1] by 16.5% leakage power saving with similar runtime. This clearly demonstrates the practicality of the proposed ε-approximation algorithm for the vt assignment problem. Copyright 2009 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/336080 |
ISSN | 2023 SCImago Journal Rankings: 0.894 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Feng, Yujia | - |
dc.contributor.author | Hu, Shiyan | - |
dc.date.accessioned | 2024-01-15T08:23:15Z | - |
dc.date.available | 2024-01-15T08:23:15Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, 2009, p. 281-287 | - |
dc.identifier.issn | 1092-3152 | - |
dc.identifier.uri | http://hdl.handle.net/10722/336080 | - |
dc.description.abstract | As VLSI technology reaches 45nm technology node, leakage power optimization has become a major design challenge. Threshold voltage (vt) assignment has been extensively studied, due to its effectiveness in leakage power reduction. In contrast to the efficiently solvable continuous vt assignment problem, the discrete vt assignment problem is known to be NP-hard. All of the existing techniques are heuristics without performance guarantee due to the NP-hardness nature of the problem. It is still not known whether there is any rigorous approximation algorithm for the discrete vt assignment problem. In this paper, the first ε-approximation algorithm is designed for the discrete vt assignment problem. The algorithm can ε-approximate the optimal vt assignment solution in (equation presented) time, where n is the size of the combinational circuit and m is the number of available threshold voltages per gate. It is based on an advanced potential function technique and an efficient dual decision core query technique. Our experiments on ISCAS'85 benchmark circuits demonstrate that the new algorithm always returns a solution with error bounded by ε even compared to the lower bound of the optimal solution. On average, it can approximate the optimal solution with 2.8% additional leakage power running in 51.3 seconds, while the integer linear programming technique is computationally prohibitive. Our algorithm also significantly outperforms the heuristic in [1] by 16.5% leakage power saving with similar runtime. This clearly demonstrates the practicality of the proposed ε-approximation algorithm for the vt assignment problem. Copyright 2009 ACM. | - |
dc.language | eng | - |
dc.relation.ispartof | IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD | - |
dc.subject | Leakage power | - |
dc.subject | NP-complete | - |
dc.subject | VT assignment | - |
dc.subject | ε-Approximation | - |
dc.title | The epsilon-approximation to discrete VT assignment for leakage power minimization | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/1687399.1687453 | - |
dc.identifier.scopus | eid_2-s2.0-76349094451 | - |
dc.identifier.spage | 281 | - |
dc.identifier.epage | 287 | - |