Describes a new technique for determining the critical path of a parallel simulation. Rather than relying on the traditional method of analyzing the dependencies in a directed graph, the new technique uses a metric called the earliest processing time (EPT) to determine the critical path. The new technique represents a slight innovation over the traditional method. This technique can be implemented either as a centralized algorithm or a distributed algorithm. As a centralized algorithm, the technique relies on a trace file containing the relevant EPTs the computation. As a distributed algorithm, this technique can be implemented so that the critical path becomes part of the output of the parallel computation. A centralized implementation of this technique has been developed and applied to a large and complex military-oriented simulation called CTLS (Concurrent Theater Level Simulation). Details of the two algorithms, and the results of applying the centralized algorithm to the CTLS simulation, are discussed in this paper.
展开▼