VIII. Parallelisierbarkeit

1. Ansatz
- parallelisierbar ist etwas, wenn es sinnvoll ist mehrere Prozessoren einzusetzen
- O Problematisch!
  - EREW Suche: O(log p) + O(log n ) = O(log n) Time
    
    p
  - geht auch mit nur einem Prozessor in O(log n) Zeit
  - würde bedeuten: nicht sinnvoll zu parallelisieren!
2. Ansatz
- Wann geht es hinreichend schnell?
  - polylogarithmische Zeit
  - polynomial viele Prozessoren
- P theoretisch interessanter
- Definition:
  - NC
    - Nick's Class
    - ein Problem ist in NC ↔ wenn es gelöst werden kann
      - mit O(log^k n) Zeit
      - und O(n^k) Prozessoren für festes k
    - aber: dieser Ansatz ist eine Notlösung!
      - EREW-Suche ist in NC, aber dennoch nicht sinnvoll parallelisierbar
      - Þ Wenn es in NC ist, muss es nicht zwangsweise parallelisierbar sein
      - aber wenn es nicht in NC ist, ist es sicher hochgradig nicht parallelisierbar
- Þ vor allem für Probleme interessant, die nicht in NC sind
Problem: gibt es Probleme, die nicht in NC sind?
- Definition P:
  - P ist die Menge aller Entscheidungsprobleme, für die es einen Polynomialzeit-Algorithmus gibt
  - = die Klasse der Sprachen, die in polynomieller Zeit entscheidbar sind auf einer
    - Turing-Maschine
- Sprache
  - Definition:
    - L ist Sprache über Σ L Í Σ*
    - Σ @ Alphabet
- p-vollständigkeit
  - sei L Î P
    - Definition P:
      - P ist die Menge aller Entscheidungsprobleme, für die es einen Polynomialzeit-Algorithmus gibt
      - = die Klasse der Sprachen, die in polynomieller Zeit entscheidbar sind auf einer
        
        Turing-Maschine
  - L ist P-vollständig "L₁ Î P: L₁ ≤_NC L
    - ≤_NC bedeutet:
      - rechter Ausdruck ist schwerer zu parallelisieren als linker
      - L₁ ≤_NC L₂ $ Algorithmus f, der für alle möglichen Inputs w für L₁ einen
        möglichen Input f(w) für L₂ berechnet, mit der Eigenschaft, dass
        w Î L₁ f(w) Î L₂ und f ist NC-berechenbar
        
        f ist NC-berechenbar, wenn Funktionswerte in O(log^k n) Time mit O(n^k) Prozessoren berechenbar
        
        L₁, L₂ sind Sprachen, w bzw. f(w) sind Wörter über den entsprechenden Alphabeten!
        
        sei etwa L₁ Î Σ₁*, L₂ Î Σ₂*
        
        →"w ÎΣ₁* wird f(w) ÎΣ₂* gebildet: w ÎL₁ f(w) Î L₂
      - kurz: es existiert ein NC-Alg. f: f transformiert jeden möglichen Input w für L₁ in einen solchen von L₂: w ÎL₁ f(w) ÎL₂
    - Beweis:
      - prüfe für jedes Wort, ob es in L₁ ist
      - dazu: ordne wÎL₁ dem f(w) zu
        
        (f von L₁ ≤_NC L₂ genommen)
      - da L₂ ÎNC, kann man "leicht" feststellen, ob f(w) Î L₂ oder nicht
        
        wenn ja Þ w Î L₁
        wenn nein Þ w Ï L₁
      - Anmerkung: dieser Reduktionssatz ist Grundlage für relative Komplexitätsbeweise
- Parallelisierbarkeit für Sprachen
  - Def:
    - Ein einem Berechnungsproblem zugeordnetes Entscheidungsproblem heiße relevant, wenn
      aus der Lösung des Berechnungsproblems die Lösung des Entscheidungsproblems direkt folgt
  - Beispiel:
    - G sei kantenmarkierter gerichteter
      - Graph
    - start (Start-)Knoten von G
    - Berechnungsproblem: DFS (geordnete Tiefensuche, depth first search)
      - Tiefensuche
    - gewünschter Output: Reihenfolge der Knoten bei Tiefensuche, beginnend mit v
    - Frage: kann man dieses Problem parallel berechnen, oder ist es Î NC?
    - Þ relevantes Entscheidungsproblem:
      - Gleicher Input
        
        G
        
        start
        
        zwei weitere Knoten u,v Î V(G)
      - Frage: kommt u in v vor, oder v in u?
  - Seien L₁, L₂ Sprachen mit L₁ ≤_NC L₂
  - Aussagen über NC:
    - Fakt: die Hintereinanderausführung zweier NC-Algorithmen ist ein NC-Algorithmus
    - Folgerung: ≤_NC ist eine transitive Relation
    - Reduktionssatz:
      - seien L₁ ≤_NC L₂
      - dann gilt:
        
        wenn L₁ Ï NC ist, so ist auch L₂ Ï NC
        
        wenn L₂ Î NC Þ L₁ Î NC
- Definition: CVP
  - circuit value problem
  - Schaltkreisproblem
  - C ist Schaltkreis C ist eine Folge <g₁, g₂,...> :
    "i: g_i ist entweder Inputvariable oder
    g_i = g_j Ú g_k oder g_i = g_j Ù g_k oder g_i = Ø g_j für alle j,k ≠ i
  - Wert (C) = 1 bei Prüfung der Inputs wert(g_n) = 1
  - Beispiel:
    - k(abÚcdÚef) := kÙ((aÙb)Ú(cÙd)Ú(eÙf)) := l
    - := <a,b,c,d,e,f,k,z₁ = aÙb, z₂=cÙd, z₃=eÙf, z₄= z₁Úz₂, z₅=z₄Úz₃, l=kÙz₅>
  - Satz: CVP ist P-vollständig
    - Beweis: ähnlich dem Theorem von Cook
      (welches aussagt, das SAT NP-vollständig ist)
      - Sat-Problem
      - np-vollständig
    - Folgerung: NOR-CVP ist P-vollständig
      - NOR-CVP: wie CVP, aber
        
        Inputs sind alle 1
        
        als Verknüpfungen ist nur NOR zugelassen
        
        g_i = NOR(g_j,g_k): j,k ≠ i
    - NOR-CVP ≤_NC DFS
      - hier ist mit DVS ein relevantes Entscheidungsproblem gemeint
      - Beweis
        
        sei C eine Instanz von NOR-CVP
        
        diesem C ordnen wir mit Hilfe einer Funktion f ein f(C) zu - ein Graph G mit Knoten
        
        start
        
        u
        
        v
        
        Ziel: Wert(C) = 1 u wird bei DFS vor v besucht

EREW Suche: O(log p) + O(log	n	) = O(log n) Time
	p