Spickzettel Klausur ETTI PDF

Preview

Summary

Spickzettel für die Klausur / Sommersemester 2018...

Description

Algorithmus nach Bellmann-Ford

Veränderungen werden später zum HSP transportiert, Geschw.vorteil wenn ein Speicherwort mehrmals geändert wird, bevor d. Transport statt-findet, Dirty-Bit dient der Feststellung ob ein Block verändert wurde, wird bei jedem Schreibzugriff auf den Cache gesetzt, bei Transport des Blocks an den HSP wird es zurückgesetzt, höherer Verwaltungsaufwand beim Lesezugriff Fehlzugriffe beim Schreiben: Write- Allocation: Write-Miss wird behandelt wie Read-iss | Write-Around: zu schreibende Speicherzelle im Cache wird gar nicht erst gesucht u. eingetragen Pipelining Ohne Pipeline: Anzahl Befehle * Takte | Mit Pipeline: Anzahl Takte + (Befehle1) | Speedup: ohne Pipeline / mit Pipeline o. Ohne Pipeline / Anzahl Takte (Anzahl Befehle (Leerbefehle)-1)

IF  Befehlsbereitstellung ID  Decodierung EX  Ausführung MEM  Speicherzugriff WB - Resultatsspeicher

Dynamische Sprungvorhersagetechniken

Iteration: L1 = Auswahl einer Zeichenreihe / L2=zwei Zeichenreihen (1+1, 1+2, 2+1, 2+2) L ={,ab,ba,aba,bab,abab,baba, ababa,babab,} -> reg, Ausdr. (ab)*+(ba)*+a(ba)*+b(ab)*

Dijkstra-Algorithmus

Dateisysteme: Datenträger sind in adressierbaren Blöcken fester Größe organisiert | aus Sicht des Datenträgers gibt es keinerlei Inhaltsverwaltung -> es muss eine geeignete Struktur v. BS bereit-gestellt werden | Dateisystem: Datenstruktur, zur Verwaltung v. Dateien (Zuordnung v. Dateien zu Blöcken, Veraltung freier Blöcke, Metadaten, Wiederherstellung, Verschlüsselung, Komprimierung) Speicherverwaltung 210 = Kilo | 220 = Mega | 230 = Giga Anzahl Bit einer logischen Adresse: Größe des logischen Speicher = 2^(Anzahl Bits logische Adresse) | zB 16 GB = 24 *230=2 34 -> 34 Bits Wortgröße in Byte Seitengröße in Worten = Seitengröße in Byte/Anzahl Byte pro Wort Anzahl Bit für einen Eintrag an in der Seitentabelle: Physik. Speicher / Seitengröße = 2^(Anzahl Bits für 1 Eintrag) | zB 4GB / 4 KB = 232/ 2 12 = 2 20 -> 20 Bits Logische Adresse -> Physikalische Adresse: Logische Adresse / Seitengröße in Byte = Seitennr. Rest Offset | Für Seitennr. entspr. Seitenrahmennr. raussuchen | Log. Adresse = Seitenrahmennr. * Seitengröße + Offset Physikalische Adresse -> Logische Adresse: Physikalische Adresse / Seitengröße in Byte = Seitenrahmennr. Rest Offset | Für Seitenrahmennr. entspr. Seitennr. raussuchen | phys. Adresse = Seitennr. * Seitengröße + Offset Speichersegmentierung Fist-Fit: erstes Segment mit ausreichend Platz | Best-Fit: verblei-bende Speicher ist am kleinsten | Worst-Fit: Gegenteil v. Best-Fit | Next-Fit: wie FirstFit ab letzten Zugriffspunkt Cache - Direkt zugeordnet o. n-fach assoziativ Sätze = Blöcke / Assozitivität (1) | Bits Wortadresse = log2 (Blockgr. in Byte) | Bits Indexadresse = log2 (Sätze) | Bits Tag = Adresslänge  Wortadresse  Index Cache  vollassoziativ: Wie oben nur ohne Indexadresse Missrate/Zugriffszeit bei direkter Zuordnung Missrate = Anzahl Fehlzugriffe / Gesamtanzahl Zugriffe Zugriffszeit = Missrate * Misstime + Hitrate *Hittime Cachezugriffe bei direkter Zuordnung 1) Bits für Tag u. Index bestimmen | 2) Bitfolge des Index in Dezimal umwandeln  in Tabelle raussuchen | 3) Tag der sich in Tabelle befindet mit unserem Tag vergleichen (Übereinstimmung = Hit / bei Miss  Tag in Tabelle eintragen) Inkonsistenz bei Schreibzugriffen: Durchschreibstrategie: Speicherwort wird v. Prozessor immer glz. i.d. Cache u. HSP geschrieben, garantierte Konsistenz, Verlust d. Verarbeitungsgeschwindigkeit (Einsatz v. Schreibpuffern) | Rückschreibestrategie: Speicherwort wird nur i.d. Cache geschrieben,

Pipeline-Konflikte: Unterbrechung des taktsynchronen Durchlaufs der Befehle durch die einzelnen Stufen der Pipeline | Daten, Steuerfluss, Ressourcenkonflikte Datenkonflikte: echte Datenabhängigkeit: Lese-nach-Schreiben-Konflikt | Gegenabhängigkeit: Schreiben-nach-Lesen-Konflikt | Ausgabeabhängigkeit: Schreiben-nach-Schreiben-Konflikt Länge eines Taktzyklus: Verzögerungszeit der Pipeline-Register + Verzögerungszeit der langsamsten Stufe | Pipeline-Maschinentakt: Zeit, die benötigt wird um einen Befehl eine Stufe weiter durch die Pipeline zu schieben | Latenz: Zeit, die ein Befehl benötigt um alle k Pipeline-Stufen zu durchlaufen | Durchsatz: Anzahl der Befehle, die eine Pipeline pro Takt verlassen können (Rechenleistung 1 Pipeline) Zeichenreihe: endliche Folge v. Symbolen eines bestimmten Alphabets | Synonyme: Wort, Zeichenkette, Zeichenfolge | endlich lange Zeichenfolgen, die über dem Alphabet E gebildet werden können | können aneinander gereiht, verkettet, konkateniert werden | leere Zeichenreihe enthält keine Symbole - kann aus jedem Alphabet kommen | E* = Menge aller Wörter über dem Alphabet E | Ek = Menge aller Zeichenreihen einer bestimmten Länge über dem Alphabet E formale Sprache: Menge aller Zeichenreihen E* wird als Sprache L bezeichnet | E* u. leeres Alphabet sind Sprachen für jedes beliebige Alphabet | können eine unendliche Anzahl v. Zeichenreihen enthalten | sind aber auf ein festes endliches Alphabet beschränkt Sprache eines EA: v. ihm akzeptierte Menge v. Zeichenreihen/Wörtern, deren Verarbeitung in einen Endzustand führt | Es sei EA = (S,E,, s0,F) ein endlicher Automat ohne Ausg. EA akzeptiert eine Zeichenreihe wE*, falls  (s0,w) F. Unter der Sprache L(EA) des Automaten EA verstehen wir die Menge aller Worte w, die EA akzeptiert: L(EA) = {wE*|(s0,w)F} RA = regulärer Ausdruck: Ausdruck in einer bestimmten Form über der Zeichenmenge | jeder RA legt eindeutig eine ihm zugeordnete Sprache fest | die Zeichen  u. Ø sind reguläre Ausdrücke | für jede Zeichenreihe w E* ist w ein regulärer Ausdruck | Sind A1 + A 2 reguläre Ausdrücke ist auch die Vereinigung/Verkettung/Iteration ein RA | RA ist das syntaktische Konstruktor u. die reguläre Sprache die Bedeutung des Konstrukts | Beschreibung einer Sprache, die nur aus einer Zeichenreihe w besteht, erfolgt idR durch die Zeichenreihe selbst als RA Endliche Automaten u. reguläre Ausdrücke: die Notationen RA u. EA repräsentieren - trotz unterschl. Ansätze zur Beschreibung v. Sprachen - die gleiche Menge v. Sprachen | Jede Sprache, die durch einen EA definiert wird, wird auch durch einen bestimmten RA definiert u. umgekehrt | Annahme: L(EA) kann kompakt durch einen RA beschrieben werden RA ist gegeben / EA ist gesucht: Beginn der Konstruktion (Grund-automat der nur  Ø u. a akzeptiert / genau ein akzeptierter Zustand, kein Übergang am Start) | Umsetzung der Operationen (Vereinigung = echte Aufspaltung in 2 Pfade/Verkettung/Iteration = Rückschleife) EA ist gegeben / RA ist gesucht: Initialisierung (2 Hilfszustände A u. E / A besitzt eine leere Transition auf den Startzustand / v. allen Endzuständen geht eine leere Transition auf E) | Kanten-, Schleifen- u. Knotenelimination = solang wiederholen wie nötig | existiert zum Schluss keine Kante mehr zw. A u. E -> RA leer | Ansonsten ist d. reguläre Ausdruck die Kantenbeschriftung zw. A u. E Bestimmung eines regulären Ausdrucks zu einem EA | Kantenelimination -> Führen zwei Transitionen mit den Eingaben a u. b v. einem Zustand si i.d. gleichen

Folgezustand sk, dann können diese mit der Bezeichnung a + b zusammengelegt werden Schleifenelimination Weist ein Zustand sj eine Schlinge auf, dann kann diese beliebig oft ausführbare Schlinge mit den aus diesem Zustand herausführenden Transitionen konkateniert werden Knotenelimination aufeinanderfolgende, durch einen Zustand getrennte Transitionen können konkateniert werden, um den Zwischenzustand zu eliminieren Funktionsprinzip magnetomotorischer Speichermedien - Speicherprinzip: bestimmte Materialien sind permanent magnetisierbar (Ferromagnete) | aus mikroskopisch kleinen Magneten zusammengesetzt | werden auf eine unmagnetische Trägerscheibe aufgebracht | diese wird zum Schreiben/Lesen an einem winzigen Elektromagneten vorbeigeführt | zwei gegensätzliche Anforderungen an die Speichercodierung: hohe Speicherkapazität bei technol. gegebener Aufzeichnungsdichte (möglichst wenige 1) und Möglichkeit der Rückgewinnung des Taktes (wenige 0) | je höher die erreichbare Speicherkapazität, desto komplexer wird die benötigte Hardware zur Codierung / Decodierung Funktionsprinzip magnetomotorischer Speichermedien  Schreibvorgang: nach der Herstellung des Ferromagnete sind die Elektromagneten völlig reglos verteilt | Anlegen eines äußeren Magnetfeldes -> Magnetisierung d. Speichermaterials (Abschnitte bleibender Magnetisierung) | in diesen Magnetisierungsmustern wird die Information codiert | Ziele: möglichst viele Informationen pro Flächeneinheit / Informationen muss beim Leseprozess sicher zurückgewinnen werden können | der Lesetakt wird mit Hilfe eines PLLSchaltkreises mit den Übergängen unterschiedl. Magnetisierung synchronisiert | Bitzellen = kleinste Abschnitte gleichgerichteter Magnetisierung Funktionsprinzip magnetomotorischer Speichermedien  Lesevorgang: Lesekopf reagiert nur bei Wechsel der Magnetisierung | bei einem Wechsel des magnet. Flusses entsteht in der Spule des Lesekopf ein Spannungsimpuls | die zu speichernden Daten müssen in ein Magnetisierungsmustern umgesetzt werden, die möglichst wenige Bitzellen pro Datenbit enthalten | die Daten müssen anhand der entstehenden Flusswechsel eindeutig rekonstruiert werden können | es gibt versch. Möglichkeiten, die Daten durch Magnetisierungszustände oder -Wechsel zu codieren | zur Rückgewinnung des Datenbit ist ein Taktsignal erforderlich, das die verstärkte Lesespannung des Kopfes abtastet | Abtastimpulse müssen genau dort liegen, an denen Flusswechsel möglich sind Funktionsprinzip magnetomotorischer Speichermedien - Codierungsarten: FM-Codierung = zeichnet mit jedem Daten-bit wenigstens einen Flusswechseln zur Taktrückgewinnung auf / für 2 Datenbits 3 Flusswechseln / durchschn. 1,5 Fluss-wechsel bzw. 2 Bitzellen pro Datenbit | MFM-Codierung = für 4 Datenbits 3 Flusswechsel / pro Datenbit: 0,75 Flusswechsel bzw. 1. Datenbit | RLL-Codierung = Zahl der Codebits ist doppelt so groß wie die Zahl der Datenbits / für 7 Daten-bits 9 Flusswechseln / pro Datenbit: 0,43 Flusswechsel / RLL 2,7: zwischen 2 Flusswechseln liegen mind. 2 u. max. 7 Abschnitte gleicher Magnetisierung North Bridge: System Controller Hub | steuert den Datenfluss zwischen den versch. Komponenten |setzt dazu Schreib u. Leseanforderungen des Prozessors, des Graphikcontrollers o. einer South-Bridge-Komponente in Speicher-Buszyklen um |dazu müssen Protokollanpassungen zwischen dem Prozessorbus, Speichers u. der Graphikcontroller-Schnitt-stelle vorgenommen werden |alle transportierten Daten werden zum Geschwindigkeitsausgleich zwischengespeichert |Front Side Bus: Verbindung des Prozessor-bausteins mit der NB | HUB-Interface verbindet NB & SB Speicher-Controller: wesentlicher Bestandteil der North Bridge (MCH) | Verbindung des Prozessors mit allen Komponenten, die eine möglichst schnelle Verbindung benötigen | mittlerweile wurde der Controller aus der NB i.d. Prozessorschip verlagert South Bridge  Aufgaben: Verbindung des Prozessors mit einer Reihe v. integrierten o. extern hinzugefügt Controllern -> Ein/Ausgabecontroller-Hub (ICH) | Regelung v. Kommunikations-verbindungen u. -Vorgänge zwischen den untersch. Ein/Ausgabe-einheiten | stellt interne Controller zur Verfügung (Zeitgeber, RealTimeClock, Zähler, Tastatur-Controller) Bestandteile: Steckermodul (unterschiedliche Komponenten der SB werden in einem besonderen Platinenbereich mit einem Steckermodul verbunden / ist nach außen zugänglich) | Interrupt-Controller | SMBus (verbindet wichtige Komponenten der Haupt-platine miteinander / Übertragung v. Steuer u. Überwachungsinformationen zwischen den Brückenbau-steinen / Überwachungsfunktion für versch. Bauteile) | Prozessor u. Systemsteuerung (ACPI):...