The Role of Long and Short Paths in Circuit Performance Optimization

Siu Wing Cheng, Hsi Chuan Chen, David H.C. Du, Andrew Lim

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


In this paper, we consider the problem of determining the smallest clock period for a combinational circuit. By considering both the long and short paths, we derive three independent bounds on the clock period. The first bound is the difference between the longest path delay and the shortest path delay, which has been studied before [6], [9], [11], [12]. The other two take the functionality of the circuit into consideration and, therefore, is usually smaller than the first one. To bring in the functionality of the circuit, we make use of a new class of paths-called the shortest destabilizing paths—as well as the longest sensitizable paths. We also show that considering both the longest sensitizable path and the shortest destabilizing path together does not always give a valid bound. The bounds on the clock period can be alternatively viewed as optimization objectives. At the physical level, the complexity of optimization very much depends on the number of long and short paths present and the number of gates shared by them. We conducted preliminary experiments to study this.

Original languageEnglish (US)
Pages (from-to)857-864
Number of pages8
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number7
StatePublished - Jul 1994

Bibliographical note

Funding Information:
Manuscript received December 2, 1991: revised February 22. 1994. This work was supported in part by NSF Grant MIP-900716X. This paper was recommended by Associate Editor R. E. Bryant. S. W. Cheng and H.-c. Chen were with the Department of Computer Science, University of Minnesota, Minneapolis. MN 55455 USA. S. W.C heng is now with the Department of Computer Science, HKUST. Clear Water Bay, Hong Kong. H.-c. Chen is now with AT&T Bell Labs., Murray Hill, NJ 7974 USA. D. H. C. Du is with the Department of Computer Science. University of Minnesota. Minneapolis. MN 55455 USA. A. Lim was with the Department of Computer and Infomaticin Sciences, University of Florida. He is now with ITI, Singapore 05 1 1. IEEE Log Number 9100667.


Dive into the research topics of 'The Role of Long and Short Paths in Circuit Performance Optimization'. Together they form a unique fingerprint.

Cite this