Software Synthesis EE202A Presentation October 18, 2001OutlineBackgroundHW/SW Co-designHW/SW Co-DesignPartitioning High-Level DesignSoftware SynthesisCode GenerationSoftware Synthesis ExampleProgramming ModelsCFSMSW Synthesis with CFSMS-GraphTask SynthesisRTOSCost/Performance EstimationSDFSchedule/MemorySW Synthesis with SDFSummaryRelated ResearchReferencesReferencesOctober 18, 2001 Cho & Kim 1Software Synthesis EE202A PresentationOctober 18, 2001Young H. Cho and Seung Hyun KimOctober 18, 2001 Cho & Kim 2OutlineBackgroundHW/SW Co-designSoftware SynthesisSummaryOctober 18, 2001 Cho & Kim 3BackgroundEmbedded SoftwareConstrained Structure“Simple,” Multiple TasksTarget ArchitectureOctober 18, 2001 Cho & Kim 4HW/SW Co-designReactive Real-time SystemMixed HW/SW SystemSoftware – FlexibilityHardware – PerformanceOctober 18, 2001 Cho & Kim 5HW/SW Co-DesignFormal LanguagesPartitioningHW SynthesisSW SynthesisRTOS Tasks Logic SynthesisCode Optimization Logic OptimizationBoard Level PrototypingCo-SimulationAndFormal VerificationOctober 18, 2001 Cho & Kim 6Partitioning High-Level DesignFormal LanguagesTextual RepresentationGraphical RepresentationDesign PartitioningPlatform ResourceHW/SW SynthesisABCOctober 18, 2001 Cho & Kim 7Software SynthesisGoal: Optimized software from high-level specificationIssues to considerTarget hardware supportRetargetable compilersResult: Efficient code for the target processorABCbegin X1=TaskA(W); X2=TaskA(W); Y=TaskB(X1); result=TaskC(X2,Y);endOctober 18, 2001 Cho & Kim 8Code GenerationStatic CodeStatic (object) code for each tasksLibrary of inline codesCode optimizationTask HandlingResource managementStatic/dynamic scheduling CommunicationOctober 18, 2001 Cho & Kim 9Software Synthesis ExampleTask BDownsample2 to 1Task AUpsample1 to 332High-LevelDescriptionStatic Codefor (i=0;i<3;i++) { Out[i]=In;}Reg=In[0]+In[1];Out=Reg>>1;main(Samples *In) { while() { /* Schedule 2A */ for (j=0;j<2;j++) { /* inline code: Task A */ for (i=0;i<3;i++) { OutA[j*3+i]=InA[j]; } } for (k=0;k<3;k++) { /* inline code: Task B */ Reg=OutA[k*2] +OutA[k*2+1]; OutB[k]=Reg>>1; } }} Code Generation2 (TaskA) 3 (TaskB)& ScheduleOctober 18, 2001 Cho & Kim 10Programming ModelsFSM ModelCo-design Finite State Machine (CFSM)Dataflow ModelsSynchronous Dataflow (SDF)Boolean DataflowDynamic DataflowProcessor NetworkOthersOctober 18, 2001 Cho & Kim 11CFSMExtended FSMGlobally Asynchronous Locally Synchronous (GALS)Unbiased towards HW or SWReactive, control-dominated systemsSize of the systems that can be mappedOctober 18, 2001 Cho & Kim 12SW Synthesis with CFSMSoftware Graph (S-Graph)Task SynthesisReal-Time Operating System (RTOS)Machine Code CompilationOctober 18, 2001 Cho & Kim 13S-GraphControl/Data-Flow DiagramDirected Acyclic Graph (DAG)BEGINpresent_c = 1a = ?ca’ := 0emit_y := 1ENDa’ := a + 1a’ := aemit_y := 0false truefalse truemodule simpleCFSM: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 loopend varend moduleOctober 18, 2001 Cho & Kim 14Task SynthesisConstructionTranslation of transition function of CFSMRecursively built from the reactive functionOptimizationReordering or collapsing test nodesCode-size estimationTranslationTarget language (e.g., C code)October 18, 2001 Cho & Kim 15RTOSSchedulingIndividual CFSMCommunication MechanismsSet of flagsMemory mapped I/O port of the micro-controllerPolling or interruptsSynthesis or Commercial RTOSOctober 18, 2001 Cho & Kim 16Cost/Performance EstimationAccurate and Quick EstimationCode sizeMin/max execution timeConsiderationsCode structuresSystem platformSolutionAssign cost/timing parametersOctober 18, 2001 Cho & Kim 17SDFDigital Signal ProcessingGraphical RepresentationActors/NodesDirected edgesDelaysSynchronyConsume TokensProduce TokensFixed number of Tokensabc12122DDOctober 18, 2001 Cho & Kim 18Schedule/MemoryStatic schedulingDetermine task buffer sizeMemory efficient edge delayDeterministic at compile timeOctober 18, 2001 Cho & Kim 19SW Synthesis with SDFLibrary of actor code blocksDetermine static scheduleOptimal code sizePerformanceInline code using scheduleOctober 18, 2001 Cho & Kim 20SummaryHW/SW Co-designSoftware SynthesisHighly optimized codeTiming constraintsEfficient Resource UsageHighest performance per costControl over implementation costOctober 18, 2001 Cho & Kim 21Related ResearchBerkeley HW/SW Co-Design Grouphttp://www-cad.eecs.berkeley.edu/~polisBerkeley Ptolemy Grouphttp://ptolemy.eecs.berkeley.eduCHINOOKhttp://www.cs.washington.edu/research/chinook/VULCANCadence Cierto VCCJeckle: the JAVA ECL compilerOctober 18, 2001 Cho & Kim 22References 1. A. Sangiovanni-Vincentelli, “What is software synthesis?,” Computer Design Editorial, Department of EECS, UC Berkeley, Berkeley, CA, June 1997.2. Berkeley POLIS Group, “A Framework for Hardware-Software Co-Design of Embedded System,” POLIS Website, Department of EECS, UC Berkeley, Berkeley, CA, 1997.3. F. Thoen, M. Cornero, G. Goosens, and H. DeMan, “Software synthesis for real-time information processing systems,” ACM SIGPLAN, Vol. 30, No. 11, November 1995.4. Linkoping University HW/SW Co-design Course Website, http://www.ida.liu.se/~zebpe/codesign/, 1998.5. EE249 “Design of Embedded Systems: Models, Validations, and Synthesis,” http://www-cad.eecs.berkeley.edu/~polis/class/index.html, UC Berkeley, CA. 2001.6. P. Chou, and G. Borriello, “Software scheduling in the co-synthesis of reactive real-time systems,’ 31st ACM/IEEE Design Automation Conference, San Diego, CA, pp. 1-4, June 1994. ..October 18, 2001 Cho & Kim 23References7. E. Lee, “Embedded software,” UC Berkeley ERL Memorandum M01/26, http://ptolemy.eecs.berkeley.edu/publications/papers/01/embsystems/8. F. Balarin, L. Lavagno, P. Murthy, and A. Sangiovanni-Vincentelli, “Scheduling for embedded real-time systems,” IEEE Design & Test of Computers, Vol. 15, No. 1, pp. 71-82, January-March 1998. http://ielimg.ihs.com/iel3/54/14269/00655185.pdf9. S. Bhattacharyya, R. Leupers, and P. Marwedel, “Software synthesis and code generation for