Deploying Event-B in an Industrial Microprocessor Development

From Evidence on Formal Methods Uses and Impact on Industry
Jump to: navigation, search
Success Story
Domain CPU
Keywords EventB, micro-electronic circuit, instruction set architecture
Source XMOS

Main -> DEPLOY Success Stories -> Micro-electronics#2

Short Description

XCore Processor

The Instruction Set Architecture is a key document for the design of a microprocessor. It is very important to have accurate specification of this because it is the primary reference source for engineers and computer scientists developing and optimizing the compiler tools. Third parties might also want to write their own implementation for microprocessors not licenced with a proprietary micro-architecture. Specification errors can be very subtle and not reveal themselves immediately but many cycles later, so ensuring the quality of such a document is quite a challenge.

The objective of XMOS was to achieve a rigorous review of the natural language specification of the instruction set architecture (ISA) of their XCore processor. XMOS decided to join the DEPLOY Associate program to evaluate how formal modelling and verification could help to provide a high level of quality of their ISA specification. The objective of the project was to see how well Event-B and the Rodin toolset could help producing a rigorous restatement of the XMOS’s existing specification, especially to identify errors and omissions.

The project was successful in producing a fully formalised and proved specification. It required some Rodin tools extension to get the right tooling support. In addition the formal model could also be used to generate a reference VM simulator of the ISA to run test suites.

Related FAQ

of Interest to Project and QA Managers

of Interest to Engineers and Analysts

  • TOOL-EA-2 Are tools functionality automating all tedious tasks?

of Interest to QA Practionners

Benefits

  • Very high quality ISA specification: it could be fully formalised and proved, error and omissions were removed - see [1]
  • Automated generation of a simulator VM on which to run test suites
  • Some domain specific effort estimation metrics based on the size of the instruction set

Limitations

  • Heavy process requiring adequate window of opportunity for a full deployment, e.g. new large project
  • Tool limitation: could be addressed through specific method and tool extensions

Elaboration

XMOS specific methods and tools extensions: in order to formalize the XMOS ISA, current methods and tools revealed a number of limitations which were overcome by specific extensions:

  • ISA Model Editor – a specific model editing tool was developed to allow rapid construction of repeating patterns in event-b models and theorem structures. This was achieved by combining the existing Rodin text editor and the expansion of the C auto generation tool.
  • ISA Specific Proof Tactics – as the model size grew, it became necessary to achieve improve proof automation especially to reduce the time spent on some simple but time consuming manual proofs. ISA specific proof tactics were added to the Rodin core. Combined with the relevance filter, the automatic rate grew from 10% to 64%. This is however still far from the 95% achieved on typical small models and the ideal 100%.
  • B2C improvement – the B2C generator was improved in order to be able to generate simulator from an Event-B specification.

XCore ISA formalisation – Based on the above extensions, the ISA could be entirely formalised and proved. The publication of the ISA specification with all proof discharge is a major success. However it was a huge effort. Some special instructions related to multi-threading and communications were in particular very tricky to model and prove. Of course during the formalisation process several issues in the original document were discovered. Those can mostly be classified in three classes: direct errors, ambiguities (leading to different interpretations) and omission (leaving to the implementation the choice of some behaviour)

Automatic generation of a VM for testing – Based on the improvement of the B2C generator a virtual machine can be generated from the model. The actual process was that the model, the VM and the test suite were developed simultaneously making sure all goals could be reached and taking benefits of both a proof-based and test-based approach.

Effort estimation – consolidating the data from a previous project and this project, similar figure about the model size and effort w.r.t. the instruction set could be produced and can be used as initial estimates for a new project.

For the full story, the DEPLOY Book [2]will report a full chapter on this work. An LNCS paper also describes the method to specify, design and construct sound and complete ISAs by stepwise refinement and formal proof using the formal method Event-B [3]

Specific DEPLOY Contributions

  • RODIN tool extension: domain specific pattern-based editor and proof rules

Further work

None

References

  1. A Formally Constructed Instruction Set Architecture Definition of the XCore Microprocessor, http://deploy-eprints.ecs.soton.ac.uk/346
  2. Industrial deployment of system engineering methods providing high dependability and productivity. A. Romanovsky, M. Thomas (Eds). Springer. 2012
  3. Fangfang Yuan, Stephen Wright, Kerstin Eder and David May, Managing Complexity through Abstraction: A Refinement-Based Approach to Formalize Instruction Set Architectures, Lecture Notes in Computer Science, Volume 6991/2011, 585-600, 2011


Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox