Schedulability-Driven Performance Analysis of Multiple Mode Embedded Real-Time Systems

Systems

YoungsooShin,DaehongKim,andKiyoungChoi

CenterforCollaborativeResearchandInstituteofIndustrialScience,

UniversityofTokyo,Tokyo106-8558,Japan

SchoolofElectricalEngineering,SeoulNationalUniversity,Seoul151-742,Korea

Abstract

Providingmultiplemodestosupportdynamicallychangingenvi-ronments,standards,andnewservicesisprevalentinembeddedsystems,especiallyinmobileradiosystems.Becausesuchasys-temfrequentlycontainstime-constrainedtasks,itisimportanttoanalyzethetemporalrequirementsaswellasthefunctionalcor-rectness.Thispaperpresentsamethodtoanalyzetemporalre-quirementsimposedonanembeddedreal-timesystemsupportingmultiplemodes.Whilemostperformanceanalysismethodsfocusonlyontestingthefeasibilityofataskorasystem,ourmethodgoesfurtherbyaddressingtheproblemoflocatinghotspotsofasystemtherebyhelpingthedesignertochooseamongalternativedesignsorarchitectures.Weformallydefinetheanalysisproblemandshowthatitisveryunlikelytobesolvedefficiently.Wepresentaheuris-ticalgorithm,whichisaccurateandfastenoughtobeusediniter-ativeprocessesinsystem-levelanalysisanddesign.Theanalysisproblemisextendedtoaccommodateprobabilisticbehaviorexhib-itedbysoftreal-timetasks.

1Introduction

Onewaytocopewithdynamicallychangingenvironments,stan-dards,andfuturetechnologiesistointroducereconfigurabilityintoasystem.WhilereconfigurabilitycanbeobtainedbyintroducingreconfigurabledevicessuchasFPGAs,recenthighperformancemicroprocessorsandDSPshavemadethesoftwareapproachin-creasinglyviablealternativeforimplementingmostpartsofacom-plexembeddedsystem,therebyenablingreconfigurabilityofasys-temviasoftware.Mobiletelephony[1]isoneofsuchapplicationsthatmightbenefitfromsoftwarereconfigurabilitybecauseitfaceswithmultipleandrapidlychangingstandards,newsignalprocess-ingalgorithms,andnewservices.Asanexample,amobileusermightreconfigureaterminal,whichisconfiguredtoprocessonlystillimagesatonetime,tohandlemotionimagesthroughdown-loadingMPEGprogramovertheairinterface[2].AsetoftasksconsistingofthesystemisalteredbyintroducingMPEGapplica-tion.Theresultisthatasystemoperatesinmultiplydefinedcon-figurationstatusormode.

Becausesuchasystem,whichwecallmultimodesysteminthispaper,maycontainhardreal-timetaskssuchasacontrolprogramaswellassoftreal-timetaskssuchasmultimediaapplications,itiscrucialtoanalyzethetemporalrequirementsofthesystemas

wellasthefunctionalcorrectness.Inthispaper,weproposeaschedulability-drivenperformanceanalysismethodformultimodesystems.Comparedtomostconventionalreal-timeanalysis[3],ourmethoddiffersintworespects.First,theconventionalmeth-odsfocusontheanalysisforafixedsetoftasks,thusforasinglemodeofoperation,whereasourmethodtargetstheanalysisoverasetofmodes.Second,mostreal-timeschedulabilityanalysismakesadecisiononwhetherornotasetoftaskscanbescheduledonaprocessororprocessorswhilesatisfyingallthetimingconstraints.However,itcannotdomuchwhenthetasksetisfoundtobeun-schedulable.Thisisthecasewherealotofengineeringapproaches,includinghand-craftedcodetuning,reimplementingcoreroutines,andexperimentingwithvarioustimingparameters,arerepeatedun-tilalltheconstraintsaresatisfied.Duringthesetime-consumingit-erativeprocesses,designersareoftenconfrontedwithquerieslike:DoesreducingtheexecutiontimeoftaskAimprovetheschedula-bility?Ifso,howmuchisnecessary?Canthesameamountofschedulabilityimprovementbeachievedbyreducingtheexecutiontimeofothertaskswithsmalleramountorlesseffort?Becausetheamountofsuchoptimizationdirectlyrelatestodesigner’seffort,itshouldbeminimized.Ourmethodautomaticallyselectstasksandcomputestheamountofoptimizationsuchthatitisminimized.Figure1showsanexampleofflowofdesignmethodologyformultimodesystems.Thefirststepadherestotheconventionaltop-downdesignmethodologyforreal-timesystems.Inthefigure,weshowthestepsadoptedinDesignApproachforReal-TimeSystems(DARTS)[4].Thesystemisspecifiedbyhierarchicallystructureddataflow/controlflowdiagrams.Itisthenstructuredintotasksac-cordingtothetaskstructuringcriteriasuchassequential,temporal,andfunctionalcohesioncriteria.Taskinterfacesarethendefinedbyanalyzingthetasks.Detaileddesignofeachtaskfollows.Inthesecondstep,wedefinemodesunderwhichthesystemoperates.Eachmodeisrepresentedasafixedsetoftasks,whicharedefinedinthefirststep.Inthethirdstep,weanalyzeperformanceofthesystemfromthedefinitionofmodes,timingconstraintsimposedonthesystem,andtimingparametersofeachtaskextractedfromthefirststep.Iftheanalysisfails,thatis,oneormoretasksfailtosatisfytheirdeadlinesorqualityofservice(QoS)requirements,weperformthedetailedanalysistorevealtheimpactcausedbyeachtasktotheperformanceofeachmode.Theanalysisresultsuggestsadesigneranoptimizationgoaltowhichdesigneffortshouldbedevoted.Thiscanbeavaluableinformationbecauseitsavesthedesignerfromspendingtimetooptimizetaskswhichhavenoeffectorpotentiallylittleeffectonthesystemperformance.Theoptimizationstepfollowsbyadoptingvariousmethodssuchastasktransformation[5],aperiodiceventtransformation[6],orhardware-softwarecodesign.

Theremainderofthepaperisorganizedasfollows.Inthenextsection,webrieflyreviewrelatedwork,whichfocusontheperfor-manceanalysisofembeddedreal-timesystems.Insection3,weintroducetheunderlyingmodeloftheperformanceanalysis,thedefinitionoftheanalysisproblem,andourstrategytotheanaly-

• Develop system specification• Structure the system into tasks• Define task interfaces• Design each taskDefine modesSatisfiedAnalyze performanceAnalyze performanceUnsatisfiedLocate design hot spotsLocate design hot spotsOptimize designFigure1:Anexampleofflowofdesignmethodologyformulti-modesystems.sisproblem.Insection4,wediscussextensionstoourstrategytotheanalysisproblemtoincorporatesoftreal-timetaskswithQoSrequirementsandprobabilisticexecutiontimesandpresentexperi-mentalresultsforanumberofreal-timesystemexamplesinsection5.Wedrawconclusionsinsection6.2RelatedWorkSchedulabilityanalysisformodechangesisproposed[7]foraflex-iblereal-timesystem,whichissimilartoourdefinitionofmul-timodesystem.Becausethetasksetinoldmodeandthatinnewmodemutuallyinterfereduringamodechange,themethodfocusesontheanalysistoverifywhethertasksduringamodechangeareschedulable.Aperformanceestimationforaudioandvideoap-plications,usuallycalledcontinuousmedia(CM)applications,ispresented[8]foranetworkedembeddedsystem.Becausesuchap-plicationsarefrequentlyassociatedwithsoftreal-timeconstraintsandprobabilisticexecutiontimevariations,astochasticapproachisproposedtoestimateadelayofeachapplicationandaprobabilitythateachapplicationmissesthespecifieddeadline.Whilemostper-formanceanalysisfocusonthefeasibilitytestforeachtask,atestforasystem,inotherwordsatestconsideringalltaskstogether,isproposed[9].Eachtaskisassociatedwithperiod,deadline,andaprobabilitydistributionofexecutiontime.Afeasibilityprobabilityofasystemiscalculatedfromaprobabilitythateachtaskmeetsitsdeadline.

Allthesemethodsaswellasclassicalreal-timeanalysisfocusonthedeterminationoftheschedulabilityonlyanddonotprovideanysolutionsincasewhenthesystemfailstosatisfygiventimingconstraints,whichisthemainingredientofourapproach.

3

PerformanceAnalysisProblem

3.1

ModelofMultimodeSystem

Thetaskmodelofmultimodesystemweuseinthispaperbuildsuponawidely-usedreal-timeprocessmodel[10].Theextendedtaskmodel(amixofhardreal-timeandsoftreal-timetask)toac-commodateprobabilisticbehaviorexhibitedbysoftreal-timetasks,thedefinitionofcorrespondinganalysisproblem,andthesolutionstrategyareallpresentedinthenextsection.

Amultimodesystemisdefinedasasetoffixednumberofmodes.Eachmodeisdefinedagainasasetoffixednumberoftasks,whicharemembersofasetoftasks,denotedbyτ.Inotherwords,amodeisasubsetofτpossiblywithintersectionwithothermodes.Foraschedulingofeachmodeofmultimodesystem,weassume,inthispaper,aratemonotonicscheduling(RMS)[10]onasingleprocessor,whichisproventobeoptimalfixedpriorityscheduling.Fixedpriorityschedulinghasseveraladvantagesoverotherschedulingschemes.Itisquitesimpletoimplementinmost

Table1:Anexampleoftaskset

TiDiCiτ10104τ116168τ2252510τ3505015τ45

50

50

13

kernels.Also,manyanalyticalmethodsareavailabletodeterminewhetherasystemisschedulableornot.However,itisnotdiffi-culttoextendourapproachtootherschedulingmethods[11]ortotakeintoaccountotherfactorssuchastaskdependencies,sched-uleroverhead[12],andaccesstosharedresources[13]byadoptingcorrespondinganalysismethods.Thesetoftasksττorsporadictasksinthedescending1τ2τordernisofanpriority,orderedi.e.setoftheperiodicpriorityofτiishigherthanthatofτj,providedthatij.Theparametersofeachtaskincludeitsperiod(theminimuminter-arrivaltimebe-tweensuccessiverequestsincaseofasporadictask)TDexecutiontime(WCET)Ci,deadlineduciblei,worstcaseexecutiontime,thatis,theamounti,andthemaximallyre-ofexecutiontimethatcanbereducedbysomekindofoptimization,mrei1.

Example1Consideranexampleofhardreal-timetasksetasshowninTable1.Ratemonotonicpriorityassignmentisanatu-ralchoicebecauseperiodsareequaltodeadlines.Prioritiesareassignedinroworderinthetable,thatis,τandτ1hasthehighestprior-ity5hasthelowestpriority.Assumethatwehavetwovideoapplications,τ1andτ4,twoaudioapplications,τ.Assume2andτthat5,andacontroltaskmanagingtheentiresystem,τ32wehave5modesasgivenby

ΠΠ1τΠ2Π3ττ2τ2τ3τ4Π4τ1ττ3τ51

2

τ35

τ33

τ4

τ5

3.2CTAProblem

AsshowninFigure1,iftheperformanceanalysisfails,weperformthedetailedanalysistorevealtheimpactcausedbyeachtasktotheperformanceofeachmode.Weformallydefinetheproblemofthisstep,whichwecallcutofftimeassignment(CTA)problem,astheproblemofcomputingtheamountofexecutiontimetobecutoff(throughoptimization)fromeachtasksuchthatalltasksareensuredtomeettheirdeadlinesinallmodes.Formally,aninstanceoftheCTAproblemisa2-tupleτΠ,where

ΠEachmodeΠiΠ(iΠτspecifiesthesetofmodesofasystem.i)isanordered(withrespecttopriorities)sub-setoftasks.Πiissaidtobefeasibleifandonlyifallofitstaskscanbescheduledwhiletheirdeadlinesaremet.

AsolutiontotheinstanceoftheCTAproblemisafunctionf:τR0,whereR0denotesthesetofnon-negativereals,suchthat

1

mreicanbeusedinvariouswaysinourmethods.Wecanassign0tomrefurtheroptimization.Incaseadegreeofoptimizationishardtoiifτnoroomforestimateihasinadvance,wecanassignthesamevalueofCthatτtimeitomrebecomesi(thusmakeanassumptionicanbeoptimizedsuchthatitsexecution0),andtheniteratetheprocessasdepictedinFigure1.2

Thismaynotberealisticassumptionbecausevideoandaudiotasksarefrequentlyregardedassoftreal-timetasks.Theassumptionisonlyfortheillustrativepurpose.

fτi

mrei

τi

τ.

iisfeasible,Π,whenCiisreducedbyfτi

ΠΠi

τi

τ.

Thecostofthesolutionisthecostmaynotbeaccurate∑τiniτfτtermsi.ofObviouslyactualcost.theFordefinitionexample,ofitisnotdirectlyproportionaltothehardwareareawhenwearetoimplementpartsoftaskswithhardwaretoreducetheexecutiontimeofeachtaskbyfτtohelpthedesignertochoosei.However,amongitalternativeissufficientlyandfunctionallyinformativeequivalentimplementations.Asolutioniscalledoptimalifandonlyifithasminimumcost.

3.3AnalysisofaSystemwithSingleMode

Inthissubsection,wereviewtheperformanceanalysisforasinglesetofhardreal-timetasks[14],onwhichourapproachisbased.TheschedulabilityanalysisforRMSisbasedonthecriticalinstanttheorem[10]whichsaysthatifataskmeetsitsdeadlinewheneverthetaskisrequestedsimultaneouslywithrequestsforallhigherpri-oritytasks,thenthedeadlinewillalwaysbemetforalltaskphas-ings.Thisimpliesthatweneedtoperformtheanalysisfromtime0uptotheleastcommonmultipleofalltaskperiodsundertheas-sumptionthatalltasksarerequestedsimultaneouslyattime0.Thisagainrequirestheanalysistobeperformedinthecontinuoustimeinterval.Lehoczkyetal.[15]showedthatweactuallyneedtheanalysisonlyatdiscretetimepointsinsteadofcontinuoustimein-terval.Thesetoftimepoints,calledschedulingpoints,fortaskτisdefinedby

iSi

TikTjτj

hepi;k

1

Tj

(1)

wherehepidenotesthesetoftaskshavingpriorityhigherthanorequaltothatofτthereexisti.τoneicanbescheduledwithoutviolatingitsdeadline,iformoreschedulingpointstSi,whichsatisfy

∑Cjt

Tjt

(2)τj

hepi

Notethatthelefthandsideoftheinequalityrepresentsthecumu-lativedemandsontheprocessorimposedbyhepi.

WeassumethatelementsofSiaresortedinascendingorder.WedefineSiForeachjasthejthelementofStask,wetrytofindai,thatis,jthschedulingpointofτi.schedulingpointthatsatisfiesin-equality(2).Ifwecanfindnosuchschedulingpoints,wecomputethetimedeviationbywhichthecorrespondingtaskmisseseachofitsschedulingpoints.Wedefine∆cijasthetimedeviationofτjthschedulingpoint,whichisgivenby

iatthe∆cSi

j

∑

Ck

ijTk

Si

j

(3)

τkhepi

Notethat∆cijispositive(thusviolatesinequality(2))forallschedul-ingpointsofτtimewhichshouldithatisnotschedulable.ItindicatestheamountofbecutofffromsomewhereintheexecutiontimeofthetasksinordertomeettheinequalityatStimeofanytasksij.Thiscanbereal-izedbyreducingtheexecutioninhepi.There-fore,foreach∆cij,wecomputetheamountoftime,denotedbydijk,whichshouldbecutofffromtheexecutiontimeofτgivenby

khepi,d∆ijkcij

S

ij

(4)Tk

Inequation(4),thedenominator,whichisthenumberofinvoca-tionsofτkduringtheintervalofSiwithTj,increasesasTkdecreases.

Therefore,dijkdecreasesk.Thisleadsustothefollowingtheorem.

Theorem1ForataskτkthatminimizesTithatisnotschedulable,dijkisminimumatsuchk.

ByTheorem1,weselectataskhavingthehighestpriority(thushavingthelowestperiod),whichhasminimumvalueofdijk,asthecandidateforexecutiontimereduction.Letthetasktobedenotedbyτkˆ.Weminimizedˆoverj,thusobtainminjdisschedulableifthereijexistsk

aschedulingpointthatijkˆ,becauseτisatisfiesin-equality(2).Thisprocessiscarriedoutforalltaskswhichmisstheirdeadlines.Then,wemaximizeminjdijkˆoveritoobtaintheminimumrequiredtimebywhichtheexecutiontimeofτtasksschedulable.Becausekˆmustbereducedinordertomakeallthetimetobetakenofffromτmaxkˆisboundedbymrekˆ,wetaketheminimumbetweeniminjdijkˆandmreˆ.Foranarbitrarytaskτk,theamountoftimethatistobecutoffk

fromCkisgivenby

Dk

minmaximinj

dijkmrek

(5)

IfmretheexecutionkistakenasDtimeofk,meaningthatitisnotsufficienttoreduceτkinordertomakethetasksetfeasible,weiteratetheabovestepswiththetaskhavingthenexthighestpriorityuntilthetasksetbecomesfeasible.Theaboveprocessisillustratedinthefollowingexample.

Example2ConsiderΠ2inExample1.Fromequation(1),wecanfindschedulingpointsforeachtask,whichyields

S2

T2

S3

T2T3

S4

T2T32T23T2T4

Itcanbeshownthatτwith2isschedulablewhereasτhelpofthefollowingtable,3andτwhich4donot.ThuswecomputeD2yields

D2

minmaxminj

d3j2minj

d4j2mre2

minmax0537mre2min37mre237

ifmre2islargerthanorequalto37.

τ3∆∆cc312d22τ14

∆∆c324117d3120d1∆cc4216d322175d31317d4∆19d4128d32316d41417∆c3c4411d4229d41345

17d432d44235d423d4339d42416434452

473

d44355d19453

855

d44411454

17

3.4AnalysisofaSystemwithMultipleModes

Whenwehaveoneormoretasksets(modes),theanalysisbecomescomplicatedbecausereducingCkbytheamountofDkwhichisob-tainedconsideringonlyonemode,affectsthefeasibilityofothermodestowhichτmodeisnotguaranteedkbelongs.Thatis,theoptimalityofDacrossmultiplemodes.Toobtainkinoneanop-timalsolution(asolutionwithminimumcost)toagiveninstanceoftheCTAproblem,itcanbeshownthatweshouldsearchallthepossiblepathsoftheprobleminstanceintheworstcase.

Toillustratethemeaningofthepath,considermodesΠΠExample1,whichisrepeatedinFigure2.Ifwe2,Πcon-3,andsideronly4inΠ2,theminimalcostisobtainedwhenwecomputese-quentiallyD2D3D4untilΠ2becomesfeasible.However,thesituationisquitedifferentwhenweconsiderallthreemodesto-gether.ReducingC2isnotthebestchoiceforΠbenefittoΠ4(seeTheorem1).Furthermore,itbringsaboutno3becauseΠ3doesnot

ΠΠ2τ2ττ4

Π3ττ5

4

τ11

ττ32

τ33

DD2ΠΠ2333

D175DD1Π306D1Π4132Π227D1Π4211Π428.D2Π237

..

Figure2:PathsofaninstanceofCTAproblem.

containτ2.τthree3maybeoneofthecandidatesbecausereducingCaffectsallmodes.Asaconsequence,alotofalternativesexist3inordertomakeallthreemodesfeasible.ThreeofthemareshowninFigure2.Considerthefirstone.ForΠisreducedby3.7,itbecomesfeasible2,iftheexecutiontimeofτ2(seeExample2)ifmreisassumedtobelargerthanorequalto3.7.Thus,D2inamodeΠ2computed2,denotedbyDstillinfeasible.2NowΠ2,weis3.7.trytoBecausereducetheΠ3doesnotcontainτ2,itisexecutiontimeofτble.While1.ForΠΠ3,D1Π306isrequiredtomakeitfeasi-4containsbothτ1andτ2,itisstillinfeasiblemeaningthatDneeded2toΠmake2D1ΠΠ3isnotandsufficient.completesFinally,apath.D1Thus,Π4the1solu-3istiongivenbythis4feasiblepathisfτexecutiontimeofτreduced1by11.99andfτ2that3of7.τThatis,iftheallthreemodes1isareguaranteedtobefeasible.2isreducedby3.7,thenSimilarly,wecantryotherpathsandcomputethecost.Unfortunately,how-ever,thenumberofpathsexponentiallygrowswiththenumberDofmodesandthenumberoftasksineachmode.Furthermore,isnotconstantbutdependsonthepreviousvaluesinthesameipath.ΠjIntheexampleshowninFigure2,D2Π2.7inthefirsttwopaths,respectively.Consequently,2hasitsvaluesthe3.7optimalandsolutionofaninstanceoftheCTAproblemisveryunlikelytobeobtainedefficiently.

Thus,weproposeaheuristicalgorithm,whichisoutlinedinFigure3.Beforeweexplainthealgorithmindetail,weintroducenotationsweuseintheexplanation.

imtheidenotesexampletheinsetFigureofinfeasible2,immodestowhichτibelongs.In2Π2Π4.

DimaxdenotesthemaximumDioverallmodesinimi,thatis,DimaxmaxΠjimiDiΠj

reduced.

Tspecifiesthesetoftaskswhoseexecutiontimeisnotyet

hpτidenotesthesetoftaskswithpriorityhigherthanthatofi.

ρij,whereij,specifiestheexpectednumberofinvoca-tionsofτjrelativetoτi.Considerρ42inExample2.TheschedulingT2Tpointsofτ4exhibitedbyτ2andτ4consistof223T2T4.The1,2,3,4numberrespectivelyofinvocationswhileofthatτ2ateachschedulingpointsareofτ4is

always1(seeinequality(2)).Thus,ρ42112131415

T2.For

arbitraryτiandτji

Ti1

j,itcanbeshownthatρi

j

j

2

Thecoreoftheheuristicistorepeattheprocessofassigningaweighttoeachtaskandreducingtheexecutiontimeofataskhavingthehighestweight.NotethatthecomplexityoftheCTAproblemstemsfromthefactthattwofactorsshouldbetakenintoaccountintheselectionofatasktoreduceitsexecutiontime:itspriority(recallTheorem1)andthenumberofmodesincludingthetask.Thus,theweightisassignedbycombiningtwofactorstogether

AlgorithmHeuristicCTAsolvebegin

L1:ConstructasetofmodesΠ;

L2:ReduceΠbyremovingΠiΠjΠjΠij;L3:ReduceΠbyremovingfeasiblemodes;L4:forα0010instepsizeof01doL5:ΠΠTΠiΠΠi;L6:whileΠφdo

L7:ComputewiforeachtaskinT;

L8:Reducetheexecutiontimeofτi,whichhasthehighestweight,byDimax;

L9:RemoveafeasiblemodefromΠ;L10:TTτi;L11:enddo

L12:Computeacost∑τiτfτiand

updatemincostmincostmincost;

L13:InitializeCiandmreiforalltaskstoitsoriginalvalue;L14:enddo

L15:

Returnmincostandfτiτiτ;end

Figure3:Pseudocodeoftheheuristicalgorithm.

suchthatitreflectsasaccuratelyaspossibletherelativeimportanceinmakingallmodesfeasible.Theweightofτi,denotedbywi,isgivenby

∑

τT

ρi

j

1

hpjhpi

wi

αβ

imifhpi

T

φ

iT

Π

iα

imβ

otherwise

Π

i(6)

whereαandβareconstantweightingfactors.Thefirsttermistheinverseoftheaverageofρofrelativeeffect,whichisnormalizedij.Thatis,itreflectstheamountwithrespecttoataskofthehighestpriority,obtainedwhenthesameamountoftheexecutiontimeisreducedfromeachtask.Intheexampleofτ3inFigure2,itcomputestoyield47meaningthatreducingtheexecutiontimeofτ3bringsaboutroughly4orτ7effectscomparedtoreducingthesameamountfromτinfeasiblemodes1which2.Thesecondtermregardsthenumberofareaffectedwhentheexecutiontimeofτisreduced.Itisnotedthattheeffectofreducingtheexecutiontimeiofataskincreasesasthenumberofinfeasiblemodesincludingitincreases.

Thealgorithmworksasfollows.First,wereducetheproblemsizebyremovingmodesthataresubsetsofsomeothermodes(L2).Thisisbasedonthefollowingtheorem.TheproofcanbefoundintheAppendix.

Theorem2IfΠiisasubsetofafeasibletasksetΠj,thenΠalsofeasible.

iis

Theproblemsizeisfurtherreducedbyremovingalreadyfeasi-blemodes(L3).Foreachtaskinvolvedinoneormoreinfeasiblemodes,wecomputeaweightfollowingtheequation(6)(L7).Theexecutiontimeofτ(L8).ThismaymakeihavingthehighestweightisreducedbyDsomeofmodesfeasibleandthosemodesimaxareremoved(L9).τiisalsoremovedfromthefutureconsideration(L10).Theprocessisrepeateduntilallmodesaremadefeasible(L6).Thecostobtainedbytheheuristicdependsonthevaluesofαandβ,whichcontroltherelativeimportanceoftwofactorsinequa-tion(6).Unfortunately,however,extensiveexperimentsrevealthatthevaluesofαandβ,whichyieldtheminimumcost,dependsontheapplication.Inourheuristic,βissetto1αandwerepeattheprocessforarangeofα(L4)andselectthebestone.

Example3ConsiderΠinExample1.mreiisassumedtobe70%ofCiforalltasks.Π2,Π3,andΠ4remainafterthenumberof

modesarereduced(L2andL3)asshowninFigure2.Forexampleofα05,wecomputeaweightforeachtask:w1083w2067w3079w4038w5042.BecauseτwereduceC1hasthehighestweight,feasible.WeremoveΠ1byD1max280T,.respectively.ThismakesΠWe3computeweightsforthe3andτremaining1fromΠandtasks:w2100w3083w4050.ReducingC2byDmainingmodesfeasibleandcompletes2themaxprocess.

367makesthere-4ExtensionstoPerformanceAnalysis

Inthissection,wepresentextensionstoperformanceanalysistoaccommodatesoftreal-timetasks.Duetospacelimitations,wein-formallyshowthebasicideasinsteadoffulldescription.Whileadeadlinemissinhardreal-timetasksleadstoasystemmalfunctionoracatastrophe,thatinsoftreal-timetasksisgenerallyregardedasaperformancedegradation.Forexample,avideoapplicationhastimingrequirementswhichariseduetoaneedforsmoothdis-playandasynchronizationwithaudio.Unlikehardreal-timetasks,tardyresultsonlydecreasethequalityofvideoratherthanleadtoamalfunction.Thus,foreachsoftreal-timetask,QoSrequirementQoSτi3isdefinedaswellasitsperiod(Ti)andsoftdeadline(Dtheexecutiontime,weassumethateachsoftreal-timei).RegardingtaskisassociatedwitharandomvariableXianditsprobabilityden-sityfunction(PDF),denotedbypbecausesoftreal-timetaskssuchXasixmultimedia,insteadofapplicationsWCET.Thisusu-isallyhavehighlyvariableexecutiontimesduetothedifferenceintheamountsofinputdatatobeprocessedateachmoment,datadependentexecution,andsoon[16].Althoughacharacterizationofdistributionforagivenapplicationisinitselfadifficultwork,weassumethatitisgiventhroughvariousmethodssuchasstaticanalysis,profiling,ormeasurement.Notethatthemodeldescribedaboveismoregeneralthantheoneintheprevioussectioninthatitcanalsomodelahardreal-timetaskbyassuming1forQoSre-quirementandDiracdeltafunctionwithcenterlocatedatWCETandwithheightof1forPDF.

Theperformanceanalysismethodpresentedintheprevioussec-tionbecomesrathercomplicatedwhenbothhardreal-timeandsoftreal-timetasksco-existbecauseofastatisticalcharacterizationofsoftreal-timetasks.Specifically,theresultofthesummationinthelefthandsideofinequality(2)isnotconstantbutanewrandomvariable.Thus,toanalyzeaschedulabilitywecomputeaPDFofthenewrandomvariable,whichisaconvolutionofPDFsofcorre-spondingrandomvariablessummedup4[17].

Weillustratehowthestepsintheanalysisinsection3ismodi-fiedwhensoftreal-timetasksareinvolvedusinganexample.Con-sideranexampleofsoftreal-timetasksetasshowninTable2andPDFofeachtaskasshowninFigure4(a).Weassumethatpri-oritiesareassignedratemonotonically.ItcanbeshownthatQoSrequirementsofbothτtheanalysisateachscheduling1andτ2aresatisfied.Forτpoint:10,16,20,and3weperform25(seeequa-tion(1)).Asanexampleat25,thePDFassociatedwiththelefthandsideofinequality(2)resultsfromtheconvolutionof6PDFs;pX1pX1ofpconvolution.X1pX2pXThe2pprobabilityX3.Figure4(b)showsgraphicallytheresultthattheoverallcompu-tationalrequirementsarelessthanorequalto25(theprobabilitythatthedeadlineat25issatisfied)isthesumofprobabilitiesbelow25atPDF,whichyields72%.Similarlyforschedulingpointsat10,16,and20,theprobabilitycomputesto0.4%,33%,and35%,respectively.

3

WedefineQoSτiastheprobabilitythatanarbitrarilychoseninstanceofτiwillmeetitsdeadline(Di).4

IfYisasumofstatisticallyindependentrandomvariablesX1andX2(YXXisaconvolutionofPDFsofX12),itsPDF1andX2.Thatis,pYy∑∞x∞pX1y

xpX2x

pX1y

pX2y.

0.60.70.70.20.20.20.10.10.22343465710pX1(x)pX2(x)pX3(x)(a)0.2030.1100.1170.0010.0150.0470.007171819202122232425262728293031(b)Figure4:(a)PDFofeachtaskand(b)Resultofconvolutionattime25.Table2:Anexampleofsoftreal-timetasksetTDQoSτ101090%τ1161680%τ23252580%BecauseQoSrequirement(80%)isnotsatisfiedatanyschedul-ingpoints,wecompute∆cij(∆c3byjinthisexample)ateachschedul-ingpoint.Itisdefined∆cijyminSij(7)whereyministheminimumofysatisfyingProbYyQoSτYissumofrandomvariablesinthelefthandsideofinequalityi.(2)atSthisformulationij.Intheexample,yweassumethatminthe26executionand∆c3time4of1.eachNotetaskthatcaninbereduceduniformallyalongitsPDF.AsanexampleofpFigure4(a),optimizeportionsbyreducing1.ThistheofacorrespondsexecutiontasknotintotimetheaconditionalkindofτX1xinof1byoptimization1meansshiftingpX1xleftpathofthewhichtasktherebyreducingtheexecutiontimeuniformallyatallcases.Theremaininganalysissteps(equation(4),(5)andstepsinsubsection3.4)arethesameasthoseoftheprevioussection.

5Experiments

Wehaveimplementedourheuristicalgorithmaswellasanexhaus-tivesearchalgorithm,whichsearchesallthepossiblepathsasout-linedinsubsection3.4withproperpruning.Anexamplemulti-modesystemisconstructedbasedoncontinuousmedia(CM)ap-plications[8],whichincludetwoaudiotasks(PCMandLPC)and

twovideotasks(v7.5fpsandv15fps,whichdifferinframerates),and4DECT(DigitalEnhancedCordlessTelephone)pro-tocoltasks(RV,SLI,ISR2.1,ISR2.2)[18].Weassumethatprotocoltasksarealwayspresentinthesystem.Audiotasksareassumedtobereconfigurablemeaningthatitisnotallowedfortwotaskstobepresentsimultaneouslyinthesystem.Videotasksareassumedsimilarly.Consequently,thereare9modesbasedonthecombinationofCMapplications.Becausethestatisticsoftheactualexecutiontimesofthetasksarenotavailable,weassumethatCMapplicationsaswellastheprotocoltasksbehaveashardreal-timetasks.Foralltasks,weassumethatmre1294.1(fRV1400,fPCM753,iis70%ofCfLPC1023i.Thecostof4,fv15fps554)isobtainedwithheuristicalgorithmin2.1s(onUltra1),whichisonlyslightlylargerthantheminimumcostof1280.2(fRV1400,fPCM614,fLPC10234,fv15fps554)obtainedin6.5h.

Tofurtherevaluatetheheuristicalgorithm,webuild17syn-theticbenchmarks(themostsimplestonewith3tasksand3modesandthemostcomplexonewith17tasksand128modes)andper-formtheexperiment.Theresultsrevealthatthecostobtainedwiththeheuristicisonlylargerthantheminimumcost,whichiseitherobtainedbyexhaustivesearchorbysimulatedannealing5,by6.6%ontheaverage.Consequently,inviewofaccuracyandspeed,theproposedheuristicalgorithmseemstobeappropriateinsystem-leveldesignasshowninFigure1,wherealotofiterativeprocessesmayberequiredtoreachthefinalimplementation.

6Conclusion

Westudyaschedulability-drivenperformanceanalysismethodforamultimodesystem,whichcanchangeitsmodebyreconfigura-tion.Whilemostperformanceanalysismethodsonlytestafeasi-bilityofeachtaskorasystem,ourmethodgoesfurtherbylocat-inghotspotofasystemtowhichdesigneffortsshouldbedevotedtherebyhelpingthedesignertochooseamongalternativedesignsorarchitectures.Italsosavesdesigncostbyhelpingdesignertoavoidunnecessaryoptimizationoftaskswhichhavenoeffectorpotentiallylittleeffectontheoverallsystemperformance.Wefor-mulatetheanalysisproblemintotheCTAproblemandshowthatitisveryunlikelytobesolvedefficiently.TheextensionstotheCTAproblemispresentedtoaccommodateprobabilisticbehaviorexhibitedbysoftreal-timetasks.Wepresentaheuristicalgorithm,whichisaccurateandfastenoughtobeusediniterativeprocessesinsystem-levelanalysisanddesign.Asfuturework,weplantoapplytheproposedmethodologytorealindustrialexample.

Appendix

ProofofTheorem2Foranytaskτscheduling

pointsineachtasksetsatisfies

kΠi

Πj,itsSkΠi

SkΠj

(8)

whereSschedulablekΠiisainsetΠofschedulingpointsofτkinΠonei.Becauseτkisj,itsatisfiesinequality(2)atormoreschedulingpointstSschedulingpointsarealsokΠinj.STherearetwocases.First,ifthosewhenkΠiτ,thenτkisalsoschedulableinΠi.ConsiderthesecondcaseoneormoreschedulingpointstkinΠSjsatisfiesinequality(2)atsumethattkΠjbuttSkΠi.As-t1andt3isconsecutiveelementsofSkΠiandthatt1,t2,andcomputational3isconsecutiveelementsofSdemandsontheprocessorkΠj.(leftLethandAbesidethecumulativeofinequal-ity(2))bytasksinΠjΠiatt2andBbethosebytasksinΠFollowingshowsthecase.

jΠi.ΠΠtiτ1tjk

AB1B

t3

A

Bt2t3

BdoesnotchangeattataskinΠ3becauset2issomeintegermultipleofperiodofjΠi.Notethatinthelefthandsideofinequality(2),

thenumberofinvocationsofτj(t

T)attwoconsecutiveschedul-ingpoints,tdiffersonlyiftj

iandtj,iissomeintegermultipleofTthenthat

j.ItfollowsBt2At3(9)

5

Wehavealsoimplementedasimulatedannealing-basedheuristictoobtainapos-siblynear-optimalresultsforexamplesforwhichwecannotobtainthecostsinrea-sonabletimebyexhaustivesearch.

becauset2t3.Thus,τkinτΠisatisfiesinequality(2)attschedulable.Becauseτ3andiskkΠiisschedulableinbothcase,Πisfeasible.

iReferences

[1]J.Mitola,“Thesoftwareradioarchitecture,”IEEECommunicationsMagizine,

pp.26–38,May1995.

[2]W.Tuttlebee,“Theimpactofsoftwareradio,”inProc.SoftwareRadioWorkshop,

May1997.

[3]C.Locke,“Softwarearchitectureforhardreal-timeapplications:cyclicexec-utivesvs.fixedpriorityexecutives,”TheJournalofReal-TimeSystems,vol.4,pp.37–53,Mar.1992.

[4]H.Gomaa,SoftwareDesignMethodsforConcurrentandReal-TimeSystems.

Reading,MA:Addison-WesleyPublishingCompany,Inc.,1993.

[5]R.GerberandS.Hong,“Semantics-basedcompilertransformationsforen-hancedschedulability,”inProc.IEEEReal-TimeSystemsSymposium,Dec.1993.

[6]G.AroraandD.Stewart,“AFTER:ACASEtooltoassistinfine-tuningofem-beddedreal-timesystems,”inProc.IEEEReal-TimeSystemsSymposium,Dec.1996.

[7]P.PedroandA.Burns,“Schedulabilityanalysisformodechangesinflexible

real-timesystems,”inProc.EuromicroWorkshoponReal-TimeSystems,pp.17–19,June1998.

[8]A.KalavadeandP.Mogh´e,“Atoolforperformanceestimationofnetworked

embeddedend-systems,”inProc.DesignAutomat.Conf.,pp.257–262,June1998.

[9]T.Zhou,X.Hu,andE.Sha,“Aprobabilisticperformancemetricforreal-time

systemdesign.”toappearinProc.Int’lWorkshoponHardware/SoftwareCo-Design,May1999.

[10]C.L.LiuandJ.W.Layland,“Schedulingalgorithmsformultiprogrammingina

hardrealtimeenvironment,”J.ACM,vol.20,pp.46–61,Jan.1973.

[11]A.AtlasandA.Bestavros,“Statisticalratemonotonicscheduling,”inProc.

IEEEReal-TimeSystemsSymposium,pp.123–132,Dec.1998.

[12]D.Katcher,H.Arakawa,andJ.Strosnider,“Engineeringandanalysisoffixed

priorityschedulers,”IEEETrans.onSoftwareEng.,vol.19,pp.920–934,Sept.1993.

[13]L.Sha,R.Rajkumar,andJ.P.Lehoczky,“Priorityinheritanceprotocols:An

approachtoreal-timesynchronization,”IEEETrans.onComputers,vol.39,pp.1175–1185,Sept.1990.

[14]Y.ShinandK.Choi,“Enforcingschedulabilityofmulti-tasksystemsby

hardware-softwarecodesign,”inProc.Int’lWorkshoponHardware/SoftwareCo-Design,pp.3–7,Mar.1997.

[15]J.Lehoczky,L.Sha,andY.Ding,“Theratemonotonicschedulingalgorithm:

Exactcharacterizationandaveragecasebehavior,”inProc.IEEEReal-TimeSys-temsSymposium,pp.166–171,Dec.1989.

[16]L.AbeniandG.Buttazzo,“Integratingmultimediaapplicationsinhardreal-time

systems,”inProc.IEEEReal-TimeSystemsSymposium,pp.4–13,Dec.1998.[17]T.Tia,Z.Deng,M.Shankar,M.Storch,J.Sun,L.Wu,andJ.Liu,“Probabilistic

performanceguaranteeforreal-timetaskswithvaryingcomputationtimes,”inProc.IEEEReal-TimeTechnologyandApplicationsSymposium,pp.164–173,May1995.

[18]F.Slomka,J.Zant,andL.Lambert,“Schedulabilityanalysisofheterogeneous

systemsforperformancemessagesequencechart,”inProc.Int’lWorkshoponHardware/SoftwareCo-Design,pp.91–95,Mar.1998.