5. Pipelining

• Idee
  • Teilen von Aufgaben t in Folgen von Teil-Aufgaben t₁,..., t_k
  • so, dass nach Beendigung von t₁ für die erste Aufgabe das t₁ für die zweite begonnen werden kann
  • gleichzeitig wird begonnen t₂ für die erste Aufgabe zu lösen
  • t¹ t¹₁ t¹₂ t¹₃
    t¹ t²₁ t²₂ ...
    t³ t³₁ ...
• am Beispiel der
  • 2-3-Bäume
    • gewurzelte
      • Bäume
    • jeder innere Knoten hat entweder 2 oder 3 Kinder
    • jeder Pfad von einem Blatt zur Wurzel hat die gleiche Länge
    • 
      
      Beispiel
    • Eigenschaften
      • Þ die Zahl der Blätter in einem 2-3-Baum der Höhe h liegt zwischen 2^h und 3^h
      • Þ Wenn n die Zahl der Blätter ist, so ist die Höhe des Baumes ÎΘ(log n)
    • Anwendung
      • Repräsentation von dynamisch veränderlichen Mengen
      • ermöglicht die Operationen
        • Suchen
        • Einfügen
        • Entfernen
        • jeweils in O(log n) Zeit, wenn n die Zahl der Knoten im bestehenden 2-3-Baum ist
    • Zugriffe
      • Suche
        • gegeben ein Element b
        • dann ist die Suche = Suche nach einem Blatt u mit dem Wert a_i, so dass a_i ≤ b < a_i+1 gilt
        • wird realisiert über binäre Suche im (Teil-)Baum r
          • ist b≤ L[r], dann erfolgt die Suche rekursiv im linken Teilbaum an r
          • ist L[r] < b ≤ M[r], dann geht die Suche rekursiv im zweiten Teilbaum von links an r weiter
          • ist b > M[r] wird im rechten Teilbaum gesucht
          • die Suche Terminiert, wenn ein Blatt gefunden wird
        • Zeit für Suche ~ Höhe (T)
      • Einfügen eines Elements b
        • dazu zunächst suchen der Einfügeposition mittels der oben beschriebenen Suche
        • es sei u das gefundene Blatt mit dem Wert a_i
        • zwei Fälle:
          • wenn a_i = b, so ist nichts mehr zu tun, denn das Element befindet sich bereits im Baum
          • anderenfalls wird ein neues Blatt u' zum Speichern des Wertes b erzeugt und direkt rechts neben u eingefügt
          • Þ weitere 2 Möglichkeiten:
            • Fall 1: der Vaterknoten p von u hat nun drei Elemente, ist das Einfügen fertig
            • Fal 2: der Vaterknoten hat nun vier Elemente:
              • erzeuge einen Nachbarknoten p'
              • verschiebe die zwei rechten Kinder von p nach p'
              • Þ p und p' haben jeweils wieder nur zwei Kinder
              • füge p' mit der gleichen Einfüge-Prozedur neben p in den Baum ein
              • Þ ggf. kaskadierend!
              • Þwenn die Wurzel vier Kinder hat, bekommt sie einen Bruder
                und wird mit diesem zusammen unter eine neue Wurzel gehängt
        • in jedem Fall muss der Baum einmal nach unten und einmal nach oben durchlaufen werden
        • denn: beim Durchlaufen nach oben müssen die Werte von L, M und R aktualisiert werden
• eine Sortierte Liste A = (a₁, a₂, ..., a_n) von Objekten mit a₁ < a₂ < ... < a_n
  kann als 2-3-Baum dargestellt werden:
  • die Blätter enthalten die Einträge geordnet von links nach rechts
  • jeder interne Knoten v enthält zwei Daten:
    • L[v] = das kleinste Element, dass sich in einem Blatt des linken Teilbaums an v befindet
    • M[v] = das größte Element, dass sich in einem Blatt des 2. Teilbaums von links an v befindet
  • jeder innere Teilbaum mit drei Kindern enthält zusätzlich noch:
    • R[v] = das größte Element in einem Blatt im rechten Teilbaum an v
    • wird normalerweise in 2-3-Bäumen nicht gespeichert
    • wird hier jedoch (später) verwendet, um das parallele Einfügen zu ermöglichen
  • 
    
    Beispiel
• Aufgabe:
  • 
    
    gegeben sei ein 2-3-Baum T mit n Blättern zur Speicherung von a₁ < a₂ < ... < a_n
  • Aufgabe:
    • Einfügen einer Folge von Elementen b₁ < b₂ < ... < b_k
    • es sei k<<n
    • 
      
      Beispiel: Einfügen der 5
    • o.B.d.A. seien die b_i von den a_i verschieden
  • Zeit im seriellen: O(k log n)
  • Ziel: Verbesserung der Zeit im Parallelen
  • dazu:
    • markieren von b₁ und b_k
    • START INSERT b₁; INSERT b_k - O(log n) Time mit dem seriellen Algorithmus
    • →Folge: Die B = (b₂ < ... < b_k-1) werden alle zwischen bestehende Blätter eingefügt
    • sei eine Kette B_i = { Elemente b Î B | a_i < b < a_i+1}
      also eine Menge von Elementen, die alle zwischen Blatt a_i und Blatt a_i+1 eingefügt werden sollen
    • sei k_i = |B_i|
    • 2 Fälle:
      • 
        
        1. Fall: k_i ≤ 1 für alle i
        • Pardo: Füge alle El. aus B gleicheitig ein
        • 
          
          → Pro Knoten im Blattbereich haben wir maximal 6 Söhne
        • 
          
          Auflösung
        • wandert nach oben durch
        • → in O(log n) Zeit kann das ganze nach oben geschickt werden; mit WORK O(k log n)
      • 2. Fall: $k_i > 1
        • 
          
          Einfügen von mehreren Knoten an einer Stelle
        • Lösung:
          • wähle in allen B_i das mittlere Element
          • füge gleichzeitig parallel alle mittleren Elemente ein
        • 
          
          → aus einem roten wird ein blaues Element → Halbierung der Gruppe der roten Elemente
        • Time ist jeweils O(log n)
        • Iterationen liefern nach log k Schritten das Resultat
        • →Gesamtzeit O(log k · log n)
        • Pipelining dabei:
          • erster Schritt: Einfügen der ersten blauen Zwischenpunkte
          • während in der darüberliegenden Ebene Ordnung geschafft wird,
            können gleichzeitig die nächsten eingefügt werden
          • Der Pipeline-Ansatz liefert stattdessen (oben) O(log k + O(log n)).
            Wegen k < n →O(log k + O(log n)) = O(log n)