Real-time Processor Architectures for Worst Case Execution Time Reduction

I submitted my PhD thesis in January 2008, and my minor corrections were accepted four months later. The thesis deals with the problem of building computers that (1) complete their tasks within a guaranteed period of time ("hard real-time"), but also (2) complete those tasks as quickly as possible ("high performance"). Research indicates that these two goals are often mutually exclusive. Nevertheless, certain design strategies can improve performance while retaining predictability. The focus of my thesis is the CPU, the part of a computer that runs programs. I found a way to implement a CPU design that combines predictability with performance, and then used WCET analysis to show that it could run programs safely and optimise it for particular applications. I extended the work in subsequent publications.

On this page, you can download my thesis in PDF ("e-book") form. You can also download the software that goes with it. The following abstract summarises the work in a technical fashion.

Abstract

In a real-time system, programs must respond to external events in a timely fashion, completing all required subtasks before a deadline elapses. Worst case execution time (WCET) analysis is used to assure that deadlines are always met by determining the maximum period of time required to execute parts of a program. WCET analysis has been extensively studied, but existing techniques do not work well with CPUs that make use of dynamic execution optimisation features such as caches and superscalar out-of-order issue units. These features work well for average case execution time (ACET) reduction, but not for WCET reduction, since software must model the worst possible behaviour of the dynamic features to find the WCET.

This thesis explores the architectural issues relating to these problems, then characterises a class of CPU architecture that is explicitly designed for WCET reduction. An implementation of this architecture enables WCET reduction by allowing programs to move worst-case execution paths into a microprogram store, which acts as an scratchpad for parallel microinstructions. The exploitation of instruction-level parallelism (ILP) across basic block boundaries is enabled by the use of a superblock scheduler, which allows the architecture to reduce WCET further than previous CPU architectures intended to facilitate timing analysis.

Instances of the new architecture class are implemented and tested using field-programmable gate array (FPGA) hardware. A WCET reduction algorithm is proposed, implemented and tested based on the implicit path enumeration technique (IPET) for WCET analysis. Experiments are used to compare the algorithm and architecture with previous work.

Files

  • jack whitham thesis.pdf - the complete thesis as a PDF.

    172 double-sided A4 pages, suitable for printing or viewing on your PC. Use a PDF viewer, such as Adobe Acrobat Reader or XPDF. Please right-click on the link to save it on your computer before viewing.

  • jack-whitham-thesis-sw-dist-2008-04-30.tar.bz2 - the software written for the thesis.

    130Mb .tar.bz2 file for i386 Linux PCs, 651Mb decompressed. The manifest lists all included files and Appendix A contains documentation. You need at least 1Gb of free space to install the software, which is likely to require a vintage Linux distribution and involves running binaries built for 32-bit x86. Additional requirements are specified in Appendix A.

Licence

The thesis text is copyright (C) Jack Whitham 2004-2008. You can download it, print it and copy it provided you don't modify it. More formally, the redistribution licence is Creative Commons "Attribution - NoDerivs 2.0 England and Wales". A similar licence (GNU GPL version 2) applies to most of the software.