Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
1999-10-08
2004-06-01
Jones, Hugh (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S013000, C703S015000, C703S016000, C716S030000, C716S030000
Reexamination Certificate
active
06745160
ABSTRACT:
1. DESCRIPTION OF THE INVENTION
1.1. Field of the Invention
The present invention is related to verification of scheduling steps in high-level synthesis. A key focus of this invention is a novel technique for verifying scheduling including all the typical transformations likely to be performed in conjunction with it. Specifically, the present invention provides a verification technique which can handle loops and a variety of loop transformations performed during scheduling.
1.2. Background of the Invention
The importance of synthesis from higher level specifications as a means to reduce the time to market circuits is well established. In addition to allowing faster synthesis, it also leads to greater reuse. Just as combinational logic verification by means of tools from Chrysalis®, Synopsys® and many other companies is necessary to validate the final logic netlist against an initial netlist specification, tools are also necessary to validate an RT level netlist obtained from a high level behavioral description. The present invention is geared toward providing improved techniques to perform validation. It is now well established that simulation by itself cannot be sufficient as a validation strategy since it is time consuming without guaranteeing correctness. Hence, a formal verification methodology is required.
Given the scope of transformations applied to realize the final RTL from an initial behavioral specification, a black box verification system that just takes as input the descriptions at the two widely disparate levels is, for all practical purposes, unviable. Fortunately, whether the synthesis itself is done using automatic tools or manually, it generally follows a common basic flow consisting of clearly demarcated fundamental steps like scheduling, resource allocation and register assignment. For a validation methodology to be practical, it must leverage off the knowledge of this flow. In fact, it can be argued that keeping the demarcation between steps like scheduling and register assignment intact is a good “design-for-verification” strategy. At the expense of some quality of the final design, the synthesis process becomes much easier to verify.
While it is easier than verifying the entire synthesis process, the verification of the individual steps in a high-level synthesis flow is by no means straightforward. Scheduling is the task of assigning time stamps to operations. In a synchronous design, this is performed by associating operations with states. In order to meet the various design requirements, transformations like operation reordering, loop unrolling, speculative execution etc. may be carried out during this step. A minimum requirement for a verification tool claiming to check scheduling is to include these transformations in its scope.
In the present disclosure, symbolic simulation implies a procedure that propagates variables rather than variable values forward through a circuit. The term “uninterpreted”, in this context means that when complex operations like the standard arithmetic operations are encountered, the input list and the operation name are forwarded rather than the value of a Boolean function of the inputs.
1.2.1. Related Work
Several conventional techniques have been proposed for verifying designs generated from high-level descriptions. Considerable activity on symbolic simulation for program and hardware verification took place in the seventies and eighties. For a key representative, see J. Darringer, “The application of program verification techniques to hardware verification,” in
Proc. Design Automation Conf
, pp. 375-381, June 1979. However, the work by Darringer and its derivatives have limited application in the context of verifying scheduling. Some of the derivative work can be found in W. Cory, “Symbolic simulation for functional verification with ADLIB and SDL,” in
Proc. Design Automation Conf
, pp. 82-89, June 1981. and V. Pitchumani and E. Stabler, “A formal method for computer design verification,” in
Proc. Design Automation Conf
., pp. 809-814, June 1982.
Importantly, the main limitation of Darringer's work was that it required the user to provide invariants for the symbolic simulator to perform checking. It is known that in practice, when comparing two hardware descriptions, invariants are the correspondence points (control points in Darringer's terminology) at which the complete state of one description must match the state of the other. In the context of scheduling, the user needs to have detailed knowledge of, for example, the loop transformations carried out by the synthesis tool in order to provide this information to the simulator. Such a requirement is hard. Further, such a requirement would partly defeat the purpose of the verification. Also, with a user providing the correspondence points, the issue of completeness remains unresolved. The same basic algorithm with the added ability to detect and utilize correspondences among intermediate signals between control points to simplify the expressions to be checked for isomorphism at the control points was proposed in C.-T. Chen and A. Parker, “A hybrid numeric/symbolic program for checking functional and timing compatibility of synthesized designs,” in
Proc. The International Symposium on High
-
Level Synthesis
, pp. 112-117, May 1994.
A few other related references have also been discussed herein. Minato proposed a Binary Decision Diagram (BDD) based approach for establishing equivalence between two hardware descriptions. See S. Minato, “Generation of BDDs from hardware algorithm descriptions,” in
Proc. Int. Conf Computer-Aided Design
, pp. 644-649, November. 1996. In this approach, all conditional branching are converted to straight line code by the use of additional variables. Further, loops are handled by unrolling each loop until the BDDs for all variables stop changing with additional unrolling. Two descriptions are deemed equivalent if their BDDs are equivalent. This method suffers from the limitations of BDDs in representing arithmetic functions, and from the need to explicitly unroll loops until the loop exit condition is satisfied. Gong et al. proposed a set of rule suites for checking the various steps in high-level synthesis. See J. Gong, C. T. Chen, and K. Kucukcakar, “Multi-dimensional rule checking for high-level design verification,” in
Proc. int. High
-
level Design Validation & Test Wkshp
., November. 1997. However, their equivalence checker was limited to checking structural isomorphism. The contribution of Bergamaschi and Raje was to show how equivalence checking could be performed when corresponding signals in the two descriptions must be observed at different time points. See R. A. Bergamaschi and S. Raje, “Observable time windows: Verifying high-level synthesis results,”
IEEE Design & Test of Computers
, vol. 8, pp. 40-50, April. 1997.
A number of techniques have been proposed recently for modeling arithmetic and control arithmetic interactions in the context of verification. See K. T. Cheng and A. S. Krishnakumar, “Automatic functional test generation using the extended finite state machine model,” in
Proc. Design Automation Conf
, June 1993; and F. Fallah, S. Devadas, and K. Keutzer, “Functional vector generation for HDL models using linear programming and 3-satisfiability,” in
Proc. Design Automation Conf
, June 1998 and J. Kukula, T. Shiple, and A. Aziz, “Implicit state enumeration for FSMs with datapaths,” in
Proc. Formal Methods in Computer Aided Design
, November. 1998. These techniques are powerful and have potential future application in conjunction with model checking techniques or theorem proving in the verification of designs generated from high-level synthesis. J. R. Burch, E. M. Clarke, D. E. Long, K. L. McMillan, and D. L. Dill, “Symbolic model checking for sequential circuit verification,”
IEEE Transactions on Computer
-
Aided Design
, vol. 13, April. 1994; R. K. Brayton et al., “VIS: A system for verification and synthesis,” in
Proc. int. Conf Computer
-
Aided Verification
, July 1996; and S. Owre, J. M. Rushby,
Ashar Pranav
Bhattacharya Subhrajit
Gupta Aarti
Raghunathan Anand
Ferris Fred
Jones Hugh
LandOfFree
Verification of scheduling in the presence of loops using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Verification of scheduling in the presence of loops using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Verification of scheduling in the presence of loops using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3293664