Témata semestrálních projektů

Typ studia:
Studijní program:
Katedra vedoucího:
Vedoucí:
Název tématu Vedoucí Typ Kapacita Katedra vedoucího
Kombinace time-triggered a event-triggered rozvrhování Ing. Ondřej Benedikt BM 1/1 13135

Popis
Vestavěné systémy reálného času většinou zahrnují time-triggered (TT) i event-triggered (ET) rozvrhování komunikace a vypočtů. Zohlednění TT i ET rozvrhování vede k lepším vlastnostem systému, ať už jde o poměr rozvrhovatelnosti, vyšší utilizace nebo propustnost, nižší latence atd. Cílem této práce je navrhnout, vyvinout a vyhodnotit algoritmus, který zahrnuje TT i ET rozvrhování. Námětem je upravit koncept zvaný rozvrhovací graf (schedule graph) navržený v [1] tak, aby byl použitelný v systémech s precedencemi a vyhrazenými zdroji a aby uvažoval již rozvržené TT úlohy. Když analýza rozvrhovacího grafu nalezne nekonzistenci, identifikuje zdroj konfliktu a předá tuto informaci algoritmu pro TT rozvrhování. Tento algoritmus pak přepočítá rozvrh s ohledem na nově odvozenou podmínku z analýzy rozvrhovacího grafu a tento proces bude iterativně opakován. Další možností by mohlo být začlenění TT rozvrhování přímo do rozvrhovacího grafu.

Studijní program
KyR LK EECS EEK EEM EK EI SIT OI KME OES BII IB BIO

Literatura
[1] Nasri, Mitra, and Bjorn B. Brandenburg. "An exact and sustainable analysis of non-preemptive scheduling." 2017 IEEE Real-Time Systems Symposium (RTSS). IEEE, 2017.

Minimalizace hyperperiody a její dopad na rozvržitelnost Ing. Ondřej Benedikt BM 0/1 13135

Popis
Rozvrhovací problémy ve vestavěných systémech reálného času, které pracují s periodickým přenosem zpráv, vytváří rozvrh konkrétní délky, po kterém se rozvrh opakuje. Délka rozvrhu je označována jako hyperperioda (HP) a je definována jako nejmenší společný násobek period všech komunikačních toků. Délka hyperperiody má obrovský dopad na paměťové požadavky přepínačů, protože rozvržené přenosy v celé hyperperiodě musí být uloženy na přepínačích ve formě seznamů zvaných gate control list. Dalším důležitým problémem je vliv hyperperiody na efektivitu rozvrhovacích algoritmů. Takové algoritmy přiřazují časy přenosu všem periodickým výskytům rámců v hyperperiodě. Pokud periody nejsou pečlivě zvoleny, může být hyperperioda velmi velká a nalezení rozvrhu v rozumné době je pak nemožné. Je proto velmi žádoucí najít množinu period s minimální hyperperiodou, aby se zmenšila velikost výsledného rozvrhu a aby se tak snížila výpočetní náročnost problému. Nicméně zkrácení period některých toků může nakonec snížit rozvrhovatelnost problému. Tato práce bude studovat (i) algoritmy minimalizující hyperperiodu množiny period a (ii) vliv těchto algoritmů na úspěšnost rozvrhovacích algoritmů.

Studijní program
KyR LK EECS EEK EEM EK EI SIT OI KME OES BII IB BIO

Online aktualizace rozvrhů v reakci na měnící se požadavky Ing. Ondřej Benedikt BM 0/1 13135

Popis
Vestavěné systémy reálného času většinou pracují na platformě, která neustále podléhá měnícím se požadavkům, což je v literatuře označováno jako rekonfigurace nebo přerozvrhování a pouze uvažuje přidání nových úloh. Současné přístupy k přerozvrhování se obvykle snaží vložit nové úlohy do stávajícího rozvrhu pomocí jednoduché jednorázové heuristiky. Pokud heuristika neuspěje, stávající rozvrh se zahodí a nový rozvrh se přepočítá od nuly, což může být neúměrně časově náročné a vede k rozvrhům, které se podstatně liší od původního rozvrhu. Tato práce se bude zabývat problémem přerozvrhování. Námětem je ukládat některá data během procesu výpočtu počátečního rozvrhu, která pak mohou být použita k urychlení procesu výpočtu nového rozvrhu s nově přidanými úlohami. Takové cenné informace shromážděné během hledání by mohly být například sady konfliktních úloh pro každou úlohu, nebo kritérium výběru úlohy může být během vyhledávání doladěno tak, aby odráželo počet konfliktů jednotlivých úloh. Pokud je tento kontext uložen po nalezení původního rozvrhu, přerozvrhovací algoritmus může začít hledat nový rozvrh s nově přidanými úlohami od tohoto kontextu. Dá se očekávat, že to bude výrazně rychlejší, ale navíc nový rozvrh bude podobný původnímu rozvrhu, což povede k stabilnějšímu chování systému. Další možností je navrhnout algoritmus provádějící pouze místní nebo minimální změny. Hlavním výzkumným úkolem je však vylepšit řešení přerozvrhování tak, aby se při každém volání přerozvrhování algoritmus učil charakter nových požadavků a snažil se vyladit nový rozvrh tak, aby byl připravenější na budoucí požadavky.

Studijní program
KyR LK EECS EEK EEM EK EI SIT OI KME OES BII IB BIO

Rozvrhování s ohledem na teplotu pro vestavěné systémy Ing. Ondřej Benedikt BM 0/1 13135

Popis
Řada zařízení musí vykonávat svou činnost za přísných teplotních omezení a to i bez použití přidaného aktivního, či pasivního, chladiče.
Toto se týká například vestavěných systému používaných v letectví, kde je (kromě jiného) třeba brát v potaz i váhová omezení a omezení na odběr energie.
Je nezbytné zkoumat nové techniky pro rozvrhování aplikací v takovýchto systémech, tak aby byl dosažen maximální výkon při zaručení bezpečného chodu.

Student bude monitorovat chování skutečného vestavěného systému, měřit a analyzovat data, a navrhovat nové strategie rozvrhování s ohledem na teplotu/odběr energie.
Navržené přístupy budou zpětně testovány na skutečném zařízení a na základě experimentů budou zhodnoceny jejich přínosy.

Studijní program
KyR LK EECS EEK EEM EK EI SIT OI KME OES BII IB BIO

Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.