Worst-Case Execution Time (WCET) Analysis for Multicore Systems - Part 2: Why Multicore Processors Change Everything

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 assess Worst-Case Exe­cu­tion Time (WCET) in mod­ern mul­ti­core embed­ded sys­tems. In part 1, we estab­lished 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. Here in part 2 of this 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.

What Worst-Case Execution Time Actually Means

The WCET of a task is the max­i­mum time that task could ever take to exe­cute, across all pos­si­ble inputs, all pos­si­ble sys­tem states, and all pos­si­ble pat­terns of inter­fer­ence from con­cur­rent­ly exe­cut­ing tasks.

This def­i­n­i­tion con­tains an impor­tant sub­tle­ty: WCET is not the longest time observed in test­ing. Mea­sure­ment can only cap­ture the sub­set of con­di­tions explored dur­ing the test cam­paign. The actu­al WCET may be longer, and it is pre­cise­ly the gap between the max­i­mum observed exe­cu­tion time (i.e. mea­sured upper bound) and the actu­al WCET that rep­re­sents risk in a safe­ty-crit­i­cal sys­tem.

Fig­ure 1 illus­trates this rela­tion­ship. The green dis­tri­b­u­tion rep­re­sents exe­cu­tion times mea­sured dur­ing test­ing. The gray dis­tri­b­u­tion shows the full range of pos­si­ble exe­cu­tion times, includ­ing rare con­di­tions that test­ing is unlike­ly to ever trig­ger or encounter. The WCET is the upper bound of the pos­si­ble dis­tri­b­u­tion, which is not the same as the max­i­mum of the mea­sured times. A tim­ing guar­an­tee that is based only on mea­sured data, with­out account­ing for the gap between mea­sured and pos­si­ble, is not a sound guar­an­tee.

Fig­ure 1. The rela­tion­ship between mea­sured and pos­si­ble exe­cu­tion times. BCET = Best-Case Exe­cu­tion Time; WCET = Worst-Case Exe­cu­tion Time; ACET = Aver­age-Case Exe­cu­tion Time. The gap between the max­i­mum observed exe­cu­tion time and the true WCET is where unde­tect­ed dead­line vio­la­tions can occur. (Source: TASKING)

Sev­er­al char­ac­ter­is­tics of mod­ern hard­ware make the prob­lem of esti­mat­ing WCET accu­rate­ly hard­er than it might appear at first:

• Exe­cu­tion times are not deter­min­is­tic: On a sin­gle-core proces­sor, exe­cu­tion time is influ­enced by instruc­tion cache state, branch pre­dic­tor state, and pipeline effects. On a mul­ti­core proces­sor, addi­tion­al influ­ences include shared cache evic­tion, bus con­tention, and mem­o­ry con­troller arbi­tra­tion, all of which vary with the behav­ior of soft­ware run­ning on other cores.
• Aver­age mea­sure­ments are not suf­fi­cient: A task that meets its tim­ing require­ment on aver­age may still occa­sion­al­ly miss its dead­line under unusu­al load con­di­tions. But real-time embed­ded sys­tems can­not tol­er­ate miss­ing even one safe­ty-crit­i­cal dead­line. There­fore, WCET analy­sis must tar­get the worst case, which rarely occurs and may never be observed in nor­mal test­ing.
• Worst-case inputs and worst-case inter­fer­ence must be con­sid­ered simul­ta­ne­ous­ly: A task’s own worst-case exe­cu­tion path may dif­fer from the path exe­cut­ed when inter­fer­ence is at its max­i­mum.
• Suf­fi­cient test­ing is required to bound WCET: When we look at the prob­lem space in safe­ty crit­i­cal con­trol law, prob­a­bilis­ti­cal­ly bound­ing WCET with an appro­pri­ate sam­pling and dis­tri­b­u­tion can be enough to guar­an­tee that a safe­ty crit­i­cal appli­ca­tion oper­ates appro­pri­ate­ly, if that is how the con­trol law was defined.

The Single-Core Baseline

On a sin­gle-core proces­sor, WCET analy­sis is well under­stood and amenable to both sta­t­ic and dynam­ic meth­ods. Sta­t­ic meth­ods ana­lyze the code’s con­trol flow graph to iden­ti­fy the longest exe­cu­tion path and bound the exe­cu­tion time of each basic block. Dynam­ic meth­ods mea­sure exe­cu­tion times across a rep­re­sen­ta­tive set of inputs and sys­tem states.

Both approach­es are com­pli­cat­ed by data cou­pling and con­trol cou­pling. Shared data and shared con­trol flags intro­duce vari­abil­i­ty that must be account­ed for in the analy­sis. Nev­er­the­less, because a sin­gle-core proces­sor does not share exe­cu­tion resources with other proces­sors, the prob­lem is bound­ed. Given suf­fi­cient test­ing of the task’s own inputs and inter­nal state, a sound WCET esti­mate can be obtained.

Why Multicore Processors Change Everything

Mul­ti­core Sys­tem-on-Chip (SoC) devices are being used in an increas­ing num­ber of safe­ty-crit­i­cal embed­ded sys­tems because they deliv­er sub­stan­tial­ly more pro­cess­ing power using less power for a lower cost than equiv­a­lent sin­gle-core solu­tions. How­ev­er, they intro­duce a qual­i­ta­tive­ly new source of WCET uncer­tain­ty: tim­ing cou­pling through shared hard­ware resources.

The most sig­nif­i­cant shared resources are:

• L2 (and high­er-level) cache mem­o­ry: Each core typ­i­cal­ly has a pri­vate L1 cache while the L2 cache is shared across cores. When tasks on dif­fer­ent cores simul­ta­ne­ous­ly access large data sets, they com­pete for L2 cache lines. Each cache miss forces a mem­o­ry access, which is orders of mag­ni­tude slow­er than a cache hit. Inter­fer­ence that caus­es more cache miss­es will neg­a­tive­ly impact exe­cut­ing time.
• Mem­o­ry bus and mem­o­ry con­troller: All cores share a sin­gle path to main mem­o­ry. Con­cur­rent mem­o­ry traf­fic from mul­ti­ple cores must be arbi­trat­ed, intro­duc­ing queu­ing delays that depend on the aggre­gate mem­o­ry access pat­tern of all cores. How mem­o­ry traf­fic is arbi­trat­ed can only be mea­sured dur­ing run­time.
• Other shared periph­er­als and inter­con­nects: DMA con­trollers, inter­rupt con­trollers, and on-chip inter­con­nect fab­rics are typ­i­cal­ly shared across cores. As such, they can be fur­ther sources of con­tention-relat­ed laten­cy.

The key insight is that tim­ing cou­pling inter­fer­ence is not a soft­ware design arti­fact because it emerges from the phys­i­cal archi­tec­ture of a mul­ti­core proces­sor. No amount of soft­ware design dis­ci­pline can elim­i­nate it. Thus, tim­ing cou­pling must be mea­sured and account­ed for ana­lyt­i­cal­ly or mit­i­gat­ed through archi­tec­tur­al choic­es such as cache par­ti­tion­ing or core iso­la­tion.

The Impact of Timing Coupling: A Concrete Example

To illus­trate the mag­ni­tude of tim­ing cou­pling inter­fer­ence, con­sid­er a study con­duct­ed by the Unit­ed States Army DEVCOM Avi­a­tion and Mis­sile Cen­ter Multi-Core Pro­cess­ing and Arti­fi­cial Intel­li­gence Lab­o­ra­to­ry in col­lab­o­ra­tion with TASKING. Two inde­pen­dent tasks — “Blue App” and “Red App”, with no data or con­trol cou­pling between them — were run con­cur­rent­ly on dif­fer­ent cores of the same mul­ti­core proces­sor. The mean exe­cu­tion time of Blue App was mea­sured as a func­tion of the data sizes used by both tasks.

The under­ly­ing mech­a­nism is the shared L2 cache. When a task’s work­ing data set fits entire­ly with­in its pri­vate L1 cache (32 KB in this exper­i­ment), it does not use the L2 cache and is there­fore effec­tive­ly immune to L2 cache inter­fer­ence from the other core. How­ev­er, as data size increas­es beyond the L1 cache capac­i­ty, the task increas­ing­ly relies on the L2 cache. This, in turn, makes the task increas­ing­ly sus­cep­ti­ble to inter­fer­ence from the other core’s con­cur­rent L2 cache access­es.

Fig­ure 2 shows the exe­cu­tion time increase (%) for Blue App across com­bi­na­tions of data sizes for both tasks. Each col­ored line rep­re­sents a fixed Blue App data size. The x-axis shows the data size of the con­cur­rent­ly run­ning Red App.

Fig­ure 2. Exe­cu­tion time increase (%) for Blue App as a func­tion of data size for both tasks run­ning con­cur­rent­ly on dif­fer­ent cores. The 512 KB Blue App / 2 MB Red App com­bi­na­tion pro­duces the high­est mea­sured inter­fer­ence: 40.86%. As the tasks have no data or con­trol cou­pling, all inter­fer­ence is tim­ing cou­pling via the shared L2 cache. (Source: TASKING / US Army DEVCOM)

The crit­i­cal results: Tasks with 24 KB data sets are small enough to fit entire­ly in the pri­vate L1 cache. By demon­strat­ing neg­li­gi­ble inter­fer­ence regard­less of what Red App does, this con­firms that the L2 cache is the inter­fer­ence mech­a­nism.

How­ev­er, when Blue App uses 512 KB of data and Red App uses 2 MB, mean exe­cu­tion time increas­es by up to 40.86% rel­a­tive to the no-inter­fer­ence base­line. Fur­ther­more, 40.86% is not the the­o­ret­i­cal max­i­mum for all sys­tems. The inter­fer­ence foot­print is spe­cif­ic to the proces­sor archi­tec­ture, the data access pat­terns of the tasks, and the cache con­fig­u­ra­tion. Each sys­tem must be char­ac­ter­ized indi­vid­u­al­ly.

Why Interference Varies Between Runs

A fur­ther com­pli­ca­tion is that tim­ing cou­pling inter­fer­ence is not con­stant - it varies between runs of the same sys­tem. The degree of inter­fer­ence depends on how and when the tasks on dif­fer­ent cores over­lap in time. Two tasks that both access the L2 cache heav­i­ly will inter­fere most when their exe­cu­tion win­dows over­lap max­i­mal­ly. When they hap­pen to exe­cute in sequence rather than con­cur­rent­ly, inter­fer­ence may be neg­li­gi­ble.

Fig­ure 3 shows the func­tion dura­tions mea­sured across many iter­a­tions of two con­cur­rent­ly exe­cut­ing tasks. Each bar rep­re­sents one func­tion invo­ca­tion over­lap. The wide vari­a­tion in dura­tion, rang­ing from near zero to over 250,000 ns, direct­ly reflects the vary­ing degree of tim­ing cou­pling inter­fer­ence as the tasks over­lap dif­fer­ent­ly in each iter­a­tion.

Fig­ure 3. Over­lap­ping func­tion dura­tions (in nanosec­onds) across many iter­a­tions of two con­cur­rent­ly exe­cut­ing tasks. The large vari­a­tion in dura­tion — despite the tasks being log­i­cal­ly inde­pen­dent — is caused by vary­ing tim­ing cou­pling inter­fer­ence as the over­lap between tasks changes from run to run. (Source: TASKING)

Because the sched­ul­ing and tim­ing of tasks can shift slight­ly from run to run (due to inter­rupt tim­ing, OS sched­ul­ing jit­ter, and other sources of non-deter­min­ism), the over­lap pat­tern, and there­fore the degree of inter­fer­ence, changes with every exe­cu­tion. This is why mea­sur­ing WCET with inject­ed inter­fer­ence pat­terns is inef­fec­tive. Arti­fi­cial­ly gen­er­at­ed inter­fer­ence does not accu­rate­ly repli­cate the com­plex, vary­ing inter­fer­ence of the real sys­tem.

Instead, WCET mea­sure­ment requires an iter­a­tive process that exer­cis­es many com­bi­na­tions of con­cur­rent task over­lap on the actu­al tar­get hard­ware. This iter­a­tive process allows devel­op­ers to accu­mu­late a sta­tis­ti­cal pic­ture of the worst-case exe­cu­tion time dis­tri­b­u­tion. Because inter­fer­ence depends on the pre­cise, run-to-run over­lap of log­i­cal­ly inde­pen­dent tasks, no sin­gle mea­sure­ment and no arti­fi­cial­ly inject­ed pat­tern can cap­ture it. The worst case must be approached empir­i­cal­ly. Crit­i­cal­ly, this sta­tis­ti­cal behav­ior must be reflect­ed in the system’s tim­ing require­ments, so that devel­op­ers can rea­son­ably guar­an­tee that the esti­mat­ed WCET is with­in estab­lished bounds to main­tain safe and reli­able oper­a­tion.

Next time in part 3 of this arti­cle series, we’ll explore a prac­ti­cal three-stage method­ol­o­gy for mea­sur­ing worst-case exe­cu­tion time (WCET) in mul­ti­core-based sys­tems with a focus on require­ments, design, and ver­i­fi­ca­tion. Worst-Case Exe­cu­tion Time (WCET) analy­sis for mul­ti­core sys­tems - Elec­tri­cal Engi­neer­ing News and Prod­ucts (Orig­i­nal­ly pub­lished in EEWorld Online)