Search

Scheduling the execution of parallel algorithms on parallel computers is a main issue in current research. Parallel computers can be used to solve scheduling problems very fast and we might be able to tackle new applications, where schedules must be obtained very quickly. Although the importance of parallel scheduling algorithms has been widely recognized, only few results have been obtained so far. In this thesis, we present new and efficient parallel scheduling algorithms. A classical problem in scheduling theory is to compute a minimal length schedule for executing n unit length tasks on m identical parallel processors constrained by a precedence relation. This problem is NP-complete in general, but there exist a number of restricted variants of it that have polynomial solutions and that are still of major interest. First, we show that if the precedence constraints are restricted to be trees, then an optimal schedule can be computed in time O(log(n)log(m)) using n/log(n) processors of an EREW PRAM. Hence, for those cases where m is not part of the input but a constant, our algorithm is work and time optimal. Second, we present a parallel algorithm that optimally schedules arbitrary precedence constraints on two processors. It runs in time O(log^2(n)) and uses n^3/log(n) processors. In addition, we show that optimal two processor schedules can be computed much more efficiently, if the precedence constraints are restricted to be series parallel graphs. In this case, an optimal schedule can be computed in logarithmic time and a linear number of operations suffice. Finally, we investigate the parallel complexity of scheduling with unit interprocessor communication delays. In this extended setting the schedule additionally takes into account the time required to communicate data between processors. After finishing a task, one unit of time must pass before any of its successors can be started on a different processor, in order to allow for transportation of results from one task to the other. The problem of computing minimal length schedules in this setting is NP-complete, even if precedence constraints are restricted to be trees. The only nontrivial class of precedence constraints for which polynomial solutions are known is the class of interval orders. We present a parallel algorithm that solves the problem for interval orders in time O(log^2(n)) using n^3/log(n) processors. This is the first NC algorithm for this problem. Um parallele Programme auf Parallelrechnern auszuführen sind Scheduling-Verfahren notwendig die die Teilaufgaben den verfügbaren Prozessoren zuordnen. In diesem Forschungsbereich wurden bereits zahlreiche Ergebnisse erzielt. Nur wenige Ergebnisse dagegen gibt es im Bereich der parallelen Scheduling-Verfahren, also solcher Scheduling-Verfahren die selbst auf einem Parallelrechner ausführbar sind. In dieser Arbeit werden neue, arbeitseffiziente parallele Scheduling-Verfahren vorgestellt. Ein klassisches Scheduling-Problem ist das folgende. Gegeben sind n gleichlange Teilaufgaben, eine Präzedenzordnung auf den Teilaufgaben und m Prozessoren. Ziel ist es, einen möglichst kurzen Schedule zu berechnen. Dieses Problem ist im allgemeinen NP-vollständig, allerdings gibt es eine Reihe von eingeschränkten Varianten davon, welche in polynomialzeit lösbar sind. Für den eingeschränkten Fall von Baumpräzedenzen zeigen wir, dass ein optimaler Schedule in Zeit O(log(n)log(m)) mittels n/log(n) EREW PRAM Prozessoren berechnet werden kann. Falls die Zahl m der Zielprozessoren nicht Teil der Probleminstanz ist sondern konstant ist, ist das Verfahren somit Zeit- und Arbeits-optimal. Als nächstes betrachten wir den Fall allgemeiner Präzedenzen und m=2. Wir zeigen, dass in diesem Fall ein optimaler Schedule in Zeit O(log^2(n)) auf n^3/log(n) Prozessoren berechnet werden kann. Für den Fall, dass die Präzedenzen darüberhinaus eine serien-parallele Struktur aufweisen, können wir einen Algorithmus angeben der nur logarithmische Zeit und eine lineare Anzahl von Operationen benötigt. Schließlich wenden wir uns der parallelen Komplexität von Scheduling mit uniformer Kommunikationsverzögerung zu. In diesem erweiterten Szenario muss ein Schedule zusätzlich die Verzögerungszeit berücksichtigen die benötigt wird um Daten zwischen Prozessoren zu transportieren. Nachdem eine Teilaufgabe beendet wurde, muss ein Zeitschritt gewartet werden bevor irgendeine Nachfolgeaufgabe auf einem anderen Prozessor ausgeführt werden kann. In diesem Szenario ist bereits das Problem Baumpräzedenzen optimal auszuführen NP-vollständig. Die einzige nicht-triviale Klasse von Präzedenzen für die polynomielle Scheduling Algorithmen existieren sind Intervallordnungen. Wir präsentieren einen parallelen Algorithmus für dieses Problem der Zeit O(log^2(n)) und n^3/log(n) Prozessoren benötigt. Dieser Algorithmus ist der erste NC Algorithmus für dieses Problem.