EPC: Extended Path Coverage for

(1)

EPC: Extended Path Coverage for

Measurement-based Probabilistic Timing Analysis

M. Ziccardi

^†

, E. Mezzetti

^†

and T. Vardanega

^†

J. Abella

^§

and F.J. Cazorla

^§‡

†University of Padua ^§BSC ^‡Spanish National Research Council

Real-Time Systems Symposium

This project and the research leading to these results

has received funding from the European Community’s

www.proxima-project.eu

(2)

Overview of MBPTA

o Probabilistic execution time estimation . Based on measurements

. Relies on solid probabilistic and statistical basis

• Posing statistical requirements on the input data (i.i.d.)

. Estimates are attached a probability of exceedance (user-provided threshold)

HW Tracing Support

SETV

Randomized HW platform

Trace collection

MBPTA

Conver- gence criteria Block selection

Curve ﬁtting Tail

exten- sion

EVT

pWCET

Exceedance Probability

Execution time EVT projection

(Inverse CDF) Threshold e.g. 10^-16

(3)

Overview of MBPTA

o Probabilistic execution time estimation . Based on measurements

. Relies on solid probabilistic and statistical basis

• Posing statistical requirements on the input data (i.i.d.)

. Estimates are attached a probability of exceedance (user-provided threshold)

SETV

MBPTA

exten- sion

EVT

pWCET

(4)

Overview of MBPTA

o Probabilistic execution time estimation . Based on measurements

. Relies on solid probabilistic and statistical basis

• Posing statistical requirements on the input data (i.i.d.)

. Estimates are attached a probability of exceedance (user-provided threshold)

SETV

MBPTA

exten- sion

EVT

pWCET

(5)

Overview of MBPTA

o Probabilistic execution time estimation . Based on measurements

. Relies on solid probabilistic and statistical basis

• Posing statistical requirements on the input data (i.i.d.)

. Estimates are attached a probability of exceedance (user-provided threshold)

SETV

MBPTA

exten- sion

EVT

pWCET

(6)

Overview of MBPTA

o Probabilistic execution time estimation . Based on measurements

. Relies on solid probabilistic and statistical basis

• Posing statistical requirements on the input data (i.i.d.)

. Estimates are attached a probability of exceedance (user-provided threshold)

SETV

MBPTA

exten- sion

EVT

pWCET

(7)

Overview of MBPTA

o Probabilistic execution time estimation . Based on measurements

. Relies on solid probabilistic and statistical basis

• Posing statistical requirements on the input data (i.i.d.)

. Estimates are attached a probability of exceedance (user-provided threshold)

SETV

MBPTA

exten- sion

EVT

pWCET

(8)

Overview of MBPTA

o Probabilistic execution time estimation . Based on measurements

. Relies on solid probabilistic and statistical basis

• Posing statistical requirements on the input data (i.i.d.)

. Estimates are attached a probability of exceedance (user-provided threshold)

SETV

MBPTA

exten- sion

EVT

pWCET

(9)

Representativeness of observations

o Inherent limitation of measurement-based approaches . Bounds are only valid for the set of paths and execution

conditions for which observations were collected

o The same applies to MBPTA

. Probabilistically captures variability from history of execution...

. ...but results are only valid for the subset of observed paths

bb0

bb1a bb1b

bb2

bb3a bb3b

bb4

φ0 φ1

(10)

Representativeness of observations

o Inherent limitation of measurement-based approaches . Bounds are only valid for the set of paths and execution

conditions for which observations were collected

o The same applies to MBPTA

. Probabilistically captures variability from history of execution...

. ...but results are only valid for the subset of observed paths

bb0

bb1a bb1b

bb2

bb3a bb3b

bb4

φ0 φ1

φ2 φ3

(11)

Extending the path coverage

o Synthetically extending the set observed paths

MBPTA

exten- sion

EVT

pWCET

Execution time

Distribution valid only for observed paths

"Fully representative" distribution for all paths in a program obtained from both observed AND synthetic observations

No EPC EPC Representativeness gap Measurements collected over a subset of the program paths

Synthetic measurements for unobserved paths HW Tracing

Support

SETV

(12)

EPC building blocks

o Path-independence

. Execution times (ET) can be made independent from the path through which they have been collected

. EPC exploits probabilistic path independence at basic blocks level

o Synthetic measurements over unobserved paths . Path-independent ET can be combined to construct

representative execution times for end-to-end (unobserved) paths

o Cannot naively sum up the maximum observed ET!

. Collected observations are only relative to a particular path

. Includes cache-level and core-level dependencies

(13)

Probabilistic path independence

o Path-independent execution times for a basic block . Values does not depend on a particular path

. Summing up a penalty or padding to each observed ET to compensate for any positive effect due to a specific path (e.g., cache behavior)

o Example of deterministic independence (caches)

. Assume all accesses were hit and add a miss-hit latency to each observed value

. For each memory access in a basic block:

Obs

⁺

(bb

i

) = Obs(bb

i

, φ) + X

@_I∈bbi

pad

^I

(@

I

) + X

@_D∈bbi

pad

^D

(@

D

)

. This is way overly pessimistic!

o Exploit the probabilistic framework

. No need to enforce each observation to upper-bound the

worst-case behavior

(14)

ATPs and probabilistic padding

o On time-randomized single-core architectures . Randomized caches are the main source of variability

. AT P (@

A

, φ) =

L

hit

L

miss

P

hit

(@

A

, φ) P

miss

(@

A

, φ)

o Probabilistic padding of ATPs

. Adding a probabilistic padding to negatively compensate potential positive effects of variability (e.g., a cache hit) on a specific path

. AT P (@

A

) =

L

_hit

L

_miss

P

hit

(@

A

) P

miss

(@

A

)

o Computing the padding probability

. Ensure the resulting ATP distribution follows the worst ET distribution for that basic block (for any program path)

. Cannot modify a set of observations to follow the exact distribution of the worst-case AT P s

• Would require to selectively compensate the effects of cache hits

on a subset of the collected observations

(15)

Over-approximating the worst-case ATP

ATP(@A,φ) ATP(@A) ATP⁺(@A) 0

1 ATP

Lmiss

Lhit Lmiss+pad

0

1 Cumulative ATP

Lmiss

Lhit Lmiss+pad

(16)

Over-approximating the worst-case ATP

ATP(@A,φ) ATP(@A) ATP⁺(@A) 0

1 ATP

Lmiss

Lhit Lmiss+pad

0

Lmiss

Lhit Lmiss+pad

(17)

Over-approximating the worst-case ATP

ATP(@A,φ) ATP(@A) ATP⁺(@A) 0

1 ATP

Lmiss

Lhit Lmiss+pad

0

Lmiss

Lhit Lmiss+pad

(18)

Over-approximating the worst-case ATP

ATP(@A,φ) ATP(@A) ATP⁺(@A) 0

1 ATP

Lmiss

Lhit Lmiss+pad

0

Lmiss

Lhit Lmiss+pad

(19)

Computing the padding probability

o Formulation of padding probability on ATP

⁺

AT P⁺(@A) = AT P (@A, φ) ⊗

D

₀ _L

pad

1 − Ppad(@A, φ) Ppad(@A, φ)

E

=

D

_L

hit Lmiss

Phit(@A, φ) Pmiss(@A, φ)

E

⊗

D

₀ _L

pad

1 − Ppad(@A, φ) Ppad(@A, φ)

E

=

Lhit Lmiss Lmiss+ Lpad

P_hit⁺ (@A) P_miss⁺ (@A) P_miss+pad⁺ (@A)

(20)

Computing the padding probability/2

o Under one single requirement

AT P

⁺

(@

A

) AT P (@

A

) implying

P

_hit⁺

(@

A

) ≤ P

hit

(@

A

)

P

_hit⁺

(@

A

) + P

_miss⁺

(@

A

) ≤ P

hit

(@

A

) + P

miss

(@

A

)

o Lower bound to P

pad

(@

A

, φ)

P

_hit⁺

(@

A

) ≤ P

hit

(@

A

) P

_hit

(@

A

, φ) · (1 − P

_pad

(@

A

, φ)) ≤ P

_hit

(@

A

)

· · ·

P

pad

(@

A

, φ) ≥ 1 − P

_hit

(@

A

)

P

hit

(@

A

, φ)

(21)

Computing the padding probability/3

Definition (Reuse distance - rd )

The reuse distance of @Aon a path φ is defined as the number of memory blocks mapped to the same set of @A accessed between @Aand the previous access to the memory block containing @A.

Definition (Unique accesses - un)

With unique accesses, instead, we refer to the number ofdistinctmemory blocks mapped to the same set of @A accessed in between @Aand the previous access to the memory block containing @Aon a path φ.

P

hit

(@

A

) = 1−P

miss

(@

A

)

where

P

miss

(@

A

) = (

1 −

^w−1_w

rd(@_A)

if rd(@

A

) < w

1 otherwise

P

hit

(@

A

, φ) ≤ uP

hit

(@

A

, φ) =

( 1 if un(@

A

, φ) < w

w−1 w

^un(@A,φ)−w+1

otherwise

(22)

Application of padding and synthetic paths

o Computational complexity in P

_pad

relatively low . Both rd and un computed on a restricted scope

(only immediate predecessors)

o Collected observations of basic blocks updated . This affects both observed values and frequencies

o Synthetic path generation

. Collect artificial execution times by iterating over all the basic blocks in each unobserved path

. Consider only a subset of all possible paths

• Pruning based on known flow facts

(23)

Feeding data into MBPTA

MBPTA

exten- sion

EVT

pWCET

Execution time

Distribution valid only for observed paths

"Fully representative" distribution for all paths in a program obtained from both observed AND synthetic observations

No EPC EPC Representativeness gap Measurements collected over a subset of the program paths

Synthetic measurements for unobserved paths HW Tracing

Support

SETV

(24)

Evaluation

o EPC extends MBPTA

. Representativeness of full path coverage → at what cost?

. Evaluate the compromise between tightness and representativeness

. Against both

• Base MBPTA (from ECRTS-12)

• Path Upper Bounding (PUB) approach (from ECRTS-14) - Based on balancing of conditional branches

- Modified executable used at analysis time

o On PROXIMA simulator

. SoCLib-based cycle-level platform simulator

. Single level time-randomized I and D caches

• 4-ways set associative

• Random placement and replacement policies

(25)

Against standard MBPTA

!"

# $ !% &

' ( !% !)' %*

+ ' %

!" " $

(26)

Against PUB

!"#$

% & #' (

) *" #' #+)"', - )"'

!"#$ $ &

(27)

From simulation to real implementation

HW Tracing Support SETV

Randomized HW platform Trace collection

MBPTA

exten- sion

EVT

pWCET

Execution time EVT projection (Inverse CDF) Threshold e.g. 10^-16

SPARC LEON3-based PROXIMA FPGA

CG GRMON

EPC

on

o Implementation within the PROXIMA project . Randomized platform under finalization

. EPC is being implemented on top of industrial-quality tool

. Tracing requirements fulfilled by available HW tracing support

(28)