Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-11-30
2004-05-18
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C703S016000, C703S017000, C703S021000, C703S022000, C703S028000, C717S104000, C717S126000, C717S128000, C717S135000, C709S201000
Reexamination Certificate
active
06738955
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to evaluating the performance of data processing systems. More specifically, the present invention relates to quantifying average performance characteristics.
2. Description of Related Art
Performance metrics attempt to quantify some aspect of system performance, examples include load latencies, cycles-per-instruction measurements, cache hit ratios, and arbitration delay and/or fairness. In extreme cases, performance problems may even yield livelock/deadlock conditions, in which the system gets “stuck” and can make no forward progress in an execution.
Most performance evaluations are calculated with respect to a set of specific test, sometimes referred to as a benchmark. Such evaluations consider aspects such as minimum values, maximum values, and average values of the performance metric. While such evaluation procedures are easy to visualize, and are quite useful with a meaningful set of tests, they suffer from not providing insight into true system performance with respect to any arbitrary test. Consequently, tests may fail to consider sequences of execution which expose worst-case behavior of the design under test. This fundamental limitation has been noted by many in the industry.
Formal verification is a rigorous validation approach; it uses mathematical reasoning to exhaustively verify the correctness of the design under test. It may reason about possibly infinite streams of execution, and in being exhaustive it may fully characterize the design under all possible streams of execution. The non-determinism supported by formal verification tools renders formal methods an attractive option for performance characterization.
Formal methods may be used to characterize absolute worst-case and best-case system performance. However, there is no manner in which a model checking framework will allow measurement of average performance along all paths. While model checking is a branching-time framework, allowing quantification at any point in time over “any path” or “all paths”, it does not allow counting of these paths. Furthermore, model checkers typically do not consider the probability of a path. Typically they count a transition with probability 1/100,000 than same as a transition with probability 99999/100,000. Thus, model checkers are quite different than simulators (where the transition with probability 1/100,000 is not likely to ever be considered).
Therefore, an enhancement to existing formal verification tools that would allow direct characterization of average performance would be desirable.
SUMMARY OF THE INVENTION
The present invention provides a method for characterizing average performance in a data processing system. This method consists of adding meta-tool level variables to a verification tool. These meta-tool variables keep track, at once, of all concurrent streams of execution that the tool is considering in its reachability analysis. The image of an initial state variable is found and then divided into a frontier of new states and a set of previously reached states. The previously reached states are ignored and the image of the frontier is found. This process continues until the frontier is empty and all possible states have been reached. In one embodiment of the present invention, the probabilities of the paths can be considered by sampling and holding input data using SMV (a model checking tool) variables.
REFERENCES:
patent: 5394347 (1995-02-01), Kita et al.
patent: 5454102 (1995-09-01), Tang et al.
patent: 5708594 (1998-01-01), Iwashita et al.
patent: 5960200 (1999-09-01), Eager et al.
patent: 6278963 (2001-08-01), Cohen
patent: 6366875 (2002-04-01), Colizzi et al.
patent: 6446241 (2002-09-01), Mobley et al.
patent: 6526561 (2003-02-01), Yokoyama et al.
patent: 58181158 (1983-10-01), None
Fischer et al., “An Integration of Deductive Retrieval into Deductive Synthesis”, 14th IEEE International Conference on Automated Software Engineering, Oct. 12, 1999, pp. 52-61.*
NB9006145, “Technique for Parallel Trace-Driven Cache Simulation”, IBM Technical Disclosure Bulletin, vol. 33, No. 1B, Jun. 1990, pp. 145-146 (5 pages).*
NN9412545, “Converting Between Object Oriented and Workflow Graph Views of Processes”, IBM Technical Disclosure Bulletin, vol. 37, No. 12, Dec. 1994, pp. 545-546 (4 pages).*
NN9411347, “Parallel Simulation of Multiprocessor Caches”, IBM Technical Disclosure Bulletin, vol. 37, No. 11, Nov. 1994, pp. 347-352 (12 pages).*
NN9205441, “Non-Interrupt Masking Trace Record Allocation”, IBM Technical Disclosure Bulletin, vol. 34, No. 12, May 1992, pp. 441-445 (8 pages).
Andersen Flemming
Baumgartner Jason Raymond
Roberts Steven Leonard
Kik Phallaka
McBurney Mark E.
O'Hagan Christopher P.
Siek Vuthe
Yee Duke W.
LandOfFree
Method and system for formal characterization of average... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for formal characterization of average..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for formal characterization of average... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3185498