by Streszczenie
Ukierunkowane acykliczne grafy zadań służą jako typowe jądro reprezentacja dla aplikacji wbudowanych. Nowoczesne wbudowane architektury wielordzeniowe stawiają nowe wyzwania dla wydajnego mapowania i planowanie zadań DAG zapewniających dużą liczbę zasoby heterogeniczne. W tym artykule hybryda Integer Linear Programowanie – Metoda programowania z ograniczeniami, która wykorzystuje Rozkład giętarek służy do znalezienia sprawdzonych optymalnych rozwiązań. Proponowana metoda jest uzupełniona o schematy generowania cięć do przyspieszenia procesu rozwiązania. Wyniki eksperymentalne pokazują że proponowana metoda systematycznie przewyższa metodę opartą na ILP metoda rozwiązania. Słowa kluczowe — architektury wielordzeniowe, mapowanie DAG, zadania szeregowanie, programowanie liniowe całkowitoliczbowe, programowanie z ograniczeniami.
WPROWADZANIE
W celu spełnienia rosnących wymagań obliczeniowych obecne i przyszłe aplikacje, nowoczesne platformy obliczeniowe obejmują dużą liczbę niejednorodnych rdzeni. on heterogeniczność pozwala na zaspokojenie różnych potrzeb docelowa domena aplikacji, podczas gdy duża ilość rdzeni umożliwia równoległe wykonywanie aplikacji. W dzisiejszych czasach te platformy są głównym stosowanym podejściem do zaspokojenia trudnych wymagania energetyczne. Ponadto są odporne na przetwarzanie zmiany i awarie obwodów, które charakteryzują prąd i przyszłe technologie głębokiego krzemu submikronowego. Jeden z głównych wyzwaniem dla tego typu platform jest rozwój metody mapowania na nich złożonych, rzeczywistych aplikacji w a sposób, który wykorzystuje ich cechy. Innymi słowy, właściwy metody przypisywania zadań aplikacji do rdzeni i planowanie ich na rdzeń są wymagane w celu optymalizacji jednego lub więcej metryk (np. czas wykonania, zużycie energii itp.)
Kiedy cechy aplikacji (np. zadania, zależności między zadaniami, czas wykonania każdego zadania per rdzeń) są znane z góry i nie zmieniają się w czasie wykonywania, statyczne można opracować metody mapowania. Ta klasa problemów
obejmuje dużą liczbę rzeczywistych aplikacji, takich jak typowe przetwarzanie sygnału i algorytmy multimedialne, które są opisane przez statyczne wykresy przepływu danych. Ponieważ mapowanie zadań to wykonywane jednorazowo w czasie kompilacji i pozostają niezmienione przez cały okres użytkowania produktu, rozsądny czas projektowania dla uzyskanie optymalnego lub prawie optymalnego rozwiązania jest uzasadnione.
Powyższy problem był w przeszłości szeroko badany, a proponowane metody można podzielić na dwa główne: kategorie. Pierwsza obejmuje algorytmy oparte na: i) heurystyki, takie jak planowanie list lub powielanie węzłów,
oraz ii) algorytmy wyszukiwania stochastycznego, takie jak genetyczne algorytmy . Zaletą tych metod jest ich niska
złożoność obliczeniowa, która pozwala im dostarczyć rozwiązanie w skróconym czasie. Cierpią jednak na trzy główne wady. Po pierwsze, ponieważ opierają się na heurystyce, nie może zagwarantować optymalności produkowanego rozwiązania. Po drugie, wytworzone rozwiązanie może być dalekie od optymalnego, gdy założenia, na których opierają się te metody, nie są zadowolona. Po trzecie, nie są łatwo rozszerzalne i muszą być opracowane na nowo, gdy nałożone zostaną nowe założenia lub ograniczenia.
