Software Estimation and Synthesis Thanks to Prof Sharad Malik at Princeton University and Prof Reinhard Wilhelm at Universitat des Saarlandes for some of the slides Outline SW estimation overview Program path analysis Micro architecture modeling Implementation examples Cinderella SW estimation in VCC SW estimation in AI SW estimation in POLIS 2 EE249Fall04 SW estimation in HW SW co design No concept of SW Capacity Architecture Fast with Function Moderate Accuracy and Low Cost Mapping HW SW Accurate at any cost 3 EE249Fall04 SW estimation overview motivation SW estimation helps to Evaluate HW SW trade offs Check performance constraints Higher reliability Reduce system cost Allow slower hardware smaller size lower power consumption 4 EE249Fall04 SW estimation overview SW estimation problems in HW SW co design The structure and behavior of synthesized programs are known in the co design system Quick and as accurate as possible estimation methods are needed Quick methods for HW SW partitioning Hu94 Gupta94 Accurate method using a timing accurate co simulation Henkel93 5 EE249Fall04 SW estimation overview tasks Architectural evaluation processor selection bus capacity Partitioning evaluation HW SW partition co processor needs System metric evaluation performance met power met size met 6 EE249Fall04 SW estimation overview Static vs Dynamic Static estimation Determination of runtime properties at compile time Most of the interesting properties are undecidable use approximations An approximation program analysis is safe if its results can always be depended on Results are allowed to be imprecise as long as they are not on the safe side Quality of the results precision should be as good as possible 7 EE249Fall04 SW estimation overview Static v s Dynamic Dynamic estimation Determination of properties at runtime DSP Processors relatively data independent most time spent in hand coded kernels static data flow consumes most cycles small number of threads simple interrupts Regular processors arbitrary C highly data dependent commercial RTOS many threads complex interrupts priorities 8 EE249Fall04 SW estimation overview approaches Two aspects to be considered The structure of the code program path analysis E g loops and false paths The system on which the software will run micro architecture modeling CPU ISA interrupts etc HW cache etc OS Compiler Needs to be done at high system level Low level e g gate level assembly language level Easy and accurate but long design iteration time High system level Reduces the exploration time of the design space 9 EE249Fall04 System level software model Must be fast whole system simulation Processor model must be cheap what if my processor did X future processors not yet developed evaluation of processor not currently used Must be convenient to use no need to compile with cross compilers debug on my desktop Must be accurate enough for the purpose 10 EE249Fall04 Accuracy vs Performance vs Cost Accuracy Speed Hardware Emulation Cycle accurate model Cycle counting ISS Dynamic estimation Static spreadsheet NRE per model per design 11 EE249Fall04 Outline SW estimation overview Program path analysis Micro architecture modeling Implementation examples Cinderella SW estimation in VCC SW estimation in AI SW estimation in POLIS 12 EE249Fall04 Program path analysis Basic blocks A basic block is a program segment which is only entered at the first statement and only left at the last statement Example function calls The WCET or BCET of a basic block is determined A program is divided into basic blocks Program structure is represented on a directed program flow graph with basic blocks as nodes A longest shortest path analysis on the program flow identify WCET BCET 13 EE249Fall04 Program path analysis Program path analysis Determine extreme case execution paths Avoid exhaustive search of program paths for i 0 i 100 i if rand 0 5 j else k 2100 possible worst case paths Eliminate False Paths Make use of path information provided by the user if ok i i i 1 else i 0 14 if i j else j j j Always executed together EE249Fall04 Program path analysis Path profile algorithm Goal Determines how many times each acyclic path in a routine executes Method identify sets of potential paths with states Algorithms Number final states from 0 1 to n 1 where n is the number of potential paths in a routine a final state represents the single path taken through a routine Place instrumentation so that transitions need not occur at every conditional branch Assign states so that transitions can be computed by a simple arithmetic operation Transforms a control flow graph containing loops or huge numbers of potential paths into an acyclic graph with a limited number of paths 15 EE249Fall04 Program path analysis Transform the problem into an integer linear programming ILP problem Basic idea max ci xi i Single exec time of basic block Bi constant Exec count of Bi integer variable subject to a set of linear constraints that bound all feasible values of xi s Assumption for now simple micro architecture model constant instruction execution time 16 EE249Fall04 Program path analysis structural constraints Linear constraints constructed automatically from program s control flow graph Example While loop Structural Constraints At each node d1 B1 q p x1 p 0 q p while q 10 q r q d4 d2 B2 while q 10 x2 d3 d5 B4 r q 17 1 1 2 outputs x2 d2 d4 d3 d5 x3 d3 d4 x4 d5 d6 B3 q x3 x4 d6 Source Code Exec count of Bi inputs Control Flow Graph Functional Constraints provide loop bounds and other path information 0x1 x3 10x1 EE249Fall04 Program path analysis functional constraints Provide loop bounds mandatory Supply additional path information optional Nested loop x1 for i 0 i 10 i x2 for j 0 j i j x3 A i B i j If statements x1 if ok x2 i i i 1 else x3 i 0 x4 x5 x6 if i j 0 else j j j x2 10x1 0x 2 x3 9x2 x3 45x1 loop bounds path info True statement executed at most 50 x2 0 5x1 B2 and B5 have same execution counts x2 x5 18 EE249Fall04 Outline SW estimation overview Program path analysis Micro architecture modeling Implementation examples Cinderella SW estimation in VCC SW estimation in AI SW estimation in POLIS 19 EE249Fall04 Micro architecture modeling Micro architecture modeling Model hardware and determine the execution time of sequences of instructions Caches CPU pipelines etc make WCET computation difficult since they make it history sensitive Worst case path Instruction execution time Program path analysis and micro
View Full Document
Unlocking...