1. Home
  2. Flashcards
  3. Preview

VS-10-Algorithmen

  1. 4 erwünschte Eigenschaften paralleler Algorithmen
    • Nebenläufigkeit
    • Skalierbarkeit
    • Lokalität
    • Modularität
  2. 4 Parallele Programmiermodelle
    • Task/Kanal
    • Message Passing
    • Datenparallelisierung
    • Shared Memory
  3. 4 Schritte beim Parallelen Design-Vorgehen (PCAM)
    • Partitionierung
    • Kommunikation
    • Agglomeration
    • Mapping
  4. 5 Items bei der Partitionierung
    • Anzahl Tasks
    • Redundanz
    • Berechnungsumfang
    • Skalierung
    • Alternativen
  5. 4 Aspekte der Kommunikation bei PCAM
    • Lokalität
    • Strukturiertheit
    • Dynamik
    • Synchronität
  6. 5 Aspekte der Agglomeration bei PCAM
    • Lokalität
    • Redundanz
    • Replikation
    • UmfangSkalierbarkeit
    • Nebenläufigkeit
  7. 4 Aspekte des Mapping-Designs bei PCAM
    • Dynamik
    • Zentralisierung
    • Kosten
    • Anzahl
  8. Formel für Effizienz eines Algorithmus
    Effizienz = Ausführungszeit_Seq. / (Anzahl Prozessoren * Ausführungszeit_Par.)
  9. Ahmdahls Gesetz
    Wenn sequenzieller Anteil 1/s beträgt, ist der maximale Speedup s
  10. Formel für Kommunikationszeit einer Nachricht
    Nachrichtenzeit T (msg) = Setupzeit T_s + Zeit Pro Wort T_w * Wortzahl L
  11. 4 Algorithmen für Load-Balancing
    • Rekursive Bisektion: iterative Lastverteilung
    • Lokal: schrittweise Lastverteilung unter Nachbarn
    • Probabilistisch: zufällige Auswahl, bei geringer Kommunikation
    • Zyklisch: jeder Prozessor jede p-te Task, bei starker Lokalität
  12. 3 Kompositionsansätze bei der Modularisierung
    • Sequenziell
    • Parallel
    • Gleichzeitig
  13. 3 Parallele Designregeln bei der Modularisierung
    • Unabhängigkeit
    • Datnverteilung
    • Komposition
  14. 4 Auswirkungen der Modularisierung
    • zusätzliche Berechnungen
    • erhöhte Idle-Zeit durch ungleiche Lastverteilung
    • erhöhter Kommunikationsaufwand
    • erhöhte Granularität
  15. 5 Merkmale Manager/Worker Designmuster
    • ein Manager
    • viele Worker
    • Manager verteilt Aufgaben
    • Worker erledigen Aufgaben
    • Manager nimmt Ergebnisse auf
  16. 7 Merkmale Producer/Consumer Designmuster
    • ein oder mehrere Producer
    • ein oder mehrere Consumer
    • Producer erzeugt Arbeitspakete
    • Producer legt Pakete in Schlange
    • Consumer holt Pakete aus Schlange
    • Consumer verarbeitet Pakete
    • Anzahl Producer/Consumer gemäß verursachter Last
  17. 3 Phasen bei Map Reduce
    • Map
    • Combine
    • Reduce
Author
Anonymous
ID
93461
Card Set
VS-10-Algorithmen
Description
Verteilte Systeme SS 2011 - Skript 11 - Parallele Algorithmen
Updated

  1. Home
  2. Flashcards
  3. Preview