2. Pointer Jumping

• 
  
  Ausgangssituation: wurzelgerichteter Baum
  • von jedem Knoten aus gibt es einen Pfad, der zur Wurzel führt
  • Darstellung über Arrays:
  • Knoten x y z
    p[x] p[y] p[z]
  • wir betrachten Wälder wurzelgerichteter Bäume
• Aufgabe: Pfadverdoppelung
  • INPUT: Wald (als Array)
  • OUTPUT: "j (j Knoten): das kanonische Element des Baumes, der j enthält - also die Wurzel
  • Komplexität im seriellen: Θ(n)
    • Suche in einem Array-Durchgang die Wurzeln
    • suche für jede Wurzel alle von ihr aus erreichbaren Knoten mit
      • Tiefensuche
    • dabei wird jeder Knoten nur einmal besucht, und "ihm mitgeteilt" zu welcher Wurzel er gehört
  • Idee des Pointer-Jumping
    • 
      
      Nutzen einer Liste
    • 
      
      ersetzen der Pointer →Verkürzen der Wege
    • →Verdoppeln der Längen der Pfeile
    • anwendbar auch, wenn Kanten Gewichte haben:
      dann bekommen die neuen Kanten die Summe der Geweichte der ersetzten Kanten
    • →anwendbar auch auf die Verarbeitung von Informationen entlang der Kanten
• Algorithmus Pointer Jumping
  • Input = Wald wurzelgerichteter Bäume (als Array)
  • Output := Wurzel S(i) "Knoten i
  • for 1 ≤ i ≤ n pardo
      s(i):=p(i)
      while s(s(i))≠s(i) do
        s(i):=s(s(i))
    • p(i) = Parent(i)
    • am Anfang wird das ursprüngliche Array in s kopiert
    • also: jeder Prozessor bearbeitet genau einen Knoten
• Algorithmus Parallel Prefix (für Bäume)
  • neu: Gewichte W(i) an allen Knoten

  • Input:

    Wald wurzelgerichteter Bäume + Gewicht W(i) "i

  • W(i) = 0 für alle Wurzeln r
  • Output := W(i) (Summe der Gewichte auf dem Pfad von i zur Wurzel) " i
  • for 1<=i<=n pardo
      s(i):=p(i)
      while (i)<>s(s(i)) do
        w(i):=w(i)+w(s(i))
        s(i):=s(s(i))
  • 
    
    Beispiel
• Zeitanalysen
  • Satz: die beiden Algorithmen benötigen O(log h) Zeit
    • h ist die Höhe des höchsten Baumes ist
    • Begründung: in jedem Schritt wird für jeden Knoten,
      der nicht an der Wurzel hängt die Pfadlänge halbiert

    • Zielhöhe ist =1 =	h
      	2x

    • 2^x = h Þ x = log h
  • Modell:
    • CREW-PRAM
      • concurrent read exclusive write parallel random access machine
  • WORK:
    • in jeder Iteration sind n Operationen auszuführen
    • →O(n log h) Operationen
    • → Q nicht optimal! (O(n) wäre optimal)
• Speziafall: Parallel-Präfix auf einzelnem Pfad
  • Definition: Problem der Berechnung der Präfix-Summen auf einer verketteten Liste
  • Folgerung: Parallel Präfix ist in logarithmischer Zeit mit O(n log n) WORK möglich!
  • Anwendung:
    • 
      
      Menge von Knoten V als Pointer-Array
    • sowie Untermenge von Knoten IÍV
    • OUTPUT:= I in der Reihenfolge der Liste als Array
    • Ansatz für Lösung des Problems:

      markiere über Gewichte mit W(i) :=

      0, wenn iÎI 1, wenn iÎV\ I

    • Parallel Präfix (oben) liefert die Indizes der Elemente aus I in der Listenreihenfolge
    • also Vorgehen:
      • Parallel Prefix ausführen
        • 
          
          Ausgangssituation
        • 
          
          Schritt 1a
        • 
          
          Schritt 1b
        • 
          
          Schritt 2a
        • 
          
          Schritt 2b
        • 
          
          Schritt 3a
        • 
          
          Schritt 3b
      • anschließend müssen die Prozesoren die auf Knoten Î I sitzen, nurnoch ihr W(i) ausgeben