Filter
Top Products
www.ti.com
3 ms 3 ms 3 ms 3 ms
A
B
Idle
4.4.2ExecutionTimeModel
ExecutionTime
Figure4-1.ExecutionTimelineforTwoPeriodicTasks
Inthiscase,bothtaskAandBmeettheirdeadlinesandwehavemorethan18%(1msevery6ms)ofthe
CPUidle.
SupposewenowincreasetheamountofprocessingthattaskBmustperformveryslightly,sayto
1.0000001msevery3ms.NoticethattaskBwillmissitsfirstdeadlinebecausetaskAconsumes2msof
theavailable3msoftaskB'speriod.Thisleavesonly1msforBbutBneedsjustabitmorethan1msto
completeitswork.IfwemaketaskBhigherprioritythantaskA,taskAwillmissitsdeadlinelinebecause
taskBwillconsumemorethan1msoftaskA's2msperiod.
Inthisexample,wehaveasystemthathasover18%oftheCPUMIPSunusedbutwecannotcomplete
bothtaskAandBwithintheirreal-timedeadlines.Moreover,thesituationgetsworseifyouaddmore
taskstothesystem.LiuandLaylandprovedthatintheworstcaseyoumayhaveasystemthatisidle
slightlymorethan30%ofthetimethatstillcan'tmeetitsreal-timedeadlines!
Thegoodnewsisthatthisworst-casesituationdoesnotoccurveryofteninpractice.Thebadnewsisthat
wecan'trelyonthisnothappeninginthegeneralsituation.Itisrelativelyeasytodetermineifaparticular
tasksetwillmeetitsreal-timedeadlinesiftheperiodofeachtaskisknownanditsCPUrequirements
duringthisperiodarealsoknown.Itisimportanttorealize,however,thatthisdeterminationisbasedona
mathematicalmodelofthesoftwareand,aswithanymodel,itmaynotcorrespond100%withreality.
Moreover,themodelisdependentoneachcomponentaccuratelycharacterizingitsperformance;ifa
componentunderestimatesitsCPUrequirementsbyeven1clockcycle,itispossibleforthesystemto
fail.
Finally,designingwithworst-caseCPUrequirementsoftenpreventsonefromcreatingviablecombinations
ofcomponents.IftheaveragecaseCPUrequirementforacomponentdifferssignificantlyfromitsworst
case,considerableCPUbandwidthmaybewasted.
Inthissection,wedescribeasimpleexecutiontimemodelthatappliestoalleXpressDSP-compliant
algorithms.Thepurposeofthismodelistoenablesystemintegratorstoquicklyassesstheviabilityof
certainalgorithmcombinations,rationallycomparedifferentalgorithmimplementations,andenablethe
creationofautomaticdesigntoolsthatoptimizeCPUutilization.Whilefarfromperfect,themodel
describedbelowsignificantlyimprovesourabilitytointegratealgorithmsintoasystem.
Allalgorithmsmustbecharacterizedasperiodicexecutionofoneormorefunctions.Forexample,avoice
encodermaybeimplementedtooperateonaframeofdatathatrepresents22.5msofvoicedata.Inthis
case,theperiodis22.5ms(becauseevery22.5msanewframeofdataisavailableforprocessing)and
thedeadlineisalso22.5ms(becausethereisnoneedtocompletetheprocessingaheadofthetimethat
thenextframeofdataisavailable).
Rule24
Allalgorithmsmustcharacterizethetypicalperiodandworst-caseexecutiontimeforeachoperation.
AlgorithmPerformanceCharacterization 42SPRU352G–June2005–RevisedFebruary2007
SubmitDocumentationFeedback