Skip to main content
  1. Posts/

Rechnerstrukturen Vorlesungszusammenfassung

Vorlesungszusammenfassung der Vorlesung Rechnerstrukturen am KIT von Prof. Dr. Karl gehalten von Dr. Lars Bauer und Übungen gehalten von Thomas Becker. Die Klausur hat typischerweise einen hohen Anteil an Wissensfragen und die Bearbeitungszeit ist sehr knapp.

Grundlagen

EinfĂŒhrung

  • ZunĂ€chst mechanische Rechner
  • Platz und KomplexitĂ€t durch Dualsystem deutlich reduziert
  • Moore’s Gesetz

    Anzahl der Transistoren, die auf einem IC integriert werden können, verdoppelt sich alle 18 Monate. SpÀter angepasst auf alle zwei Jahre.

  • Stufen des Systemaufbaus
  • Arten von Befehlssatzarchitekturen

    Die Befehlssatzarchitektur (ISA) beschreibt welche Instruktionen und Register ein Prozessor zur VerfĂŒgung hat

    • CISC

      Complex Instruction Set Computer

      • Aus einer Zeit, in der von Hand Assembly geschrieben wurde
      • Einzelne Instruktionen implementieren komplexe FunktionalitĂ€t, nahe an Konstrukten höherer Sprachen
      • Mikroprogrammierte Implementierung des Steuerwerks
      • Variables Befehlsformat und BefehlslĂ€nge
    • RISC

      Reduced Instruction Set Computer

      • Nur grundsĂ€tzliche Maschinenbefehle
      • Einheitliches und festes Befehlsformat
      • Load/Store-Architektur
        • Befehle arbeiten auf Registeroperanden
        • Explizite Lade- und Speicherbefehle
      • Einzyklus Maschinenbefehle
      • Ermöglicht Compileroptimierungen
  • RISC ISA Pipeline
  • Definition Rechnerarchitektur (Disziplin)

    Ingenieurwissenschaftliche Disziplin, die bestehende und zukĂŒnftige Rechenanlagen

    • beschreibt, 📝
    • vergleicht, ⚖
    • beurteilt, 👍👎
    • verbessert ❀‍đŸ©č und
    • entwirft. ⚙
  • Was versteht man unter dem Familienkonzept fĂŒr Rechnerstrukturen?

    Rechnerstrukturen der gleichen Familie teilen sich eine ISA, sodass Programme untereinander Kompatibel sind.

Grundlagen des Entwurfs von Rechenanlagen

  • Einsatzgebiete fĂŒr Rechnerstrukturen
    • Eingebettete Systeme (IoT)
    • Desktop Rechner
    • Mobile Rechner
    • Server
  • Definition Leistung P

    Energie E, Leistung P und Zeit t

    P=EtP=\frac{E}{t}ï»ż

    Leistung bezeichnet die aufgenommene bzw. verbrauchte Energie pro Zeit

  • Was versteht man unter der elektrischen Leistungsdichte?

    Verlustleistung pro FlĂ€che (Watt/cmÂČ)

  • Was ist ein Die?

    Klein geschnittener Wafer. Wafer ist meistens kreisrund. Die ist rechteckig.

  • Entwurfskriterien
    • ZuverlĂ€ssigkeit

      Bezeichnet die FÀhigkeit eines Systems, wÀhrend einer vorgegebenen Zeitdauer bei zulÀssigen Betriebsbedingungen die spezifizierte Funktion zu erbringen.

      • Überlebenswahrscheinlichkeit R(t)

        Gibt an, mit welcher Wahrscheinlichkeit ein zu Beginn (also zum Zeitpunkt t=0) fehlerfreies System bis zum Zeitpunkt t ununterbrochen fehlerfrei bleibt

        R(t)=Ns(t)NR(t) = \frac{N_s(t)}{N}

        Ns(t)N_s(t)ï»ż — Anzahl der bis Anzahl der Komponenten, die bis zum Zeitpunkt t ĂŒberleben

        N — Gesamtzahl der Komponenten

        R(t)=1−FL(t)R(t) = 1-F_L(t)
      • MTTF

        mean time to failure

        • bezeichnet die mittlere Zeitdauer bis zum Ausfall
        • Sie wird mithilfe der Überlebenswahrscheinlichkeit R(t) berechnet, Erwartungswert
      • FIT

        (failures in time), Ausfallrate

        1MTTF⁥\frac{1}{\operatorname{MTTF}}ï»ż

        Anzahl der AusfĂ€lle pro10910^9ï»ż Stunden

      • MTTR

        bezeichnet die mittlere Instandsetzungsdauer

      • MTBF

        mean time between failures

        bezeichnet die mittlere Zeitdauer zwischen zwei AusfÀllen

        MTBF⁥=MTTF⁥+MTTR⁥\operatorname{MTBF}=\operatorname{MTTF}+\operatorname{MTTR}ï»ż

      • (Punkt-)VerfĂŒgbarkeit

        Ist ein Maß, dass eine reparierbare Einheit zum Zeitpunkt t funktionsfĂ€hig ist, im Hinblick auf den Wechsel zwischen fehlerfreien und fehlerbehafteten Zustand

        v=MTTF⁥MTTF⁥+MTTR⁥v = \frac{\operatorname{MTTF}}{\operatorname{MTTF}+\operatorname{MTTR}}ï»ż

      • Ausfallrate
        • Die Ausfallrate bezeichnet den Anteil der in einer Zeiteinheit ausfallenden Komponenten bezogen auf den Anteil der noch fehlerfreien Komponenten
        • Eine Komponente kann zum Zeitpunkt t nur dann ausfallen, wenn sie bis dahin ĂŒberlebt hat
        z(t)=1R(t)⋅ddtFL(t)=−1R(t)⋅ddtR(t)z(t)= \frac{1}{R(t)} \cdot \frac{d}{d t} F_L(t) = -\frac{1}{R(t)} \cdot \frac{d}{d t} R(t)
    • Niedriger Energieverbrauch bzw. Leistungsaufnahme
      • Thermal Design Power (TDP): Maximale Verlustleistung in Watt unter Volllast
      • Verlustleistung hĂ€ngt von Last ab
      • Berechnung der maximalen Verlustleistung

        = Maximal zulÀssige Versorgungsspannung x höchster Stromverbrauch

      • Ausrichten der KĂŒhlung nach dem TDP-Wert
      • Dynamic Voltage-Frequency Scaling (DVFS)

        Techniken zur Verbesserung der Energieeffizienz: FĂŒr PMDs, Laptops, oder Server gibt es Perioden mit geringer AktivitĂ€t, sodass es nicht notwendig ist, mit höchsten Taktfrequenzen und Spannungen zu arbeiten

      • Zusammenhang Leistungsaufnahme und Taktfrequenz

        P∌fP\sim fï»ż

      • Zusammenhang Leistungsaufnahme und Versorgungsspannung

        P∌Vdd2P \sim V_{dd}^2ï»ż und damitP∌Vdd2⋅fP \sim V_{dd}^2\cdot fï»ż

      • CMOS-Schaltung: Leistungsaufnahme
        • Dynamischer Leistungsverbrauch (bei ZustandsĂ€nderung)
        Ptotal=Pswitching+Pshortcircuit+Pstatic+PleakageP_\text{total}=P_\text{switching}+P_\text{shortcircuit}+P_\text{static}+P_\text{leakage}
        • PswitchingP_\text{switching}ï»ż

          Laden oder Schalten einer kapazitiven Last

          Pswitching=Ceff⋅Vdd2⋅fP_\text{switching} = C_\text{eff} \cdot V^2_\text{dd}\cdot f
          • CeffC_\text{eff}ï»ż

            effektive KapazitÀt

            Ceff=C⋅aC_\text{eff} = C \cdot a
            • a: Wie viele Zustandswechsel (von 1 nach 0 oder umgekehrt) passieren im Schnitt pro Takt
        • PshortcicuitP_\text{shortcicuit}ï»ż

          Leistungsverbrauch wĂ€hrend des Übergangs am Ausgang in einem CMOS Gatter, wenn sich die EingĂ€nge Ă€ndern. WĂ€hrend des Wechsels des Eingangssignals tritt eine ĂŒberlappende LeitfĂ€higkeit der nMOS und pMOS-Transistoren auf.

          • ImeanI_\text{mean}ï»ż: mittlerer Strom wĂ€hrend des Wechsels des Eingangssignals
          Pshorcicuit=Imean⋅VddP_\text{shorcicuit} = I_\text{mean} \cdot V_\text{dd}
        • PstaticP_\text{static}ï»ż Bei CMOS konzeptuell nicht vorhanden
        • PleakageP_\text{leakage}ï»ż Leistungsverbrauch durch Kriechströme

          Bei realen CMOS-Schaltungen kommt zu dem Stromfluss beim Wechsel des logischen Pegels ein weiterer stÀndiger Stromfluss hinzu: Leckströme (Leakage)

          • WiderstĂ€nde zwischen den Leiterbahnen sind nicht unendlich hoch
          • Transistoren sperren nicht perfekt
          • Leckströme wachsen mit zunehmender Integrationsdichte
          • Bei Integrationsdichten mit Strukturen kleiner als 100 nm kann die Leistungsaufnahme aufgrund von Leckströmen nicht mehr vernachlĂ€ssigt werden
      • Pschalt\mathbb{P}_{\text{schalt}}ï»ż
        Pschalt=2⋅PAusgang=1⋅(1−PAusgang=1)\mathbb{P}_{\text{schalt}} = 2\cdot \mathbb{P}_{\text{Ausgang}=1}\cdot(1-\mathbb{P}_{\text{Ausgang}=1})
    • Kosten
      • Entwurfskosten und Herstellungskosten: Herstellungskosten sinken im Lauf der Zeit
      • Betriebskosten
      • Kosten eines Dies

        Wafer sind rund, da sie gezogene Einkristalle sind. Diese lassen sich nicht anders produzieren.

         Kosten des Dies = Kosten des Wafers  Dies pro Wafer ⋅ Ausbeute \text { Kosten des Dies }=\frac{\text { Kosten des Wafers }}{\text { Dies pro Wafer } \cdot \text { Ausbeute }}ï»ż

         Dies pro Wafer =π⋅(12⋅ Durchmesser des Wafers )2 Flašche des Dies −π⋅ Durchmesser des Wafers 2⋅ Flašche des Dies \text { Dies pro Wafer }=\frac{\pi \cdot\left(\frac{1}{2} \cdot \text { Durchmesser des Wafers }\right)^{2}}{\text { FlĂ€che des Dies }}-\frac{\pi \cdot \text { Durchmesser des Wafers }}{\sqrt{2 \cdot \text { FlĂ€che des Dies }}}ï»ż

         Ausbeute = Wafer Ausbeute ⋅1(1+ Defekte pro Flašcheneinheit ⋅ Die Flašche )N\text { Ausbeute }=\text { Wafer Ausbeute } \cdot \frac{1}{(1+\text { Defekte pro FlĂ€cheneinheit } \cdot \text { Die FlĂ€che })^{\mathrm{N}}}ï»ż

        NNï»ż: Maß fĂŒr die KomplexitĂ€t des Herstellungsprozesses

        Die Kosten pro Chip wachsen ungefÀhr mit der Quadratwurzel der Chip-FlÀche. Der Entwickler hat einen Einfluss auf die Chip-FlÀche und daher auf die Kosten, je nachdem welche Funktionen auf dem Chip integriert werden und durch die Anzahl der I/O Pins

      • Kosten eines integriertem Schaltkreis (IC)
        cost⁡IC =cost⁡die +cost⁡dii − test +cost⁡packaging Yfinal \operatorname{cost}_{\text {IC }}=\frac{\operatorname{cost}_{\text {die }}+\operatorname{cost}_{\text {dii }- \text { test }}+\operatorname{cost}_{\text {packaging }}}{Y_{\text {final }}}
    • Randbedingung: Technologische Entwicklung / Performance
      • Prozessor
        • Strukturbreiten
        • Integrationsdichte
        • Chip-FlĂ€che
      • Speicher
        • DRAM SpeicherkapazitĂ€t
        • Flash (SSD) (8-10x billiger/Bit als DRAM)
        • MagnetspeicherkapazitĂ€t: 200-300x billiger/Bit als DRAM
      • Erreichbare Taktfrequenz
        • Flacht ab

Bewertung von Rechensystemen

Einfache Hardwaremaße

  • CPU-Zeit einer ProgrammausfĂŒhrung

    Texe=IC⋅CPI⋅TCT_{\text{exe}} = IC\cdot CPI \cdot T_Cï»ż

    ICICï»ż Anzahl der ausgefĂŒhrten Befehle

    CPICPIï»ż Anzahl der Zyklen pro Instruktion (Maß fĂŒr die Effizienz einer Architektur)

    TCT_Cï»ż Zykluszeit

  • Instruktionen pro Zyklus

    IPC=1CPIIPC = \frac{1}{CPI}ï»ż

  • MIPS

    Millions of Instructions Per Second

    MIPS=Anzahl der ausgefušhrten Instuktionen106⋅AusfušhrungszeitMIPS = \frac{\text{Anzahl der ausgefĂŒhrten Instuktionen}}{10^6\cdot \text{AusfĂŒhrungszeit}}ï»ż

  • MFLOPS

    Es werden nur Fließkommaoperationen gezĂ€hlt. Kein Kontrollfluss, kein Speicherzugriff

    MFLOPS=Anzahl der ausgefušhrten Gleitkommaoperationen106⋅AusfušhrungszeitMFLOPS = \frac{\text{Anzahl der ausgefĂŒhrten Gleitkommaoperationen}}{10^6\cdot\text{AusfĂŒhrungszeit}}ï»ż

  • Probleme von einfachen Hardware-Maßzahlen
    • AbhĂ€ngigkeit vom Programm/Befehlssequenz
    • AbhĂ€ngigkeit von ISA: Kein Vergleich unterschiedlicher Architekturen möglich
    • MIPS/MFLOPS Angaben von Herstellern oft nur best-case-Annahme: Theoretische Maximalleistung

Benchmarks

SPEC: Organisation, die reale numerische und nicht numerische Programme bestimmt, mit denen ein Benchmark gemacht werden soll.

  • Spec-Ratio
    treftexec\frac{t_{\text{ref}}}{t_{\text{exec}}}
  • Geometrisches Mittel der SPECratios
    ∏i=1nSPECratio⁡in\sqrt[n]{\prod_{\mathrm{i}=1}^{\mathrm{n}} \operatorname{SPECratio}_i}
  • Bedienzeiten und Durchsatz

    X = Zugriffszeit + Übertragungszeit

    Dmax=1XD_{max} = \frac{1}{X}
  • Auslastung

    TatsÀchlicher Durchsatz durch tatsÀchliche Auslastung

Monitore

  • Hardware Monitore
    • Performance Counter in der CPU integriert
    • Kann von einer API ausgelesen werden
    • Aufzeichnung von prozessorinternen Ereignissen
    • UnabhĂ€ngige physikalische GerĂ€te, keine Beeinflussung der Anlage
  • Software Monitore

    Einbau in das Betriebssystem mit BeeintrÀchtigung der normalen BetriebsverhÀltnisse

  • Arten von Aufzeichnungen mit Monitoren
    • Kontinuierlich oder sporadisch
    • Gesamtdatenaufzeichnung (Tracing)
    • Realzeitauswertung
    • UnabhĂ€ngiger Auswertungslauf (Post Processing)

Modelltheoretische Verfahren

  • Analytische Methoden
    • Warteschlangenmodell
      • Gesetz von Little

        Voraussetzung statistisches Gleichgewicht

        L=λ⋅tL = \lambda \cdot tï»ż bzw.Q=λ⋅wQ=\lambda\cdot wï»ż Die Komponenten werden in disjunkte Schichten partitioniert

        • LLï»ż: mittlere Anzahl von AuftrĂ€gen im Wartesystem
        • QQï»ż: mittlere WarteschlangenlĂ€nge
        • λ\lambdaï»ż: mittlere Ankunftsrate
        • ttï»ż: mittlere Verweilzeit (Gesamtheit der Zeit, die ein Auftrag im Wartesystem verbringt)
        • wwï»ż: mittlere Bedienzeit (Zeit, die ein Auftrag in der Warteschlange verbringt)
    • Petrinetze
    • Diagnosegraphen
  • Arten von Simulationen
    • User-Level Simulation
    • Full-System Simulation

      Erkennt zum Beispiel auch fehlenden Hardwaresupport (viele Syscalls sind bottleneck)

    • Funktionale Simulation

      Modelliert nur die FunktionalitĂ€t (ohne BerĂŒcksichtigung der Mikroarchitektur)

      Emulation der ISA (z.B. Unicorn)

    • Zyklen genaue Simulation
      • Mikroarchitekturblöcke sind parametrisierbar
      • Schwer zu bauen
    • Trace-driven Simulation

      Simuliere nur die relevanten Aspekte. z.B. Caches

    • Execution-driven Simulation

ZuverlĂ€ssigkeit, VerfĂŒgbarkeit und Fehlertoleranz

  • Definition ZuverlĂ€ssigkeit

    bezeichnet die FÀhigkeit eines Systems, wÀhrend einer vorgegebenen Zeitdauer bei zulÀssigen Betriebsbedingungen die spezifizierte Funktion zu erbringen.

  • Definition Sicherheit

    Bezeichnet das Nicht-Vorhandensein einer Gefahr fĂŒr Menschen oder Sachwerte. Unter einer Gefahr ist ein Zustand zu verstehen, in dem (unter anzunehmenden Betriebsbedingungen) ein Schaden zwangslĂ€ufig oder zufĂ€llig entstehen kann, ohne dass ausreichende Gegenmaßnahmen gewĂ€hrleistet sind. Im Gegensatz zur ZuverlĂ€ssigkeit schließt es die Anwendung mit ein

  • Definition Fehlertoleranz

    Fehlertoleranz bezeichnet die FÀhigkeit eines Systems, auch mit einer begrenzten Anzahl fehlerhafter Subsysteme die spezifizierte Funktion (bzw. den geforderten Dienst) zu erbringen. Fehlertoleranz ist eine Technik, die die ZuverlÀssigkeit eines Systems erhöht.

  • Fehler Wirkungskette

    Fehler / Defekt (fault) → Fehlzustand (error) → Funktionsausfall (failure)

  • Unterschied ZuverlĂ€ssigkeit und Fehlertoleranz

    ZuverlÀssigkeit ist ein Optimierungsziel beim Systementwurf, wohingegen Fehlertoleranz eine Technik zur Erhöhung der ZuverlÀssigkeit ist

  • Fehlerklassifikationsachsen
    • Fehlerklassifikation nach Ursachen
      • Fehler beim Entwurf
      • Herstellungsfehler
      • Betriebsfehler
    • Fehlerklassifikation nach Entstehungsort
      • Hardwarefehler
      • Softwarefehler
    • Fehlerklassifikation nach Dauer
      • Permanente Fehler
      • TemporĂ€re/sporadische/intermittierende Fehler
        • Können zu permanenten Fehlern fĂŒhren
      • Transiente Fehler
        • FĂŒhren nicht zu permanenten Fehlern
  • Ausfallverhalten: Arten von AusfĂ€llen
    • Teilausfall: Von einer fehlerhaften Komponente fallen eine oder mehrere, aber nicht alle Funktionen aus
    • Unterlassungsausfall: Eine fehlerhafte Komponente gibt eine Zeit lang keine Ergebnisse aus; wenn jedoch ein Ergebnis ausgegeben wird, dann ist dieses korrekt
    • Anhalteausfall: Eine fehlerhafte Komponente gibt nie mehr ein Ergebnis aus
    • Haftausfall: Eine fehlerhafte Komponente gibt stĂ€ndig den gleichen Ergebniswert aus
    • BinĂ€rstellenausfall: Ein Fehler verfĂ€lscht eine oder mehrere BinĂ€rstellen des Ergebnisses
  • Ausfallverhalten: Arten von Systemen
    • Fail-stop-System: Ein System, dessen AusfĂ€lle nur AnhalteausfĂ€lle sind
    • Fail-silent-System: Ein System, dessen AusfĂ€lle nur UnterlassungsausfĂ€lle sind
    • Fail-safe-System: Ein System, dessen AusfĂ€lle nur unkritische AusfĂ€lle sind
  • Struktur-Funktions-Modell
    • Das Struktur-Funktions-Modell ist ein gerichteter Graph, dessen Knoten die Komponenten und dessen Kanten die Funktionen eines Systems reprĂ€sentieren
      • Eine gerichtete Kante von der Komponente A zur Komponente B bedeutet, dass A eine Funktion erbringt, die von B benutzt wird
    • Komponenten können zu einer Komponentenmenge zusammengefasst und als eine Einheit betrachtet werden
    • Komponenten können beliebige HW oder SW Komponenten darstellen
      • Prozessoren, Speicher, Teile des Betriebssystems, Teile der Anwendung etc.
  • Schichtenmodell
    • Ist eine AusprĂ€gung des Struktur-Funktions-Modells
    • Die Komponenten werden in disjunkte Schichten partitioniert
    • Funktionszuordnungen sind nur von niedrigeren an höhere Schichten (eine Halbordnung) und innerhalb von Schichten möglich
  • BinĂ€res Fehlermodell
    • Systemfunktion
      • Systemfunktion ist eine bool’sche Formel der Komponenten
      • Sie gibt in AbhĂ€ngigkeiten der Komponenten an, ob das System fehlerfrei ist
      • Eine Komponente ist genau dann wahr, wenn sie funktioniert
    • ZuverlĂ€ssigkeitsblockdiagramm
    • Fehlerbaum = Strukturbaum
    • Wozu wird ein Strukturbaum ĂŒblicherweise verwendet?

      Ein Strukturbaum wird verwendet, um einen Systemfehler auf Fehler der einzelnen Komponenten zurĂŒckzufĂŒhren.

  • Badewannenkurve

    Badewannenkurve: Ausfallrate ĂŒber die Lebenszeit eines Systems

    • FrĂŒhphase – Ausfallrate exponentiell abfallend (InitialausfĂ€lle)
    • Betriebsphase – nahezu konstante Ausfallrate
    • SpĂ€tphase – Ausfallrate exponentiell ansteigend (Alterungseffekte)

  • Redundanz eines Parallelsystems

    Parallelsystem (Einfachsystem mit ungenutzter oder fremdgenutzter Redundanz)

  • Redundanz eines Seriensystems
  • Arten von Redundanz
    • Dynamische Redundanz
      • Bezeichnet das Vorhandensein von redundanten Mitteln, die erst nach Auftreten eines Fehlers aktiviert werden, um eine ausgefallene Nutzfunktion zu erbringen
      • Typisch fĂŒr dynamische strukturelle Redundanz ist die Unterscheidung in PrimĂ€r- und Ersatzkomponenten (bzw. SekundĂ€r- oder Reservekomponenten)
      • Ungenutzte Redundanz

        Ersatzkomponenten fĂŒhren keine sonstigen Funktionen aus und bleiben bis zur fehlerbedingten Aktivierung passiv

      • Gegenseitige Redundanz

        Ersatzkomponenten erbringen die von einer anderen Komponente zu unterstĂŒtzenden Funktionen, die Komponenten stehen sich gegenseitig als Reserve zur VerfĂŒgung

      • Fremdgenutzte Redundanz

        Ersatzkomponenten erbringen nur Funktionen, die nicht zum betreffenden Subsystem gehören und im Fehlerfall bei niedrigerer Priorisierung ggf. verdrÀngt werden

    • Statische Redundanz
      • Bezeichnet das Vorhandensein von redundanten Mitteln, die wĂ€hrend des gesamten Einsatzzeitraums die gleiche Nutzfunktion erbringen.
      • z.B. m-aus-n-System
  • m-aus-n-System

    Das System ist funktionsfÀhig, wenn m der n Komponenten funktionieren.

  • Funktionswahrscheinlichkeit eines m-aus-n-Systems
    φmn=∑k=nm(mk)⋅φ(K)k⋅(1−φ(K))(m−k)\varphi_m^n=\sum_{k=n}^m\left(\begin{array}{c} m\\ k \end{array}\right) \cdot \varphi(K)^k \cdot (1-\varphi(K))^{(m-k)}
    • Binomialkoeffizient

      Mit dem Binomialkoeffizienten bestimmt man die Anzahl der Möglichkeiten aus einer Menge mit n Elementen, eine Teilmenge mit k Elementen auszuwĂ€hlen. Das Ziehen selbst erfolgt ohne ZurĂŒcklegen und ohne Beachtung der Reihenfolge

      (nk)=n!k!(n−k)!{n \choose k} = \frac{n!}{k!(n-k)!}

Formen des Parallelismus und Klassifizierung von Rechnerarchitekturen

  • NebenlĂ€ufigkeit

    Eine Maschine arbeitet nebenlÀufig, wenn die Objekte vollstÀndig gleichzeitig abgearbeitet werden.

  • Pipelining

    Pipelining auf einer Maschine liegt dann vor, wenn die Bearbeitung eines Objektes in Teilschritte zerlegt und diese in einer sequentiellen Folge (Phasen der Pipeline) ausgefĂŒhrt werden. Die Phasen der Pipeline können fĂŒr verschiedene Objekte ĂŒberlappt abgearbeitet werden. (Bode, 95)

  • Ebenen der ParallelitĂ€t
    • Programmebene
      • Beispiel Unix-Pipeline
    • Prozessebene
      • Programm wird in Anzahl parallel ausfĂŒhrbarer Prozesse zerlegt
      • Synchronisation und Kommunikation
    • Blockebene
      • Threads
      • Anweisungsblöcke
        • Z.B. Innere und Ă€ußere parallele Schleifen in FORTRAN-Dialekten oder MPI
    • Anweisungs- oder Befehlsebene
      • Umordnen und Parallelisieren der Befehle durch Compiler und CPU
    • Suboperationsebene
      • Elementare Anweisung wird durch Compiler oder durch die Maschine in Suboperationen aufgebrochen, die parallel ausgefĂŒhrt werden
        • Microcode in CISC
      • Vektoroperationen
  • GranularitĂ€t ParallelitĂ€t

    Die Körnigkeit oder GranularitÀt (grain size) ergibt sich aus dem VerhÀltnis von Rechenaufwand zu Kommunikations- oder Synchronisationsaufwand. Sie bemisst sich nach der Anzahl der Befehle in einer sequentiellen Befehlsfolge.

    • Programm-, Prozess- und Blockebene werden hĂ€ufig auch als grobkörnige (large grained) ParallelitĂ€t
    • die Anweisungsebene als feinkörnige (finely grained) ParallelitĂ€t bezeichnet.
    • Selten bezeichnet mittelkörnig (medium grained) die ParallelitĂ€t auf Blockebene
  • Klassifizierung nach M. Flynn

    Viele Rechner sind Kombinationen verschiedenen Kategorien, deshalb ist die Klassifizierung wenig aussagekrÀftig.

    • SISD Single Instruction – Single Data
      • Uniprozessor
    • SIMD Single Instruction – Multiple Data
      • Vektorrechner, Feldrechner
    • MISD Multiple Instructions – Single Data
      • In der Praxis untypisch
    • MIMD Multiple Instructions – Multiple Data
      • Multiprozessor
  • Parallelisierungsprozess

Prozessortechniken

RISC und SuperskalaritÀt

  • Pipelining RISC vs. CISC

    Nur RISC erlaubt Pipelining, da sich CISC-Befehle zu unterschiedlich sind, um zerlegt zu werden

  • Leistungsaspekte einer Pipeline
    • AusfĂŒhrungszeit eines Befehls (Latenz)
    • AusfĂŒhrungszeit T eines Programms
      • Sequenzielle AusfĂŒhrungT=n⋅kT=n\cdot kï»ż
      • Parallele AusfĂŒhrungT=n+k−1T=n+k-1ï»ż
    • BeschleunigungS=n⋅kn+k−1S=\frac{n\cdot k}{n+k-1}ï»ż
  • Vor- und Nachteile Verfeinerung der Pipeline-Stufen
    • Weniger Logik-Ebenen pro Pipeline-Stufe
    • Erhöhung der Taktrate
    • FĂŒhrt aber auch zu einer Erhöhung der AusfĂŒhrungszeit (Latenz) pro Instruktion
    • „Superpipelining“
  • Arten von Pipeline-Konflikten

    Situationen, die verhindern, dass die nĂ€chste Instruktion im Befehlsstrom im zugewiesenen Taktzyklus ausgefĂŒhrt wird

    • Strukturkonflikte
      • Ergeben sich aus Ressourcenkonflikten
      • Die Hardware kann nicht alle möglichen Kombinationen von Befehlen unterstĂŒtzen, die sich in der Pipeline befinden können
      • Beispiel: Gleichzeitiger Schreibzugriff zweier Befehle auf eine Registerdatei mit nur einem Schreibeingang
    • Datenkonflikte
      • Ergeben sich aus DatenabhĂ€ngigkeiten zwischen Befehlen im Programm
      • Konflikte aufgrund einer echten DatenabhĂ€ngigkeit
        • Instruktion benötigt das Ergebnis einer vorangehenden und noch nicht abgeschlossenen Instruktion in der Pipeline
      • Konflikte aufgrund von NamensabhĂ€ngigkeiten
        • Wiederverwendung von Registernamen
        • FrĂŒherer Befehl wird aufgehalten und schreibt aber ins gleiche Register wie spĂ€terer Befehl, zwischen denen aber keine DatenabhĂ€ngigkeit besteht.
        • In diesem Fall mĂŒssen Registernamen getauscht werden
    • Steuerkonflikte

      Treten bei Verzweigungsbefehlen und anderen Instruktionen, die den BefehlszÀhler verÀndern, auf

  • Auflösung der Pipeline-Konflikte
    • Pipeline Stall
    • Pipeline Bubble
    • Pipeline Flushes
    • Umsortierung des Codes
    • Forwarding
  • Speedup durch k-stufigen Pipeline ĂŒber n Befehle
    nkn+k−1\frac{nk}{n+k-1}

Parallelismus auf Instruktionsebene

  • Dynamische vs. statische NebenlĂ€ufigkeit

    Dynamisch: Der Prozessor sorgt zur Laufzeit fĂŒr NebenlĂ€ufigkeit, z.B. Superskalartechnik

    Statisch: Der Compiler wĂ€hlt nebenlĂ€ufige Instruktionen fĂŒr das Programm, der Prozessor fĂŒhrt diese einfach aus, ohne weitere Entscheidungen zu treffen, z.B. VLIW (Very Long Instruction Word), EPIC (Explicitly Parallel Instruction Computer)

  • Eigenschaften Superskalar-Prozessor
    • Viel-stufige Befehlspipeline
    • Mehrere voneinander unabhĂ€ngige AusfĂŒhrungseinheiten
    • Zur Laufzeit werden pro Takt mehrere Befehle aus einem sequenziellen Befehlsstrom den Verarbeitungseinheiten zugeordnet und aufgefĂŒhrt
    • Dynamische Erkennung und Auflösung von Konflikten zwischen Befehlen im Befehlsstrom ist Aufgabe der Hardware
  • Aufbau Superskalar-Prozessor
  • Warum muss ein Reordering stattfinden
    • Traps und Interrupts
    • Memory mapped IO
  • Superskalartechnik bei CISC-Architekturen
    • Aufteilung der Dekodierung in mehrere Schritte
    • Bestimmung der Grenzen der geholten Befehle
    • Dekodierung der Befehle
    • Generierung einer Folge von RISC-Ă€hnlichen Operationen mithilfe dynamischer Übersetzungstechniken
    • Ermöglicht effizientes Pipelining und superskalare Verarbeitung
    • Beispiel Intel Pentium- und AMD Athlon-Familie
  • Superskalarpipeline
    • Befehlsholphase (IF)
      • Holen mehrerer Befehle aus dem Befehls-Cache in den Befehlsholpuffer
      • Anzahl der Befehle, die geholt werden, entspricht typischerweise der Zuordnungsbandbreite
      • Welche Befehle geholt werden hĂ€ngt von der Sprungvorhersage ab
      • BTAC

        Branch Target Address Cache

        • Speichert die Adresse der Verzweigung und das entsprechende Sprungziel
        • Realisierung als Direct Mapped Cache
        • Vor der ID-Phase, deshalb noch nicht klar, um welche Instruktion es sich handelt.
        • Tag und Index ist eine Kombination von Adresse der Instruktion und Instruktionsbytes
      • BHT
        • Branch History Table (BHT)
        • Festhalten des Verhaltens der Sprungbefehle (T, NT) wĂ€hrend der AusfĂŒhrung des Programms: PrĂ€diktoren
        • Vorhersage des Verhaltens eines geholten Sprungbefehls
      • Statische v.s. dynamische Sprungvorhersage
        • Statische Sprungvorhersage (PrĂ€dikation)
          • Die Richtung der Vorhersage ist fĂŒr einen Befehl immer gleich
          • FĂŒr superskalare Prozessorarchitekturen zu unflexibel und nicht geeignet
        • Dynamische Sprungvorhersage (PrĂ€diktion)
          • Die Verzweigungsrichtung hĂ€ngt von der Vorgeschichte der Verzweigung ab
          • BerĂŒcksichtigung des Programmverhaltens
          • Genaue Vorhersagen möglich
          • Hoher Hardware Aufwand!
      • 2-Bit PrĂ€diktor (SĂ€ttigungszĂ€hler)
      • 2-Bit PrĂ€ditor (HysteresezĂ€hler)

        Vermeidet ”Flattern“ zwischen Weakly-ZustĂ€nden

      • Problemfall 2-Bit PrĂ€diktor

        Alternierendes Nehmen und Nichtnehmen von SprĂŒngen (ungerade Zahlen)

      • (m,n)-KorrelationsprĂ€diktor
    • Dekodierphase (ID)
      • NamensabhĂ€ngigkeit

        Treten auf, wenn zwei Instruktionen dasselbe Register, dieselbe Speicherzelle (den Namen) verwenden, aber kein Datenfluss zwischen den Befehlen mit dem Namen verbunden ist GegenabhÀngigkeit (Anti dependency)

        ADD R2,R3,R4
        ...
        XOR R3,R5,R6

        AusgabeabhÀngigkeit (Output dependency)

        ADD R2,R3,R4
        ...
        XOR R2,R5,R6
      • Registerumbenennung
        • Dynamische Umbenennung der Operanden- und Ergebnisregister
        • Abbildung der nach außen hin sichtbaren Architekturregister in interne physikalische Register
        • Zur Laufzeit wird fĂŒr jeden Befehl das jeweils spezifizierte Zielregister auf ein noch nicht belegtes physikalisches Register abgebildet
        • Nachfolgende Befehle, die dasselbe Architekturregister als Operandenregister verwenden, erhalten das entsprechende physikalische Register
        • Anzahl der Umbenennungsregister kann die Anzahl der Architekturregister ĂŒberschreiten
        • Auflösen von Konflikten aufgrund von NamensabhĂ€ngigkeiten
    • Zuordnungsphase (Dispatch)
      • ZufĂŒhrung der im Befehlsfenster wartenden Befehle zu den AusfĂŒhrungseinheiten
      • Dynamische Auflösung der Konflikte aufgrund von echten DatenabhĂ€ngigkeiten und Ressourcenkonflikten
      • Echte DatenabhĂ€ngigkeit
        • Ein Befehl j ist datenabhĂ€ngig von einem Befehl i, wobei der Befehl i im Programm vor dem Befehl j steht, wenn eine der folgenden Bedingungen gilt:
          • Befehl i produziert ein Ergebnis, das von Befehl j verwendet wird, oder
          • Befehl j ist datenabhĂ€ngig von Befehl k und Befehl k ist datenabhĂ€ngig von Befehl i (AbhĂ€ngigkeitskette)
        Befehl i: ADD R2,R3,R4
        ...
        Befehl j: SUB R5,R2,R6
      • Reservierungstabellen

        Zum Auflösen von Lese-nach-Schreib-Konflikt (Read-After-Write, RAW)

        • liegen vor den Verarbeitungseinheiten
        • Zuordnung eines Befehls an Umordnungspuffer kann nur erfolgen, wenn ein freier Platz vorhanden ist, ansonsten mĂŒssen die nachfolgenden Befehle warten (Ressourcenkonflikt)
    • BefehlsausfĂŒhrung (Ex)
    • Fertigstellen (Complete)
      • Eine Instruktion beendet ihre AusfĂŒhrung, wenn das Ergebnis fĂŒr nachfolgende Befehle bereitsteht (Forwarding, Puffer)
      • Completion heißt: eine BefehlsausfĂŒhrung ist „vollstĂ€ndig“
      • Erfolgt unabhĂ€ngig von der Programmordnung!
    • RĂŒckordnungsstufe (Retire)
      • Commitment
        • Nach der VervollstĂ€ndigung beenden die Befehle ihre Bearbeitung (Commitment), d.h. die Befehlsresultate werden in der Programmreihenfolge gĂŒltig gemacht
        • Ergebnisse werden in den Architekturregistern dauerhaft gemacht, d.h. aus den internen Umbenennungsregistern (Schattenregistern) zurĂŒckgeschrieben
      • Bedingungen fĂŒr Commitment
        • Die BefehlsausfĂŒhrung ist vollstĂ€ndig (Completion)
        • Alle Befehle, die in der Programmordnung vor dem Befehl stehen, haben bereits ihre Bearbeitung beendet oder beenden ihre Bearbeitung im selben Takt
        • Der Befehl hĂ€ngt von keiner Spekulation ab
        • Keine Unterbrechung ist vor oder wĂ€hrend der AusfĂŒhrung aufgetreten (precise interrupts)
  • Warum ist Sprungvorhersage schon in IF möglich?

    Nachdem der Sprungbefehl das erste Mal dekodiert wurde, wird die Adresse des Sprungbefehls im Branch Target Address Cache gespeichert, wodurch bereits an der Befehlsadresse erkannt werden kann, ob es sich um ein Sprungbefehl handelt.

  • Backward Propagation of Stalling

    Stalling bezeichnet eine Methode zur Auflösung von Pipelinekonflikten durch das Anhalten der Pipeline. Dies verzögert ebenso die AusfĂŒhrung nachfolgender Befehle, wenn ein Überholen der wartenden Instruktion nicht erlaubt ist. Das Stalling setzt sich also durch die nachfolgenden Instruktionen fort.

  • Skalarpipeline vs. Supersklarpipeline

    Die Superskalar-Technik ermöglicht es (im Gegensatz zur skalaren Befehlspipeline), pro Takt mehrere Befehle den unabhĂ€ngigen AusfĂŒhrungseinheiten zuzuordnen und eine gleiche Anzahl von BefehlsausfĂŒhrungen pro Takt zu beenden.

Tomasulo-Verfahren

  • Zweck des Tomasulo-Verfahrens

    Auflösen von Datenkonflikten in der Zuordnungsphase (implementiert im IBM 360/91)

  • Aufbau des Umordungspuffer/Reservierungstabelle
    • Die Werte der zwei Quelloperanden (Src1, Src2)
    • Jeweils ein Flag fĂŒr jeden Operanden, das anzeigt, ob ein Operand verfĂŒgbar (Valid, Vld) ist (Vld1, Vld2)
    • Die Nummern (Namen, Tags) der Reservierungstabellen derjenigen Funktionseinheiten, welche die Quelloperanden fĂŒr die auszufĂŒhrende Operation liefern werden (RS1, RS2), falls der Operand noch berechnet wird
    • Einen Namen (destination tag) fĂŒr das Ziel (Dest)
  • Aufbau der Reservierungstabelle bei Tomasulo

VLIW

Compiler optimiert Zuteilung zu den Recheneinheiten

Parallelismus auf Blockebene

  • Parallelindex

    Wie viele Tasks/Instruktionen werden im Durchschritt gleichzeitig ausgefĂŒhrt

    I(n)=P(n)T(n)I(n) = \frac{P(n)}{T(n)}

    WobeiP(k)P(k)ï»ż die Anzahl der Operationen bei der AusfĂŒhrung aufkkï»ż Prozessoren angibt.

  • Beschleunigung (Speedup)

    S(n)=T(1)T(n)S(n)=\frac{T(1)}{T(n)}ï»ż

  • Effizienz
    E(n)=S(n)nE(n)=\frac{S(n)}{n}
  • Mehraufwand
    R(n)=P(n)P(1)R(n) = \frac{P(n)}{P(1)}

    WobeiP(k)P(k)ï»ż die Anzahl der Operationen bei der AusfĂŒhrung aufkkï»ż Prozessoren angibt.

  • Auslastung
    U(n)=I(n)n=R(n)E(n)=P(n)nT(n)U(n)=\frac{I(n)}{n}=R(n)E(n)=\frac{P(n)}{nT(n)}
    • Entspricht dem normierten Parallelindex I(n)
    • Gibt an, wie viele Operationen jeder Prozessor im Durchschnitt pro Zeiteinheit ausgefĂŒhrt hat
  • Gesetz von Amdahl
  • Annahmen fĂŒr das Gesetz von Amdahl

    Amdahl geht von einer festen ProblemgrĂ¶ĂŸe aus. Damit eine pessimistische SchĂ€tzung

  • GrĂŒnde fĂŒr einen superlinearen Speedup
    • Theorie: einen „superlinearen Speedup“ kann es nicht geben
    • Jeder parallele Algorithmus lĂ€sst sich auf einem Einprozessorsystem simulieren, indem in einer Schleife jeweils der nĂ€chste Schritt jedes Prozessors der parallelen Maschine emuliert wird
    • Ein „superlinearer Speed-up“ kann aber real beobachtet werden, z.B. bei:
      • Parallelem Backtracking (depth-first search, wo es im sequenziellen Fall quasi Zufall ist, ob der richtige Ast gewĂ€hlt wird)
      • Beim Programmlauf auf einem Rechner passen die Daten nicht in den Hauptspeicher des Rechners (hĂ€ufiger Seitenwechsel), aber: bei Verteilung auf die Knoten des Multiprozessors können die parallelen Programme vollstĂ€ndig in den Cache- und Hauptspeichern der einzelnen Knoten ablaufen
  • Probleme, die bei Parallelismus auftreten können
    • Verwaltungsaufwand (Overhead)
      • Steigt mit der Zahl der zu verwaltenden Prozessoren
    • Möglichkeit von Systemverklemmungen (deadlocks)
    • Möglichkeit von SĂ€ttigungserscheinungen
      • Können durch SystemengpĂ€sse (bottlenecks) verursacht werden

Vektorrechner und Feldrechnerprinzip

  • Was versteht man unter einem Vektorrechner?

    Unter einem Vektorrechner versteht man einen Rechner mit pipelineartig aufgebautem/n Rechenwerk/en zur SIMD-Verarbeitung von Arrays von Gleitpunktzahlen.

  • Wie können If-Anweisungen bei Vektorrechnern umgesetzt werden?

    Zur Umsetzung von IF-Anweisungen wird das Vektor-Mask-Register eingesetzt, das ermöglicht nur auf den auf 1 gesetzten EintrÀgen zu arbeiten.

  • SIMD

    Single Instruction Multiple Data

  • Vektor Stride

    Ablegen des Stride-Wertes in ein Allzweckregister

  • Was ist der Vorteil der Verkettung von Vektor-Pipelines?

    Die Ergebnisse einer Pipeline werden sofort der nĂ€chsten Pipeline zur VerfĂŒgung gestellt, wodurch die GesamtausfĂŒhrungszeit der Vektoroperationen reduziert wird.

Multiprozessoren

  • Konfigurationen von Multiprozessoren
  • Parallele Architekturmodelle
    • UMA
      • UMA: Uniform Memory Access
      • Gemeinsamer, zentraler, global adressierter Speicher
      • Gleiche Speicherzugriffszeit fĂŒr jeden Prozessor
      • Anlage von Speichermodulen fĂŒr parallelen Speicherzugriff
      • Skaliert nicht beliebig
    • NORMA
      • NORMA: No Remote Memory Access
      • Nachrichtengekoppelter (Shared-nothing-) Multiprozessor
      • Verteilter Speicher, verteilter Adressraum
      • Datenkommunikation ausschließlich ĂŒber Nachrichten möglich
      • Skaliert beliebig

    • NUMA
      • NUMA: Non-Uniform Memory Access
      • Distributed shared memory (DSM) multiprocessor
      • Globaler Adressraum ĂŒber Knotengrenzen: Zugriff auf entfernten Speicher ĂŒber load / store Operationen
      • Nicht einheitliche Zugriffszeit
      • Skaliert deutlich besser als UMA
      • CC-NUMA
        • Cache-Coherent Non-Uniform Memory Access
        • In HW implementiertes Cache-KohĂ€renzprotokoll
  • Schritte des Parallelisierungsprozess
  • OpenMP
    • Shared Memory Programmiermodell
  • Message Passing Interface (MPI)
    • Message Passing Programmiermodell
    • MPI ist ein Standard fĂŒr die nachrichtenbasierte Kommunikation in einem Multiprozessorsystem
    • Nachrichtenbasierter Ansatz gewĂ€hrleistet eine gute Skalierbarkeit
    • Bibliotheksfunktionen koordinieren die AusfĂŒhrung von mehreren Prozessen, sowie Verteilung von Daten, per Default keine gemeinsamen Daten
    • Single Program Multiple Data (SPMD) Ansatz
  • Cycle-by-Cycle Interleaving vs. Block Interleaving

    Bei Cycle-by-Cycle Interleaving wird in jedem Takt einer der ausfĂŒhrungsbereiten KontrollfĂ€den ausgewĂ€hlt und der nĂ€chste Befehle dieses Kontrollfadens ausgefĂŒhrt. Bei Block Interleaving werden die Befehle eines Kontrollfadens so lange ausgefĂŒhrt, bis eine Instruktion mit einer langen Latenzzeit ausgefĂŒhrt wird. Erst dann wird zu einem anderen Kontrollfaden gewechselt.

Grundlagen, Verbindungsnetze, LeistungsfÀhigkeit

  • NoC und SAN
    • Network on Chip (NoC)
      • Chip-Multiprozessor (CMP)
    • System / Storage Area Network (SAN)
      • Multiprozessor mit verteiltem Speicher (nachrichtenorientierter Multiprozessor)
      • Multiprozessor mit gemeinsamem Speicher
  • Aufbau eines Pakets
  • Hierarchische Aufteilung einer Message
    • Message: Die zu ĂŒbertragende Datenmenge
    • Message besteht aus ein oder mehreren Paketen
      • Paket hat feste LĂ€nge
      • Header, Payload, Error Code, Trailer
    • Paket besteht aus ein oder mehreren Flits (flow control units)
      • Flusskontrolle (soll gepuffert oder weitergeschickt werden?) passiert auf Ebene der Flits
    • Flit besteht aus ein oder mehreren Phits (physical transfer units)
      • Ein Phit ist genauso breit, wie die Links zwischen den Schaltelementen
  • Arten des Datentransfers (Schaltstrategie)
    • Durchschalte-/Leitungsvermittlung (Circuit switching)
      • Eigenschaft eines Netzes eine direkte Verbindung zwischen zwei oder mehreren Knoten eines Netzes zu schalten
      • Die physikalische Verbindung bleibt fĂŒr die gesamte Dauer der InformationsĂŒbertragung (Message) bestehen
        • Keine Pakete und Flits erforderlich, sondern nur Phits
          • Man kann aber trotzdem Pakete einfĂŒhren, um eine Zwischenebene fĂŒr z.B. Fehlerkorrektur/behandlung zu haben
        • Phits werden ohne Unterbrechung vom Sender zum EmpfĂ€nger ĂŒbertragen
        • Phits mĂŒssen keine Routing-Information mitfĂŒhren, da der Weg aufgebaut wird, bevor sie versendet werden
        • Vermeidet Routing-Overhead in jedem Schaltelement
        • Keine Netzwerkressource auf dem Kommunikationspfad ist fĂŒr andere Kommunikationen verfĂŒgbar, bis die gesamte Message am Ziel angekommen ist
    • Paketvermittlung
      • Pakete werden entsprechend eines Wegefindungsalgorithmus (routing) vom Absender zum EmpfĂ€nger geschickt
      • Zieladresse wird in jedem Knoten (Switch) gelesen und das Paket wird zum nĂ€chsten Knoten weitergeleitet, bis die Nachricht das Ziel erreicht
      • Je nach Routing-Verfahren kommen die Pakete einer Message nicht zwingend in der ‚richtigen‘ Reihenfolge (in-order) an
      • Die Ressourcen eines Schaltelements werden nur solange belegt wie sie benötigt werden
      • Falls ein Schaltelement belegt ist und der Weg eines anderen Pakets fĂŒhrt zu diesem Schaltelement, tritt ein Konflikt auf
      • Flusskontrolle
        • Strategie zur Auflösung des Konflikts bei einer Blockierung
        • Bestimmt, wann ein Paket von einem Schalter zu einem anderen Schalter ĂŒbertragen wird
        • Flit: Informationseinheit, auf die die Flusskontrolle angewendet wird
      • Store-and-forward
        • Ein Paket wird vollstĂ€ndig von Knoten zu Knoten ĂŒbertragen
          • Alle Teile eines Pakets mĂŒssen von einem Knoten empfangen worden sein, bevor ein Teil von ihm zum nĂ€chsten Knoten geleitet wird
          • Jeder Knoten enthĂ€lt einen Puffer zum Aufnehmen des vollstĂ€ndigen Pakets
      • (Virtual) Cut-through
        • Das ganze Paket passt in einen Flit und wird als ganzes in einem Knoten aufgehalten
        • Teile des Pakets (Phits) werden von einem Schaltelement schon weiter geschickt, bevor das komplette Paket von dem Schaltelement empfangen wurde; wie in einer Pipeline
        • Im Falle einer Blockierung ist in dem Schaltelement, von dem aus es temporĂ€r nicht weiter geht, garantiert genug Puffer fĂŒr das gesamte Paket reserviert worden
        • Der Kopfteil des Pakets enthĂ€lt die EmpfĂ€ngeradresse und wird in jedem Schaltelement bei der Ankunft des Pakets dekodiert, sodass der einzuschlagende Weg fĂŒr alle nachfolgenden Phits bestimmt werden kann
        • Kopf-Information wird gespeichert, bis das letztes Phit des Pakets weitergeleitet wurde
          • Danach wird auch der Puffer wieder freigegeben
      • Wormhole Switching
        • Solange keine Links blockiert sind, mit dem (virtual) Cut-through-Modus identisch
        • Falls der Kopfteil der Nachricht auf einen Link trifft, der gerade belegt ist, wird er abgeblockt
        • Puffer-GrĂ¶ĂŸer im Schaltelement ist ein Vielfaches der Flit-GrĂ¶ĂŸe, aber nicht notwendigerweise groß genug fĂŒr ein ganzes Paket (so wie es beim virtual cut- through wĂ€re)
        • Bei blockiertem Header Flit können nachfolgende Flits nachrĂŒcken, bis der Puffer des Schaltelements voll ist
          • Nachfolgende Flits verbleiben in vorherigen Schaltelementen
          • Der Abstand zwischen Header und Tail Flit schrumpft
      • Buffered Wormhole Switching

        Verwendung eines zentralen Puffers, um blockierende Pakete (Flits) zu speichern

  • Statische Verbindungsnetze
    • Nach Aufbau des Verbindungsnetzes bleiben die Verbindungen fest
    • Gute Leistung fĂŒr Probleme mit vorhersagbaren Kommunikationsmustern zwischen benachbarten Knoten
    • VollstĂ€ndige Verbindung
      • Höchste LeistungsfĂ€higkeit
        • Arbeitet fĂŒr alle Anwendungen mit allen Arten von Kommunikationsmustern effizient
      • Aber: nicht praktikabel in Parallelrechnern
        • Netzwerkkosten steigen quadratisch mit der Anzahl der Prozessoren
    • Gitter
      • 1-dimensionales Gitter (lineares Feld, Kette)
        • Verbindet N Knoten mit (N-1) Verbindungen
        • Endknoten haben den Grad 1, Zwischenknoten den Grad 2 und sind mit benachbarten Knoten verbunden
        • Disjunkte Bereiche des linearen Netzwerkes können gleichzeitig genutzt werden, aber es sind mehrere Schritte notwendig, um eine Nachricht zwischen zwei nicht benachbarte Knoten zu verschicken
      • k-dimensionales Gitter mit N Knoten

    • Ringe
      • Ring
        • ErhĂ€lt man, wenn man die Endknoten eines linearen Feldes miteinander verbindet
        • Unidirektionaler Ring mit N Knoten
          • Nachrichten werden in einer Richtung vom Quellknoten zum Zielknoten verschickt
          • Bei Ausfall einer Verbindung bricht die Kommunikation zusammen
      • Bidirektionaler Ring mit N Knoten
        • Der lĂ€ngste Pfad, den eine Nachricht nehmen muss, ist nicht lĂ€nger als N/2
        • Bei Ausfall einer Verbindung bricht die Kommunikation noch nicht zusammen, wĂ€hrend zwei AusfĂ€lle von Verbindungen das Netzwerk in zwei disjunkte Teilnetzwerke aufteilen
      • Chordaler Ring
        • HinzufĂŒgen redundanter Verbindungen
        • Erhöht Fehlertoleranzeigenschaft des Verbindungsnetzwerkes
        • Höherer Knotengrad und kleinerer Diameter gegenĂŒber Ring
    • Baumstrukturen
      • Einfacher Baum
        • Finde gemeinsamen Elternknoten P von S und D
        • Gehe von S nach P und von P nach D
      • Fat Tree
    • Hyperkubus

      Die Knotennummern werden als BinÀrzahlen geschrieben, dadurch unterscheiden sich benachbarte Knoten in genau einer Stelle, die zudem die Richtung der Verbindung angeben kann (Hamming Distanz)

      Pro Ecke sind2n/n2^n/nï»ż Knoten im Bild unten also zwei pro „Kreis“

  • Dynamische Verbindungsnetzwerke

    Geeignet fĂŒr Anwendungen mit variablen und nicht regulĂ€ren Kommunikationsmustern

    • Kreuzschienenverteiler (Crossbar)
      • VollstĂ€ndig vernetztes Verbindungswerk mit allen möglichen Permutationen der N Einheiten, die ĂŒber das Netzwerk verbunden werden
      • Alle angeschlossenen Prozessoren können paarweise disjunkt gleichzeitig und blockierungsfrei miteinander kommunizieren.
    • Schalterelemente (2x2 Kreuzschienenverteiler)

      Bestehen aus Zweierschaltern mit zwei EingĂ€ngen und zwei AusgĂ€ngen, die entweder durchschalten oder die Ein- und AusgĂ€nge ĂŒberkreuzen können

    • Permutationsnetze
      • Einstufige Permutationsnetze

        Enthalten eine einzelne Spalte von Zweierschaltern

      • Mehrstufige Permutationsnetze

        Enthalten mehrere Spalte von Zweierschaltern

      • RegulĂ€re Permutationsnetzwerke

        p EingÀnge, p AusgÀnge und k Stufen mit jeweils p/2 Zweierschaltern, wobei die Zahl p normalerweise eine Zweierpotenz ist

      • IrregulĂ€re Permutationsnetzwerke

        Weisen gegenĂŒber der vollen regulĂ€ren Struktur LĂŒcken auf

      • Kreuzpermutation K (Butterfly)

        Abwechseln Bit tauschen und nicht

      • Tauschpermutation T (Butterfly)

        Negation des niedrigwertigen Bits

      • Umkehrpermutation U
      • Mischpermutation M (Perfect Shuffle)

        Rotate left

      • Omega-Netzwerk
    • Wo befindet sich die Steuerung des Verbindungsaufbaus bei dynamischen Verbindungsstrukturen?

      Die Steuerung des Verbindungsaufbaus ist bei dynamischen Verbindungsstrukturen im Schaltnetz konzentriert.

  • Charakterisierung von Verbindungsnetzwerken
    • Latenz
      • Sender overhead:
        • Zusammenstellen des Pakets und Ablegen in Sendepuffer der Netzwerkschnittstelle
      • Time of flight:
        • Zeit, um ein Bit von der Quelle zum Ziel zu senden, wenn Weg festgelegt und konfliktfrei
      • Transmission time
        • ZusĂ€tzliche Zeit, die benötigt wird, alle Bits eines Pakets zu ĂŒbertragen, nachdem erstes Bit beim EmpfĂ€nger angekommen ist
      • HĂ€ngt von Linkbandbreite ab
        • Phit (physical transfer unit): Informationseinheit, die in einem Zyklus auf einem Link ĂŒbertragen wird
      • Routing time:
        • Zeit, um den Weg aufzusetzen, bevor ein Teil des Pakets ĂŒbertragen werden kann
      • Switching time:
        • HĂ€ngt von der Switching-Strategie ab
      • Receiver overhead:
        • Ablegen der Verwaltungsinformation und Weiterleiten des Pakts aus dem Empfangspuffer
    • Durchsatz oder Übertragungsbandbreite
    • Bisektionsbandbreite

      Maximale Anzahl von Megabytes pro Sekunde, die das Netzwerk ĂŒber die Bisektionslinie, die das Netzwerk in zwei gleiche HĂ€lften teilt, transportieren kann

    • Radius
    • Durchmesser
    • Verbindungsgrad
    • Mittlere Distanz
    • Erweiterbarkeit
    • Skalierbarkeit
    • KomplexitĂ€t oder Kosten
  • Verbindungsstrukturen QPI
  • QPI Layer

Speichergekoppelte Multiprozessoren

Caches

  • Cache-Speicher: Aktualisierungsstrategien
  • Cache-kohĂ€rent
    • Eine Cache-Speicherverwaltung heißt Cache-kohĂ€rent, wenn ein Lesezugriff immer den Wert des zeitlich letzten Schreibzugriffs auf das entsprechende Speicherwort liefert
    • Der Prozessor hat dann eine Cache-kohĂ€rente Sicht auf den Hauptspeicher
  • KohĂ€renz vs. Konsistenz
    • KohĂ€renz
      • Definiert, welcher Wert bei einem Lesezugriff geliefert wird
    • Konsistenz
      • Bestimmt, wann ein geschriebener Wert fĂŒr einen Lesezugriff sichtbar wird
  • Mittlere Zugriffszeit einer Cachestufe
    ta=rH∗tHundefinedHit +rM∗tMemundefinedMiss t_a=\underbrace{r_H * t_H}_{\text {Hit }}+\underbrace{r_M * t_{M e m}}_{\text {Miss }}
  • Mittlere Zugriffszeit zwei Cachestufen bei parallelem Zugriff
    ta=rH1∗tL1undefinedHit L1 +rM1∗(rH2∗tL2undefinedHit L2 +rM2∗tMemundefinedMiss L2)undefinedMiss L1t_a=\underbrace{r_{H 1} * t_{L 1}}_{\text {Hit L1 }}+\underbrace{r_{M 1} *(\underbrace{r_{H 2} * t_{L 2}}_{\text {Hit L2 }}+\underbrace{r_{M 2} * t_{M e m}}_{\text {Miss } L 2})}_{\text {Miss } L 1}
  • Mittlere Zugriffszeit zwei Cachestufen bei sequentiellem Zugriff
    ta=rH1∗tL1undefinedHit L1+rM1∗(rH2∗(tL1+tL2)undefinedHit L2+rM2∗(tL1+tL2+tMemundefinedMiss L2)undefinedMiss L1)t_a=\underbrace{r_{H 1} * t_{L 1}}_{\text{Hit } L1}+\underbrace{r_{M 1} *(\underbrace{r_{H 2} *\left(t_{L 1}+t_{L 2}\right)}_{\text{Hit } L2 }+\underbrace{r_{M 2} *\left(t_{L 1}+t_{L 2}+t_{M e m}\right.}_{\text{Miss } L 2})}_{\text{Miss } L 1})
  • Vorteil und Nachteil von parallelem Cachezugriffen
    • Vorteil: Bei einem Miss muss nicht zuerst gewartet werden, bis Zugriff auf höhere Ebene durchgefĂŒhrt wurde (geringere Zugriffszeit)
    • Nachteil: Bei einem Hit in einem der Caches wurde zuvor trotzdem eine Anfrage an Hauptspeicher gestartet, die dann abgebrochen wird. Der Bus wird also unnötigerweise blockiert.
  • Arten von Cache Misses
    • Compulsory Miss
    • Capacyity Miss
    • Conflict Miss
      • Set zu klein und bereits gecachtes Datum wurde aus Set entfernt (Cache nicht zwangslĂ€ufig voll)
      • Nur bei nicht-vollassoziativem Cache
    • Coherency Miss
      • Nur bei Multiprozessor-Systemen mit KohĂ€renzprotokoll
      • Unterscheidung zwischen False- und True-Sharing
      • False-Sharing, falls nicht eigentliches Wort sondern anderes Wort in Cache-Block geĂ€ndert wurde
  • Arten von KohĂ€renzprotokollen
    • Bus-Snooping-basiert
      • Write-Invalidate Protokoll
        • arbeitet auf Cacheline-Ebene
        • benötigt nur ein Invalidate
        • Vertreter
          • MSI
          • MESI
          • MOESI
      • Write-Update Protokoll
        • arbeitet auf Wort-Ebene
        • u. U. mehrere Update-Broadcasts nötig
    • Verzeichnisbasiert
  • MESI-Zustandsautomat
  • MESI Signale
    • Invalidate-Signal
      • Invalidieren von bestimmten EintrĂ€gen in den Caches aller anderer Prozessoren
    • Shared-Signal
      • Zeigt an, dass ein zu ladender Block bereits als Kopie vorhanden ist
    • Retry-Signal
      • Aufforderung fĂŒr einen Prozessor, das Laden eines Blockes abzubrechen, da es modifiziert in einem anderen vorliegt
      • Das Laden wird dann wieder aufgenommen, wenn ein anderer Prozessor aus dem Cache in den Hauptspeicher zurĂŒck geschrieben hat
  • MOESI

    Es gibt einen Owned Zustand in falls es zuvor Modified war und dann von einem anderen Prozess gelesen wird

Weitere Rechnerstrukturen

Warehouse-scale Computers

  • Anwendungsbereich Warehouse-scale Computers
    • Internet Dienste
    • Z.B. Suche, Social Networking, Online Karten, Video Sharing, Online Shopping, Email, Cloud Computing, etc.
  • Abgrenzung WSC von HPC
    • HPC-Systeme (Cluster) haben leitungsfĂ€higere Prozessoren und Verbindungsnetzwerke
    • HPC-Systeme (Cluster) nĂŒtzen Parallelismus auf Prozess-/Thread-Ebene (thread- level parallelism), WSCs sind auf “Request-level Parallelismus” ausgerichtet
  • Abgrenzung WSC von Datacentern
    • Datacenters haben verschiedene Maschinen und Software an einem Standort
    • Datacenters arbeiten mit virtuellen Maschinen und heterogener Hardware um verschiedene Kunden bedienen zu können
  • Entwurfsfaktoren fĂŒr WSC
    • Preis-Leistung
      • Skalierung: Schon wenige Einsparungen wirken sich auf die Kosten aus
    • Energieeffizienz
      • Wirkt sich auf die Stromversorgung und KĂŒhlung aus
      • „Arbeit“ pro Joule
    • ZuverlĂ€ssigkeit mit Hilfe von Redundanz
    • Netzwerk I/O
    • Interaktive- und Batch-Arbeitslasten
    • AusnĂŒtzen des Parallelismus bei Berechnungen hat nicht die Bedeutung
      • Die meisten Jobs sind unabhĂ€ngig voneinander
      • „Request-level Parallelismus“
    • Betriebskosten
      • Niedriger Energieverbrauch ist eines der wichtigsten Entwurfsziele
    • Standort

      NÀhe zu Interbackbones, ElektrizitÀtskosten, Steuern, niedrige GefÀhrdung durch Naturkatastrophen

    • Effiziente Berechnungen bei nicht voller Auslastung