A Formal, Hierarchical Design and Validation Methodology for VLSI
Davie, Bruce S.
The high cost of fabricating VLSI circuits requires that they be validated, that is, shown to function correctly, before manufacture. The cost of design errors can be kept to a minimum if such validation occurs as early as possible; this is achieved by integrating validation into a hierarchical design procedure. In this thesis, a hierarchical approach to design, in which validation is performed between each pair of adjacent levels in the hierarchy, is developed. In order to adopt such an approach, a language is required for the formal description of hardware behaviour and structure. Therefore an important aspect of the development of the methodology, and a major theme of the thesis, is the development of languages to support the methodology. An enhanced version of CIRCAL, which enables large and abstract devices to be described concisely and supports formal reasoning about the behaviour of constructed systems, is presented. Specifications should accurately model the behaviour of real hardware and should be useful for design and validation; they should also be easy to write. In order to realise these goals, a number of specification techniques have been developed and a new language which enforces some of these techniques, thereby easing the specification task, is proposed. Ways in which a language may assist design have been investigated. Language constructs which restrict a designer, thereby removing some design decisions, have been developed. A simple correctness-preserving transformation is presented, illustrating another way in which a designer may be assisted by a formal language. Specification techniques play an important part in the validation task, as accurate and consistent modelling is vital in establishing the correctness of implementations. Techniques have also been developed which enable detailed implementations to be usefully compared with more abstract specifications. This is demonstrated in a large example, the specification, design and formal verification of a simple microprocessor. Finally, the concept of contextual constraints, restrictions on the environment in which a device may be placed, is introduced. A method of specifying such constraints has been developed, and it is shown that their formal treatment can provide assistance in specification, design and verification.