HW/SW SynthesisOutlinePOLIS MethodologyHardware - Software ArchitectureSystem PartitioningSoftware SynthesisSlide 7Software Implementation ProblemSoftware ImplementationSlide 10Software Synthesis ProcedureTask ImplementationSW Modeling IssuesSlide 14ROBDDsROBDDs and Combinational VerificationROBDDs and Memory ExplosionTechnique for Handling ROBDD Memory ExplosionHandling Memory Explosion: Variable OrderingSlide 20SW Model: S-graphsAn Example of S-graphS-graphs and FunctionsSlide 24Example of S-graph ConstructionSlide 26S-graph OptimizationFrom S-graphs to InstructionsSlide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Performance and Cost Estimation: SummaryPerformance and Cost EstimationOpen ProblemsHW/SW SynthesisHW/SW Synthesis2OutlineOutlineSynthesisSynthesisCFSM OptimizationCFSM OptimizationSoftware synthesisSoftware synthesisProblemProblemTask synthesisTask synthesisPerformance analysisPerformance analysisTask schedulingTask schedulingCompilationCompilation3Aptix Board Consists of–micro of choice–FPGA’s–FPIC’sAptix Board Consists of–micro of choice–FPGA’s–FPIC’sPOLIS MethodologyGraphical EFSM+EsterelGraphical EFSM+EsterelJava................CFSMsPartitioningSW SynthesisSW Code + RTOSLogic NetlistHW SynthesisSW EstimationHW EstimationPhysical PrototypingHW/SW Co-SimulationPerformance/trade-off EvaluationFormal VerificationCompilersECEC4Hardware - Software ArchitectureHardware - Software ArchitectureHardware:Hardware:Currently:Currently:Programmable processors (micro-controllers, DSPs)Programmable processors (micro-controllers, DSPs)ASICs (FPGAs)ASICs (FPGAs)Software:Software:Set of concurrent Set of concurrent taskstasksCustomized Real-Time Operating SystemCustomized Real-Time Operating SystemInterfaces:Interfaces:Hardware modulesHardware modulesSoftware procedures (polling, interrupt handlers, ...)Software procedures (polling, interrupt handlers, ...)5System PartitioningSystem PartitioningCFSM1CFSM1CFSM7CFSM7CFSM6CFSM6CFSM5CFSM5CFSM4CFSM4CFSM3CFSM3CFSM2CFSM2e2e2e8e8e3e3e2e2e1e1e9e9e3e3e5e5e7e7e9e9port5port5port1port1port2port2port3port3HW partition 1HW partition 1HW partition2HW partition2SW partition 3SW partition 3SchedulerSchedulerport6port6port7port76Software SynthesisSoftware SynthesisTwo-level processTwo-level process““Technology” (processor) independent:Technology” (processor) independent:best decision/assignment sequence given CFSMbest decision/assignment sequence given CFSM““Technology” (processor) dependent:Technology” (processor) dependent:conversion into machine codeconversion into machine codeinstruction selectioninstruction schedulingregister assignment (currently left to compiler) need need performance and cost analysisperformance and cost analysisWorst Case Execution Timecode and data size7Software SynthesisSoftware SynthesisTechnology-independent phase:Technology-independent phase:Construction of Control-Data Flow Graph from CFSMConstruction of Control-Data Flow Graph from CFSM(based on BDD representation of Transition Function)(based on BDD representation of Transition Function)Optimization of CDFG forOptimization of CDFG forexecution speedexecution speedcode sizecode size(based on BDD sifting algorithm)(based on BDD sifting algorithm)Technology-dependent phase:Technology-dependent phase:Creation of (restricted) C codeCreation of (restricted) C codeCost and performance analysisCost and performance analysisCompilationCompilation8Software Implementation ProblemSoftware Implementation ProblemInput: Input: Set of tasks (specified by CFSMs)Set of tasks (specified by CFSMs)Set of timing constraints (e.g., input event rates and response constraints)Set of timing constraints (e.g., input event rates and response constraints)Output:Output:Set of procedures that implement the tasks Set of procedures that implement the tasks Scheduler that satisfies the timing constraintsScheduler that satisfies the timing constraintsMinimizing:Minimizing:CPU cost CPU cost Memory sizeMemory sizePower, etc.Power, etc.9Software ImplementationSoftware ImplementationHow to do it ? How to do it ? Traditional approach:Traditional approach:Hand-coding of proceduresHand-coding of proceduresHand-estimation of timing input to scheduling algorithmsHand-estimation of timing input to scheduling algorithmsLong and error-proneLong and error-proneOur approach: three-step Our approach: three-step automated automated procedure:procedure:Synthesize each task separatelySynthesize each task separatelyExtract (estimated) timingExtract (estimated) timingSchedule the tasksSchedule the tasksCustomized RT-OS (scheduler + drivers)Customized RT-OS (scheduler + drivers)10Software ImplementationSoftware ImplementationCurrent strategy: Current strategy: Iterate between synthesis, estimation and schedulingIterate between synthesis, estimation and schedulingDesigner chooses the scheduling algorithm Designer chooses the scheduling algorithm Future work: Future work: Top-down propagation of timing constraintsTop-down propagation of timing constraintsSoftware synthesis under constraintsSoftware synthesis under constraintsAutomated scheduling selection Automated scheduling selection (based on CPU utilization estimates)(based on CPU utilization estimates)11Software Synthesis ProcedureSoftware Synthesis ProcedureSpecification, partitioningS-graph synthesisTiming estimationScheduling, validationnot feasiblefeasibleCode generationCompilationTesting, validationProductionpassfail12Task Implementation Task Implementation Goal: quick response time, within timing and size constraintsGoal: quick response time, within timing and size constraintsProblem statement:Problem statement:Given a CFSM transition function and constraintsGiven a CFSM transition function and constraintsFind a procedure implementing the Find a procedure implementing the transition functiontransition function while meeting the while meeting the constraintsconstraintsThe procedure code is acyclic:The procedure code is acyclic:Powerful optimization and analysis techniquesPowerful optimization and analysis techniquesLooping, state storage etc. are implemented outside Looping, state storage etc. are implemented outside (in the OS)(in the OS)13SW Modeling IssuesSW
View Full Document