Your browser does not support JavaScript! Skip to main content
Free 30-day trial Customer portal Careers DO-178C Handbook
 
Rapita Systems
 

Industry leading verification tools & services

Rapita Verification Suite (RVS)

  RapiTest - Unit/system testing   RapiCover - Structural coverage analysis   RapiTime - Timing analysis (inc. WCET)   RapiTask - Scheduling visualization   RapiCoverZero - Zero footprint coverage analysis   RapiTimeZero - Zero footprint timing analysis   RapiTaskZero - Zero footprint scheduling analysis

Multicore verification

  MACH178   Multicore Timing Solution   RapiDaemons

Services

  V & V Services   Qualification   Training   Tool Integration  Support

Industries

  Aerospace (DO-178C)   Automotive (ISO 26262)   Space

Other

  RTBx   Mx-Suite   Software licensing   Product life cycle policy  RVS development roadmap

Latest from Rapita HQ

Latest news

RVS 3.18 Launched
Solid Sands partners with Rapita Systems
Danlaw Acquires Maspatechnologies - Expanding Rapita Systems to Spain
Rapita co-authored paper wins ERTS22 Best paper award
View News

Latest from the Rapita blog

Measuring response times and more with RapiTime
Why mitigating interference alone isn’t enough to verify timing performance for multicore DO-178C projects
There are how many sources of interference in a multicore system?
Supporting modern development methodologies for verification of safety-critical software
View Blog

Latest discovery pages

do178c DO-178C Guidance: Introduction to RTCA DO-178 certification
matlab_simulink MATLAB® Simulink® MCDC coverage and WCET analysis
code_coverage_ada Code coverage for Ada, C and C++
amc-20-193 AMC 20-193
View Discovery pages

Upcoming events

Aerospace Tech Week Europe 2023
2023-03-29
Aeromart Montreal 2023
2023-04-04
Certification Together International Conference
2023-05-10
View Events

Technical resources for industry professionals

Latest White papers

DO178C Handbook
Efficient Verification Through the DO-178C Life Cycle
A Commercial Solution for Safety-Critical Multicore Timing Analysis
Compliance with the Future Airborne Capability Environment (FACE) standard
View White papers

Latest Videos

Streamlined software verification with RVS 3.18
Sequence analysis with RapiTime
Visualize call dependencies with RVS thumbnail
Visualize call dependencies with RVS
Analyze code complexity thumbnail
Analyze code complexity with RVS
View Videos

Latest Case studies

Supporting ISO 26262 ASIL D software verification for EasyMile
RapiCover’s advanced features accelerate the certification of military UAV Engine Control
Front cover of whitepaper collins
Delivering world-class tool support to Collins Aerospace
View Case studies

Other Downloads

 Webinars

 Brochures

 Product briefs

 Technical notes

 Research projects

Discover Rapita

Who we are

The company menu

  • About us
  • Customers
  • Distributors
  • Locations
  • Partners
  • Research projects
  • Contact us

US office

+1 248-957-9801
info@rapitasystems.com
Rapita Systems, Inc.
41131 Vincenti Ct.
Novi
MI 48375
USA

UK office

+44 (0)1904 413945
info@rapitasystems.com
Rapita Systems Ltd.
Atlas House
Osbaldwick Link Road
York, YO10 3JB
UK

Spain office

+34 930 46 42 72
info@rapitasystems.com
Rapita Systems S.L.
Parc UPC, Edificio K2M
c/ Jordi Girona, 1-3, Office 306-307
Barcelona 08034
Spain

Working at Rapita

Careers

Careers menu

  • Current opportunities & application process
  • Working at Rapita
Back to Top

Why Static analysis doesn't work for Multicore WCET estimation

Breadcrumb

  1. Home
  2. Blog
  3. Why Static analysis doesn't work for Multicore WCET estimation
Christos Evripidou & Daniel Wright
2019-10-07

The true worst-case execution time (WCET) of an application executing on modern hardware cannot be feasibly calculated. This is typically because of performance optimization features present in modern hardware. In domains featuring critical applications, the term WCET is synonymous with a WCET estimate, which must be tight (not too pessimistic), but never optimistic.

The estimation of a tight WCET for applications running on multicore processors is far more challenging than for those running on single core processors. Multicore processors are more complex in design, and less predictable in behavior than single core systems.

Not only are multicore processors inherently more complex, they also suffer from interference due to contention for shared resources and other hardware idiosyncrasies. Constructing an accurate enough model of the hardware is not feasible due to the level of complexity and strict restrictions on disclosing closely guarded IP block design features. Static WCET estimation techniques generally cannot account for all possible sources of interference, and even if they could, they would be very complex and extremely computationally expensive to run.

What is static analysis?

Static analysis was developed as a method of worst-case execution time estimation. The key advantage of static analysis over measurement-based methods is that no measurements from a real target are required, minimizing the cost of testing.

Static analysis techniques rely on having a precisely accurate model of the timing characteristics of the processor, including the behavior of pipelines, caches, memory, buses, and any other hardware features that affect the execution time of machine instructions.

Static analysis techniques analyze the program and compute the worst-case path and worst-case execution time by reference to the model of the processor's timing behavior. This is done without executing the code on the target platform.

Static analysis for multicore is too pessimistic

Static analysis techniques can identify an upper bound on the worst-case execution time by finding the worst-case path with cross-core interference factored in. In the context of safety-critical systems, this pessimistic approach may at first seem the safest way to approach MCP WCET estimation for such unpredictable systems.

However, the pathological WCET that static analysis techniques can theoretically produce is so pessimistic it is not fit for purpose. As the identifies in the Assurance of Multicore Processors in Airborne Systems document, “Abstractions used for the WCET evaluation, for instance processor models, may not be correct or be so inaccurate that the computed WCETs are too pessimistic”.

The excessive pessimism of static WCET estimation stems from two fundamental problems:

  1. It is intractable to simulate actual MCP behavior via system modelling. Some semiconductor manufacturers do not even understand some of the behaviors observed in the MCPs they produce, so creating a 100% accurate model that always behaves exactly like the real thing is extremely difficult.
  2. As MCPs feature so many different interoperable components running in parallel, it is theoretically possible for every-possible-interference-channel to affect the application running to the worst-possible-extent at one particular time. This would generate a massive WCET for that worst case scenario, despite the likelihood of this scenario being extremely low in this context.

To understand the implications of these two problems when estimating MCP WCET, WCETs determined by static analysis for some MCPs have been observed to be more than 200 times higher than the equivalent dynamic WCET figure.

The implication of excessively pessimistic WCET estimation is that more of the MCP’s resources/computational power need to be set aside for handling vanishingly unlikely worst-case scenarios which theoretically could happen, but careful scheduling could prevent.

A measurement-based approach is better

A measurement-based approach to WCET estimation for multicore systems can yield practical values.

Measurement-based timing analysis tools such as RapiTime can help support some of the challenges of multicore timing analysis. One of the major challenges is in handling and analysis of the huge amount of data that must be collected across a comprehensive multicore timing analysis test campaign. RapiTime solves this challenge by providing various options for how data is summarized and displayed, including allowing filtering of results on specific tests and performance metrics, and allowing baselines to be set against which to compare results.

A common approach to determining WCET by a measurement-based approach is to design and run timing tests that use interference generator applications to generate interference on the multicore system. Rapita have a library of such applications, called RapiDaemons, which generate configurable, constant, predictable, and reproducible loads on specific shared multicore resources. In a measurement-based approach, the execution time of software running on one core is tested while interference generators such as RapiDaemons are executed on none, one or more other cores, so the impact of multicore interference on the software execution time can be understood (e.g. Figure 1).

RapiDaemons generate multicore interference
Figure 1. RapiDaemons can be used to generate interference in multicore systems

To apply a measurement-based approach to multicore WCET estimation, detailed understanding of the multicore platform and the shared resources and interference channels on it is needed. Expert engineers are needed to understand the system, analyze performance requirements, develop test plans, and generate test scenarios that stress the system’s execution time by selecting appropriate interference generators to use and performance monitoring counters to observe during tests. At Rapita, we apply a V-model based approach as shown in Figure 2.

Rapita V model approach to multicore timing analysis
Figure 2. Rapita V-model based approach to multicore timing analysis

The use of a measurement-based approach that utilizes interference generators such as RapiDaemons avoids the pitfalls of static analysis; as execution times are determined from real measurements, there are no errors due to incorrect models (and there are currently no models available that can accurately model multicore systems and their interference), and as tests are specifically designed to identify the high-water mark paths through the code, the results are not overly pessimistic.

A proven approach for multicore WCET estimation

Rapita’s MACH178 solution and Multicore Timing Solution are the only commercial solutions for WCET estimation for multicore systems. A key part of these solutions is the supporting tool suite which includes RapiTime, a dynamic analysis tool identified by The FAA as “an example of a mature tool in this aspect [dynamic timing analysis]”.

DO-178C webinars

DO178C webinars

White papers

DO178C Handbook Efficient Verification Through the DO-178C Life Cycle
A Commercial Solution for Safety-Critical Multicore Timing Analysis
Compliance with the Future Airborne Capability Environment (FACE) standard
5 key factors to consider when selecting an embedded testing tool

Related blog posts

Measuring response times and more with RapiTime

.
2023-03-10

Why mitigating interference alone isn’t enough to verify timing performance for multicore DO-178C projects

.
2022-11-17

Robust partitioning for multicore systems doesn’t mean freedom from interference

.
2022-01-05

Assured Multicore Partitioning for FACE Systems

.
2020-11-10

Pagination

  • Current page 1
  • Page 2
  • Page 3
  • Page 4
  • Next page Next ›
  • Last page Last »
  • Solutions
    • Rapita Verification Suite
    • RapiTest
    • RapiCover
    • RapiTime
    • RapiTask
    • MACH178

    • Verification and Validation Services
    • Qualification
    • Training
    • Integration
  • Latest
  • Latest menu

    • News
    • Blog
    • Events
    • Videos
  • Downloads
  • Downloads menu

    • Brochures
    • Webinars
    • White Papers
    • Case Studies
    • Product briefs
    • Technical notes
    • Software licensing
  • Company
  • Company menu

    • About Rapita
    • Careers
    • Customers
    • Distributors
    • Industries
    • Locations
    • Partners
    • Research projects
    • Contact
  • Discover
    • AMC 20-193
    • What is CAST-32A?
    • Multicore Timing Analysis
    • MC/DC Coverage
    • Code coverage for Ada, C & C++
    • Embedded Software Testing Tools
    • Aerospace Software Testing
    • Automotive Software Testing
    • Certifying eVTOL
    • DO-178C
    • WCET Tools
    • Worst Case Execution Time
    • Timing analysis (WCET) & Code coverage for MATLAB® Simulink®

All materials © Rapita Systems Ltd. 2023 - All rights reserved | Privacy information | Trademark notice Subscribe to our newsletter