Värsta tänkbara exekveringstid

Den värsta exekveringstiden ( WCET ) för en beräkningsuppgift är den maximala tid som uppgiften kan ta att köra på en specifik hårdvaruplattform .

Vad den används till

Worst case-exekveringstid används vanligtvis i tillförlitliga realtidssystem , där det är viktigt att förstå det värsta fallets timingbeteende för programvara för tillförlitlighet eller korrekt funktionellt beteende.

Som ett exempel kan ett datorsystem som kontrollerar beteendet hos en motor i ett fordon behöva svara på indata inom en viss tid. En komponent som utgör svarstiden är den tid som ägnas åt att exekvera programvaran – därför om programvarans värsta exekveringstid kan bestämmas, då kan konstruktören av systemet använda detta med andra tekniker som schemaläggningsanalys för att säkerställa att systemet svarar snabb nog.

Medan WCET potentiellt kan tillämpas på många realtidssystem, används i praktiken en försäkran om WCET främst av realtidssystem som är relaterade till hög tillförlitlighet eller säkerhet. Till exempel, i luftburen programvara krävs viss uppmärksamhet på programvaran enligt DO178C avsnitt 6.3.4. Den ökande användningen av mjukvara i fordonssystem driver också behovet av att använda WCET-analys av mjukvara.

I designen av vissa system används WCET ofta som en input till schemaläggningsanalys , även om en mycket vanligare användning av WCET i kritiska system är att säkerställa att de förtilldelade tidsbudgetarna i ett partitionsschemalagt system som ARINC 653 är inte kränkt.

Beräkning

Sedan de första dagarna av inbäddad datoranvändning har utvecklare av inbäddade mjukvaror antingen använt:

end-to-end-mätningar av kod, till exempel genom att sätta ett I/O-stift på enheten till högt i början av uppgiften och till lågt i slutet av uppgiften och använda en logisk analysator för att mäta den längsta pulsen bredd, eller genom att mäta i själva programvaran med hjälp av processorklockan eller antalet instruktioner.
manuella statiska analystekniker som att räkna assemblerinstruktioner för varje funktion, slinga etc. och sedan kombinera dem.

Båda dessa tekniker har begränsningar. Änd-to-end-mätningar lägger en stor börda på mjukvarutestning för att uppnå den längsta vägen; räkneinstruktioner är endast tillämpliga på enkel mjukvara och hårdvara. I båda fallen används ofta en marginal för fel för att ta hänsyn till oprövad kod, uppskattningar av hårdvaruprestanda eller misstag. En marginal på 20 % används ofta, även om det finns mycket lite motivering för denna siffra, förutom för historiskt förtroende ("det fungerade förra gången").

Eftersom mjukvara och hårdvara har ökat i komplexitet har de drivit på behovet av verktygsstöd. Komplexitet blir alltmer ett problem i både statisk analys och mätningar. Det är svårt att bedöma hur bred felmarginalen bör vara och hur väl testat mjukvarusystemet är. Systemsäkerhetsargument baserade på ett högvattenmärke som uppnåtts under testning används ofta, men blir svårare att motivera eftersom mjukvaran och hårdvaran blir mindre förutsägbara.

I framtiden är det troligt att ett krav på säkerhetskritiska system är att de analyseras med både statiska och mätbaserade metoder. ^{[ citat behövs ]}

Överväganden

Problemet med att hitta WCET genom analys är likvärdigt med stoppproblemet och är därför inte lösbart generellt. Lyckligtvis, för den typ av system som ingenjörer vanligtvis vill hitta WCET för, är programvaran vanligtvis välstrukturerad, kommer alltid att avslutas och är analyserbar.

De flesta metoder för att hitta en WCET innebär approximationer (vanligtvis en avrundning uppåt när det finns osäkerheter) och därför anses i praktiken den exakta WCET i sig ofta vara ouppnåelig. Istället ger olika tekniker för att hitta WCET uppskattningar för WCET. Dessa uppskattningar är vanligtvis pessimistiska, vilket innebär att den uppskattade WCET är känd för att vara högre än den verkliga WCET (vilket vanligtvis är vad som önskas). Mycket arbete med WCET-analys går ut på att minska pessimismen i analysen så att det uppskattade värdet är tillräckligt lågt för att vara värdefullt för systemdesignern.

WCET-analys hänvisar vanligtvis till exekveringstiden för en enda tråd, uppgift eller process. Men på modern hårdvara, särskilt multi-core, kommer andra uppgifter i systemet att påverka WCET för en given uppgift om de delar cache, minneslinjer och andra hårdvarufunktioner. Vidare bör uppgiftsschemaläggningshändelser såsom blockering eller att vara avbrott beaktas i WCET-analys om de kan inträffa i ett visst system. Därför är det viktigt att överväga det sammanhang i vilket WCET-analys tillämpas.

Automatiserade tillvägagångssätt

Det finns många automatiserade metoder för att beräkna WCET utöver de manuella teknikerna ovan. Dessa inkluderar:

analytiska tekniker för att förbättra testfall för att öka förtroendet för mätningar från slut till slut
statisk analys av programvaran (“statisk” betyder utan att köra programvaran).
kombinerade tillvägagångssätt, ofta kallade "hybrid" analys, är en kombination av mätningar och strukturanalys

Statisk analysteknik

Ett statiskt WCET-verktyg försöker uppskatta WCET genom att undersöka datorprogramvaran utan att köra det direkt på hårdvaran. Statiska analystekniker har dominerat forskningen inom området sedan slutet av 1980-talet, även om det i en industriell miljö var standardmetoder för mätning från slut till ände.

Statiska analysverktyg arbetar på en hög nivå för att bestämma strukturen för ett programs uppgift, och arbetar antingen på en källkod eller en demonterad binär körbar fil . De arbetar också på en låg nivå och använder tidsinformation om den verkliga hårdvaran som uppgiften kommer att utföras på, med alla dess specifika funktioner. Genom att kombinera dessa två typer av analyser försöker verktyget ge en övre gräns för den tid som krävs för att utföra en given uppgift på en given hårdvaruplattform.

processorns genomsnittliga fallprestanda : instruktions-/ datacacher , grenprediktion och instruktionspipelines , till exempel. Det är möjligt, men allt svårare, att fastställa snäva WCET-gränser om dessa moderna arkitektoniska egenskaper beaktas i den tidsmodell som används av analysen.

Certifieringsmyndigheter som European Aviation Safety Agency förlitar sig därför på modellvalideringssviter. ^{[ citat behövs ]}

Statisk analys har resulterat i bra resultat för enklare hårdvara, men en möjlig begränsning av statisk analys är att hårdvaran (speciellt CPU) har nått en komplexitet som är extremt svår att modellera. I synnerhet kan modelleringsprocessen introducera fel från flera källor: fel i chipdesign, brist på dokumentation, fel i dokumentation, fel i modellskapande; allt leder till fall där modellen förutsäger ett annat beteende än det som observeras på verklig hårdvara. Vanligtvis, där det inte är möjligt att exakt förutsäga ett beteende, används ett pessimistiskt resultat, vilket kan leda till att WCET-uppskattningen är mycket större än något som uppnåtts under körning.

Att få snäva statiska WCET-uppskattningar är särskilt svårt på flerkärniga processorer.

Det finns ett antal kommersiella och akademiska verktyg som implementerar olika former av statisk analys.

Mät- och hybridtekniker

Mätbaserade och hybridmetoder försöker vanligtvis mäta exekveringstiderna för korta kodsegment på den verkliga hårdvaran, som sedan kombineras i en analys på högre nivå. Verktygen tar hänsyn till programvarans struktur (t.ex. loopar, grenar) för att producera en uppskattning av WCET för det större programmet. Grunden är att det är svårt att testa den längsta vägen i komplex programvara, men det är lättare att testa den längsta vägen i många mindre komponenter av den. En worst case-effekt behöver bara ses en gång under testningen för att analysen ska kunna kombinera den med andra worst case-händelser i sin analys.

Vanligtvis kan de små sektionerna av programvaran mätas automatiskt med hjälp av tekniker som instrumentering (lägga till markörer i programvaran) eller med hårdvarustöd som avlusare och CPU-hårdvaruspårningsmoduler. Dessa markörer resulterar i ett spår av exekvering, som inkluderar både vägen som tagits genom programmet och tidpunkten då olika punkter exekveras. Spårningen analyseras sedan för att fastställa den maximala tiden som varje del av programmet någonsin har tagit att köra, vad den maximala observerade iterationstiden för varje slinga är och om det finns några delar av programvaran som är oprövade (kodtäckning ) .

Mätbaserad WCET-analys har resulterat i goda resultat för både enkel och komplex hårdvara, även om den liksom statisk analys kan drabbas av överdriven pessimism i situationer med flera kärnor, där effekten av en kärna på en annan är svår att definiera. En begränsning av mätningen är att den förlitar sig på att observera de värsta effekterna under testning (men inte nödvändigtvis samtidigt). Det kan vara svårt att avgöra om de värsta effekterna nödvändigtvis har testats.

Det finns ett antal kommersiella och akademiska verktyg som implementerar olika former av mätbaserad analys.

Forskning

De mest aktiva forskargrupperna finns i Sverige (Mälardalen, Linköping), Tyskland (Saarbrücken, Dortmund, Braunschweig), Frankrike (Toulouse, Saclay, Rennes), Österrike (Wien), Storbritannien (University of York och Rapita Systems Ltd), Italien ( Bologna), Spanien (Kantabrien, Valencia) och Schweiz (Zürich). Nyligen har ämnet timinganalys på kodnivå fått mer uppmärksamhet utanför Europa av forskargrupper i USA (North Carolina, Florida), Kanada, Australien, Bangladesh (MBI LAB och RDS), Saudiarabien-UQU(HISE) LAB) och Singapore.

WCET Tool Challenge

Den första internationella WCET Tool Challenge ägde rum under hösten 2006. Den arrangerades av Mälardalens högskola och sponsrades av ARTIST2 Network of Excellence on Embedded Systems Design. Syftet med utmaningen var att inspektera och jämföra olika tillvägagångssätt för att analysera den värsta avrättningstiden. Alla tillgängliga verktyg och prototyper som kan bestämma säkra övre gränser för WCET av uppgifter har deltagit. De slutliga resultaten presenterades i november 2006 vid ISOLA 2006 International Symposium i Paphos , Cypern.

En andra utmaning ägde rum 2008.

Se även

^ " Det värsta tänkbara exekveringstidsproblemet – översikt över metoder och undersökning av verktyg ", Wilhelm, Reinhard, et al., ACM Transactions on Embedded Computing Systems (TECS), Vol. 7, nr 3, 2008.
^ "Arkiverad kopia" (PDF) . Arkiverad från originalet (PDF) 2011-10-01 . Hämtad 2010-08-15 . {{ citera webben }} : CS1 underhåll: arkiverad kopia som titel ( länk )
^ "WCET Challenge 2008" . Arkiverad från originalet 2012-02-16 . Hämtad 2008-08-16 .

Artiklar och vitböcker

externa länkar

[1] " Det värsta tänkbara exekveringstidsproblemet – översikt över metoder och undersökning av verktyg ", Wilhelm, Reinhard, et al., ACM Transactions on Embedded Computing Systems (TECS), Vol. 7, nr 3, 2008.

[2] "Arkiverad kopia" (PDF) . Arkiverad från originalet (PDF) 2011-10-01 . Hämtad 2010-08-15 . {{ citera webben }} : CS1 underhåll: arkiverad kopia som titel ( länk )

[3] "WCET Challenge 2008" . Arkiverad från originalet 2012-02-16 . Hämtad 2008-08-16 .