Worst-Case Execution Time (WCET) Analysis for Multicore Systems - Part 1: Interference and Coupling

By Jay Thomas, Senior Direc­tor of Field Engi­neer­ing, TASKING, and Ger­ard Vink, Indus­try Spe­cial­ist, TASKING

This four-part arti­cle series explains how to under­stand, mea­sure, and mit­i­gate Worst-Case Exe­cu­tion Time (WCET) in mod­ern mul­ti­core embed­ded sys­tems with a focus on require­ments, design, and ver­i­fi­ca­tion. In part 1, we’ll estab­lish the con­cep­tu­al foun­da­tion for under­stand­ing WCET by defin­ing what inter­fer­ence and cou­pling are, how mul­ti­core hard­ware intro­duces hid­den sources of tim­ing vari­abil­i­ty, and the sig­nif­i­cant impact these can have on sys­tem exe­cu­tion.

Foundations: Interference and Coupling

Many safe­ty-crit­i­cal embed­ded sys­tems, includ­ing auto­mo­tive, avion­ics, indus­tri­al con­trol, mil­i­tary, and med­ical appli­ca­tions, must guar­an­tee that crit­i­cal tasks are always com­plet­ed with­in fixed time bud­gets. Miss­ing a dead­line even once in a hard real-time sys­tem can be cat­a­stroph­ic. Con­sid­er an air­craft flight-con­trol loop that must respond with­in mil­lisec­onds, or an auto­mo­tive safe­ty func­tion that must actu­ate a brake to avoid a col­li­sion.

The tra­di­tion­al approach to meet­ing tim­ing guar­an­tees is to deter­mine the Worst-Case Exe­cu­tion Time (WCET) for each crit­i­cal task and demon­strate that it fits with­in the allo­cat­ed time bud­get. In prin­ci­ple, this sounds straight­for­ward. In prac­tice, espe­cial­ly when writ­ing soft­ware for mod­ern mul­ti­core proces­sors, assess­ing WCET is one of the most tech­ni­cal­ly demand­ing chal­lenges in safe­ty-crit­i­cal soft­ware develop­ment.

This arti­cle series explains why. We begin by intro­duc­ing two foun­da­tion­al con­cepts that under­pin the WCET prob­lem: inter­fer­ence and cou­pling (part 1). Under­stand­ing these con­cepts pre­cise­ly is essen­tial, because they are the root cause of the tim­ing vari­abil­i­ty that makes WCET hard to bound. The rest of the series will cover hid­den tim­ing cou­pling in mul­ti­core proces­sors (part 2), a three-stage method­ol­o­gy for accu­rate­ly access­ing WCET (part 3), and ways to mit­i­gate tim­ing cou­pling inter­fer­ence to guar­an­tee real-time dead­lines (part 4).

Unintentional Interference: The Core Concept

Inter­fer­ence occurs when one soft­ware com­po­nent unin­ten­tion­al­ly affects the behav­ior or state of anoth­er dur­ing exe­cu­tion. Inter­fer­ence is not a delib­er­ate inter­ac­tion. Rather, inter­fer­ence is an unwant­ed side effect that aris­es when two or more com­po­nents share a resource with­out suf­fi­cient coor­di­na­tion.

Inter­fer­ence is par­tic­u­lar­ly dan­ger­ous in safe­ty-crit­i­cal sys­tems because it is often invis­i­ble at the design level. A soft­ware archi­tect may have designed two tasks as com­plete­ly inde­pen­dent. Yet at run­time, when these tasks exe­cute on shared hard­ware, they can inter­fere with each other through shared microar­chi­tec­tur­al resources such as caches, mem­o­ry buses, inter­rupt con­trollers that lie below the soft­ware abstrac­tion layer.

In the con­text of tim­ing analy­sis, the key effect of inter­fer­ence is vari­abil­i­ty in exe­cu­tion time. When inter­fer­ence occurs, a task takes longer to exe­cute than it would in iso­la­tion. Cru­cial­ly, the amount of extra time depends on the behav­ior of other tasks run­ning con­cur­rent­ly and can vary with every run. This vari­abil­i­ty adds com­plex­i­ty to mea­sur­ing the WCET because it is dif­fi­cult to deter­mine which com­bi­na­tion of inter­fer­ence pro­duces the worst-case impact.

Coupling: The Structural Source of Interference

Cou­pling describes the degree of depen­den­cy between two soft­ware com­po­nents. Where inter­fer­ence is a run­time phe­nom­e­non, cou­pling is a struc­tur­al one as it describes the path­ways through which inter­fer­ence can occur.

There are three forms of cou­pling rel­e­vant to WCET analy­sis. They are not mutu­al­ly exclu­sive, and a real-world sys­tem will typ­i­cal­ly exhib­it all three. How­ev­er, they arise from dif­fer­ent sources and thus require dif­fer­ent analy­sis tech­niques to mea­sure their impact.

Data Coupling

Data cou­pling occurs when two tasks share access to the same data. Con­sid­er a sim­ple exam­ple: Task A reads a value and begins a cal­cu­la­tion. Task B needs to update that same value. How­ev­er, if Task B mod­i­fies the value while Task A is mid-cal­cu­la­tion, Task A may pro­duce incor­rect results. To pre­vent this, one task must wait for the other to fin­ish, intro­duc­ing a delay.

This delay adds vari­abil­i­ty to exe­cu­tion time. In a sys­tem with many tasks shar­ing many data objects, the inter­ac­tions can become high­ly com­plex, and the cumu­la­tive neg­a­tive effect on tim­ing can be sig­nif­i­cant.

Control Coupling

Con­trol cou­pling occurs when one task direct­ly influ­ences the exe­cu­tion path of anoth­er, typ­i­cal­ly through shared flags, sta­tus vari­ables, or mode reg­is­ters. For exam­ple, an engine con­trol mod­ule may behave dif­fer­ent­ly depend­ing on whether a “land­ing gear engaged” flag has been set by a sep­a­rate task. The exe­cu­tion time of the con­trol mod­ule varies with the value of that flag, which is set exter­nal­ly to the mod­ule.

Con­trol cou­pling affects tim­ing because it intro­duces con­di­tion­al branch­es whose exe­cu­tion depends on the state of other tasks, not just the task’s own inputs.

Timing Coupling

Tim­ing cou­pling is the form of cou­pling most spe­cif­ic to mul­ti­core sys­tems. It is also the most dif­fi­cult to ana­lyze. While not explic­it­ly men­tioned in DO-178C or AC 20-193, the effect of tim­ing cou­pling emerges by exam­in­ing data and con­trol flow cou­pling over time. Tim­ing cou­pling occurs when two tasks inter­fere with each other through shared hard­ware resources. This means tim­ing cou­pling can arise even when the two soft­ware com­po­nents have no data or func­tion­al rela­tion­ship at the soft­ware level.

For exam­ple, two tasks run­ning on dif­fer­ent cores of a mul­ti­core proces­sor may com­pete for the same L2 cache, the same mem­o­ry bus, or the same mem­o­ry con­troller. Such com­pe­ti­tion, also known as resource con­tention, caus­es each task to exe­cute with more delay than it would if it were the only task run­ning in the sys­tem. Crit­i­cal­ly, tasks are not “aware” of each other at the soft­ware level as they are log­i­cal­ly inde­pen­dent. The inter­fer­ence aris­es entire­ly from shared hard­ware infra­struc­ture and how resource con­tention is man­aged.

This is why tim­ing cou­pling is con­sid­ered “hid­den”. As it can­not be detect­ed by inspect­ing the soft­ware archi­tec­ture. It can only be mea­sured by run­ning the tasks con­cur­rent­ly on real tar­get hard­ware and mea­sur­ing the result­ing exe­cu­tion times.

Cou­pling Type	Source of Depen­den­cy	Vis­i­ble in Soft­ware Design?	Analy­sis Approach
Data cou­pling	Shared data objects / mem­o­ry	Yes	Sta­t­ic analy­sis, data flow analy­sis
Con­trol cou­pling	Shared flags / sta­tus vari­ables	Yes	Sta­t­ic analy­sis, con­trol flow analy­sis
Tim­ing cou­pling	Shared hard­ware resources (cache, bus)	No - hard­ware level only	On-tar­get dynam­ic mea­sure­ment

The Relationship Between Coupling and Interference

Cou­pling and inter­fer­ence are relat­ed but dis­tinct con­cepts. Cou­pling is the struc­tur­al con­di­tion that makes inter­fer­ence pos­si­ble. Inter­fer­ence is the run­time man­i­fes­ta­tion of insuf­fi­cient­ly con­trolled cou­pling.

Where there is no cou­pling — no shared data, no shared con­trol paths, no shared hard­ware resources — inter­fer­ence can­not occur. Where cou­pling exists but is tight­ly con­trolled (through syn­chro­niza­tion mech­a­nisms, exclu­sive resource allo­ca­tion, or tem­po­ral par­ti­tion­ing), inter­fer­ence can be elim­i­nat­ed or bound­ed.

In the con­text of WCET, the goal is there­fore twofold: iden­ti­fy all cou­pling points (data, con­trol, and tim­ing) and quan­ti­fy the worst-case inter­fer­ence that each cou­pling point can intro­duce dur­ing exe­cu­tion.

Next time in part 2 of this arti­cle series, we’ll cover what worst-case exe­cu­tion real­ly means and how it dif­fers between sin­gle-core and mul­ti­core-based sys­tems.

Worse-Case Exe­cu­tion Time (WCET) analy­sis for multi-core sys­tems - Elec­tri­cal Engi­neer­ing News and Prod­ucts (Orig­i­nal­ly pub­lished in EEWorld Online)