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

摘要

We present a new approach to the verification of hardware systems with datadependencies using temporal logic symbolic model checking. As a benchmark we take Tomasulo's 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.