COM05 RapiTime: Worst-Case Execution Time technology - Confidential
Submitting InstitutionUniversity of York
Unit of AssessmentComputer Science and Informatics
Summary Impact TypeEconomic
Research Subject Area(s)
Information and Computing Sciences: Computation Theory and Mathematics, Computer Software
Summary of the impact
Impact: The underpinning research resulted in an innovative
Worst-Case Execution time (WCET) analysis technology now called RapiTime,
which was transferred to industry via a spin-out company, Rapita Systems
Ltd. The technology enables companies in the aerospace and automotive
industries to reduce the time and cost required to obtain confidence in
the timing correctness of the systems they develop. The RapiTime
technology has global reach having been deployed on major aerospace and
automotive projects in the UK, Europe, Brazil, India, China, and the USA.
Key customers include leading aerospace companies such as: [text removed
for publication]; as well as major automotive suppliers: [text removed for
publication]. Since 2008, Rapita has won export orders to China worth over
[text removed for publication]. From 2008/9 to 2011/12, the company's
annual revenues have more than doubled from [text removed for publication]
to over [text removed for publication]. As of August 2013, Rapita employs
[text removed for publication] people at its offices in York and
Context: Determining the longest time that software components can
execute on a microprocessor, referred to as the Worst-Case Execution Time
(WCET), is a key issue in the development of real-time embedded systems in
the aerospace and automotive industries. Here, intermittent timing
failures caused by software exceeding its budgeted execution time can lead
to operational problems, reliability issues, and in some cases
catastrophic consequences. In these applications the WCET of software
components needs to be tightly bounded to avoid the need to overprovision
hardware in terms of faster, but more costly processors.
Prior to the underpinning research, there were two main approaches to
WCET estimation; end-to-end measurement and static analysis. End-to-end
measurement techniques insert profiling code into the software. During
testing this profiling code records the end-to-end execution time of each
invocation of each software component. End-to-end measurement alone
typically under-estimates the WCET, and provides little confidence that
timing constraints will always be met during operation. Static analysis
techniques analyse the software object code and compute the WCET using a
model of the timing behaviour of the microprocessor. This is done without
running the code. Using static analysis alone has the disadvantage that
the computed WCETs depend on the accuracy of the timing model of the
processor and its hardware acceleration features.
Underpinning research: During the NextTTA project (1st
Jan 2002 to 31st Jan 2004) four members of the Real-Time
Systems Research Group (RTSRG) in the Department of Computer Science at
the University of York, Guillem Bernat, Antoine Colin, Stefan Petters, and
Alan Burns developed a set of hybrid and probabilistic techniques for WCET
analysis , , , , and , now referred to as RapiTime. The
RapiTime approach combines static analysis of the structure of the source
code with timing measurements taken during testing, which record the
execution time of short sub-paths through the code. RapiTime recognises
that the best possible model of an advanced microprocessor is the
microprocessor itself and therefore uses online testing to measure
the execution time of short sub-paths in the code. By contrast, offline
static analysis is the best way to determine the overall structure of the
code and the paths through it. Therefore RapiTime uses path analysis
techniques to build up a precise model of the overall code structure and
determine which combinations of sub-paths form complete and feasible paths
through the code. Finally the measurement and path analysis information
are combined using statistical methods to compute WCETs in a way that
captures accurately the execution time variation on individual paths due
to hardware effects.
This novel and innovative approach combines the advantages of both
measurement and static analysis techniques while avoiding their drawbacks.
Unlike static analysis, it does not require the expensive and time
consuming production of a precise timing model for each new microprocessor
variant and its hardware acceleration features, and so is portable to a
wide range of different microprocessors. RapiTime is also viable when the
only accurate timing model that is available is the microprocessor itself.
Further, RapiTime does not require the plethora of manual annotations that
static analysis alone needs to establish essential information about
control flow. This greatly reduces the amount of engineering time required
before meaningful results can be obtained, and removes a potential source
of errors. Compared to measurement, RapiTime is able to identify the
worst-case path and compute the overall WCET of software components from
the WCETs of sub-paths when not all of the complete paths through the code
have been executed. This significantly reduces the amount of testing
required to verify timing correctness.
For the full duration of the NextTTA project, while carrying out the
underpinning research, Guillem Bernat was a Lecturer, Antoine Colin and
Stefan Petters were Research Associates, and Alan Burns was a Professor in
the Computer Science Dept. at the University of York. (Martin Newby,
Professor of Statistical Science at City University in London, assisted
with some of the probabilistic methods used in ; however, the
overwhelming majority of the underpinning research was done at the
University of York). Antoine Colin left the University of York on 31st
Jan 2003, Stefan Petters on 31st July 2004, and Guillem Bernat
on 6th October 2005 (on secondment). Prof. Alan Burns remains
at the University of York to this day.
References to the research
 G. Bernat, A. Colin, S. M. Petters, "WCET Analysis of Probabilistic
Hard Real-Time Systems" IEEE Real-Time Systems Symposium (RTSS), December
2002, Austin, Texas, USA.
 A. Colin, S. M. Petters "Experimental Evaluation of Code Properties
for WCET Analysis" IEEE Real-Time Systems Symposium (RTSS), Cancun,
Mexico, December 2003.
 A. Colin, G. Bernat, "Scope Tree: a Program Representation for
Symbolic WCET Analysis" In Proc. 14th Euromicro Conference on Real-Time
Systems (ECRTS), June 2002, Vienna, Austria. DOI:
 G. Bernat, A. Colin, S. M. Petters, "pWCET a Toolset for automatic
Worst-Case Execution Time Analysis of Real-Time Embedded Programs" 3rd
Int. Workshop on WCET Analysis, at the Euromicro conference on Real-Time
Systems, Porto, Portugal, 1 July 2003. (Available as a technical report https://www.cs.york.ac.uk/ftpdir/reports/2003/YCS/353/YCS-2003-353.pdf)
Number of citations: Google Scholar 29th Aug 2013  - 256,
 - 49,  - 52,  - 53,  - 81. Scopus 29th Aug 2013:
 - 60,  - not indexed,  - 11,  - 12 (11/11/13),  - not
indexed. References , , and  best indicate the quality of the
underpinning research. Note that RTSS is widely recognised as the premier
conference in the real-time systems field. It is rated A according to the
ERA conference rankings 2010. ECRTS is also an A rated international
The research published in , , , , and  was carried out
under the EU funded FP5 project NextTTA (High-Confidence Architecture for
Distributed Control Applications) IST 2001-32111 (1st Jan 2002
to 31st Jan 2004, PI Prof. Alan Burns, University of York,
Details of the impact
Impact: The underpinning research was exploited in the development
of an innovative Worst-Case Execution time (WCET) analysis technology now
called "RapiTime". This technology was transferred to industry via the
formation in 2004 of a successful spin-out company; Rapita Systems Ltd.
This technology has been deployed on, and is in continuous use on, a
number of major long-term aerospace and automotive projects world-wide,
- [text removed for publication]: Flight Control Computer (FCC) and the
[text removed for publication] (RapiTime in continuous use since 2006)
- [text removed for publication]: FADEC (Full Authority Digital Engine
Control) for the [text removed for publication] (Since 2009).
- [text removed for publication]: (Since 2011).
- Alenia Aermacchi (Italy): Flight Control System for the M-346 military
transonic trainer. (Since 2010) .
- [text removed for publication] a European Space Agency [text removed
for publication] (Since 2012).
- [text removed for publication]: Used in a proof-of-concept relating to
new processes for the development of Flight Control Systems. (Since
- [text removed for publication]: Evaluation and tool qualification for
use on the [text removed for publication]. (Since 2008).
- [text removed for publication]: Development of [text removed for
publication] software modules. (Since 2009).
- [text removed for publication] control system for small vehicles,
[text removed for publication] (Since 2010).
Other customers since 2008 include [text removed for publication] and the
European Space Agency (ESA).
Note, commercially sensitive detailed quantification of end-user benefits
are not available from the above major international companies.
Since 2008, Rapita has also won significant export orders to China worth
over [text removed for publication] via its distributor Cinawind.
Customers include: [text removed for publication].
From 2008/9 to 2012/13, the company's annual revenues have more than
doubled [text removed for publication], with annual profits increasing
from [text removed for publication] to circa [text removed for
publication]. The majority of Rapita's revenues come from products and
services based on RapiTime.
Route to Impact: Above we detailed specific exploitation of the
technology and impact and during the REF period. Next we detail the
evidential link between the underpinning research and that impact. During
the EU FP5 NextTTA project members of the RTSRG group, Guillem Bernat,
Antoine Colin, Stefan Petters, and Alan Burns, introduced the underpinning
research on hybrid measurement-based WCET analysis. This approach combined
both measurement and static analysis techniques to accurately estimate the
WCET of complex software components running on advanced microprocessors.
As part of the project, they also developed a prototype WCET analysis tool
called pWCET . This tool was evaluated on an Audi drive-by-wire system.
Audi was an industrial partner in the NextTTA project. Audi's expression
of interest in pWCET and its capabilities led directly to the formation of
a spin-out company to transfer this technology into industry.
In 2004, members of the RTSRG; Guillem Bernat, Ian Broster, Antoine
Colin, and Robert Davis, and the University of York founded a spin-out
company called Rapita Systems Ltd. (www.rapitasystems.com)
to commercialise the technology and bring it to market. All rights to the
technology and prototype tools were transferred to the company by the
University of York which became a shareholder in the company.
In 2005, Rapita Systems received £200k of funding from Viking Investments
Ltd. and an associated group of Business Angels . Following the initial
technology transfer, the pWCET prototype was re-implemented as a
commercial quality tool and re-branded as RapiTime. RapiTime has since
been extended to support analysis of systems written in C++ as well as the
C, and Ada programming languages, and has recently been complemented by a
Code Coverage tool (RapiCover) which uses the underpinning RapiTime
technology for code instrumentation and analysis. Together, RapiTime and
RapiCover are part of the Rapita Verification Suite (RVS).
In 2006, BAE Systems used RapiTime on the Hawk Advanced Jet Trainer
project . Here, RapiTime was used to identify opportunities for WCET
reduction, thus creating headroom for new functionality to be added to the
system, while avoiding the need for a costly hardware upgrade. Using
RapiTime, BAE identified that just 1% of hundreds of thousands of lines of
code contributed 29% of the overall WCET. Further, by focusing
optimisation efforts on this 1% of the code, they were able to reduce the
WCET by 23% . Further, RapiTime was quantified as being able to
identify timing problems with less than 10% of the effort of previous
approaches, potentially saving months of work. As a result Rapita received
a BAE chairman's award for Innovation in the category Transferring Best
Since 2008, Rapita has focused on sales of its RVS product, centred on
RapiTime, to customers in the aerospace and automotive markets. This
impact has been described in the previous section.
The RTSRG at the University of York continues to have strong links with
Rapita; Prof. Alan Burns is chairman of the Board, while Dr. Robert Davis
is a Non-Executive Director of the company and also a member of the RTSRG.
Beneficiaries: RapiTime enables companies in the aerospace and
automotive electronics industries to reduce the time and cost required to
obtain confidence in the timing correctness of the systems they develop.
It provides a cost-effective means of targeting software optimisation,
such that new functionality can be added to existing systems without the
need for expensive hardware upgrades. Further, RapiTime is portable across
a wide range of different microprocessors, meaning that companies can use
the same technology across multiple projects without the need for
re-training or adoption of multiple solutions.
[text removed for publication], the major [text removed for publication]
aerospace supplier, described the benefits of using RapiTime to identify
timing problems during continued development of the Flight Control System
for the [text removed for publication] as follows: "The biggest
benefit that RapiTime brought to our development process was just how
quickly we could get comprehensive timing measurements from our tests.
Not only did we reduce our effort requirements for the testing, but we
could use our results in ways that were infeasible before. It is now
significantly faster for us to identify a timing issue, update the
software to resolve the issue, test the updated software and verify that
it's fixed" — Wayne King, Engineering Fellow, [text removed for
publication] — 30th July 2009 .
Without RapiTime, the timing measurement and analysis process needed to
determine WCETs has to be done manually. This is a painstaking and error
prone process that takes considerable time and effort. It also needs to be
repeated when changes are made to the application software. Further, the
manual process provides no information about the worst-case path, or the
contribution of different sections of code to the WCET. This makes code
optimisation an ad-hoc, ineffective and inefficient process, as optimising
for the worst-case is very different from optimising for the average case.
Alenia Aermacchi engineers working on the M-346 Flight Control System
said, "the main advantage [of using RapiTime] is the possibility to
identify software bottlenecks that can be subject to optimisation.
Without RapiTime the mandatory code optimisation would have been done
without the knowledge of where to concentrate the efforts." .
Overall, "Using RVS, customers have cut the worst-case execution time
of large scale, legacy applications by up to 50% with only a few days
effort, and significantly reduced unnecessary testing and
instrumentation overheads" .
Rapita has offices in York and opened a second office in Cambridge in May
2012. Rapita has created and sustained [text removed for publication] high
technology jobs . The success and indeed the existence of the company
is a consequence of the underpinning research as described in the
Corroboration of all of the facts presented above about Rapita and its
customers etc. can be obtained from .
Sources to corroborate the impact
 G. Bernat, R.I. Davis, N. Merriam, J. Tuffen, A. Gardner, M. Bennett,
D. Armstrong. "Identifying Opportunities for Worst-case Execution Time
Reduction in an Avionics System". Ada User Journal pp. 189-194,
Volume 28, Number 3, Sept 2007.
 Chief Financial Officer (CFO), Rapita Systems Ltd.