NDLI: The epsilon-approximation to discrete VT assignment for leakage power minimization

Content Provider	IEEE Xplore Digital Library
Author	Yujia Feng Shiyan Hu
Copyright Year	2009
Description	Author affiliation: Dept. of Electrical and Computer Engineering, Michigan Technological University, Houghton, Michigan 49931 (Yujia Feng; Shiyan Hu)
Abstract	As VLSI technology reaches 45rara 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 $O(mn^{3}$ log n log 1/∊ + $mn^{3}$ $log^{2}$ 1/∊ ÷ $∊^{2})$ 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 e 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.
Starting Page	281
Ending Page	287
File Size	233078
Page Count	7
File Format	PDF
ISBN	9781605588001
ISSN	10923152
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-11-02
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Association for Computing Machinery, Inc. (ACM)
Subject Keyword	Threshold voltage Algorithm design and analysis Timing Power engineering computing Design engineering Power engineering and energy Very large scale integration Design optimization Circuits Distributed computing Leakage Power ∊-Approximation NP-Complete VT Assignment
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in