Kapitel IV:

Swap-Sort als Lastaufteilungsverfahren für Multiprozessorsysteme

1. Multitasking bzw. Multithreading mit Swap-Sort

Nun wollen wir untersuchen, welche Teile man parallel bzw. gleichzeitig ausführen kann. Dazu erweitert man Swap-Sort mittels eines Parameters p, welcher die Anzahl der Prozessoren angibt, welche in einem Multiprozessorsystem verfügbar sind.

Swap-Sort(a[],f,l,p) { // darf auf maximal p Prozessoren verteilt werden
         if(f<l) {
                   // Aufteilung - Phase 1
                   k=f+(l-f)/2;                // Aufteilung des Problems in kleinere Teile
                   if(p==1) {
                           sortiere a[] von Index f bis Index k       // sortiert 1. Teil des Problems
                           sortiere a[] von Index k+1 bis Index l   // sortiert 2. Teil des Problems
                   } else parallel {
                           // erzeugt mindestens einen zusätzlichen Task, falls Ressource verfügbar
                           Swap-Sort(a[],f,l,p/2);       // darf p/2 Prozessoren verwenden
                           Swap-Sort(a[],f,l,p-p/2);   // darf p-p/2 Prozessoren verwenden
                   }

                   // MergeOfSwap-Sort() – swappt (Phase 2) und mischt (Phase 3)
                   MergeOfSwap-Sort(a[],f,k,k+1,l,p); // mischen zweier sortierter Arrays
         }}

Die Befehlsabarbeitung im Block, der mit dem Schlüsselwort parallel eingeleitet wird, soll folgendes festlegen: Es sind in diesem Block 2 Funktionen bzw. Anweisungen enthalten, die gleichzeitig ausgeführt werden sollen. Dabei versucht man für die 1. Funktion einen neuen Task zu erzeugen. Wir nehmen an, dies sei immer möglich. Andernfalls könnte man z.B., die in diesem Block enthaltenen Funktionen nacheinander abarbeiten. Sobald der Task für die 1. Funktion erzeugt wurde, wird die Programmausführung mit der 2. Funktion, die im Block enthalten ist, fortgesetzt. Sobald man nach Ausführung der 2. Funktion am Ende des Blocks angelangt ist, muß man noch so lange warten, bis die 1. Funktion abgearbeitet bzw. der zusätzlich erzeugte Task beendet wurde.

Da die Aufteilungsphase von Swap-Sort, selbst die Sortieraufgabe in kleinere Sortieraufgaben teilt, die allerdings noch gemischt werden müssen, eignet sich die Aufteilungsphase zur Aufteilung der Arbeit auf mehrere Prozessoren.

Nun betrachten wir die Mischfunktion von Swap-Sort:

MergeOfSwap-Sort(a[],i,j,k,l,p){ // darf auf maximal p Prozessoren verteilt werden
n=Calculate_n(a[],i,j,k,l);
if (!n--){
         // Austauschen – Phase 2
         Swap(a[],j-n,j,k,k+n,p); // swap Teil 2 mit Teil 3 mit Hilfe von p Prozessoren

         // Mischen – Phase 3
         if(p==1) {
                     if(i!=j-n) { // mischt Teil 1 mit Teil 3
                                 mische a[] von Index i bis Index j-n-1 mit a[] von Index j-n bis Index j
                     }
                     if(l!=k+n) { // mischt Teil 2 mit Teil 4
                                   mische a[] von Index k bis k+n mit a[] von Index k+n+1 bis Index l
         }} else parallel {
                     // erzeugt mindestens einen zusätzlichen Task für die 1. Anweisung,
                     // falls Ressource verfügbar
                     if(i!=j-n) MergeOfSwap-Sort(a[],i,j-n-1,j-n,j,p/2);           // verwende p/2 Prozessoren
                     if(l!=k+n) MergeOfSwap-Sort(a[],k,k+n,k+n+1,l,p-p/2); // verwende p-p/2 Prozessoren
         }}}

Hieraus ist ebenfalls ersichtlich, daß die Arbeitsaufteilung der Austauschphase und der Mischphase sich gut auf mehrere Prozessoren verteilen lassen.

Die Abarbeitung der Vorsortierphase und die Austauschphase reduziert sich ca. auf 1/p der Zeit. Die Abarbeitung der Mischphase reduziert sich auf beinahe 1/p der Zeit. Die Berechnung der Zahl n, welche festlegt, wie viele Elemente von der 1. mit der 2. Folge ausgetauscht werden sollen, fällt kaum ins Gewicht, da mittels Berechnung durch Intervallteilung, die Anzahl der Vergleiche auf log(Minimum(Anzahl der Elemente einer der beiden Teilfolgen)) reduziert wurde.

Allerdings gibt es bei der Abarbeitung in der Reihenfolge Sortierphase => Austauschphase => Mischphase 2 Engpässe zwischen den Phasen, da man von der einen auf die andere Phase erst übergehen kann, wenn die vorhergehende abgearbeitet wurde. Daher ist es wichtig, daß die Aufteilung der Arbeit in den einzelnen Phasen so geschieht, daß diese jeweils in annähernd gleich zeitaufwendige Unteraufgaben aufgeteilt werden.

2. Verteilung von Fibers an Tasks

Im vorhergehenden Abschnitt wurde in jeder einzelnen Phase von Swap-Sort, die Aufgaben so verteilt, daß hierfür immer wieder Tasks erzeugt und beendet wurden. Dieses kann zu einem merklichen Overhead führen, der sich insbesondere bei nicht umfangreichen und auf viele Prozessoren aufgeteilten, sowie bei zahlreich aufeinanderfolgenden Sortieraufgaben bemerkbar macht. Um diesen Overhead einzuschränken, kann man vor dem 1. Aufruf von Swap-Sort (p-1) zusätzliche Tasks erzeugen. In diesem einfachen Scheduler-Modell arbeitet ein Task gerade einen Fiber (Programmeinheit, welche in einem Task abläuft, aber vom Anwender verwaltet wird) ab, oder er befindet sich in einem Wartezustand. Ein Task bearbeitet eine Nachricht erst dann, wenn er sich wieder in dem Wartezustand befindet. Befindet ein Task sich im Wartezustand, wartet er immer solange, bis er eine Nachricht erhält. Erhält er eine Nachricht, daß er einen Fiber ausführen soll, dann führt er in diesem Fall eine in der Nachricht mitgeteilte Funktion aus. Nach der Abarbeitung des Fibers sendet dieser Task eine Nachricht jenem Task, der die Aufforderung einen Fiber abzuarbeiten sendete. Danach geht er wieder in den Wartezustand über. Ist das gesamte Sortierproblem bearbeitet, werden alle zusätzlich (p-1) erzeugten Tasks wieder beendet bzw. freigegeben.

ScheduleFibers() { // einer der zusätzlich erzeugten Tasks
         while(GET_MESSAGE(Message)) {            // wartet, solange bis er eine Nachricht erhält
                   if (IS_SCHEDULE_MSG(Message)) {// ist eine Nachricht in der Message-Queue,
                                                                         // die einen Fiber zur Ausführung bringen soll,
                           STARTE_FIBER(Message);     // dann wird ein Fiber gestartet
                           SEND_FINISHED_MSG(Message); // nach Abarbeitung des Fibers, wird dem Task
                   }}}                                                   // der die Nachricht sendete, eine Nachricht
                                                                         // zurückgesendet

Swap-Sort(a[],f,l,p[],p1,p2) {              // p[] Task-Liste
                                                     // alle Tasks zwischen p1 und p2 dürfen von dieser Funktion
                                                     // verwendet werden
                                                     // Task p2, ist jener Task, der gerade ausgeführt wird
         if(f<l) { // Aufteilung - Phase 1
                   k=f+(l-f)/2;          // Aufteilung des Problems in kleinere Teile
                   if(p1==p2) {        // wenn kein zusätzlicher Task verfügbar => tue
                             sortiere a[] von Index f bis Index k      // sortiert 1. Teil des Problems
                             sortiere a[] von Index k+1 bis Index l  // sortiert 2. Teil des Problems
                   } else {// wenn ein zusätzlicher Task verfügbar => tue
                             // Task p2 sendet eine Nachricht an Task p1+(p2-p1)/2,
                             // daß die Funktion Swap-Sort() mit den mitgesendeten Parameterwerten
                             // ausgeführt werden soll
                             SEND_MESSAGE_START_SORT(Swap-Sort,a[],f,l,p[],p1,p1+(p2-p1)/2,p2);
                             Swap-Sort(a[],f,l,p[],p1+(p2-p1)/2+1,p2);
                             // Task p2 wartet auf eine Nachricht von Task p1+(p2-p1)/2
                             WAIT_MESSAGE(p1+(p2-p1)/2);
                   }
                   // Austauschen (Phase 2) und Mischen (Phase 3)  kann analog für die Ausführung von Fibers
                   // programmiert werden
                   mische a[] von Index f bis k mit a[] von Index k+1 bis Index l
       }}