NDLI: Fast approximation for peak power driven voltage partitioning in almost linear time

Content Provider	IEEE Xplore Digital Library
Author	Jia Wang Xiaodao Chen Lin Liu Shiyan Hu
Copyright Year	2012
Description	Author affiliation: Department of Electrical and Computer Engineering, Michigan Technological University, Houghton, Michigan 49931 (Jia Wang; Xiaodao Chen; Lin Liu; Shiyan Hu)
Abstract	Voltage partitioning on functional units/blocks targeting peak power minimization has been demonstrated to be effective for energy reduction considering voltage island shutdown impact. However, the existing technique can only solve this NP-hard problem efficiently on small designs. In this paper, a much faster linear time approximation scheme is proposed, which can approximate the optimal voltage partitioning solution within a factor 1+ ∊, for any 0 < ∊ < 1, and runs in O(n + $1/∊^{O(1)})$ time, where n is the number of functional units. There are multiple ingredients in such a surprisingly low time complexity algorithm. It first categorizes all the functional units into big functional units and small functional units using an ∊ related threshold. Subsequently, a rounding based dynamic programming procedure is performed to handle big functional units and a linear programming based algorithm is performed to handle small functional units, which is followed by the discretization of the continuous linear programming solution. Moreover, through the exploration of the unique nature of our problem, a greedy algorithm is proposed to optimally solve the linear programming formulation in a combinatorial fashion. Further, since patching a salient partitioning solution of big functional units with that of small functional units could lead to a much worse combined solution, a highly efficient enumeration process running in time independent of n is proposed. The experimental results demonstrate that our algorithm runs very fast. It needs only 0.3 second to partition a testcase with 5000 functional units which is more than 10000 X faster than the existing algorithm while still reducing the peak power by 7.4%.
Starting Page	698
Ending Page	704
File Size	692084
Page Count	7
File Format	PDF
ISBN	9781450315739
ISSN	10923152
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-11-05
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Association for Computing Machinery, Inc. (ACM)
Subject Keyword	Capacitance Partitioning algorithms Linear programming Dynamic programming Approximation methods Heuristic algorithms Greedy algorithms Energy Efficiency Linear Time Approximation Scheme Voltage Partitioning Peak Power
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