An efficient algorithm for library-based cell-type selection in high-performance low-power designs

Li Li*, Peng Kang, Yinghai Lu, Hai Zhou

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

24 Scopus citations


In this paper, we present a complete framework for celltype selection in modern high-performance low-power designs with library-based timing model. Our framework can be divided into three stages. First, the best design performance with all possible cell-types is achieved by a Minimum Clock Period Lagrangian Relaxation (Min-Clock LR) method, which extends the traditional LR approach to conquer the difficulties in discrete scenario. Min-Clock LR fully leverages the prevalent many-core systems as the main body of its workload is composed of independent tasks. Upon a timing-valid design, we solve the timing-constrained power optimization problem by min-cost network flow. Especially, we identify and address the core issues in applying network flow technique to library-based timing model. Finally, a power prune technique is developed to take advantage of the residual slacks due to the conservative network flow construction. Experiments on ISPD 2012 benchmarks show that on average we can save 13% more leakage power on designs with fast timing constraints compared to start-of-the-art techniques. Moreover, our algorithm shows a linear empirical runtime, finishing the largest benchmark with one million cells in 1.5 hours.

Original languageEnglish (US)
Article number6386613
Pages (from-to)226-232
Number of pages7
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
StatePublished - Dec 1 2012
Event2012 30th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2012 - San Jose, CA, United States
Duration: Nov 5 2012Nov 8 2012

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'An efficient algorithm for library-based cell-type selection in high-performance low-power designs'. Together they form a unique fingerprint.

Cite this