Clustering for processing rate optimization

Chuan Lin*, Jia Wang, Hai Zhou

*Corresponding author for this work

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


Clustering (or partitioning) is a crucial step between logic synthesis and physical design in the layout of a large scale design. A design verified at the logic synthesis level may have timing closure problems at post-layout stages due to the emergence of multiple-clock-period interconnects. Consequently, a trade-off between clock frequency and throughput may be needed to meet the design requirements. In this paper, we find that the processing rate, defined as the product of frequency and throughput, of a sequential system is upper bounded by the reciprocal of its maximum cycle ratio, which is only dependent on the clustering. We formulate the problem of processing rate optimization as seeking an optimal clustering with the minimal maximum-cycle-ratio in a general graph, and present an iterative algorithm to solve it. Since our algorithm avoids binary search and is essentially incremental, it has the potential of being combined with other optimization techniques. Experimental results validate the efficiency of our algorithm.

Original languageEnglish (US)
Title of host publicationProceedings of theICCAD-2005
Subtitle of host publicationInternational Conference on Computer-Aided Design
Number of pages7
StatePublished - 2005
EventICCAD-2005: IEEE/ACM International Conference on Computer-Aided Design, 2005 - San Jose, CA, United States
Duration: Nov 6 2005Nov 10 2005

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152


OtherICCAD-2005: IEEE/ACM International Conference on Computer-Aided Design, 2005
Country/TerritoryUnited States
CitySan Jose, CA

ASJC Scopus subject areas

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


Dive into the research topics of 'Clustering for processing rate optimization'. Together they form a unique fingerprint.

Cite this