Task-Platzierung auf Many-Core-Prozessoren mit fehlerhaften Komponenten

Die vorliegende Dissertation beschreibt die Entwicklung und Evaluierung dreier Algorithmen zur Platzierung von parallelisierten Applikationen auf zukünftigen Many-Core-Prozessoren. Die Algorithmen sind in der Lage, auftretende permanente Fehler der Hardware zu kompensieren und dadurch einen allmählichen Funktionsausfall anstatt eines Programmabsturzes herbeizuführen. Es werden permanent ausgefallene Kerne, Router und Interconnect-Verbindungen des Many-Cores betrachtet. Das Hauptziel der Platzierungsalgorithmen besteht darin, eine funktionsfähige, jedoch auch performante Platzierung von Applikationen, welche aus einzelnen miteinander kommunizierenden Tasks bestehen, auf einen Many-Core-Prozessor durchzuführen. Da die Algorithmen jeweils zu Beginn eines jeden Programms ausgeführt werden, ist darauf zu achten, dass die Laufzeit der Platzierungsentscheidung nicht übermäßig wächst. Many-Core-Prozessoren und Applikationen werden als Graphen dargestellt, die sowohl die Kommunikationsstrukturen als auch die Intensitäten der Kommunikationen abbilden. Es kommen sowohl synthetische Task-Graphen als auch Umsetzungen realer Applikationen zum Einsatz. Die vorliegende Arbeit entwirft den Konnektivitätssensitiven Algorithmus, der statisch Platzierungen erzeugt, welche versuchen, die Entfernungen zwischen den Tasks gering zu halten. Als Verfeinerung werden zusätzlich der Fitting Algorithmus und der Favorite Neighbour Algorithmus entwickelt. Diese beiden Erweiterungen des Basisalgorithmus sollen bei der Platzierung mehrerer Task-Graphen und bei der Platzierung von Task-Graphen mit starkem Ungleichgewicht der Verbindungen Vorteile bringen. Die Ergänzung der statischen Platzierungsmethoden um dynamische Verfahren erfordert Änderungen an der Hardware und der Platzierungsstrategie. Es können aber Vorteile bei der Platzierungsgeschwindigkeit und der Qualität der Ergebnisse erzielt werden. Ein ausführliches Evaluierungskapitel betrachtet alle Aspekte der Task-Platzierung auf potentiell fehlerhaften Many-Core-Prozessoren. Hierbei untersucht die Arbeit sowohl der fehlerfreie Fall als auch die Platzierung unter Annahme von fehlerhaften Hardwarekomponenten. Die Auswirkungen jeder Fehlerart des verwendeten Fehlermodells werden, vor der Betrachtung von Fehlerkombinationen, zuerst einzeln analysiert. Ein Vergleich mit den Ergebnissen eines bekannten Algorithmus aus der Literatur und zwei einfachen Platzierungsmetriken ist ebenfalls Teil der Evaluierung. Unterschiedliche Netzwerk-Topologien und die Belastung des On-Chip-Netzwerks werden auch behandelt. Es stellt sich heraus, dass der entwickelte Konnektivitätssensitive Algorithmus in den meisten Fällen die Platzierung mit dem geringsten Kommunikationsoverhead erzeugen kann und zusätzlich auch bei hohen Fehlerraten gültige Abbildungen findet. Die beiden erweiterten Algorithmen schneiden schlechter ab