The estimation of signal stable ranges in a combinational circuit is an important issue for determining clock time in a synchronous system. An optimal clocking period time highly depends on the accuracy of the shortest path length as well as the longest path length in a combinational circuit. In this paper, a sensitization criterion for the short path is first proposed. Based on this sensitization criterion, an accurate model for calculation of signal stable range can be created. This will allow the output stable range of a gate to be the union of its inputs when the input leads hold a controlling value, rather than to be always the intersection. Then, an LS-algorithm for calculation of signal stable ranges is presented in which both the sensitizable shortest path and the sensitizable longest path are considered. It avoids the exhaustive search by tracing the path sensitization and eliminates some conservative restriction to get more accurate results in a more efficient way, compared to the previous approaches. The speedup and the improved accuracy of the proposed LS-algorithm showed promising experimental results.>

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-algorithm is especially suitable and can be used to determine the sensitizability of a given path in a parallel processing environment. We also present an implementation of parallel DT-algorithm that can be executed on a shared memory multiprocessor. The experimental results show that a reasonable speed-up can be obtained.>

The problem of selecting a set of paths to optimize the performance of a combinational circuit is studied, assuming that gate resizing and buffer insertion are the two possible optimizing techniques for reducing the delay of a circuit. The objective of the path selection problem is to select as small as possible a set of paths to ease the optimization processing to guarantee that the delay of the circuit is no longer than a given threshold tau if the delays of all the selected paths are no longer than tau . It is shown that the path selection is different from path sensitization. An input vector-oriented path selection algorithm is proposed. Because it may be infeasible for complex circuits with many primary inputs, a path-oriented algorithm is also developed and implemented. Experimental results on ISCAS85 benchmark circuits show a potentially big improvement for the optimization process.>

In this paper we study the problem of selecting a set of paths to optimize the performance of a circuit.We assume that gate resizing is the optimizing technique used to reduce the delay of a circuit.That is, during the optimization process the topology of a circuit remains the same and the gate delays are reduced.The objective of the path selection problem is to select as few paths as possible so that when the delays of all selected paths are shortened, the delay of the optimized circuit is guaranteed to meet its performance requirement.We first propose an input vector oriented path selection algorithm.Due to the fact that the input vector oriented algorithm may be not feasible for complex designs with many input pins, we have designed and developed a path oriented algorithm.For some ISCAS circuits, less than 10% of the long paths are selected by our path oriented algorithm.

Article Free Access Share on An efficient parallel critical path algorithm Authors: Li-Ren Liu Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , David H. C. Du Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , Hsi-Chuan Chen Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 535–540https://doi.org/10.1145/127601.127728Published:01 June 1991Publication History 11citation431DownloadsMetricsTotal Citations11Total Downloads431Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The estimation of signal stable ranges in combinational circuits is an important issue for setting clock time in a synchronous system. The authors first propose a sensitization criterion for the shortest path, and they then use a path-oriented approach to reduce search space. Considering the possible case where the signal stable range at the output of a gate could be the union of inputs, one can obtain more accurate results than with the intersection approach.>