shared memory implementations of synchronous dataflow specifications using lifetime analysinew

《shared memory implementations of synchronous dataflow specifications using lifetime analysinew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、June3,1999SharedMemoryImplementationsofSynchronousDataflowSpecificationsUsingLifetimeAnalysisTechniquesPraveenK.MurthyAngelesDesignSystemspmurthy@angeles.comShuvraS.BhattacharyyaECEDept.,andInstituteforAdvancedComputerStudies,UniversityofMaryland,CollegeParkssb@eng.umd.eduAbst

2、ractTherehasbeenaproliferationofblock-diagramenvironmentsforspecifyingandprototypingDSPsys-tems.TheseincludetoolsfromacademialikePtolemy[6],andcommercialtoolslikeSPWfromCadenceDesignSystems,andCossapfromSynopsys.Theblockdiagramlanguagesusedintheseenvironmentsareusuallybasedond

3、ataflowsemanticsbecausevarioussubsetsofdataflowhaveproventobegoodmatchesforexpressingandmodelingsignalprocessingsystems.Inparticular,synchronousdataflow(SDF)[14]hasbeenfoundtobeaparticularlygoodmatchforexpressingmultiratesignalprocessingsystems[5].Oneofthekeyproblemsthatarises

4、duringsynthesisfromanSDFspecificationisscheduling.Pastworkonscheduling[3]fromSDFhasfocusedonoptimizationofprogrammemoryandbuffermemory.However,in[3],noattemptwasmadeforoverlayingorsharingbuffers.Inthispaper,weformallytackletheproblemofgeneratingoptimallycompactschedulesforSDFg

5、raphs,thatalsoattempttominimizebufferingmem-oryundertheassumptionthatbufferswillbeshared.Thiswillresultinscheduleswhosedatamemoryusageisdrasticallylowerthanmethodsinthepasthaveachieved.Themethodweuseisthatoflifetimeanalysis;wedevelopamodelforbufferlifetimesinSDFgraphs,anddevel

6、opschedulingalgorithmsthatattempttogenerateschedulesthatminimizethemaximumnumberoflivetokensundertheparticularbufferlifetimemodel.WedevelopseveralefficientalgorithmsforextractingtherelevantlifetimesfromtheSDFschedule.Wethenusethefirstfitheuristicforpackingarraysefficientlyinto

7、memory.WereportextensiveexperimentalresultsonapplyingthesetechniquestoseveralpracticalSDFsystems,andshowimprovementsthataverage50%overprevioustechniques,withsomesystemsexhibitinguptoan83%improvementoverprevioustechniques.1IntroductionBlockdiagramenvironmentsareprovingtobeincre

8、asinglypopularfordevelopingDSPsystems.Thereasonsfortheirpopul