An efficient parallel critical path algorithm

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

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

6 Scopus citations


Parallel algorithms for critical path problems are studied. A sensitization criterion is presented. Based on this sensitization criterion, the DT-algorithm, which is a variation of the D-algorithm with stable time range of signals also taken into consideration, is developed. It is especially suitable to determine the sensitizability of a given path in a parallel processing environment. The authors discuss a parallel implementation of the critical path algorithm on a shared-memory multiprocessor. The experimental results show that a reasonable speed-up can be obtained.

Original languageEnglish (US)
Title of host publicationProceedings - Design Automation Conference
PublisherPubl by IEEE
Number of pages6
ISBN (Print)0818691492
StatePublished - Jun 1 1991
EventProceedings of the 28th ACM/IEEE Design Automation Conference - San Francisco, CA, USA
Duration: Jun 17 1991Jun 21 1991

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0146-7123


OtherProceedings of the 28th ACM/IEEE Design Automation Conference
CitySan Francisco, CA, USA


Dive into the research topics of 'An efficient parallel critical path algorithm'. Together they form a unique fingerprint.

Cite this