HW SW Synthesis Outline Synthesis CFSM Optimization Software synthesis Problem Task synthesis Performance analysis Task scheduling Compilation 2 POLIS Methodology Graphical GraphicalEFSM EFSM Esterel Esterel Java EC EC Compilers SW Synthesis SW Estimation SW Code RTOS HW Synthesis CFSMs Partitioning HW Estimation HW SW Co Simulation Performance trade off Evaluation Formal Verification Physical Prototyping Logic Netlist Aptix Board Aptix Board Consists Consistsof of micro of micro of choice choice FPGA s FPGA s FPIC s FPIC s 3 Hardware Software Architecture Hardware Currently Programmable processors micro controllers DSPs ASICs FPGAs Software Set of concurrent tasks Customized Real Time Operating System Interfaces Hardware modules Software procedures polling interrupt handlers 4 System Partitioning Scheduler CFSM1 e2 port1 CFSM4 e2 e5 port7 CFSM2 e3 port5 e7 port2 CFSM5 e1 CFSM6 e3 HW partition 1 e9 port6 port3 e9 CFSM3 CFSM7 e8 SW partition 3 HW partition2 5 Software Synthesis Two level process Technology processor independent best decision assignment sequence given CFSM Technology processor dependent conversion into machine code instruction selection instruction scheduling register assignment currently left to compiler need performance and cost analysis Worst Case Execution Time code and data size 6 Software Synthesis Technology independent phase Construction of Control Data Flow Graph from CFSM based on BDD representation of Transition Function Optimization of CDFG for execution speed code size based on BDD sifting algorithm Technology dependent phase Creation of restricted C code Cost and performance analysis Compilation 7 Software Implementation Problem Input Set of tasks specified by CFSMs Set of timing constraints e g input event rates and response constraints Output Set of procedures that implement the tasks Scheduler that satisfies the timing constraints Minimizing CPU cost Memory size Power etc 8 Software Implementation How to do it Traditional approach Hand coding of procedures Hand estimation of timing input to scheduling algorithms Long and error prone Our approach three step automated procedure Synthesize each task separately Extract estimated timing Schedule the tasks Customized RT OS scheduler drivers 9 Software Implementation Current strategy Iterate between synthesis estimation and scheduling Designer chooses the scheduling algorithm Future work Top down propagation of timing constraints Software synthesis under constraints Automated scheduling selection based on CPU utilization estimates 10 Software Synthesis Procedure Specification partitioning Code generation S graph synthesis Compilation Timing estimation fail not Scheduling validation feasible feasible Testing validation pass Production 11 Task Implementation Goal quick response time within timing and size constraints Problem statement Given a CFSM transition function and constraints Find a procedure implementing the transition function while meeting the constraints The procedure code is acyclic Powerful optimization and analysis techniques Looping state storage etc are implemented outside in the OS 12 SW Modeling Issues The software model should be Low level enough to allow detailed optimization and estimation High level enough to avoid excessive details e g register allocation instruction selection Main types of user mode instructions Data movement ALU Conditional unconditional branches Subroutine calls RTOS handles I O interrupts and so on 13 SW Modeling Issues Focus on control dominated applications Address only CFSM control structure optimization Data path left as don t touch Use Decision Diagrams Bryant 86 Appropriate for control dominated tasks Well developed set of optimization techniques Augmented with arithmetic and Boolean operators to perform data computations 14 ROBDDs Reduced Ordered BDDs Bryant 86 A node represents a function given by the Shannon decomposition f x1 x2 x3 f x f x x f x f Variable appears once on any path from x x root to terminal x Variables are ordered No two vertices represent the same fx x function 0 1 Canonical Two functions are equal if and only if ROBDD their BDDs are isomorphic direct application in equivalence checking 1 1 2 1 3 15 ROBDDs and Combinational Verification Given two circuits Build the ROBDDs of the outputs in terms of the primary inputs Two circuits are equivalent if and only if the ROBDDs are isomorphic Complexity of verification depends on the size of ROBDDs Compact in many cases 16 ROBDDs and Memory Explosion ROBDDs are not always compact Size of an ROBDD can be exponential in number of variables Can happen for real life circuits also e g Multipliers Commonly known as Memory Explosion Problem of ROBDDs 17 Technique for Handling ROBDD Memory Explosion Enhancements Variable ROBDDs Node Decomp OFDDs OKFDDs Ordering Relax Ordering Free BDDs Partitioning Partitioned ROBDDs All the representations are canonical combinational equivalence checking 18 Handling Memory Explosion Variable Ordering BDD size very sensitive to variable ordering a1b1 a2b2 a3b3 a1 1 a1 b1 a2 2 a3 a2 a3 a3 a3 b1 b1 b1 b1 b2 a3 b2 b2 b3 b3 0 a 1 Good Ordering 8 nodes 0 1 Bad Ordering 16 nodes 19 Handling Memory Explosion Variable Ordering Good static as well as dynamic ordering techniques exist Dynamic variable reordering Rudell 93 Change variable order automatically during computations Repeatedly swap a variable with adjacent variable Swapping can be done locally Select the best location a1b1 a2b2 a1 a1 1 a2 a2 b1 b1 a2 b1 b2 0 b2 1 0 1 20 SW Model S graphs Acyclic extended decision diagram computing a transition function S graph structure Directed acyclic graph Set of finite valued variables TEST nodes evaluate an expression and branch accordingly ASSIGN nodes evaluate an expression and assign its result to a variable Basic block branch is a general CDFG model but we constrain it to be acyclic for optimization 21 An Example of S graph input event c output event y state int a input int b forever if detect c if a b a a 1 emit y else a 0 emit y BEGIN detect c F a b T T a a 1 F a emit y END 22 S graphs and Functions Execution of an s graph computes a function from a set of input and state variables to a set of output and state variables Output variables are initially undefined Traverse the s graph from BEGIN to END Well formed s graph Every time a function depending on a variable is evaluated that variable has a defined value How do we derive an s graph implementing a given function 23 S
View Full Document
Unlocking...