An Efficient Parallel Critical Path Algorithm

Li Ren Liu, David H.C. Du, Hsi Chuan Chen

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

The problem of identifying one of the longest sensitizable paths in a circuit is called a critical path problem. Several critical path algorithms have been proposed in the last few years. However, due to the long computation time required to produce accurate results, these algorithms may not be able to generate any result for large designs with many long false paths unless the accuracy of the results is compromised. Parallel processing seems to be an appropriate way to speed up the required computation. In this paper, we study the parallel algorithms for critical path problem. We first present a sensitization criterion. Based on this sensitization criterion an algorithm called DT-algorithm, which is a variation of the D-algorithm with stable Time range of signals also taken into consideration, is developed. The DT-algorithrn is especially suitable and can be used to determine the sensitizability of a given path in a parallel processing environment. We also presented an implementation of parallel DT-algorithm that can be executed on a shared memory multiprocessor. The experimental results show that a reasonable speedup can be obtained.

Original languageEnglish (US)
Pages (from-to)909-919
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume13
Issue number7
DOIs
StatePublished - Jul 1994

Bibliographical note

Funding Information:
work was supported in part by NSF Grant MIP-9007168. This paper was recommended by Associate Editor R. E. Bryant. L.-R. Liu is with Actel, Sunnyvale, CA 94086 USA. D. H. C. Du is with the Department of Computer Science, University of Minnesota, Minneapolis, MN 55455 USA. H.-C. Chen is with AT&T Bell Labs., Murray Hill, NJ 07974 USA. IEEE Log Number 9400665.

Fingerprint

Dive into the research topics of 'An Efficient Parallel Critical Path Algorithm'. Together they form a unique fingerprint.

Cite this