A revisit to voltage partitioning problem

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


研究成果: Conference contribution

3 被引用数 (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.

ホスト出版物のタイトルProceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI
出版ステータスPublished - 2010
イベント20th Great Lakes Symposium on VLSI, GLSVLSI 2010 - Providence, RI
継続期間: 2010 5月 162010 5月 18


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

ASJC Scopus subject areas

  • 工学一般


「A revisit to voltage partitioning problem」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。