A revisit to voltage partitioning problem

Tao Lin*, Sheqin Dong, Bei Yu, Song Chen, Satoshi Goto

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


We revisit voltage partitioning problem when the mapped voltages of functional units are predetermined. If energy consumption is estimated by formulation E=CV2, a published work claimed this problem was NP-hard. We clarify that it is polynomial solvable, then propose an optimal algorithm, its time complexity is O(nk+k2d) which is best so far, where n, k, and d are respectively the numbers of functional units, available supply voltages, and voltages employed in the final design. In reality, considering leakage power the energy-voltage curve is not simply monotonically increasing and there is still no optimal polynomal polynomial time algorithm. However, under the assumption that energy-voltage curve is quasiconvex, which is also a good approximation to actual situation, the optimal solution can be got in time O(nk2). Experimental results show that our algorithms are more efficient than previous works.

Original languageEnglish
Title of host publicationProceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI
Number of pages4
Publication statusPublished - 2010
Event20th Great Lakes Symposium on VLSI, GLSVLSI 2010 - Providence, RI
Duration: 2010 May 162010 May 18


Other20th Great Lakes Symposium on VLSI, GLSVLSI 2010
CityProvidence, RI


  • quasiconvex assumption
  • voltage partition

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'A revisit to voltage partitioning problem'. Together they form a unique fingerprint.

Cite this