EECE 276 – Embedded Systems1EECE 276Embedded SystemsPerformance analysis and optimizationTheoryEECE 276 – Embedded Systems2TheoryO Performance analysis: crucial for real-time systems O Scaling/complexity» How the algorithm behaves as the size of the problem changesO NP-Completeness» NP-complete problems: the only known algorithms scale exponentially» Example: (general) scheduling– Online optimal scheduler for systems with mutexes– Multiprocessor scheduling (many variants)O Undecidability – Halting problem» Certain classes of computational problems cannot be solved algorithmically» Example: Does a program P terminate if given input I?EECE 276 – Embedded Systems3“Laws” of parallelismO Amdahl’s Law:» Processors = n, sequential portion (%) of the code = s» If s=0 : linear speedup as a function of processors» If s>0 : perfect speedup is not possible» Underlying assumption: problem size is constant, and thus there is a diminishing margin of return for speeding up the computation.» In reality: problems tend to scale with the size of the parallelsystemsnnSpeedup)1(1 −+=EECE 276 – Embedded Systems4“Laws” of parallelismO Gustafson’s Law:» Problems scale up with the number of processors» Estimate for serial portion: s + p*n» Parallel processors should work on different portions of data (data parallel processing)O Parallel embedded systems» DSP networks – “fabric”» DSP pipelinesnSpeedup=≈EECE 276 – Embedded Systems5Performance analysisO Code execution time estimation» Instruction counting:– Generate assembly, count cycles on the WCET path– Note: pipelining and caches may distort results» Instruction execution time simulators» Using the system clock– Measure execution time using system calls– Note clock resolution» Code profiling– Which part of the code was executed most frequentlyEECE 276 – Embedded Systems6Performance analysisO Analysis of polled loops:» Delays = HW delay+ test flag(f)+ process event(P)» Problem: overlapping events– Time for processing n-th overlapping event: nfP– Avoid overlapping eventsO Analysis of co-routines » Explicit “yield” – cooperative scheduling» Trace WCET path through each taskEECE 276 – Embedded Systems7Performance analysisO Analysis of round-robin systems:» Cyclic execution of tasks, round-robin» Tasks=n, Max. exec time=c (over all tasks), timeslice=q.» Each task gets 1/n of the CPU time» Each task waits max. (n-1)*q time units.» Each task requires at most ceil(c/q) units» The waiting time is: (n-1)*q*ceil(c/q).» Worst-case time from readiness to completion:T = (n-1)*q*ceil(c/q) + c» With context switching overhead o:T = ((n-1)*q + n*o)*ceil(c/q) + cEECE 276 – Embedded Systems8Performance analysisO Analysis of fixed period systems:» For highest priority task: w.c.r.t = exec. time» For all other tasks: – Rk=ek+ Ik(exec. time + max. delay caused by other tasks)» Consider task tm(higher priority than tk):– Within [0,Rk) : release of tmoccurs ceil(Rk/pm) times.– Maximum interference caused by tm: ceil(Rk/pm)*em– All interference with tk: Ik= sum(m) ceil(Rk/pm)*em, where sum is over all the tasks with higher priority than tk– Response time can be calculated as the solution to the recurrence relation:Solution: Iterate until a fix-point is reached.jiHPjjniiniepRceileR∑∈++=)(1*)/(EECE 276 – Embedded Systems9Performance analysisO Analysis of fixed-period systems:» RMA Example:Highest priorityStart with 4, iterateStart with 2, iterateO Sporadic/aperiodic interrupt systems» Calculate interrupt latency via counting» Consider (macro)instruction finish