7. accelerated cascading

• Idee
  • gegeben sei ein Problem
  • für dieses sei bekannt:
    • I) nicht ganz so schneller Algorithmus; optimal
    • II) superschneller Algorithmus; nicht optimal
  • 
    
    Kaskade
  • 
    
    Beispiel: Summe von n Zahlen, die als Blätter in einem Baum stehen
    • Alg. I = serieller Algorithmus

      • wird mit	n	Prozessoren angewendet
        	log n

      • diese addieren jeweils log n Zahlen
    • Alg. II = Baumparadigma
      • Addieren der Zwischenergebnisse
    • → O(log n) optimal
• Ausführung auf
  • CRCW
    • = concurrent read, concurrent write
    • mehrere Prozessoren können eine Speicherzelle gleichzeitig schreiben/lesen
    • mehrere Varianten:
      • Priority
      • common
• Aufgabe: Bestimmung des Maximums einer Menge von Elementen
  • {a₁, ..., a_n} → max { }
  • o.B.d.A. Annahme: die a_i sind paarweise verschieden
  • ist im parallelen richtig schwer!
  • Satz: in O(log n) Time kann man das Maximum optimal bestimmen (auf der CREW)
  • auf CRCW in O(log log n)
• Algorithmus BASIS-MAX
  • INPUT: p paarweise verschiedene Elemente im Array A[1..p]
  • OUTPUT: Max (als bool'sches Array mit M[i]=1 ↔ A[i]=Max)
  • Begin
  • for i,j := 1 to p pardo
    • if A[i] ≥ A[j] setze B(i,j):=1
    • else B(i,j):=0
  • for i := 1 to p pardo
    • M[i] = B[i,1) Ç B(i,2) Ç ... Ç B(i,p)
      • // M[i] ist zu Start = 0^p
      • // wird nur dann 1; wenn alle Prozessoren die 1 schreiben wollen
  • end
  • Analyse
    • Work = O(p²) Operationen → sehr unoptimal
    • Auf CRCW geht das in O(1) Zeit (mit p² Prozessoren)
• Frage: geht das mit der CREW? - nein! Resultat:
  • Sei fⁿ eine n-stellige Boolsche Funktion
  • Input I=(x₁,...,x_n)
  • I(i) = (x₁, ... , x_i, ... , x_n)
  • I ist kritisch für fⁿ genau dann, wenn "i(1≤ i ≤ n): f(I) ≠ f(I(i))
    • also eine Eingabe ist genau dann kritisch,
      wenn jede Veränderung eines Bits eine Veränderung der Ausgabe bewirkt
  • Beispiel:
    • f(x₁,..,x_n) = x₁ Å x₂ Å ... Å x_n]
    • I=(0,...,0), I kritisch für f
  • Haupttheorem: fⁿ: {0;1}ⁿ→{0,1} besitze kritischen Input
    • Dann muss man immer alle Eingaben zur Berechnung des Funktionswertes betrachten
    • Þ auf der CREW braucht man Ω(log n) Zeit
  • da die logische Konjunktion einen kritischen Input hat,
    braucht man für das Maximum auf der CREW O(log n) Zeit
• 1. Ziel: WORK reduzieren (Baum doppelt logarithmischer Tiefe)
  • Annahme: sei n = 2^2k Þ k = log log n
  • Definition:
    • Baum doppelt logarithmischer Tiefe (DLT) für n Blätter
      • Root habe 2^2k-1 Söhne ( @ √n)
      • Beispiele:
        • 
          
          n = 16 = 2²²
        • 
          
          n = 256 = 2²³
      • jeder dieser Söhne habe 2^2k-2 Söhne
        • 
          
          
        • 
          
          
      • jeder Knoten im Level i habe 2^{2k- i -1} Söhne für 0 ≤ i≤ k-1
      • jeder Knoten im Level k habe 2 Söhne
        • 
          
          
        • 
          
          
  • Fakt
    • 1) Jeder Knoten im Level i hat 2^{2k- i -1} Söhne
    • 2) es gibt 2^2k-2k-i Knoten im Level i
      • Beweis: mit Induktion über Fakt 1
    • 3) Tiefe eines solchen Baumes ist (k+1) = (log log n) + 1
  • Algorithmus (*)
    • Start bei den Knoten der Höhe 1 (also auf Level k) → Maximum der Blätter
    • Fortsetzung Richtung Wurzel (level by level) unter Benutzung unseres Basisalgorithmus
  • Analyse:
    • sei n' die Zahl der Inputs.
    • Das Maximum der n' Elemente kann mit diesem Algorithmus (*) in O(log log n) Zeit
      mit O(n·log log n) WORK berechnet werden
    • Beweis
      • Die Zahl der Operationen pro Knoten im Level i ist quadratisch!
      • nach Fakt 1: O((2^2k-i-1)²) Vergleiche pro Knoten!
      • Þ Gesamt im Level i: O((2^2k-i-1)² · (2^2k-2k-i)) = O(2^2k) = O(n)
      • ÞLemma
    • Anmerkung: geht immer noch von der CRCW aus!
• 2. Ziel: optimaler Algorithmus (mit accelerated cascading)
  • Algorithmus MAX WT-optimal
  • Phase 1: Binärbaumalgorithmus
    • insgesamt \ceil{log log log n} Levels
    • 
      
      
    • also Eingabe sind n = 2^22k Elemente

    • nach log log log n Level-Binärbaumbearbeitung bleiben noch n' =	n	Elemente
      	log log n

  • Phase 2: Anwendung des Algorithmus (*)
    • auf Baumes DLT
    • Tiefe = verbleibende n' = 2^2k'
  • Time:
    • Phase 1: O(log log log n) Î O(log log n)
    • Phase 2: O(log log n') Î O(log log n) wegen n' < n
    • Σ = O(log log n)
  • WORK:
    • Phase 1: O(n)
      • im untersten Level braucht man n Operationen

      • im 2. Level	n	, im 3. n , im 4. n 8 4
        	2

      • wegen Σ	∞ i=1	n	≤ n folgt, dass weniger als 2n Operationen benötigt werden
        		2i

    • Phase 2:
      nach Lemma unter (1. Ziel):

      O(n) + O(n' log log n') Î O(n) + O(n' log log n) Î O(n) + O(	n	·log log n) = O(n)
      	log log n

  • 
    
    dieser Algorithmus ist WT-Optimal