Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

NonamemanuscriptNo.(willbeinsertedbytheeditor)ModularStaticSchedulingofSynchronousData-flowNetworksAnefficientsymbolicrepresentationMarcPouzetPascalRaymondReceived:January2010/Accepted:dateAbstractThispaperaddressesthequestionofproducingmodularsequentialimpera-tivecodefromsynchronousdata-flownetworks.Precisely,givenasystemwithseveralinputandoutputflows,howtodecomposeitintoaminimalnumberofclassesexecutedatomicallyandstaticallyscheduledwithoutrestrictingpossiblefeedbackloopsbetweeninputandoutput?ThoughthisquestionhasbeenidentifiedbyRaymondintheearlyyearsofLustre,ithasalmostbeenleftasideuntiltherecentworkofLublinerman,SzegedyandTripakis.Theproblemisproventobeintractable,inthesensethatitbelongstothefamilyofoptimizationproblemswherethecorrespondingdecisionproblem—thereexistsasolutionwithsizec—isNP-complete.Then,theauthorsderiveaniterativealgorithmlookingforsolutionsforc=1,2,...whereeachstepisencodedasasatisfiability(SAT)problem.Despitetheapparentintractabilityoftheproblem,ourexperienceisthatrealpro-gramsdonotexhibitsuchacomplexity.BasedonearlierworkbyRaymond,thecurrentpaperpresentsanewencodingoftheproblemintermsofinput/outputrelations.Thisencodingsimplifiestheproblem,inthesensethatitrejectssomesolutions,whilekeep-ingalltheoptimalones.Itallows,inpolynomialtime,(1)toidentifynodesforwhichseveralschedulesarefeasibleandthusarepossiblesourcesofcombinatorialexplosion;(2)toobtainsolutionswhichinsomecasesarealreadyoptimal;(3)otherwise,togetanontriviallowerboundforctostartaniterativecombinatorialsearch.Themethodhasbeenvalidatedonseveralindustrialexamples.Revisedandextendedversionof[14].ThisworkissupportedbytheSYNCHRONICSlargescaleinitiativeofINRIA.MarcPouzetE´coleNormaleSupe´rieureandUniversite´PierreetMarieCurie.Physicaladdress:E´coleNormaleSupe´rieure,45ruedUlm,75230Pariscedex05,France.E-mail:Marc.Pouzet@ens.fr.PascalRaymondLaboratoireVERIMAG,2avenuedeVignate,38610Gie`res,France.E-mail:Pascal.Raymond@imag.fr.
2Fig.1AScade(v5)block-diagramThesolutionappliestoalargeclassofblock-diagramformalismsbasedonatomiccomputationsandadelayoperator,rangingfromsynchronouslanguagessuchasLus-treorScadetomodelingtoolssuchasSimulink.KeywordsReal-timesystems,Synchronouslanguages,Block-diagrams,Compilation,NP-completeness,Partialorders,Preorders1IntroductionThesynchronousblock-diagramordata-flowformalismisnowpreeminentinavarietyofdesigntoolsforembeddedsystems.Sequentialcodegenerationofsynchronousblock-diagramshavebeenconsideredintheearlyyearsofLustre[7]andSignal[1]andis21providedbyindustrialtoolssuchasScadeandRtBuilderforalmostfifteenyears.Thoughithasbeenconsideredmorerecently,modelingandsimulationtoolssuchasSimulink3andModelica4arenowequippedwithautomaticcodegenerators.Wefocushereontheproblemofgeneratingimperative,sequentialcode,imple-mentingthefunctionalbehaviorofaparalleldata-flownetwork.Wekeepabstractedthe(somehoworthogonal)problemofdatamanagement,thatis,howvaluesareac-tuallypassedfromonenodetoanotherandeventheinterpretationofeachoperator.Inparticular,weaddressbothdata-flownetworkswithdiscrete-time(e.g.,Scade)orcontinuous-time(e.g.,Simulink)semantics.Figure1givesanexampleofaScadeblock-diagramandFigure2,anexampleofaSimulinkone.Whateverbethesemanticsofnodesinanetwork,therearebasicallytwotypesofatomicnodes.Instantaneousnodesneedtoevaluatealltheirargumentsinordertoproducetheiroutputs(e.g.,combinatorialfunctions).Onthecontrary,delaynodesareabletoproducetheiroutputsbeforereadingtheirinputs.Theycorrespondtounitaryregistersinsynchronousdesigns(theso-calledpreoperatorofLustre),initializedbuffersinKahnprocessnetworks[9,10]orcontinuousintegratorsinSimulink.Delays1http://www.esterel-technologies.com/scade/2http://www.geensoft.com/en/article/rtbuilder3http://www.mathworks.com/product/simulink4http://www.modelica.org
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin