Last Time Response time analysis Blocking terms Priority inversion And solutionsRelease jitterRelease jitter Other extensionsToday Timing analysis Answers a question we commonly ask: • At most long can this code take to run? Response time over CAN Worst-case message timesHolistic schedulingHolistic schedulingTiming Analysis Definitions Worst case execution time (WCET): Longest execution time of a program on a given platform, considering all possible inputs Precise timing analysis problem: Compute WCET Trivially reduces to halting problem•Though not in practice•Though not in practice• But still too hard Timing analysis problem: Compute a conservative estimate of the WCET I.e., estimate of WCET can be > true WCET This is decidable• Correct analyzer could always return ∞Timing Analysis by Testing WCET is often estimated by looking for the maximum execution time over many executions This is easy However, it does not solve the problem!TrueNumber of executionsWCET estimateTrueWCETLongest observed ET #2Execution timeNumber of executionsLongest observed ET #1Timing Analysis by Testing Always true:  Longest observed ET ≤ true WCET ≤ WCET estimate Question: What is the requirement for correctly estimating WCET using testing?Static Timing Analysis Static timing analysis: Estimate WCET without running a program Problem 1: Can’t do this from source code Which variables go into registers? Which functions are inlined?Which switches become jump tables vs. cascaded tests?Which switches become jump tables vs. cascaded tests? Solution: Analyze compiler output Problem 2: Understanding what’s going on in HW Where are the branch mispredicts? Where are the icache / dcache misses? Solution: Build model of the hardwareStatic Timing Analysisint foo1 (int a, int b){int c = b + 31*a;int e = 120 - c - a;return e;}link a6,#0link a6,#0move.l 8(a6),d0moveq #-32,d1muls.l d1,d0sub.l 12(a6),d0addi.l #120,d0 unlk a6rts  What does it take to estimate WCET of this code?Analyzing Branchesvoid foo2 (int a) {if (a) {x += 3*a;} else {y -= x-a;}}link a6,#0move.l 8(a6),d2tst.l d2tst.l d2beq.s *+16moveq #3,d0muls.l d0,d2add.l d2,_xbra.s *+24move.l _x,d1sub.l d2,d1move.l _y,d0sub.l d1,d0move.l d0,_yunlk a6rtsAnalyzing Loopsvoid foo3 (int a){do { y++; } while (a--);}link a6,#0move.l 8(a6),d2move.l 8(a6),d2move.l _y,d1move.l d2,d0addq.l #1,d1subq.l #1,d2tst.l d0bne.s *-8 move.l d1,_yunlk a6rtsLoop Analysis Strategies1. Programmer annotates loops with bounds Not very fun Doesn’t work well for library code However, could argue that in critical software programmer should always know the loop bounds2.Analyzer tries to figure out loop bounds2.Analyzer tries to figure out loop bounds Doesn’t always work Derived bound might be too high Reasonable answer: Analyzer figures out simple loops, programmer annotates difficult onesBottom-Up WCET Analysisvoid foo4 (void){if (y==0) {if (x>5) {x++;if y == 0foo4max(7,13) + 2 = 1515+3 = 18x++;} else {x = 1;}} else {x *= 3;}}if x>5x++ x = 1x=1ReturnReturn Return3 3 33+2 = 5 3+1 = 43+10 = 13max(5,4) + 2 = 7Real-World Problems Timing models for complex processors are difficult to create Probably impossible for processors like Pentium 4• Not even Intel knows! However, easy for ColdFire, ARM, and lots of othersCaches, TLBs, branch predictors enormously Caches, TLBs, branch predictors enormously complicate WCET analysis Need to estimate cache, TLB, predictor state at every program point Difficult, imprecise, and computationally expensive Pointers and heap allocation are very difficult to analyze But critical software typically doesn’t do much of theseHardware Horror Story Start with some simple code: Measure time per loop iteration for k = 1..32Result on NEC V850EResult on Pentium IIIResult on AthlonCommercial Timing Analysis aiT from Absint Supports ARM7TDMI, ColdFire 5307, PowerPC 755, MPC5xx Analysis steps: Reconstruct control flow from object code Value analysis: Computation of address ranges for Value analysis: Computation of address ranges for instructions accessing memory  Cache analysis: Classification of memory references as cache misses or hits  Pipeline analysis: Predicting the behavior of the program on the processor pipeline  Path analysis: Determination of the worst-case execution path of the program  Analysis of loops and recursive proceduresMaking Predictable Systems Avoid recursion Avoid deeply nested loops Avoid if/else where one branch is a lot faster than the otherAvoid data-dependent loopsAvoid data-dependent loops Use fixed iteration count whenever possible Avoid variable-time data structures E.g. hash tables are usually very unpredictable Avoid unpredictable thread blocking E.g. on disk, network, etc. Avoid unpredictable processors This is any processor that is much faster than its memoryTiming Analysis Summary WCET estimation for simple hardware + simple software Largely a solved problem Technology far less mature than e.g. compiler technology WCET estimation for complex hardware + complex softwaresoftware Open problem May not be possible May not even be a good idea• I.e. nobody cares about WCET of spell check in MS Word Products exist What kind of chip should one use for a high-performance, time-critical embedded system?Time Guarantees over CAN Basic idea: Processors scheduled using priorities We know WCET of tasks CAN scheduled using priorities We know WCTT of messagesCan put it all together using “holistic scheduling”Can put it all together using “holistic scheduling” Why do we care? Accelerometer on your pickup is on CAN bus Airbags are also on CAN bus Want to guarantee airbag deployment within 150 ms of when you start to roll the truck• Even if lots of other stuff is going over the busModeling the CAN Bus Recall: CAN message stores 0-64 bits of data 47 bits of message overhead Bit stuffing occurs – in worst case every 5 bits has a 6thadded34 overhead bits stuffed34 overhead bits stuffed For an n-byte message: WC number of stuff bits = floor ((34 + 8n -1)/4)bitiiissCτ−+++=51834478Modeling