Lr. Liu et al., AN EFFICIENT PARALLEL CRITICAL PATH ALGORITHM, IEEE transactions on computer-aided design of integrated circuits and systems, 13(7), 1994, pp. 909-919
The problem of identifying one of the longest sensitizable paths in a
circuit is called a critical path problem. Several critical path algor
ithms have been proposed in the last few years. However, due to the lo
ng computation time required to produce accurate results, these algori
thms may not be able to generate any result for large designs with man
y long false paths unless the accuracy of the results is compromised.
Parallel processing seems to be an appropriate way to speed up the req
uired computation. In this paper, we study the parallel algorithms for
critical path problem. We first present a sensitization criterion. Ba
sed on this sensitization criterion an algorithm called DT-algorithm,
which is a variation of the D-algorithm with stable Time range of sign
als also taken into consideration, is developed. The DT-algorithm is e
specially 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 s
hared memory multiprocessor. The experimental results show that a reas
onable speed-up can be obtained.