Von-Neumann-Rechner im Detail

Rechen- und Steuerwerk

Die Von-Neumann CPU besteht aus zwei Komponenten: Dem Rechenwerk (ALU) und dem Steuer-/Leitwerk (Control Unit). Das Rechenwerk arbeitet mit logischen Verknüpfungen und Rechenoperationen. Das Leitwerk verschaltet Daten und ALU-Komponenten. Es interpretiert die Anwendungen des Programms, während das Rechenwerk diese ausführt.

RISC und CISC

Es gibt zwei Arten von CPUs: CISC und RISC. Dabei stellt CISC komplexe Befehle zur verfügung, die via Microcode die wenigen Register (x86 z.B. 9) nutzen. RISC stellt mehr Register zur Verfügung. Diese sind fest verdrahtet und nicht so komplex wie die einer CISC-CPU.

CISC reduziert durch komplexe Befehlssätze den Hauptspeicherzugriff, allerdings erledigt caching diesen Job ebenfalls und Hauptspeicher ist günstiger geworden.

RISC ermöglicht durch gleich kleine Befehle Pipelining und verlagert die Komplexität auf den Compiler.

Im allgemeinen findet man aufgrund der Skalierbarkeit bei Mehrkernsystemen meist einen Mix aus beiden Systemen, bei dem die Grenzen verwaschen sind, so dass Pipelining auch auf CISC stattfindet und RISC teilweise komplexere Befehele durch CISC-Simulation emuliert.

Pipelining
  1. IF Instruction Fetch (Befehl lesen)
  2. ID Instruction Decode (Identifizieren, Daten vorbereiten)
  3. EX Execute
  4. MEM Speicherzgriff
  5. WB Writeback

Probleme treten auf bei

  • Structural Hazards (Selbe Hardware benötigt)
    • z.B. weitere ALU einführen
  • Data-Hazards (Datenabhängigkeit, NOP)
    • Data Bypassing (Zwischenergebnisse teilen)
  • Control-Hazards (Sprünge)
    • Stall, Freeze, Prediction
Caching
  • Latenzzeit (Dauer bis Daten bereit)
  • Zugriffszeit (Dauer anlegen bis lesen)
  • Zykluszeit (Erhohlzeit zwischen Zugriffen)
  • Datenintergrität (Bitfehlerkorrektur)

Cache besteht aus SRAM bausteinen, enthält Cacheblocks aus dem Hauptspeicher.

  • Zeitliche Lokalität : mehrfacher Zugriff wahrscheinlich
  • Örtliche Lokalität : Zugriff auf "nahen" Speicher wahrscheinlich

Der Cache ist ein Assoziativspeicher für Blöcke des Hauptspeichers: Tag entspricht der Speicheradresse im Hauptspeicher.

  • Fully Associative : Cacheadresse ergibt sich aus Modulo mit Hauptspeicheradresse
  • Direct Mapped : Block wird irgendwo eingefügt. Ort in Tag-RAM gespeichert
  • Set Associative : Tag-RAM mit mehreren Fully Associative Caches

Liegen die Daten im Cache gibt es einen Cache Hit. Ein Cache Miss entseht Comulsory (erster Zugriff), Capacity (Cache war zu klein) oder Conflict (War noch platz, aber verdrängt).

Das aktualisieren passiert per Write-Through (direkt im HS aktualisieren) oder im Write-Back (bei verdrängung aktualisieren).

Meist werden bei der Verdrängung FIFO oder LRU (Last Recently Used) genutzt.

Speicherverwaltung

Virtuelle Pages liegen physikalisch auf Pages gleicher Größe. Beim Zugriff wird aus der Pagetable dass die richtige Page geladen wird. Die relativen Adressen bleiben gleich (Pages nicht fragmentiert), aber der Speicher kann z.B. auch auf der Festplatte liegen.

Die Pagetable enthält Informationen über den Seitenrahmen (Header-Adresse der physikalischen Page) und die Gültigkeit.

Pageverdrängung arbeitet ähnlich wie Cacheverdrängung.

Page-Flattering tritt auf wenn Prozesse oft unterschiedliche Pages benötigt. Dies liegt oft an zu vielen Prozessen, schlechter Programmierung oder einer schlechten Ersetzungsstrategie.

Thrashing bezeichnet eine Einschränkung des kompletten Systems durch übermäßiges Paging. Die Auslöser sind die selben wie oben.

Prozesse

Der Prozess-Scheduler organisiert (vom BS aus) die Übergänge eines Prozesses von blockiert zu rechenbereit zu rechnend. Ein guter Schedulingalgorithmus sollte fair und effizient sein.

Auf Batch-Systemen sollte zudem die CPU-Auslastung möglichst hoch sein, genauso wie der Job-Durchsatz, wobeid die Durchlaufzeit minimal sein soll. Auf Dialogsystemen wird eine kurze Antwortzeit betont, auf Echtzeitsystemen gilt es Zeitfenster einzuhalten und deterministisch zu bleiben.

Strategien sind z.B.:

  • First-Come, First-Serve (FCFS,FIFO)
    • Bearbeitung nach Startreihenfolge, Prozessorabgabe nur bei warten oder ende
  • Shortest Job First (SJF)
    • Verwendet auf Batch-Systemen
    • Jobs nach geschätzter Ausführungszeit bearbeitet
    • Große Jobs eventuell nie dran
  • Round-Robin
    • Gleichgroße Zeitscheiben der Reihe nach

Durchschnittliche Verweilzeit: Mittlere Job-Endzeit

RAID
  • RAID 0 : Striping, größere Transferrate
  • RAID 1 : Mirroring, selbe Daten auf allen Platten
  • RAID 5 : Striping + Paritätsbit

Rechnerarchitekturen

Flynnsche Klassifikation : SISD = Von-Neumann-Rechner, SIMD = heutige PCs, MISD = Fehlertolerant, MIMD = verteilte Systeme

Shared Memory Systeme:
Symmetric Multi Processing = gemeinsamer Specher, ccNUMA = geteilter Speicher

Distributed Memory Systeme: MPI

Amdahls Law: maximaler Parallelisierungsgewinn durch seriellen Teil beschränkt

Qubits

Können neben null und eins auch in einer Superposition sein, die nicht gemessen werden kann.
Qubits können zu Quantenregistern zusammengefasst werden.

Die Hadamard-Transformation bringt Qubits in eine Superposition in der beide Zustände gleich wahrscheinlich sind.

Quantenteilchen können verschränkt sein und dann nur noch als ganzes betrachtet werden.

Grovers Algorthmus ist ein Suchalgorithmus für unsortierte Datenmengen.

  1. Starte mit Superposition aller Suchelemente
  2. Das Quantenorakel negiert das Vorzeichen des gefundenen Wertes
  3. Berechne den Mittelwert der Amplituden
  4. Spiegel die Amplituden

Shors Algorithmus

  1. Wähle eine Zahl kleiner $N$
  2. Prüfe ob diese $N$ teilt
  3. Berechne die Periode (Quantenteil)
  4. Wenn die Periode alle anforderungen erfüllt rechne damit, sonst wieder (1)