Accession Number:

ADA346065

Title:

Combining Symbolic Model Checking with Uninterpreted Functions for Out-of-Order Processor Verification

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Report Date:

1998-04-20

Pagination or Media Count:

21.0

Abstract:

We present a new approach to the verification of hardware systems with data dependencies using temporal logic symbolic model checking. As a benchmark we take Tomasulos algorithm HP96 for out-of-order instruction scheduling. Our approach is similar to the idea of uninterpreted function symbols BD94. We use symbolic values and instructions instead of concrete ones. This allows us to show the correctness of the machine independently of the actual instruction set architecture and the implementation of the functional units. Instead of using first order terms as in BD94, we represent symbolic values with a new compact encoding. In addition, we apply some other reduction techniques to the model. This significantly reduces the state space and allows the use of highly efficient symbolic model checkers like SMV instead of special decision procedures. The correctness of the method has been proven formally with the PVS theorem prover.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE