Čas provedení nejhoršího případu - Worst-case execution time

Doba nejhoršího provedení ( WCET ) výpočetní úlohy je maximální doba, po kterou by mohla úloha trvat na konkrétní hardwarové platformě.

K čemu se používá

Doba provedení nejhoršího případu se obvykle používá ve spolehlivých systémech v reálném čase , kde je porozumění chování časování softwaru v nejhorším případě důležité pro spolehlivost nebo správné funkční chování.

Například počítačový systém, který řídí chování motoru ve vozidle, může potřebovat reagovat na vstupy ve specifickém čase. Jednou komponentou, která tvoří dobu odezvy, je čas strávený prováděním softwaru - pokud tedy lze určit dobu spuštění softwaru v nejhorším případě, může to návrhář systému použít s jinými technikami, jako je analýza plánovatelnosti, aby se zajistilo, že systém reaguje dostatečně rychle.

Zatímco WCET je potenciálně použitelný pro mnoho systémů v reálném čase, v praxi jistotu WCET používají hlavně systémy v reálném čase, které souvisejí s vysokou spolehlivostí nebo bezpečností. Například ve vzdušném softwaru vyžaduje určitá pozornost softwaru část 17.4.4 DO178B . Rostoucí využívání softwaru v automobilových systémech také vede k potřebě používat analýzu softwaru WCET.

Při návrhu některých systémů je WCET často používán jako vstup do analýzy plánovatelnosti , ačkoli mnohem běžnějším používáním WCET v kritických systémech je zajistit, aby předem přidělené rozpočty časování v systému naplánovaném na oddíly, jako je ARINC 653, byly neporušeno.

Výpočet

Od počátků integrovaných počítačů vývojáři vestavěného softwaru buď používali:

  • end-to-end měření kódu, například prováděné nastavením I/O pinu na zařízení na vysokou úroveň na začátku úlohy a na nízkou hodnotu na konci úlohy a pomocí logického analyzátoru k měření nejdelšího impulsu šířku nebo měřením v samotném softwaru pomocí hodin procesoru nebo počtu instrukcí.
  • techniky ruční statické analýzy, jako je počítání instrukcí assembleru pro každou funkci, smyčku atd. a jejich kombinace.

Obě tyto techniky mají omezení. End -to -end měření klade velkou zátěž na testování softwaru k dosažení nejdelší cesty; pokyny k počítání platí pouze pro jednoduchý software a hardware. V obou případech se často používá marže pro chyby, aby se zohlednil nevyzkoušený kód, aproximace výkonu hardwaru nebo chyby. Často se používá marže ve výši 20%, i když pro toto číslo je použito velmi malé ospravedlnění, s výjimkou historické jistoty („minule to fungovalo“).

Vzhledem k tomu, že se složitost softwaru a hardwaru zvýšila, vyvolaly potřebu podpory nástrojů. Složitost se stále více stává problémem jak ve statické analýze, tak v měření. Je těžké posoudit, jak široké by mělo být rozpětí chyb a jak dobře je softwarový systém testován. Argumenty bezpečnosti systému založené na značce vysoké vody dosažené během testování jsou široce používány, ale je stále obtížnější je zdůvodnit, protože software a hardware se stávají méně předvídatelnými.

V budoucnosti je pravděpodobné, že požadavek na systémy kritické z hlediska bezpečnosti je, aby byly analyzovány pomocí statických i měřicích přístupů.

Úvahy

Problém nalezení WCET analýzou je ekvivalentní problému zastavení, a proto není obecně řešitelný. Naštěstí pro systémy, pro které inženýři obvykle chtějí najít WCET, je software obvykle dobře strukturovaný, vždy skončí a je analyzovatelný.

Většina metod pro hledání WCET zahrnuje aproximace (obvykle zaokrouhlování směrem nahoru, pokud existují nejistoty), a proto je v praxi samotný přesný WCET často považován za nedosažitelný. Místo toho různé techniky pro hledání WCET vytvářejí odhady pro WCET. Tyto odhady jsou typicky pesimistické, což znamená, že je odhadováno, že odhadovaný WCET je vyšší než skutečný WCET (což je obvykle to, co je žádoucí). Velká část práce na analýze WCET spočívá ve snížení pesimismu v analýze, takže odhadovaná hodnota je dostatečně nízká, aby byla pro návrháře systému cenná.

Analýza WCET obvykle odkazuje na dobu provedení jednoho vlákna, úkolu nebo procesu. Na moderním hardwaru, zejména vícejádrovém, však budou mít jiné úkoly v systému vliv na WCET daného úkolu, pokud budou sdílet mezipaměť, paměťové linky a další hardwarové funkce. Události plánování úkolů, jako je blokování nebo přerušení, by měly být dále zohledněny v analýze WCET, pokud se mohou vyskytnout v konkrétním systému. Proto je důležité vzít v úvahu kontext, ve kterém je analýza WCET aplikována.

Automatizované přístupy

Existuje mnoho automatizovaných přístupů k výpočtu WCET nad rámec výše uvedených manuálních technik. Tyto zahrnují:

  • analytické techniky ke zlepšení testovacích případů za účelem zvýšení důvěryhodnosti v koncová měření
  • statická analýza softwaru („statický“ význam bez spuštění softwaru).
  • kombinované přístupy, často označované jako „hybridní“ analýza, což je kombinace měření a strukturální analýzy

Techniky statické analýzy

Statický nástroj WCET se pokusí odhadnout WCET prozkoumáním počítačového softwaru, aniž by jej spustil přímo na hardwaru. Techniky statické analýzy dominují výzkumu v této oblasti od konce 80. let, ačkoli v průmyslovém prostředí byly standardní praxí přístupy měření typu end-to-end.

Statické analytické nástroje pracují na vysoké úrovni, aby určily strukturu úkolu programu , a to buď na kousku zdrojového kódu, nebo rozebraném binárním spustitelném souboru . Pracují také na nízké úrovni a využívají informace o načasování skutečného hardwaru, na kterém bude úkol spuštěn, se všemi jeho specifickými funkcemi. Kombinací těchto dvou druhů analýzy se nástroj pokusí poskytnout horní hranici času potřebného k provedení daného úkolu na dané hardwarové platformě.

Statická analýza WCET je na nízké úrovni komplikována přítomností architektonických funkcí, které zlepšují průměrný výkon procesoru : například mezipaměti instrukcí/dat , předpověď větví a kanály instrukcí . Je možné, ale stále obtížnější, určit těsné hranice WCET, pokud jsou tyto moderní architektonické prvky zohledněny v časovacím modelu používaném analýzou.

Certifikační orgány, jako je Evropská agentura pro bezpečnost letectví , proto spoléhají na sady pro ověřování modelů.

Statická analýza přinesla dobré výsledky pro jednodušší hardware, avšak možným omezením statické analýzy je, že hardware (zejména CPU) dosáhl složitosti, kterou je extrémně těžké modelovat. Proces modelování může zejména zavést chyby z několika zdrojů: chyby v návrhu čipu, nedostatek dokumentace, chyby v dokumentaci, chyby při vytváření modelu; vše vede k případům, kdy model předpovídá jiné chování, než jaké bylo pozorováno na skutečném hardwaru. Typicky tam, kde není možné přesně předpovědět chování, se použije pesimistický výsledek, který může vést k tomu, že odhad WCET bude mnohem větší než cokoli dosaženého za běhu.

Získání těsného statického odhadu WCET je obzvláště obtížné u vícejádrových procesorů.

Existuje řada komerčních a akademických nástrojů, které implementují různé formy statické analýzy.

Měřicí a hybridní techniky

Přístupy založené na měření a hybridní přístupy se obvykle pokoušejí změřit doby provádění segmentů krátkého kódu na skutečném hardwaru, které jsou poté spojeny do analýzy na vyšší úrovni. Nástroje berou v úvahu strukturu softwaru (např. Smyčky, větve), aby vytvořily odhad WCET většího programu. Důvodem je, že je těžké testovat nejdelší cestu ve složitém softwaru, ale je snazší otestovat nejdelší cestu v mnoha menších komponentách. Účinek nejhoršího případu musí být během testování viděn pouze jednou, aby byla analýza schopna jej kombinovat s dalšími událostmi nejhoršího případu ve své analýze.

Malé části softwaru lze obvykle měřit automaticky pomocí technik, jako je přístrojové vybavení (přidání značek do softwaru) nebo pomocí hardwarové podpory, jako jsou debuggery, a modulů pro sledování hardwaru CPU. Tyto značky mají za následek stopu spuštění, která zahrnuje jak cestu provedenou programem, tak čas, kdy byly provedeny různé body. Trasování je poté analyzováno, aby se určil maximální čas, který kdy každá část programu potřebovala k provedení, jaká je maximální pozorovaná doba iterace každé smyčky a zda existují nějaké části softwaru, které nejsou testovány ( pokrytí kódu ).

Analýza WCET založená na měření přinesla dobré výsledky pro jednoduchý i složitý hardware, ačkoli jako statická analýza může trpět nadměrným pesimismem ve vícejádrových situacích, kde je těžké definovat dopad jednoho jádra na druhé. Omezením měření je, že se spoléhá na pozorování nejhorších účinků během testování (i když ne nutně současně). Může být těžké určit, zda byly nutně testovány účinky nejhorších případů.

Existuje řada komerčních a akademických nástrojů, které implementují různé formy analýzy založené na měření.

Výzkum

Nejaktivnější výzkumné skupiny jsou ve Švédsku (Mälardalen, Linköping), Německu (Saarbrücken, Dortmund, Braunschweig), Francii (Toulouse, Saclay, Rennes), Rakousku (Vídeň), Velké Británii (University of York a Rapita Systems Ltd), Itálii ( Bologna), Španělsko (Kantábrie, Valencie) a Švýcarsko (Curych). V poslední době téma analýzy časování na úrovni kódu nachází mimo Evropu větší pozornost výzkumných skupin v USA (Severní Karolína, Florida), Kanadě, Austrálii, Bangladéši (MBI LAB a RDS), Království Saúdské Arábie-UQU (HISE LAB) a Singapuru.

WCET Tool Challenge

První mezinárodní WCET Tool Challenge se uskutečnil na podzim roku 2006. Pořádala jej Univerzita v Mälardalenu a sponzorovala ji síť excelence ARTIST2 pro návrh integrovaných systémů. Cílem výzvy bylo zkontrolovat a porovnat různé přístupy při analýze doby provedení nejhoršího případu. Zúčastnily se všechny dostupné nástroje a prototypy schopné určit bezpečné horní hranice pro WCET úkolů. Konečné výsledky byly prezentovány v listopadu 2006 na mezinárodním sympoziu ISoLA 2006 v Paphosu na Kypru.

Druhá výzva proběhla v roce 2008.

Viz také

Reference

  1. ^ „ Problém doby provedení v nejhorším případě-přehled metod a průzkum nástrojů “, Wilhelm, Reinhard a kol., ACM Transactions on Embedded Computing Systems (TECS), sv. 7, č. 3, 2008.
  2. ^ "Archivovaná kopie" (PDF) . Archivováno z originálu (PDF) dne 2011-10-01 . Citováno 2010-08-15 .CS1 maint: archivovaná kopie jako název ( odkaz )
  3. ^ "Archivovaná kopie" . Archivováno od originálu dne 2012-02-16 . Citováno 2008-08-16 .CS1 maint: archivovaná kopie jako název ( odkaz )

Články a bílé knihy

externí odkazy