The SECD Microprocessor - Graham, Brian T.

. .

Résumé :
emThe SECD Microprocessor/em is a substantial case study in hardware specification and verification. The subject is a silicon implementation of Landin's SECD machine, which is transformed into a layout, formally specified, and partially verified using the HOL proof assistant. It is important as a nontrivial worked example, clearly describing the organization and execution of the correctness of proof, and by making the sources available, will be helpful to those considering the use or learning about the application of formal methods. br/ The architecture is designed to provide support for functional programming, with complex machine instruction to support recursive definitions and function calls. This considerably raises the complexity of the state transitions to be verified, and an abstract data type and operations are introduced to express the specification. br/ emThe SECD Microprocessor/em illustrates what formal methods can achieve today, not only by some expert elite, but by anyone prepared to carefully consider the problems at hand. br/

Sommaire:
1 Formal Methods and Verification.- 1.1 Achievements in Hardware Verification.- 1.2 The HOL System.- 2 LispKit and the SECD Architecture.- 2.1 The Syntax of LispKit.- 2.2 The Interpretation of LispKit.- 2.3 SECD Architecture.- 2.4 LispKit to SECD Machine Code.- 2.5 Summary.- 3 SECD Architecture: Silicon Synthesis.- 3.1 Project Context.- 3.2 Levels of the Design.- 3.3 The Chip Interface.- 3.4 Internal Architecture and Microcode.- 3.5 The Final Layout.- 3.6 Summary and Status.- 4 Formal Specification of the SECD Design.- 4.1 Modelling Hardware.- 4.2 The Top Level Specification.- 4.3 The Low Level Definition.- 4.4 Register Transfer Level Specification.- 4.5 Relating the Levels.- 4.6 Summary.- 5 Verification of the SECD Design.- 5.1 Constraints.- 5.2 Structure of the Proof.- 5.3 Unfolding the System Definition.- 5.4 Phase Stage: Effect of Each Microinstruction.- 5.5 Microprogramming Stage: Symbolic Execution.- 5.6 Liveness.- 5.7 Computations across abstraction.- 5.8 Summary.- 6 Denouement.- 6.1 Putting the Proof Result into Context.- 6.2 Retrospective Improvements.- 6.3 Hardware Verification.