Yosinori Watanabe

SynthesisofEmbeddedSoftwareforReactiveSystemsRobertClariso1JordiCortadella1AlexKondratyev2LucianoLavagno3ClaudioPasserone3YosinoriWatanabe21UniversitatPolitecnicadeCatalunya,Barcelona,Spain2CadenceBerkeleyLabs,Berkeley,USA3PolitecnicodiTorino,Torino,ItalyFromthehandoutsoftheSecondInternationalWorkshoponIntegrationofSpecicationTechniquesforApplicationsinEngineering(INT’02)Abstract:Embeddedsystemsareusuallydeployedinenvi-ronmentswithtighttimingconstraints.Increasingrun-timeperformanceisoftenacriticalissue.Thispaperaddressestheproblemofsynthesizingecientsoftwareforembeddedsystemsspeciedasasetofcommunicicatingsequentialpro-cesses.TheQuasi-StaticSchedulingalgorithmispresented,alongwithresultsfromanindustrialexample.Openprob-lemsinthiseld,suchasincorporatingdata-owanalysisintotheschedulingalgorithm,arediscussed.1Introduction1.1EmbeddedsystemsEmbeddedsystemsaredrivingresearchfromtheelectroniccommunityduetotheirwidespreaduse.Inourdailyroundweinteractwithmultipleem-beddedsystems:aVCR,acellularphone,anelectronicorganizer,adigitalcamera,etc.Thedesignofsuchdevicesrequiresamultidisciplinarknowl-edgeofsoftwareandhardwaresystems.Italsorequiresapreciseknowledgeofhowthesysteminteractswiththeenvironment.Moreformally,anembeddedsystemisaspecializedcomputationunitthatperformsasetoftaskswithinalargersystemcalledenvironment.Theinteractionwiththeenvironmentistypicallyreactive,i.e.theembeddedsystemmustprocessinputsfromtheenvironmentundersometimingcon-straintssuchasthespeed(throughput)orthedelay(latency).ThisworkhasbeenpartiallyfundedbyCICYT98-0410andbyagrantfromCadenceDesignSystemsAsembeddedsystemsarehighlyconcurrentbynature,specicationsoftenemployformalmodels[6,5]thatexposeparallelismexplicitly.Someexamplesofformalmodelsaredataownetworks[15],PetriNetbasedmod-els[7],CommunicatingSequentialProcesses[13]andKahnprocessnetworks[14].Theimplementationofthesespecicationsisgenerallyasoftwarecom-ponentrunningontopofahardwarearchitecturethatmightincludesev-eralCPUs,DSPs,co-processors,andsoon.Thesynthesisofthissoftware-hardwaremixedimplementationdenesthreeproblems:(a)amappingfromelementsofthespecicationtohardwareandsoftwarecomponents,(b)anal-locationofsoftwarecomponentstohardwarecomputationunits(e.g.CPUs)oftheembeddedsystem,and(c)aschedulingofthesoftwarecomponentsineachofthehardwarecomputationunits.Technologymappingandallocationaredependentonseveralfactors,includingcostandtechnologyconstraints.However,theremainingschedulingproblemallowsaformalapproachasitisonlydependentontheconstraintsdictatedbytheenvironment.1.2SchedulingofreactivesystemsInthecaseofreactivesystems,theschedulingproblemissubjecttotimingconstraintsontheresponsetotheinputsfromtheenvironment.Minimizingrun-timeoftheinputprocessing,ifpossible,andminimizingidleCPUtimewillthemainconcernsoftheschedulingalgorithm.Theformerisamatterofchoosingthebestalgorithmandusinganoptimizingcompiler.ButthelattercanbeimprovedbyreducingtheCPUtimespentbytheoperatingsystem.Onepossibleschedulingapproachcouldbedynamicscheduling:wegen-erateoneprocessforeachfunctionalprocessinourspecication,lettingtheoperatingsystemdecidewhichprocessshouldbeexecutedatrun-time.Theproblemwithdynamicschedulingisthattaskcontextswitchingcausesarun-timeoverhead,whichcanbeunacceptableinsomeenvironments.Therefore,althoughdynamicschedulingisusedwidespreadininteractivesystems,itisnotappropiateforreactivesystems.Staticschedulingtechniquestrytomakemostdecisionsaboutexecutionorderatcompile-time,thusreducingthetimeconsumedbytheoperat-ingsystemduringrun-time.Thesealgorithmsrequirethatsomeinforma-tionabouttherateofarrivalsofinputsfromtheenvironmentisknownatcompile-time.Eventhen,completelystaticschedulesareonlypossibleifwerestrictourselvestospecicationswithoutdata-dependentchoices.Real-timeembeddedsystems,whereafailuretosatisfyadeadlinecanleadtoaseriousfailure,cancopewiththisrestrictions.Butgenericembeddedsys-temswouldbeverylimitedwithoutdata-dependentconstructs.Theprob-lemofndingpartialschedulesinaconcurrentsystemwithdatadependentconstructsensuringthattherewillnotbebueroverowisknownasQuasiStaticScheduling(QSS).ThispaperpresentstheQSSproblemandastaticmethodtosynthesizeasetoftasksforaconcurrentsystemthatprovidebetterrun-timeperfor-mancethatasetofprocesseswithrun-timescheduling.Therestofsec-tionsareorganizedasfollows.Section2providestheoreticbackgroundandnecessarydenitionsfromthePNdomain.Section3containsahigh-leveldescriptionofthealgorithm,andsection4presentssomeresultsobtainedfromanindustrialexample.Section5describesrelevantopenproblemsthatwillprobablyleadtofutureresearchonthearea.1.3AmotivatingexampleFigure1showsanexampleofembeddedsystemthatcontrolstheenviron-mentalconditionsinaroomofalibrary.Thebooksintheroomcanbedamagedbyahighhumidityoraquickriseintemperature.Twosensorsinthesystemmonitorthetemperatureandhumidityintheroom;thesystemcanreactbyactivatingairconditioningoradryer.Finally,ifthetemper-aturebecomestoohigh,thesystemassumesthatthereisareandraisesanalarm.Thesystemisdividedinthreeprocesses.Twoprocesses,namelytheTEMP