About / Advertise
Ny typ av verktyg för realtidsprogrammering beräknar exakt hur lång tid en uppgift tar
En ny typ av programverktyg för att räkna ut körtider i realtidssystem finns i forskarnas labb. I stället för provkörningar görs en analys av själva programkoden.
En ny typ av programverktyg för att räkna ut körtider i realtidssystem finns i forskarnas labb. I stället för provkörningar görs en analys av själva programkoden.
| Hjälper trimma tiderna i programmet Tidsanalysen svarar på frågan hur lång tid programmet tar att köra i värsta fall. Det första problemet är att räkna ut hur många cykler en instruktion stjäl. I processorer som 8051, AVR och Pic, är det sedan bara att summera cyklerna. Processorer som Arm, V850E och C5400 kör instruktioner parallellt i pipelines. Men de är ändå möjliga att analysera precist. Det visar Jakob Engbloms forskning. Svåraste utmaningen är dynamiska pipelines, som finns i Pentium- och PowerPC-processorer. De kan på vinst och förlust i förskott utföra instruktioner som kanske aldrig blir aktuella. De kan kasta om ordningen mellan instruktioner. Och de har flera nivåer av cache. Problem nummer två är flödesanalys -- vilka vägar kan programkörningen ta? Denna del av analysen beror av programspråket och är oberoende av processor. Problemet är teoretiskt olösligt, men i praktiken kan man komma långt, särskilt om programmeraren disciplinerar sig och skriver tydliga program, exempelvis använder loopar som uttryckligen anger antalet varv. Disciplineringen är en del av poängen med verktyget, på liknande sätt som programverktyget Lint varnar för dålig programmeringsstil varnar ett tidsverktyg för oklara tidsegenskaper. Tidsverktyget kan också hitta flaskhalsar. Tidsanalysen ger den värsta körtiden, som sedan kan användas som indata till en schemaläggningsalgoritm, om parallella program ska köras i systemet. Dagens programmerare använder provkörningar och inte tidsanalys. I strängt tidskritiska sammanhang, som rymd-, flyg-, medicin- och fordonsteknik, går man runt problemet genom att använda enkla processorer och programspråk med begränsningar. |
Frågan som behöver svar är: hur lång tid tar det innan ett givet program kört klart? Vilken är den längsta tänkbara körtiden, worst case excecution time (WCET)?
Dagens programmerare söker svar genom provkörningar.
- Ofta brukar jag tända en lysdiod när programmet startar och släcka när det är klart. Och så mäter jag med stoppur, berättar Jan Lindblad, systemingenjör på OSE Systems.
Men provkörningar kan aldrig ge ett säkert svar. Det kan bara en formell analys av programkoden göra. Det kallas statisk WCET-analys. Programmet kompileras, men det körs aldrig.
Grunden är enkel, processormanualen ger cykeltider för enskilda instruktioner. Men det blir snabbt svårare. Vilka vägar kan programmet ta? Och hur hanterar man processorer med cache och pipelines?
- Tekniken är inte allmänt känd. När jag berättar om mitt tidsmätningsverktyg tror folk först att jag pratar om profilering, säger Jakob Engblom, Uppsaladoktor i körtidsanalys.
Om körtidsanalys görs idag, sker den för hand, kanske med hjälp av Excel.
- Det är trivialt att göra en överskattning och anta att loopen går en miljard varv. Utmaningen är
att komma så nära den verkliga tiden som möjligt, säger Jakob Engblom.
Jakob Engblom vill göra körtidsanalys tillgänglig som ett standardverktyg, vid sidan av kompilatorer, avlusare och profilerare.
50 cykler eller en
Moderna processorer gör analysen besvärlig. Cache betyder att en minnesaccess kan ta 50 cykler eller en enda, beroende på vad som finns i cacheminnet.
- Det är inte alltid ens tillverkaren vet hur hårdvaran arbetar, säger Jakob Engblom.
Analysen kräver en detaljerad beskrivning av processorn. Jakob Engblom och hans kollegor på Uppsala universitet har tagit fram modeller för Arm9 och Nec V850E.
Flernivåcache och processorer som kastar om ordningen mellan instruktioner, är närmast omöjliga utmaningar. Det enklaste är ofta att stänga av cache och andra finesser. Eller att analysera som om de inte fanns. Men då går prestandavinsten förlorad.
- Jag anser att sådana processorer inte har i realtidssystem att göra. Det är att ta sig vatten över huvudet, säger Jakob Engblom.
Men Jakob Engbloms tyska forskarkollegor bygger analysatorer till Coldfire och PowerPC.
- Jakob ger upp före oss, ler Reinhard Wilhelm, professor på Saarland-universitetet i Saarbrücken.
Det är flygplanstillverkaren Airbus som ska använda MPC755 i trevåningsplanet A380. Airbus gamla arbetshäst M68020 har tjänat ut.
Vatten över huvudet
Airbus fuskar en smula. C-koden automatgenereras ur ett grafiskt programmeringsverktyg. Det gör analysen enklare.
Tillverkare av kompilatorer, DSP:er och RTOS borde alla vara intresserade av att kunna erbjuda sina kunder tidsanalys, tror Jakob Engblom. Hans egen arbetsgivare IAR gör kompilatorer.
- Vi utvärderar tekniken, men inget är lanserat. Tekniskt skulle vi kunna göra ett fungerande verktyg idag. Egentligen handlar det mest om att lägga energin på det, säger Jakob Engblom.
- Ju viktigare det är att man är säker, desto mer konkurrenskraftig blir den här typen av verktyg, säger Jan Lindblad på OSE.
- Många av våra kunder frågar efter tidsuppskattningar. En teoretiskt maximal tid vore bättre än att bara berätta hur lång tid det tar när man mäter.
- Om vi kan ange bättre gränser är det en konkurrensfördel, säger Jan Lindblad.
OSE lät en exjobbare körtidsanalysera företagets operativsystem.
- Vi fick inte fram någon användbar siffra till slut, men i princip fungerade det, berättar Jan Lindblad.
Exjobbaren använde forskarnas prototypverktyg.
- Det är inte solklart att tidsverktyget kan bli så lättanvänt att det kan användas brett. Men det kommer alltid att finnas nischanvändare inom rymd- och flygbranschen, säger Jakob Engblom.
Jan Tångring
