RS Zusammenfassung PDF

Preview

Summary

Alle wichtige Infos ...

Description

RS Zusammenfassung

Zustandsmenge Q={q0 ,q1 ,q2 } Startzustand q0 =a Eingabealphabet Σ={M,H}

dodod 24. Februar 2020 1

Ausgabealphabet ∆={B,N }

Rechnen mit ganzen Zahlen

1.1

¨ Ubergangsfunktion δ=

M q1 q1 {z

q0 q1

Addition |

• • • •

Addition VB: Klappt nicht Addition im ZK: Klappt Addition im EK: Kappt nur, wenn man am Ende 1 addiert Addition Exzess: Nach der Addition einmal den Bias subtrahieren

Q q0 q1

Ausgabefunktion λ =

Multiplikation

Rechnen mit Fließkommazahlen

2.1 • • • •

λ B N {z

4.2

6-Tupel Mealy-Automat

• Zu jedem Mealy-Automat existiert ein ¨aquivalenter MooreAutomat • Ausgabe bei jedem Zustandswechsel Definiert durch: M ={Q,q0 ,Σ,∆,δ,λ} Zustandsmenge Q={q0 ,q1 } Startzustand q0 =q0

Addition

ex ≥ey , sonst x und y tauschen sz = sx sx = 6 sy ⇒my in ZK umwandeln und addieren Mantisse in ZK umwandeln: Alle bis zur letzten 1 flippen: 1,101101000···→0,010011000...

Eingabealphabet Σ={M,H} Ausgabealphabet ∆={B,N } ¨ Ubergangsfunktion δ=

2.2

Subtraktion

|

q0 q1

Ausgabefunktion λ =

Multiplikation

1. sz =sx ⊕sy 2. Komma in Mantissen an richtige Stelle schieben (implizite 1 nicht vergessen) 3. Mantissen wie bei ganzen Zahlen multiplizieren 4. normalisieren ucksichtigen 5. ez =ex +ey − b und eventuell Normalisierung ber¨ 3

q0 q1

M q1 q1 {z

H q0 q0 }

Bsp: Befindt sich der Automat in Zustand q0 und erfolgt die Eingabe M , so geht der Automat in den Zustand q1 ¨uber.

• Vorzeichen der zweiten Zahl invertieren und dann addieren

2.3

}

Bsp: Befindet sich der Automat in Zustand q1 so erfolgt Ausgabe N

• an Stellen wo eine 1 steht, rechte Zahl von oben entsprechend einger¨ uckt abschreiben und anschließend addieren

2

}

Bsp: Befindt sich der Automat in Zustand q0 und erfolgt die Eingabe M , so geht der Automat in den Zustand q1 ¨uber.

| 1.2

H q0 q0

|

M N N {z

H N B }

Bsp: Befindet sich der Automat in Zustand q1 und erfolgt die Eingabe M , so erfolgt Ausgabe N

5

Schaltnetze

Takt

• Pegelsteuerung: aktiv, wenn 1 anliegt • positive Flankensteuerung: aktiv, wenn Wechsel von 0 • Zur Realisierung eines MUX2d werden 2d + 1 MUXd nach 1 ben¨ otigt. • negative Flankensteuerung: aktiv, wenn Wechsel von 1 5.1 Ripple Carry Adder nach 0 • Vorteil: klein • Nachteil: sehr tief ⇒ langsam 4 Automaten 5.2 Carry Look-Ahead-Adder 4.1 Moore-Automat • berechnet alle Carry-Bits im voraus Definition (6-Tupel): • Vorteil: schneller als RCA • Nachteil: sehr groß, großer Fan-In M ={Q,q ,Σ,∆,δ,λ} 0

5.3 Serienaddierwerk • im Gegensatz zum Mealy-Automat Ausgabe nur vom seinem • Realisierung mit Flip-Flops Zustand abh¨angig • Vorteil: addiert beliebig lange Betragszahlen • zu jedem Moore-Automaten, gibt es einen a¨quivalenten • Sehr langsam, Berechnung eines Bits pro Takt Mealy-Automaten 1

5.4

Von Neumann-Addierwerk

• Um ein Signal einen Takt zu verz¨ ogern 7.4

• fertig, wenn y x 1 1 0 y 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 6

JK-Flip-Flop

• Vorteil: Mehr don’t cares in der Ansteuertabelle • Nachteil: Gr¨ oßer als RS-Flipflop Qalt Qneu J K 0 0 0 * 0 1 1 * 1 0 * 1 1 1 * 0

komplett 0 ist 1 0 1 0 0 1 1 0 0 0 1 0 1 1 0 0 0 0

8

Programmierbare Bausteine

Hazards

• statisch - Ausgabewert soll gleich bleiben, ¨ andert sich aber • dynamisch - Ausgabewert soll sich a¨ndern, a¨ndert sich aber mehrfach • Funktionshazard - schon in der Funktionsdefinition ent- Name Typ f1 (x,y) halten (erkennbar im KV-Diagramm) Identer 0 y • Schaltungshazard - Hazard, der kein Funktionshazard ist, Addierer 1 x∨y sondern durch die Wahl der Schaltung entsteht Multiplizierer 2 y – vermeidbar durch Verwendung aller Primimplikanten im Negat-Multiplizierer 3 y Schaltnetz Monomrealisierung (vertikal): – vermeidbar durch l¨ angere Leitungen zum Ausgleich von • Typ 0 falls Variable fehlt Laufzeitdifferenzen • Typ 2 falls Variable xi vorkommt – vermeidbar durch Takt • Typ 3 falls Variable xi vorkommt 7 Flip-Flops Polynom (horizontal) 7.1

RS-Flip-Flop

• Typ 1 zum ausw¨ ahlen“ des Monoms ” • Typ 0 sonst 8.1 Qalt 0 0 1 1

7.2

Qneu 0 1 0 1

R * 0 1 0

PLA als Speicher

S 0 1 0 *

T-Flip-Flop

• Q wird bei jeder Eingabe negiert (”toggle”) 7.3

f2 (x,y) x x x∧ y x∧ y

9

D-Flip-Flop

9.1

Register & Schieberegister Register

• Register werden als SRAM, ha¨ufig mit D-Flip-Flops realisiert 9.2

Schieberegister

• Zur Multiplikation praktisch (Multiplikation nutzt viele Bit-Shifts) 2

10

Speicherhierarchie

11

MIPS

• Prozessadressen = ˆ virtuelle Adressen • Maschinenadressen = ˆ reale Adressen • interne Fragmentierung: innerhalb einer Organisationseinheit (z.B. Page, Segment usw.) • externe Fragmentierung: zwischen den ganzen Organisationseinheiten 10.1

Segmentadressierung

• Segmentnummer zu Basis Tabelle • Basis wird auf virtuelle Adresse addiert, um reale Adresse zu bekommen • heutzutage nicht mehr ohne Paging verwendet • Einteilung in Daten, Stack, Programm-usw. Segment pro Prozess (mehrere Segmente pro Prozess) • Segmente k¨ onnen mit Zugriffsrechten versehen werden • aufw¨andige Neuanordnung 10.2

Paging

• • • •

Einteilung des virt. Adressr. in Pages Kacheln mit gleicher Gr¨oße wie Pages im realen Speicher • Little endians: der am wenigsten signifikante Teil eines Mapping zwischen beiden in Seitentabelle Wortes erh¨ alt die niedrigste Byteadresse (lesE) Selten verwendete Pages, k¨ onnen auf langsamere Speicher • Big endians: der signifikanteste Teil eines Wortes erh¨ alt bis schließlich zur Platte ausgelagert werden (swapping) die niedrigste Byteadresse (Esel) • Invertierung der beiden letzten Adressbits bewirkt Umschal10.3 Segmentadressierung mit Seitenadressierung tung zwischen beiden Systemen • Einteilung der Segmente in Pages • nur noch interne Fragmentierung • keine Kopieroperationen der Segmente mehr n¨otig 10.4

11.1

Registerspeicher

11.1.1

Allgemein

Homogene Registers¨ atze • Alle Register besitzen dieselbe Funktionalit¨at Heterogene Registers¨ atze • Vorteil: Befehle mit vielen (≥ 4) Registern leicht zu realisieren, weniger Registernummern im Befehl • Nachteil: Separate Kopierbefehle n¨ otig

Translation Look Aside Buffer

• spezieller Cache f¨ ur Adress-Mapping-Tabellen • drei Organisationsformen: – direct mapping

oße ∗ Adressierung ¨uber Index (Teil der Seitennummer) 11.1.2 Registersatzgr¨ ∗ Anschließender abgleich ¨uber Tag Viele Register • Vorteile: Entlastung des Hauptspeichers, schnelle Zugriffe – set associative mapping • Nachteile: Befehlswortbreite w¨ achst an, Retten und ∗ mehrere Seiten pro Index R¨ uckschreiben aufwendiger ∗ parallele Suche nach passendem Tag 12 Von-Neumann-Rechner ∗ z.B. LRU zum aktualisieren 1. Einteilung des Speichers in Zellen gleicher Gr o¨ße, die u ¨ ber Adressen angesprochen werden k¨onnen. ∗ nur noch parallele Suche nach passendem Tag 2. Verwendung von speicherprogrammierbaren Programmen ∗ keine Suche mehr nach Index 3. Speicherung von Programmen und Daten in demselben ∗ komplex, deshalb nur beschr¨ankte Gr¨ oße, bei lokal Speicher. arbeitenden Prozessen aber sehr performant 4. Die sequentielle Abarbeitung von Befehlen. 5. Nach jedem Befehl wird der PC erh o¨ht (außer bei Sprungbefehlen) (Abarbeitung in der Reihenfolge der Speicherung) 6. Verwendung von Folgen von Bin¨arzeichen, um alle Gr ¨ oßen 10.5 Caches darzustellen • virtueller Cache - Verwendung von virtuellen Adressen 7. Keine explizite Typangabe im Bitvektor, Typ muss aus dem Kontext klar sein – meist schneller, da TLB und Cache parallel arbeiten – associative mapping

• realer Cache - Verwendung bereits durch MMU ¨ ubersetzter Adressen • Write-Through: Schreiboperationen werden direkt auch im Hauptspeicher ausgef¨uhrt • Copy-Back, Write-Back, Conflicting Use Write-Back: Erst bei u ¨ berschreiben im Cache (+dirty bit)

13 13.1

n-Adressmaschinen 3-Adressmaschine

• ADD C, A, B (C:=A+B) 13.2

2-Adressmaschine

• ADD C, A (C:=C+A) 3

13.3

1-Adressmaschine

17.1

Fließbandverarbeitung

• Konzeptuelle Aufteilung des Speichers in Daten- und Be• LOAD C (Acc:=C) • ADD A (Acc:=Acc+A) fehlsspeicher • Aufteilung des Rechenwerks in Fließbandstufen, Trennung • STORE B (B:=Acc) durch Pufferregister 13.4 0-Adressmaschine • Pipeline Hazards durch eventuelle datenabh¨angigkeit von vorherigen Befehlen, die jedoch noch nicht komplett verarbeitet • Verwendung eines Stacks, jeweils die obersten beiden Elewurden (L¨ osung durch NOOP) mente werden miteinander kombiniert • Delayed Branches - Der Slot nach einem Branch wird immer noch ausgef¨uhrt (delay slot(s), sollte vom Compiler 14 RISC/CISC sinnvoll gef¨ullt werden, sonst NOOP) RISC CISC • dynamisch L¨ange der Instruk- fest 18 E/A tionen Zyklen pro Instruk- ¨uberlicherweise 1, meist ≥ 2 • PCI: Bussystem tion maximal wenige • PCI-Express: Kein Bussystem mehr, stattdessen Switch f ¨ ur mehr Punkt-zu-Punkt-Verbindungen Adressierungstyp einfach auch indirekt 18.1 Adressierungsarten ja semantische L¨ucke nein • Speicherbezogene E/A-Adressierung (Verwaltung wie Speizwischen Hochcher mit speziellen Speicheradressen) sprachen und As– Einfacher, aber Zugriffsschutz nur ¨uber Speicherverwalsemblerbefehlen tung Beispielprozessoren MIPS Intel x86 • Spezielle E/A-Adressen Load/Store Archi- ja nein tektur? 18.2 synchrone und asynchrone Busse • CPI - Cycles per Instruction • unidirektional - Verlassen darauf, dass Partner in vorge• CISC - complex instruction set computer gebener Zeit reagiert • RISC - reduced instruction set computer – einfach, bei konstanten Antwortzeiten schnell – Kommunikationspartner muss in bestimmter Zeit ant15 Interrupts worten • Unterbrechung entspricht dem Sprung zu einem Trap-Handler, – bei synchronen Bussen + Speicherbussen je nach Ausnahmeart, die den Fehler handlet • bidirektional - Kommunikationspartner best ¨atigen (Ack) • synchrone Unterbrechungen - Ausnahmesituation wird – passt sich unterschiedlichen Geschw. an durch das aktuell ausgef ¨uhrte Programm herbeigef ¨uhrt (z.B. – komplex Arithmetik- ¨Uberlauf) – asynchrone-, EA- und Peripheriebusse • asynchrone Unterbrechungen - Ausnahmesituation 18.3 Kommunikationsarten ohne Bezug zum aktuellen Programm (z.B. Netzausfall) • Coprozessor k ¨ummert sich um die Bearbeitung des Fehlers • immediate devices - k¨onnen mit CPU mithalten • Busy-Waiting - so lange warten, bis Bereit-Bit gesetzt 16 RT-Strukturen (Loop) – keine Verarbeitung anderer Aufgaben parallel m¨ oglich 16.1 ALU – bremst bei langsamen Ger¨ aten extrem aus • Arithmetisch logische Einheit – nur bei sehr schnellen E/A-Ger¨aten oder wenn keine • erlaubt Addition, Subtraktion, Verundung, Veroderung andere Aufgabe vorliegt • Polling - Gelegentliches Pr ¨ufen des Bereit-Bits aller Ger ¨ ate 17 MIPS-Maschine Hardware – gerechte Bedienung aller Ger¨ ate – vermeidet DOS – hohe Reaktionszeit • Interrupt – großer Overhead, deshalb keine hohe Daten¨ ubertragungsrate m¨oglich – daf¨ ur kurze Reaktionszeit + Prozessor kann parallel Aufgaben verrichten • DMA - Direct Memory Access – Datentransport nebenl¨aufig ohne CPU zwischen Speicher und EA-Ger¨at 19

Multithreading

• Dispatcher schalten zwischen Prozessen um und rettet Daten in Prozesseigenen Speicherblock

4...