Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Noname manuscript No will be inserted by the editor

De
29 pages
Noname manuscript No. (will be inserted by the editor) Modular Static Scheduling of Synchronous Data-flow Networks An efficient symbolic representation Marc Pouzet · Pascal Raymond Received: January 2010 / Accepted: date Abstract This paper addresses the question of producing modular sequential impera- tive code from synchronous data-flow networks. Precisely, given a system with several input and output flows, how to decompose it into a minimal number of classes executed atomically and statically scheduled without restricting possible feedback loops between input and output? Though this question has been identified by Raymond in the early years of Lustre, it has almost been left aside until the recent work of Lublinerman, Szegedy and Tripakis. The problem is proven to be intractable, in the sense that it belongs to the family of optimization problems where the corresponding decision problem — there exists a solution with size c — is NP-complete. Then, the authors derive an iterative algorithm looking for solutions for c = 1, 2, ... where each step is encoded as a satisfiability (SAT) problem. Despite the apparent intractability of the problem, our experience is that real pro- grams do not exhibit such a complexity. Based on earlier work by Raymond, the current paper presents a new encoding of the problem in terms of input/output relations. This encoding simplifies the problem, in the sense that it rejects some solutions, while keep- ing all the optimal ones.

  • output

  • problem — there

  • node

  • tools such

  • sequential

  • flow networks

  • main compilation approaches

  • such

  • code


Voir plus Voir moins
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