Synthesis of Software Programs for Embedded Control Application Felice Balarin Massimiliano Chiodo Paolo Giusto Harry Hsieh ASV etc Presented by Guang Yang Outline Introduction Preliminaries Software Graphs Generation of the Real Time Operating System Experimental Results Conclusions Introduction Embedded Systems Electronic components of a physical system that typically Monitor variables of the physical system Process information Output signals Implementation of Embedded Systems Full hardware configuration Full software implementation Mixed configuration Introduction cont The problem Software Synthesis software development software analysis right for the first time Inadequate SW synthesis vs HW synthesis SW synthesis vs SW compilation Optimization translation process vs Close to implementation level Introduction cont The problem Software Synthesis software development software analysis right for the first time Inadequate SW synthesis vs HW synthesis SW synthesis vs SW compilation Optimization translation process 1970 theoretical work vs Close to implementation level Introduction cont Compiler Technology 20 years progress Semilocal High level constructs opt Arch spec Intermediate code opt Machine code Why semilocal Time Complexity Introduction cont SW vs HW Compilation functional reg allocation scheduling component synthesis optimization vs reg allocation instruction selection and local optimization HW syntheis is stronger than SW synthesis Synthesize SW HW in a single system make SW HW like Introduction cont Restricted Application Domains Simpler and more optimal In this paper Control dominated embedded sys MoC FSM Advantages Easily understand widely used Abundant theoretical practical results Disadvantages No good support for computation Previous FSM extension pays too much CFSM Introduction cont This paper s approach to SW synthesis Assumption Specification written in a network of CFSM s A Real Time OS An existing general purpose C compiler Includes Optimization techniques function description and coupling of optimization and estimation Introduction cont Approach 1 Optimized translation of the transition 2 3 4 5 function of a given CFSM into an s graph using BDD S graph optimization and code size estimation Translation of the s graph into a target lang Scheduling CFSM s and generating RTOS Compilation into machine code Preliminaries Previous work Software synthesis synchronous language Esterel v3 single FSM implementation fast but big v4 multi FSM implementation linear size but no low level opt can t opt module by module CFSM approach User can choose granularity of CFSMs User can manipulate CFSM hierarchy in synthesis Opt done close to final c code implementation Both Boolean circuit and decision tree based optimization Previous work cont Software synthesis high level language Scheduling of operations to satisfy timing constraints CFSM approach Software generation for each CFSM Scheduling of CFSM transitions to satisfy timing constraints Hardware High Level Synthesis Behavioral RT level synthesis Input Sequential specification Without with fixed timing and actions Output cycle by cycle register and register changes gate level netlist Behavioral level synthesis operates on structurally similar description to the original one but outputs are in a form that facilitates BDD logic opt BDD like structures are very efficient program implementations Hardware Simulation Software synthesis techniques come from cycle based hardware simulation Efficiently compute on a sequential machine the transition function of an FSM There are differences Starting point large syn circuit at gate level vs explicit representation of an Extended FSM Target execution on high end workstation vs very small embedded controllers Binary Decision Diagrams An efficient representation for Boolean functions Node Variable Edge Value Size reduce Canonicity 1 a 0 b 1 1 b 0 1 0 0 0 0 Characteristic Functions f X Y 0 1 or f x y y f x where X X 1 X m Y Y1 Yl Restriction Projection Support f x j b S x j f f x j 1 f x j 0 The support of an output is the set of inputs that the output depends on Network of Codesign FSM s Globally Asynchronous Locally Synchronous Locally Synchronous Take snapshot of inputs valued or value less Perform computation Change state or emit output events Globally Asynchronous Events happen at any time and independently No guarantee to receive events Synchrony Asynchrony Asynchronous comm does not overly restrict the implementation domain Synchronous lang s restriction is too strong 0 computation time Imply single large FSM Formal verification and analysis technieques Small solution space Synchronous program must be analogous to combinational circuit Asynchronous comm Model Nondeterministic Complicate design and verification Ease modeling unpredictability of reaction delay at spec level and implementation level Software implemented in RTOS Reasons for introducing CFSM A network of components can express a complex behavior while keeping the complexity of each component at a reasonable level Behavior spec is extended with computation Delays are useful to model and constrain timing Asynchronous comm is more efficient for representing interactions among tasks Software Graphs module simple input c integer output y var a integer in loop await c if a c then a 0 emit y else a a 1 end if end loop end var end module Input output signals are associated with two values boolean and value State variable is associated with current and next states S Graphs S Graph model resemble but differ from branching programs and BDD Single variable predicated on TEST nodes Assignments to only a single output Evaluation of multioutput function Evaluation of multioutput function S Graphs Definition 2 Let G be an s graph and let be partitioned among input and output variables as assumed by procedure evaluate G is functional if every output variable zj 1 is assigned by eval step at least one defined i e different from value for each combination of values of the input variables 2 has a defined value whenever a predicate or a function depending on zj is visited by eval step It is easy to show that for a functional s graph evaluate defines a completely specified I O function It is easy to check that a non functional s graph denotes Either an incompletely specified funciton Or a relation between the input and the output variables S Graph Implementation and Optimization Represent CFSM Again focus on control part but support date
View Full Document
Unlocking...