Paper Review: Timing verification and the timing analysis program

Timing Verifications consists of validating ht epath delays (primary input or storage element to primary output or storage element) to be sure they are not too long or too short and checking the clock pulses to be sure they are not too wide or too narrow. The programs addressing these problems neither produce input patterns like test pattern generators nor require input patterns like traditional simulators. Several programs (described here) operate by tracing paths [P173, WO78, SA81, KA81]. One program [MC80] extends simulation into a pessimistic analyzer not dependent on test patterns.

Timing Analysis, a program described recently in [HI82a], is designe dot analyze the timing of large digital computers and is based, in part, on the concepts discloed in a patented method [DO81] for determining the extreme characteristics of logic block diagrams. The output of Timing Analysis includes "slack" at each block to provide a measure of the severity of the timing problem. The program also generates stnadard deviations for the times so that a statistical timing design can be produced rather than a worst case approach.

Paper is located here

Citation:

[1] R. Hitchcock Sr, "Timing verification and the timing analysis program," Proceedings of the 19th conference on Design automation, IEEE Press Piscataway, NJ, USA, 1982, p. 594–604.

Positive:

• Introduces what appears to be novel terminology ("slack") which is now widely relied upon in timing analysis.

• Extremely large comparison of similar work. Goes into great depth on how similar algorithms function and their advantages and disadvantages. Provides examples of each.

• Brings out that their technique allows a designer more freedom. For example, their technique shows a measure of the "badness" of the path at hand, and would allow a designer to visually identify and replace the worst parts. This works in the opposite direction as well, as the forward slack might allow designers to use smaller circuits with larger delay.

Negative:

• Abstract fails to tell you what the paper is about. It informs you of what timing verification is and of a program that does such, but has no apparent hint as to what the author will be presenting other than likely related to this topic somehow.

• Misuses terminology within itself. A bit ambiguous, a "block" is defined inside the path-based algorithm GRASP. This is different to the "block"-oriented algorithms that are described later.

• Discusses running time of the Timing Analysis program, but fails to use standard terminology. It seems to imply O(n)

• Also fails to do a side-by-side comparison of actual run times. The comparison is very hand-waved without real results, though it is a methodology paper more than a runtime paper.