Rechnerarchitektur Vorlesungsskript 2024/2025 PDF

Gliederung der Vorlesung 1) Meilensteine aus der Geschichte 2) Grundstrukturen 3) Leistungsbewertung 4) Befehlssätze und Assemblerprogrammierung 5) Datenpfad und Steuerwerk 6) Fließbandverarbeitung (Pipelining) 7) Speicherorganisation (insb. Cache-Organisation, virtueller Speicher) 8) Ein-/A...

Gliederung der Vorlesung 1) Meilensteine aus der Geschichte 2) Grundstrukturen 3) Leistungsbewertung 4) Befehlssätze und Assemblerprogrammierung 5) Datenpfad und Steuerwerk 6) Fließbandverarbeitung (Pipelining) 7) Speicherorganisation (insb. Cache-Organisation, virtueller Speicher) 8) Ein-/Ausgabe RA - WS 2024/2025 Geschichte 1 Interessante Links § Geschichte http://www.hnf.de § International Roadmap for Systems and Devices https://irds.ieee.org/ RA - WS 2024/2025 Geschichte 2 Entwicklung und Bau von Rechnern § Voraussetzungen Idee Technische Realisierungsmöglichkeit § Ursachen für Leistungssteigerung Innovative Konzepte und Ideen Technologischer Fortschritt RA - WS 2024/2025 Geschichte 3 Rechenmaschine von Wilhelm Schickard (1592 - 1635) § Wilhelm Schickard geb. in Herrenberg Professor für biblische Sprachen in Tübingen, später auch für Astronomie und Mathematik § 1623 Vorschlag für zahnradgetriebene Rechenmaschine für 4 Grundrechenarten Addition mit Zahnrädern (automatischem Übertrag) Multiplikation: Walzen mit kleinem Einmaleins RA - WS 2024/2025 Geschichte 4 Skizzen aus Brief an Kepler RA - WS 2024/2025 Geschichte 5  Kepler Hahn Schickard „Schwäbisches Silicon Valley“ Heute: Cybervalley … Vgl. RAhttps://cyber-valley.de/ - WS 2024/2025 Geschichte 6 Addition Beispiel: 1 + 3 1 2 0 0 9 1 3 8... 4... 7 Problem: Übertrag 9 0 1 8 9 0 2 1... 3... 2 RA - WS 2024/2025 Geschichte 7 Multiplikation Beispiel: 99 * 4...... 8 9 0 8 9 0 1 1 *2 8 8 2 2 *3 7 7 3 3 *4 6 6......... 33 66 396 RA - WS 2024/2025 Geschichte 8 Rekonstruktion RA - WS 2024/2025 Geschichte 9 Rechenmaschine von Blaise Pascal (1623 - 1662) § 1642: Maschine zur Addition und Subtraktion Mechanischer Zähler als Räderwerk 2 Sätze von je 6 Zählscheiben mit 10 Ziffern automatischer Übertrag. Subtraktion: Addition von Komplementzahlen RA - WS 2024/2025 Geschichte 10 RA - WS 2024/2025 Geschichte 11 Gottfried Wilhelm Leibniz (1646-1716) § Erweiterung der Maschine von Pascal um Multiplikation und Division, mechanische Probleme wegen Verwendung des Dezimalsystems § 1679: “De Progressione Dyadica” Skizze für Rechenmaschine mit Dualzahlen RA - WS 2024/2025 Geschichte 12 RA - WS 2024/2025 Geschichte 13 Philip Hahn (1739-1790) § Lösung mechanischer Probleme bei Rechenmaschine von Leibniz (Pfarrer und Uhrmacher, Schwager Mechaniker) RA - WS 2024/2025 Geschichte 14 Charles Babbage (1792-1871) § 1823: Differenzmaschine Erstellung von Navigationstafeln – trigonometrische Tafeln Rückgeführt auf Auswertung eines Polynoms f(x) = anxn + an-1xn-1 +... + a0x0 Notwendige Hardwareoperationen bei direkter Implementierung: – Addition – Multiplikation – evtl. Potenzieren Differenzmaschine verwendet nur Addition RA - WS 2024/2025 Geschichte 15  Beispiel x 1 2 3 4 5 6 f(x) = x2 1 4 9 16 25 36 Differenzen 3 5 7 9 11 Differenzen 2 2 2 2 Startwerte Berechnung mit Addition möglich RA - WS 2024/2025 Geschichte 16 Brockhaus - Conversations - Lexikon, 1882: “Seine Rechenmaschine sollte zufolge ihres Zwecks, mathematische und seemännische Tafeln zu berechnen und zu drucken, aus zwei wesentlich verschiedenen Teilen, einem rechnenden und druckenden, bestehen. Der erste wurde 1828 zu bauen angefangen und war 1833 zum größten Teil in bewunderungswürdiger Schönheit und Vollkommenheit vollendet, als eine Unterbrechung im Bau der Maschine eintrat. Der druckende Teil war damals noch nicht halb fertig, und dennoch war der Gesamtaufwand beim Bau bis auf 17.000 Pfund Sterling gestiegen. Da die vollständige Ausführung noch auf doppelt so viel veranschlagt wurde, ließ man die Sache liegen.” Zum Vergleich: G. Scheutz (1785 - 1873) 15-stellige - Dampflokomotive “John Bull”, drei Maschine für Polynome 3. Grades Jahre vorher für 784 Pfund gebaut. - DB bestellt 1988 Triebkopf für ICE RA - WS 2024/2025 für 8,7 Millionen Mark (Wikipedia) Geschichte 17 1834: Analytical Engine Rechenwerk Speicher Druckwerk (“the mill”) (“the store”) oder (+,-, · ,/) Kartenlocher Steuerung “Operationskarten” “Variablenkarten” (zur Auswahl von Speicherplätzen) RA - WS 2024/2025 Geschichte 18 Analytical Engine (2) - Merkmale § Aufteilung in Steuer-, Rechen-, Speicherwerk und Ausgabe § Programmsteuerung durch Lochkarten § Bedingte Sprünge: Zieladresse durch Vor- und Rücklaufen der als Band angeordneten Steuerkarten § Direkte Ausgabe über Stahlstempel RA - WS 2024/2025 Geschichte 19 Analytical Engine (3) § Nicht gebaut, Babbage tritt 1839 von seiner Professur zurück § Erfolgreiche Rekonstruktion, Science Museum London, 1991 RA - WS 2024/2025 Geschichte 20 Nachbau der Analytical Engine RA - WS 2024/2025 Geschichte 21 Ada Byron, Lady Lovelace (1815-1852) § übersetzt Artikel von Menabrae über die Analytical Engine § entwickelt erstes Programm für Analytical Engine § 1979 Programmiersprache ADA wird nach ihr benannt RA - WS 2024/2025 Geschichte 22 Elektrische Maschinen § Konrad Zuse (1910 - 1995) § 1938: ZUSE Z1 Dualsystem, rein mechanische Schaltelemente aus Blech Z1 und Z2 wurden im 2. Weltkrieg zerstört § 1941: ZUSE Z3 im Auftrag der DVL RA - WS 2024/2025 Geschichte 23 Struktur der Zuse Z3 Programmspeicher (“Plan-Speicherwerk”) Steuerwerk (“Planwerk”, “Programmwerk”) Eingabewerk: Tastenfeld und Lochstreifen Wählwerk Ausgabe: Rechenwerk Speicher Anzeigenfeld (“Arbeits- (“Speicher- (Lampen) werk”) werk”) RA - WS 2024/2025 Geschichte 24 Merkmale der Z3 (1) § Binärdarstellung von Befehlen und Zahlen § Binäre Schaltelemente für Speicherung und Verarbeitung § Verwendung des Aussagenkalküls (UND, ODER, NICHT) zur Realisierung der Rechenoperationen § Gleitkomma-Darstellung von Zahlen (Vorzeichen, Exponent, Mantisse) RA - WS 2024/2025 Geschichte 25 Merkmale der Z3 (2) § Darstellung des Ablaufs als Folge von Rechenschritten (noch keine bedingten Befehle) § Aufbau mit elektromagnetischen Relais (600 für Rechenwerk, 1400 für Speicherwerk: 64 Speicherworte à 22 Bit) RA - WS 2024/2025 Geschichte 26 Merkmale der Z3 (3) § Steuerung über 8-Kanal-Lochstreifen § Geschwindigkeit: 3 Sekunden für Multiplikation, Division, Wurzelziehen RA - WS 2024/2025 Geschichte 27 Zuse Z4 (aus Comm. ACM 2/17) Figure 13. Zuse’s binary relay computer Z4 was first commercially available in 1945; this tape-controlled programmable machine with floating-point arithmetic was in operation in Zürich from 1950 to 1955 and included an innovative mechanical memory without relays. Courtesy of ETH Library Zürich, Switzerland. RA - WS 2024/2025 Geschichte 28 Howard Aiken (1900 - 1973) § 1944: Automatic Sequence Controlled Computer (Harvard Mark I) elektromechanisch Dezimalsystem RA - WS 2024/2025 Geschichte 29 1. Bug: 1945 im Harvard Mark II entdeckt von Grace Murray Hopper 1906 - 1992 Elektronische Computer § 1943-1946: Electronical Numerical Integrator and Calculator (ENIAC) entwickelt von J. W. Mauchly, J.P. Eckert 17 468 Röhren 1 500 Relais 174 kW Leistung 30 t Gewicht 0,2 ms Additionszeit 2,8 ms Multiplikationszeit RA - WS 2024/2025 Geschichte 31 Vgl. Ausstellung im Heinz Nixdorf Forum RA - WS 2024/2025 Geschichte 32 Speicherprogrammierbare Rechner § Burks, Goldstine, J. v. Neumann: § 1945-1951: Electronic Discrete Variable Computer, (EDVAC) Programm: abstrakte, veränderbare Darstellung der Steuerung RA - WS 2024/2025 Geschichte 33 Aufbau eines von-Neumann Rechners Rechen- werk Speicher (enthält Daten und Programme) Steuer- CPU werk Der Rechner wiederholt ständig den gleichen “Befehlszyklus” RA - WS 2024/2025 Geschichte 34 Befehlszyklus § Befehl aus dem Speicher holen (in “Maschinensprache“) § Befehl auswerten (Steuerwerk) § Befehl ausführen (Rechenwerk), dazu evt. Daten aus dem Speicher holen RA - WS 2024/2025 Geschichte 35  aus IEEE Spectrum – The Institute RA - WS 2024/2025 September 2024Geschichte 36  1961: NASA setzt Szene aus dem Film „Hidden Figures“ IBM 7090 ein https://www.youtube.com/watch?v=x5GV7ODht78 (diskrete Transistoren) RA - WS 2024/2025 Geschichte 37 µProzessor-Entwicklung (1) 1969 Fa. Datapoint gibt bei Intel Bildschirmsteuerung in Auftrag 1971 Intel 4004 (vgl. auch http://www.intel4004.com/qa4004.htm) RA - WS 2024/2025 Geschichte 38 µProzessor-Entwicklung (2) § 1972: Intel 8008 8-Bit Daten, 14-Bit Adressen Befehlssatz: ADD, SUB, Logikbefehle § Ziel: Standardisierte Hardware, Funktionsbeschreibung in Opcodes statt in Gattern, 8-16 Bit pro Gatter, 1 kByte Programm ersetzt 500-1000 Gatter RA - WS 2024/2025 Geschichte 39 µProzessor-Entwicklung (3) § Erwartungen: Geringere HW-Entwicklungskosten, Vereinfachte Lagerung und Wartung, (Unterschätzung des SW-Problems) RA - WS 2024/2025 Geschichte 40 Performance Trends Revisited (Architectural Innovation) 1000 Performance Supercomputers 100 Mainframes 10 Minicomputers Microprocessors 1 CISC/RISC 0.1 1965 1970 1975 1980 1985 1990 1995 2000 RA - WS 2024/2025 Geschichte 41 in SPECmark Entwicklung der Prozessorleistung Gleitkomma- programme 300 Sun UltraSparc 1.54X/yr P 250 e r f 200 DEC 21064a o r m a 150 n IBM Power 2/590 c e 100 DEC AXP 3000 Integer MIPS M/120 HP 9000/750 Programme 50 MIPS M2000 Sun-4/260 1.35X/yr IBM RS6000/540 0 1987 1988 1989 1990 1991 1992 1993 1994 1995 RA - WS 2024/2025 Geschichte 42 Aus einer Intel-Broschüre zum 40. Jahrestag von Moore‘s Law (2006) 1010 relative manufacturing cost per component 109 number of components per integrated circuit 108 107 106 105 104 Entwicklung (Beispiel Sparc) Microprocessor 1997 2009 2011 chip in the year Ultra II Sparc64 VIIIfx SparcT4 (SUN) (Fujitsu) (Oracle) Minimum feature size 0.28 µm 45 nm 40 nm of process technology Total number of transistors 5.4 M 760 M 855 M Chip size 156 mm2 513 mm2 403 mm2 Clock frequency 250 - 330 MHz 2 GHz 2,85 - 3 GHz Number of I/O connections 787 1271 ? Number of wiring levels 5 ?? ? Supply voltage 2.5 V adjustment ? ( around 1 V ) Power dissipation 26 W 58 W 240 W Number of cores 1 8 8 RA - WS 2024/2025 Geschichte 44  2024: Apple M3 Max mit 4,05 GHz, 3 nm Technologie, 92.000 M Transistoren Prognose der ITRS Roadmap 2009 2009 2013 2018 2024 Minimum feature size of 54 nm 27 nm 15 nm 7.5 nm process technology Maximum number of 7.299 M 29.198 M 92.697 M 370.786 M transistors Number of usable logic 851 M 3.403 M 10.804 M 43.215 M transistors/cm² Chip size 260 mm² 260 mm² 164 mm² 164 mm² Chip frequency 5,4 GHz 7,3 GHz 10,7 GHz 16,6 GHz Number of I/O connections 4620 5616 7167 9605 Number of wiring levels 12 13 14 15 Supply voltage 1,0 V 0,87 V 0,73 V 0,6 V Power dissipation 143 W 149 W 136 W 130 W RA - WS 2024/2025 Geschichte 45 Grenzenlose Weiterentwicklung ?? RA - WS 2024/2025 Geschichte 46 Computer sind heute überall § PCs § Server § Supercomputer § Eingebettete Computer § Personal Mobile Devices (PMDs) § Cloud Computing RA - WS 2024/2025 Geschichte 47 The PostPC Era (aus Hennessy/Patterson) RA - WS 2024/2025 Geschichte 48 International Roadmap for Devices and Systems RA - WS 2024/2025 Geschichte 49 Notes for Table ES1: Required for specintrate scaling Frequency increase slowing down, but increases because of better cooling (allowing higher TDP)) Load-to-use latency dictates constant or limited growth in L1 data cache size Instruction footprint for cloud apps going up (refer Google data warehouse paper) HBM: 128GB/s per port, in sockets 2015, HBM2: 256GB/s per port, can be in sockets 2017, HBM3: 512GB/s, can be in sockets 2019 A lane is defined as: a) Single wavelength and polarization that is received by a single detector; b) Pulse Amplitude Modulation with 4 amplitude levels (PAM4) would a single lane; c) Input (IQ) and Output (OQ) can be independent lanes; d) Multiple wavelengths in a fiber would be multiple lanes: e) If multiple lanes are required to support the required data rate, circuitry will be required to separate the data stream into multiple lanes and recombine in the receiver. RA - WS 2024/2025 Geschichte 50 Wo liegen die Probleme und Grenzen? § Technologieentwicklung ? § “Design Productivity Gap” ? § Power ? § Qualitätssicherung / Zuverlässigkeit ? RA - WS 2024/2025 Geschichte 51 Power: IBM Watson gewinnt Jeopardy (Feb. 2011) 200.000 W 25 W RA - WS 2024/2025 Geschichte 52  Hinter den Kulissen...... Watson, consisting of ten racks of ten Power 750 servers, had to be kept apart from the human contestants because of the roar of its cooling system and was represented at the podium by an avatar of IBM's Smarter Planet logo, whose moving lines would go green when Watson had cracked a thorny problem, orange when the answer was wrong... http://www.techrepublic.com/article/ibm-watson-the-inside-story-of-how-the- jeopardy-winning-supercomputer-was-born-and-what-it-wants-to-do-next/ http://www.venraytechnology.com/IBM_Watson_Strategy.htm RA - WS 2024/2025 Geschichte 53 Wo liegen die Probleme und Grenzen? § Technologieentwicklung ? § “Design Productivity Gap” ? § Power ? § Qualitätssicherung / Zuverlässigkeit ? RA - WS 2024/2025 Geschichte 54 RA - WS 2024/2025 Geschichte 55 Ausbeute (Yield) und Chipkosten Wafer_cost Die_cost = Dies_per_Wafer * Die_yield Wafer_area Dies_per_Wafer ≈ Die_area Die_yield ≈ −α ⎛ Defects_per_unit_area * Die_area ⎞ Wafer_yield * ⎜1 + ⎟ ⎝ α ⎠ RA - WS 2024/2025 Geschichte 56 Annahmen § Defekte sind zufällig über den Wafer verteilt § Chipausbeute ist umgekehrt proportional zur Komplexität des Herstellungsprozesses § Bei modernen Prozessen: a » 4,0 oder größer § Bei älteren Prozessen: a zwischen 2,0 und 3,0 § Waferausbeute kann vereinfacht als 1,0 angenommen werden RA - WS 2024/2025 Geschichte 57 Technologiefortschritt vs. Ausbeute 65nm 45nm 90nm Defect 130nm Density 180nm 00 02 04 06 Time From: R. Madge, ITC 2004 RA - WS 2024/2025 Geschichte 58 Wo liegen die Probleme und Grenzen? § Technologieentwicklung ? § “Design Productivity Gap” ? § Power ? § Qualitätssicherung / Zuverlässigkeit ? RA - WS 2024/2025 Geschichte 59 Ist mit immer schnelleren Rechnern alles berechenbar ? § Berechenbarkeit Eine Funktion f : D ® W heißt berechenbar im intuitiven Sinn, wenn es einen Algorithmus (“effektives Rechenverfahren”) gibt, der bei einer Eingabe x Î D schließlich die Ausgabe f(x) Î W liefert Ein Programm (ohne Endlosschleife!) auf einem PC ist z. B. ein effektives Rechenverfahren RA - WS 2024/2025 Geschichte 60 § Satz Es gibt Funktionen f : IN ® {0,1}, die nicht berechenbar im intuitiven Sinn sind. § Für alle bisher bekannten Rechnermodelle gilt: Es können genau die im intuitiven Sinn berechenbaren Funktionen berechnet werden RA - WS 2024/2025 Geschichte 61 Werden wir in Zukunft mit Quantencomputern rechnen? RA - WS 2024/2025 Geschichte 62 Gliederung der Vorlesung 1) Meilensteine aus der Geschichte 2) Grundstrukturen 3) Leistungsbewertung 4) Befehlssätze und Assemblerprogrammierung 5) Datenpfad und Steuerwerk 6) Fließbandverarbeitung (Pipelining) 7) Speicherorganisation (insb. Cache-Organisation, virtueller Speicher) 8) Ein-/Ausgabe RA – WS 2024/2025 Grundstrukturen 1 Prinzipielle Rechnerstruktur Rechen- werk Speicher (enthält Daten und Programme) Steuer- CPU werk „von Neumann Rechner“ RA – WS 2024/2025 Grundstrukturen 2 Eigenschaften (1) § Programmgesteuerter Universalrechner Zentraleinheit mit Steuerwerk & Operationswerk Speicher enthält Daten & Programme E/A-System als Schnittstelle nach außen RA – WS 2024/2025 Grundstrukturen 3 Eigenschaften (2) § Speicher besteht aus Plätzen fester Wortlänge, über Adressen einzeln ansprechbar § Darstellung von Daten und Befehlen als Binärzahlen § Programme und Daten können an derselben Stelle abgelegt werden § Programme können verarbeitet werden und sich selbst modifizieren RA – WS 2024/2025 Grundstrukturen 4 Befehlszyklus – 2-Phasen-Konzept Befehl holen und dekodieren Befehl ausführen RA – WS 2024/2025 Grundstrukturen 5 Phase 1: Interpretationsphase § Befehlszähler zeigt Adresse einer Speicherzelle an, Inhalt wird geholt und als Befehl interpretiert. § Transport des Befehls vom Hauptspeicher in das Befehlsregister. Erhöhen des Befehlszählers. RA – WS 2024/2025 Grundstrukturen 6 Phase 2: Ausführungsphase § Inhalt weiterer Speicherzellen, deren Adressen im Befehl spezifiziert sind, wird geholt und verarbeitet. Transport der Operanden vom Hauptspeicher oder dem Register in das Operationswerk. Ausführen der Operation. Transport des Resultats vom Operationswerk in den Hauptspeicher oder den Registerspeicher. Weiter mit nächster Interpretationsphase. RA – WS 2024/2025 Grundstrukturen 7 Beispiel: Berechne (8+7)*2 = 30 CPU Speicher aktueller add mult 111 100 110 Befehl 101111 111 Adresse Daten/Befehle 000 add 100 101 111 aktuelles Datum 1 0000000000001000 0000000000001111 001 mult 111 110 111 aktuelles Datum 2 0000000000000111 0000000000000010 010 011 100 0000000000001000 Ergebnis 0000000000001111 0000000000011110 101 0000000000000111 110 0000000000000010 000 Befehlszähler 001 111 0000000000001111 0000000000011110 RA – WS 2024/2025 Grundstrukturen 8 Klassische Strukturen für Zentraleinheit § Stack § Akkumulator § Struktur mit allgemeinem Registersatz RA – WS 2024/2025 Grundstrukturen 9 Stack-basierte Struktur Haupt- speicher ALU Befehl Aktion PUSH Speicher Inhalt von HS-Adresse Speicher wird auf Stack gelegt POP Speicher Oberstes Wort wird vom Stack entfernt und an HS-Adresse Speicher geschrieben OP Operanden werden vom Stack entfernt, verknüpft und das Ergebnis wird auf den Stack zurückgelegt RA – WS 2024/2025 Grundstrukturen 10 Beispiel: C = A + B Befehlsformate PUSH A befehl adresse PUSH B befehl adresse ADD befehl POP C befehl adresse RA – WS 2024/2025 Grundstrukturen 11  Tafelbeispiel E = (A + B) · C + D RA – WS 2024/2025 Grundstrukturen 12 Bewertung § Vorteile: einfaches Konzept, kurze Befehle § Nachteile: langsam, komplizierte Compiler RA – WS 2024/2025 Grundstrukturen 13 Beispiele für Stack-Rechner § Borroughs B5000, 1963 § Taschenrechner § Java Virtual Machine picoJava Core von SUN RA – WS 2024/2025 Grundstrukturen 14 Akkumulator-basierte Struktur ALU Haupt- speicher Akkumulator Befehl Aktion LOAD Speicher Inhalt der HS-Adresse Speicher wird in den Akkumulator geschrieben STORE Speicher Inhalt des Akkumulators wird an HS-Adresse Speicher geschrieben OP Speicher Inhalt der HS-Adresse Speicher wird mit dem Akku- mulator verknüpft, Ergebnis im Akkumulator abgelegt RA – WS 2024/2025 Grundstrukturen 15 Beispiel: C = A + B Befehlsformate LOAD A befehl adresse ADD B befehl adresse STORE C befehl adresse RA – WS 2024/2025 Grundstrukturen 16  Tafelbeispiel E = (A + B) · C + D RA – WS 2024/2025 Grundstrukturen 17 Bewertung § Vorteile: kurze Befehle (1-Adressbefehle) § Nachteile: langsam, hohe Speicherkommunikation RA – WS 2024/2025 Grundstrukturen 18 Beispiele für Akkumulator-Rechner § IAS Rechner von J. von Neumann § Microcontroller für Spezialanwendungen RA – WS 2024/2025 Grundstrukturen 19 Rechner mit allgemeinem Registersatz (GPR machines) Haupt- speicher Register 0 Register 1 ALU Register n RA – WS 2024/2025 Grundstrukturen 20 Klassifikation von GPR Maschinen § # Adressen Beispiel: 2-Adressbefehle und 3-Adressbefehle – ADD R1, R2 (R1 = R1 + R2) – ADD Rd, Rs1, Rs2 (Rd = Rs1 + Rs2) § # Operanden im Hauptspeicher (m, n) Klassifikation: von n Operanden sind m im Hauptspeicher RA – WS 2024/2025 Grundstrukturen 21 (0, n): Register-Register-Maschine § Einfache Befehlscodierung § Befehle gleicher Art benötigen gleiche Taktzahl § Hohe Zahl von Befehlen, lange Programme RA – WS 2024/2025 Grundstrukturen 22  (m, n), m > 0: Register-Speicher-Maschine § leichterer Datenzugriff § hohe Befehlsdichte § Operanden nicht äquivalent § variierende Taktzahl RA – WS 2024/2025 Grundstrukturen 23 (m, m): Speicher-Speicher-Maschine § kompakte Programme § viele Speicherzugriffe § variierende Taktzahl RA – WS 2024/2025 Grundstrukturen 24  Tafelbeispiel E = (A + B) · C + D RA – WS 2024/2025 Grundstrukturen 25 Beispiel für GPR-Maschine: MIPS § Ursprung: MIPS RISC Projekt in Stanford RISC: Reduced Instruction Set Computer Projektstart 1981 Ab 1984 kommerziell verfügbar Einsatz in Hochleistungsrechnern aber auch Consumer Electronics (z.B. Playstation 2) § Grundlage für viele moderne RISC Prozessoren RISC-V als Weiterentwicklung, Open-Source Hardware RA – WS 2024/2025 Grundstrukturen 26 MIPS Strukturmerkmale § 32 Register R0,..., R31 Register R0 = 0 § Speicher...000...001...010...011 32-bit Worte...100...101...110...111 Byte Adressierung.... RA – WS 2024/2025 Grundstrukturen 27 MIPS-Befehle (3 Befehlsrahmen) Load/Store Befehle, Verzweigungen 6 5 5 16 opcode rs rt address Registerbefehle 6 5 5 5 5 6 opcode rs rt rd shamt func Sprungbefehle 6 26 opcode address RA – WS 2024/2025 Grundstrukturen 28  MIPS-Struktur (vereinfacht) M U X Schieben(2) 4 Add PC Erg. Add 5 Register 1 ALU Funktion Adresse 5 Lesen Daten aus Befehl Register 1 3 Register 2 Befehls- 5 Lesen M Null Daten aus Erg. speicher Register 3 U Register 2 ALU Schreiben X Erweiterung Daten für Register 3 Registersatz Sp.L. Sp.Schr. Reg.Schreiben Adresse Daten Daten M Datenspeicher U X RA – WS 2024/2025 Grundstrukturen 29  Befehlszyklus: 1. Befehl holen (Instruction Fetch / IF) M U X Schieben(2) 4 Add PC Erg. Add 5 Register 1 ALU Funktion Adresse 5 Lesen Daten aus Befehl Register 1 3 Register 2 Befehls- 5 Lesen M Null Daten aus Erg. speicher Register 3 U Register 2 ALU Schreiben X Erweiterung Daten für Register 3 Registersatz Sp.L. Sp.Schr. Reg.Schreiben Adresse Daten Daten M Datenspeicher U X RA – WS 2024/2025 Grundstrukturen 30  2. Befehl dekodieren, Register holen (Instruction Decode / ID) M U X Schieben(2) 4 Add PC Erg. Add 5 Register 1 ALU Funktion Adresse 5 Lesen Daten aus Befehl Register 1 3 Register 2 Befehls- 5 Lesen M Null Daten aus Erg. speicher Register 3 U Register 2 ALU Schreiben X Erweiterung Daten für Register 3 Registersatz Sp.L. Sp.Schr. Reg.Schreiben Adresse Daten Daten M Datenspeicher U X RA – WS 2024/2025 Grundstrukturen 31  3. Befehl ausführen (Execute / EX) M U X Schieben(2) 4 Add PC Erg. Add 5 Register 1 ALU Funktion Adresse 5 Lesen Daten aus Befehl Register 1 3 Register 2 Befehls- 5 Lesen M Null Daten aus Erg. speicher Register 3 U Register 2 ALU Schreiben X Erweiterung Daten für Register 3 Registersatz Sp.L. Sp.Schr. Reg.Schreiben Adresse Daten Daten M Datenspeicher U X RA – WS 2024/2025 Grundstrukturen 32  4. Speicherzugriff (Memory / MEM) M U X Schieben(2) 4 Add PC Erg. Add 5 Register 1 ALU Funktion Adresse 5 Lesen Daten aus Befehl Register 1 3 Register 2 Befehls- 5 Lesen M Null Daten aus Erg. speicher Register 3 U Register 2 ALU Schreiben X Erweiterung Daten für Register 3 Registersatz Sp.L. Sp.Schr. Reg.Schreiben Adresse Daten Daten M Datenspeicher U X RA – WS 2024/2025 Grundstrukturen 33  5. Ergebnis zurückschreiben (Write Back / WB) M U X Schieben(2) 4 Add PC Erg. Add 5 Register 1 ALU Funktion Adresse 5 Lesen Daten aus Befehl Register 1 3 Register 2 Befehls- 5 Lesen M Null Daten aus Erg. speicher Register 3 U Register 2 ALU Schreiben X Erweiterung Daten für Register 3 Registersatz Sp.L. Sp.Schr. Reg.Schreiben Adresse Daten Daten M Datenspeicher U X RA – WS 2024/2025 Grundstrukturen 34 RA – WS 2024/2025 Grundstrukturen 35 Gliederung der Vorlesung 1) Meilensteine aus der Geschichte 2) Grundstrukturen 3) Leistungsbewertung 4) Befehlssätze und Assemblerprogrammierung 5) Datenpfad und Steuerwerk 6) Fließbandverarbeitung (Pipelining) 7) Speicherorganisation (insb. Cache-Organisation, virtueller Speicher) 8) Ein-/Ausgabe RA - WS 2024/2025 Leistung und Kosten 1 Leistung und Kosten § Verhältnis (Trade-off) Leistung - Kosten entscheidend für Rechnerbewertung RA - WS 2024/2025 Leistung und Kosten 2 Kosten für Workstation (nach A. Bechtoldsheim, SUN, 1993) System Subsystem % Gesamtkosten Gehäuse Metall, Plastik 1% Stromversorgung, Ventilatoren 2% Kabel, Schrauben, Muttern 1% (Teilsumme) (4%) CPU-Platine Prozessor 6% DRAM (64MB) 36% Video System 14% I/O System 3% Platine 1% (Teilsumme) (60%) I/O Tastatur, Maus 1% Monitor 22% Plattenspeicher (1 GB) 7% Bandlaufwerk (DAT) 6% (Teilsumme) (36%) RA - WS 2024/2025 Leistung und Kosten 3 Kosten für $1000 PC, 2001 (nach Hennessy/Patterson) System Subsystem % Gesamtkosten Gehäuse Metall, Plastik 2% Stromversorgung, Ventilatoren 2% Kabel, Schrauben, Muttern 1% Verpackung, Manuals 1% (Teilsumme) (6%) CPU-Platine Prozessor 22% DRAM (128 MB) 5% Video Karte 5% Motherboard 5% (Teilsumme) (37%) I/O Tastatur, Maus 3% Monitor 19% Plattenspeicher (20 GB) 9% DVD Laufwerk 6% (Teilsumme) (37%) Software Betriebssystem und Office Paket 20% RA - WS 2024/2025 Leistung und Kosten 4 Chipherstellung § Waferherstellung § Aufteilung in Chips (“dies”) § Chips mit Gehäuse versehen (“packaging”) RA - WS 2024/2025 Leistung und Kosten 5 Wafer mit 564 MIPS S64 20K* Prozessoren * MIPS S64 mit speziellen Befehlen für 3D Graphik RA - WS 2024/2025 Leistung und Kosten 6 Chipkosten abhängig von § Kosten des Wafers § Zahl der Chips pro Wafer § Ausbeute (Anteil der funktionsfähigen Chips) RA - WS 2024/2025 Leistung und Kosten 7 Chipkosten (nach Hennessy/Patterson) Wafer_cost Die_cost = Dies_per_Wafer *× Die_yield Wafer_area Dies_per_Wafer ≈ Die_area Die_yield ≈ −α ⎛ Defects_per_unit_area *× Die_area ⎞ Wafer_yield *× ⎜1 + ⎟ ⎝ α ⎠ RA - WS 2024/2025 Leistung und Kosten 8 Annahmen § Defekte sind zufällig über den Wafer verteilt § Chipausbeute ist umgekehrt proportional zur Komplexität des Herstellungsprozesses § Bei modernen Prozessen: a » 4,0 § Bei älteren Prozessen: a zwischen 2,0 und 3,0 § Waferausbeute kann vereinfacht als 1,0 angenommen werden RA - WS 2024/2025 Leistung und Kosten 9  Beispiele Chip Metal Line Wafer Defects Area Dies/ Yield Die Cost layers width cost /cm2 mm2 wafer µm 386DX 2 0.90 $900 1.0 43 360 71% $4 486DX2 3 0.80 $1200 1.0 81 181 54% $12 PowerPC 601 4 0.80 $1700 1.3 121 115 28% $53 HP PA 7100 3 0.80 $1300 1.0 196 66 27% $73 DEC Alpha 3 0.70 $1500 1.2 234 53 19% $149 SuperSPARC 3 0.70 $1700 1.6 256 48 13% $272 Pentium 3 0.80 $1500 1.5 296 40 9% $417 Aus: "Estimating IC Manufacturing Costs,” by Linley Gwennap, Microprocessor Report, August 2, 1993, p. 15 RA - WS 2024/2025 Leistung und Kosten 10 Technologiefortschritt vs. Ausbeute 45nm 90nm 65nm Defect 130nm Density 180nm 00 02 04 06 Time From: R. Madge, ITC 2004 RA - WS 2024/2025 Leistung und Kosten 11 Preisentwicklung für Pentium3 Prozessoren Leistung - Grundbegriffe Logik Register & Register … & … =1 … Takt Takt Taktsignal Zykluszeit Frequenz = 1/Zykluszeit RA - WS 2024/2025 Leistung und Kosten 13 Grundbegriffe § Antwortzeit/Ausführungszeit/CPU-Zeit: # CPU-Takte × Zykluszeit = # CPU-Takte / Frequenz § Durchsatz: # erledigte Aufgaben pro Zeiteinheit RA - WS 2024/2025 Leistung und Kosten 14 Was heisst n-mal schneller als? § Rechner A ist n-mal schneller als Rechner B bedeutet: AusführungszeitB n= AusführungszeitA § bzw: DurchsatzA n= DurchsatzB RA - WS 2024/2025 Leistung und Kosten 15 Speedup § Speedup: Ausführungszeit mit alter / langsamer Variante Ausführungszeit mit neuer / schneller Variante RA - WS 2024/2025 Leistung und Kosten 16 Quantitative Prinzipien beim Rechnerentwurf § Berücksichtige Technologieentwicklung § Nutze Lokalitätsprinzip Beispiel: Speicherhierarchie Haupt- CPU Cache Festplatte speicher § Amdahl’s Law RA - WS 2024/2025 Leistung und Kosten 17 Amdahl’s Law § Zeitgewinn durch verbessertes Modul M ist begrenzt durch die Zeit, in der M genutzt werden kann § tneu = talt(1 - AnteilM) + talt/SpeedupM × AnteilM talt § Speedupgesamt = talt/tneu = talt(1 - AnteilM + AnteilM/SpeedupM) § Anteil an Rechenzeit: Häufigkeit der Nutzung * Zeit RA - WS 2024/2025 Leistung und Kosten 18 Beispiel 1 M: Gleitkommaeinheit, nach Verbesserung doppelte Geschwindigkeit für Gleitkommabefehle Aber: Gleitkommabefehle tragen nur 10% zur Rechenzeit bei tneu = 0,9 × talt + 0,1 × talt /2 = 0,95 × talt 1 Speedupgesamt = = 1,053 0,95 RA - WS 2024/2025 Leistung und Kosten 19 Beispiel 2 – Verschiedene Befehlsklassen Befehlsklasse talt Häufigkeit Speedup I 12 10 % 3 II 6 80 % 1,5 III 4 10 % 1 talt = 0,1 × 12 + 0,8 × 6 + 0,1 × 4 = 1,2 + 4,8 + 0,4 = 6,4 tneu = 0,1 × 4 + 0,8 × 4 + 0,1 × 4 = 0,4 + 3,2 + 0,4 = 4 Speedupgesamt = 6,4 / 4 = 1,6 RA - WS 2024/2025 Leistung und Kosten 20 Leistungsbewertung § Auswertung von Hardwareparametern z. B. Taktfrequenz § Laufzeitmessungen RA - WS 2024/2025 Leistung und Kosten 21 Auswertung von Hardwareparametern § Systemleistung: Ausführungszeit auf unbelastetem System § CPU-Zeit = # CPU-Takte × Zykluszeit = # CPU-Takte / Taktfrequenz RA - WS 2024/2025 Leistung und Kosten 22 CPI § Takte pro Befehl (clocks per Instruction): CPI Damit: CPU-Zeit = CPI × # Befehle / Taktfrequenz Durchschnittswert § Bei Befehlssatz mit n Befehlen I1,..., In: – CPIi : durchschnittliche Taktzahl von Befehl Ii – pi : relative Häufigkeit von Befehl Ii CPI = S CPIi × pi RA - WS 2024/2025 Leistung und Kosten 23 Bestimmung der pi § MIXE typische Mischung von Befehlen § Kernprogramme Anwenderprogramme aus charakteristischen Stücken echter Programme RA - WS 2024/2025 Leistung und Kosten 24 Maßzahlen § MIPS (Millionen Instruktionen pro Sekunde) 1 Taktfrequenz MIPS = = CPI × Zykluszeit × 106 CPI × 106 § MFLOPS (Millionen Gleitkommaoperationen pro Sekunde) § Probleme: Instruktionen haben unterschiedliches “Gewicht”, sind nicht vergleichbar... RA - WS 2024/2025 Leistung und Kosten 25 Laufzeitmessungen § Maßzahlen werden aus Laufzeitmessungen für “Benchmarks” bestimmt § Benchmarks sind synthetische oder typische Anwenderprogramme § Beispiele für synthetische Benchmarks Whetstone, 1976 Dhrystone, 1984 RA - WS 2024/2025 Leistung und Kosten 26 SPEC Benchmarks § SPEC: System Performance Evaluation Cooperation 1989 von Computer Firmen gegründet (Apollo/HP, DEC, MIPS und SUN) erste Benchmarks waren z.B. Gnu Compiler, TeX, Spice Leistung wird bewertet im Vergleich zu einer Referenzmaschine (VAX-11/780 bei ersten Benchmarks) Reproduzierbarkeit der Ergebnisse wird durch ausführliche Dokumentation von Benchmarkexperimenten unterstützt Vgl. http://www.spec.org RA - WS 2024/2025 Leistung und Kosten 27 SPEC 2017 für CPU-intensive Programme § Vgl. SPEC Webseite http://www.spec.org/cpu2017/Docs/overview.html#metrics RA - WS 2024/2025 Leistung und Kosten 28 SPEC 2017 für CPU-intensive Programme § Referenzmaschine “The reference machine is a historical Sun Microsystems server, the Sun Fire V490 with 2100 MHz UltraSPARC-IV+ chips. The UltraSPARC-IV+ was introduced in 2006, and is newer than the chip used in the CPU 2000 and CPU 2006 reference machines (the 300 MHz 1997 UltraSPARC II).“ RA - WS 2024/2025 Leistung und Kosten 29 Bestimmung von SPECspeed § Determine elapsed time in s for all benchmarks § Calculate ratio to numbers for reference machine time for reference machine / time for new machine § Calculate geometric mean over all benchmarks RA - WS 2024/2025 Leistung und Kosten 30 Genauer § Gegeben: Maschinen Mj, j = 1, …, k Programme Pi, i = 1, …, n Referenzmaschine Mj* Ausführungszeiten tij von Pi auf Mj § Berechnung von SPECspeed SPEC(M j ) = n ∏ t ij* =n ∏t ij* t ij ∏t ij RA - WS 2024/2025 Leistung und Kosten 31 € Warum geometrisches Mittel? § Ergebnis unabhängig von der Reihenfolge bei Normalisierung und Mittelwertbildung ∏ tij* n ∏ tij* SPEC ( M j ) = n = ∏ tij n ∏ tij RA - WS 2024/2025 Leistung und Kosten 32 § Rangfolge für Maschinen unabhängig von der Auswahl der Referenzmaschine n SPEC ( M j ) < SPEC ( M l ) ⇔ ∏ tij* < n ∏ tij* ⇔ n ∏ tij n ∏ til gilt nicht für arithmetisches n ∏ til < n ∏ tij ⇔ Mittel n ∏ tij** < n ∏ tij** n ∏ tij n ∏ til RA - WS 2024/2025 Leistung und Kosten 33  Geometrisches « Arithmetisches Mittel Laufzeit absolut Referenz- Referenz- Referenz- maschine A maschine B maschine C A B C A B C A B C A B C Prg. 1 20 200 400 1 0,1 0,05 10 1 0,5 20 2 1 Prg. 2 20 2 0,4 1 10 50 0,1 1 5 0,02 0,2 1 Ar. M. 20 101 200,2 1 5,05 25,03 5,05 1 2,75 10,01 1,1 1 Geo. M. 20 20 12,65 1 1 1,58 1 1 1,58 0,63 0,63 1 RA - WS 2024/2025 Leistung und Kosten 34 § Problem bei geometrischem Mittel Maschine mit bester Gesamtzeit bekommt nicht unbedingt die beste Bewertung § Ist Mittelwert überhaupt sinnvoll? RA - WS 2024/2025 Leistung und Kosten 35 Weitere Benchmarks § SPECapc: Graphikleistung § SPECviewperf: Graphikleistung mit OpenGL § SPEC... § Weitere Benchmarkinitiativen RA - WS 2024/2025 Leistung und Kosten 36 Weitere Verfahren zur Leistungsbewertung § Überwachung des Betriebs mit HW oder SW “Monitoren” § Modelltheoretische Verfahren Analytische Verfahren, Warteschlangenmodelle Simulationsverfahren RA - WS 2024/2025 Leistung und Kosten 37  Übersicht – Rechnerbewertung und Anwendungsmöglichkeiten Auswertung Laufzeit- Messungen Modell- von Hardware- messungen während des theoretische parametern Betriebs Verfahren Rechner- Maßzahlen auswahl für die Operations- geschwindigkeit Benchmarks Mixe Kernprogramme Rechner Hardware- Tuning monitore Software- monitore Rechner- Analytisch entwurf Simulationen RA - WS 2024/2025 Leistung und Kosten 38 Gliederung der Vorlesung 1) Meilensteine aus der Geschichte 2) Grundstrukturen 3) Leistungsbewertung 4) Befehlssätze und Assemblerprogrammierung 5) Datenpfad und Steuerwerk 6) Fließbandverarbeitung (Pipelining) 7) Speicherorganisation (insb. Cache-Organisation, virtueller Speicher) 8) Ein-/Ausgabe RA - WS 2024/2025 Befehlssätze 1 Befehlssatz ist HW / SW Schnittstelle Software Befehlssatz (instruction set) Hardware RA - WS 2024/2025 Befehlssätze 2 Beispiel § C++ Statements int a = 3; int b = 4; int c = 0; c = a + b; RA - WS 2024/2025 Befehlssätze 3 Beispiel RISC-V § RISC-V Projekt startet 2010 an der Universität Berkeley (Krste Asanovic und David A. Patterson) § Weiterentwicklung des MIPS-Prozessors § Open-Source Hardware § Aktuelle Infos unter https://riscv.org/ RA - WS 2024/2025 Befehlssätze 4 RISC-V Hardware RA - WS 2024/2025 Befehlssätze 5 RISC-V Assemblercode # Assemblercode zur Addition zweier 32-Bit Zahlen …. # core of program starts lw t1, vara # load variable a into register t1 lw t2, varb # load variable b into register t2 add t3, t2, t1 # add contents of t1 and t2, result in t3 sw t3, varc # store contents of t3 as variable c # core of program ends … RA - WS 2024/2025 Befehlssätze 6 Compiler, Assembler, Linker und Loader C program Compiler Assembly language program Assembler Object: Machine language module Object: Library routine (machine language) Linker Executable: Machine language program Loader Memory Assemblersprache § Eigenschaften Symbolische Repräsentation eines Maschinenprogramms Spezifisch für eine Rechnerfamilie (“Instruction Set Architecture” / ISA), z. B. RISC-V Assembler, x86-Assembler, etc. § In Assembler programmieren? Manchmal im Bereich eingebetteter Systeme Bei Programmen für General Purpose Rechner lieber nicht (Programme sind unübersichtlich, schlechter wartbar, rechnerspezifisch, …)! RA - WS 2024/2025 Befehlssätze 8  Assembler § Übersetzt in Maschinensprache und erzeugt Programmdatei im Objektformat Aufbau der Datei: Grösse und Beispiel: Header UNIX Position der anderen Bereiche Objektformat Program Text Befehle in Maschinensprache Static Data Statisch definierte Daten Relocation Information Information über Befehle und Daten, die von absoluten Adressen abhängen Symbol Table Liste von noch nicht definierten Adressen, Debug Information z.B. Referenzen zu externen Prozeduren Information zu Datenstrukturen, Name der Quelldatei, etc. RA - WS 2024/2025 Befehlssätze 9 Exkurs: RISC-V Assemblersimulator Ripes § Downloads und Tutorials unter https://github.com/mortbopet/Ripes RA - WS 2024/2025 Befehlssätze 10 Beispiel $ Berechne !𝑖 für n = 5 !"# RA - WS 2024/2025 Befehlssätze 11 Maschinen- 0: 4: 00400893 10000517 00000000010000000000100010010011 00010000000000000000010100010111 code 8: ffc50513 11111111110001010000010100010011 c: 00000073 00000000000000000000000001110011 10: 10000297 00010000000000000000001010010111 14: 0212a283 00000010000100101010001010000011 18: 00100313 00000000000100000000001100010011 1c: 006003b3 00000000011000000000001110110011 00000020 : 20: 00130313 00000000000100110000001100010011 24: 006383b3 00000000011000111000001110110011 28: fe534ce3 11111110010100110100110011100011 2c: 00400893 00000000010000000000100010010011 30: 10000517 00010000000000000000010100010111 34: ff050513 11111111000001010000010100010011 38: 00000073 00000000000000000000000001110011 3c: 00038513 00000000000000111000010100010011 40: 00100893 00000000000100000000100010010011 44: 00000073 00000000000000000000000001110011 RA - WS 2024/2025 Befehlssätze 12  0: 00400893 addi x17 x0 4 4: 10000517 auipc x10 0x10000 Assemblercode 8: ffc50513 addi x10 x10 -4 c: 00000073 ecall 10: 10000297 auipc x5 0x10000 14: 0212a283 lw x5 33 x5 18: 00100313 addi x6 x0 1 1c: 006003b3 add x7 x0 x6 00000020 : 20: 00130313 addi x6 x6 1 24: 006383b3 add x7 x7 x6 28: fe534ce3 blt x6 x5 -8 2c: 00400893 addi x17 x0 4 30: 10000517 auipc x10 0x10000 34: ff050513 addi x10 x10 -16 38: 00000073 ecall 3c: 00038513 addi x10 x7 0 40: 00100893 addi x17 x0 1 44: 00000073 ecall RA - WS 2024/2025 Befehlssätze 13.data “komfortabler” prompt1:.string "\nWelcome to our first program!\n" prompt2:.string "\nThe result is: " Assemblercode varn:.word 5.text # print welcome message li a7 4 la a0 prompt1 Direktiven ecall # compute formula sum(1,n,i) lw t0 varn Labels li t1 1 add t2 zero t1 loop: addi t1 t1 1 add t2 t2 t1 zusätzlich möglich: blt t1 t0 loop Kommentare # print ressult symbolische li a7 4 Registernamen la a0 prompt2 ecall Pseudobefehle mv a0 t2 li a7 1 ecall RA - WS 2024/2025 Befehlssätze 14 Konventionen für die Verwendung der Register Register Alias Usage x0 zero constant 0 x1 ra return address x2 sp stack pointer x3 gp global pointer x4 tp thread pointer x5 - x7 t0 - t2 temporary registers (not preserved across call) x8 s0/fp saved register / frame pointer x9 s1 saved register x10 - x11 a0 - a1 function arguments (return values) x12 - x17 a2 - a7 function arguments x18 - x27 s2 - s11 saved registers x28 - x31 t3 - t6 temporary registers RA - WS 2024/2025 Befehlssätze 15 Beispiel für Assemblerdirektiven Directive Meaning.data Store the subsequent items in the data segment.string.byte.word.text Store the subsequent items in the text segment (instructions or words). RA - WS 2024/2025 Befehlssätze 16 Environment Calls (ecall) a7 a0 Name Description Prints the value located in a0 as a 1 (integer to print) print_int signed integer Prints the value located in a0 as a 2 (float to print) print_float floating point number Prints the null-terminated string 4 (pointer to string) print_string located at address in a0 10 - exit Halts the simulator Prints the value located in a0 as 11 (char to print) print_char an ASCII character Prints the value located in a0 as a 34 (integer to print) print_hex hex number Prints the value located in a0 as a 35 (integer to print) print_bin binary number Prints the value located in a0 as 36 (integer to print) print_unsigned an unsigned integer Halts the simulator and exits with 93 (status code) exit RA - WS 2024/2025 status code in a0 17 Befehlssätze  Ende Exkurs RA - WS 2024/2025 Befehlssätze 18 Entscheidungen beim Befehlssatzentwurf (1) # Assemblercode zur Addition von zwei 32-Bit Zahlen Adressierung …. # core of program starts lw t1, vara # load variable a into register t1 lw t2, varb # load variable b into register t2 add t3, t2, t1 # add contents of t1 and t2, result in t3 sw t3, varc # store contents of t3 as variable c # core of program ends Welche Befehle? … Was noch? Kodierung RA - WS 2024/2025 Befehlssätze 19 Entscheidungen beim Befehlssatzentwurf (2) // recursive function for n! int fac(int n) { if (n == 0) return 1; else return n*fac(n-1); Unterstützung von } Hochsprachen, insbesondere von int main() Funktionsaufrufen { // integer for testing n! int n = 7; cout = t1) j cont less_than: add t2 t1 zero # es gilt (t0 < t1) # move t1 to t2 (result) cont: add a0 t2 zero # schreibe Ergebnis in Register fuer # Parameteruebergabe jr ra # Ruecksprung RA - WS 2024/2025 Befehlssätze 69 Rekursive Funktionsaufrufe § Problem: Rücksprungadresse in Register ra wird bei wiederholtem Funktionsaufruf immer wieder überschrieben Entsprechendes gilt für lokale Daten in Registern § Lösung: Sichere Rücksprungadressen und lokale Daten auf einem Stack RA - WS 2024/2025 Befehlssätze 70 Stack sp sp – 4*xx weitere niedrige Daten Adressen ra sp + 4(xx-1) Stackpointer sp spezieller Bereich im Hauptspeicher... hohe Adressen RA - WS 2024/2025 Befehlssätze 71 Beispiel § Fakultät int fak(n) { if (n < 1) return 1; else return n*fak(n-1); } RA - WS 2024/2025 Befehlssätze 72 RISC-V Assemblercode.data prompt1:.string "\nWelcome to our first recursive program!\n" prompt2:.string "\nThe result is: " varn:.word 4.text # print welcome message... # compute function factorial(n) main: lw a1 varn # Lade Parameter n jal ra fac # Funktionsaufruf # print ressult... #exit... #function factorial fac:... RA - WS 2024/2025 Befehlssätze 73 RISC-V Assemblercode (1) fac: addi sp sp -8 # schaffe Platz auf dem Stack sw a1 0(sp) # sichere Parameter n sw ra 4(sp) # sichere Rücksprungadresse blt zero a1 recursion # prüfe Abbruchbedingung addi a1 zero 1 # für n=0 ist das Ergebnis 1 addi sp sp 8 # Stack freigeben jalr ra # Rücksprung recursion: addi a1 a1 -1 # n = n-1 jal ra fac # rekursiver Funktionsaufruf lw ra 4(sp) # hole Rücksprungadresse vom Stack lw t1 0(sp) # hole Parameter vom Stack addi sp sp 8 # Stack freigeben mul a1 a1 t1 # Ergebnis ist fac(n-1)*n jalr ra # Rücksprung RA - WS 2024/2025 Befehlssätze 74 Allgemein Hauptprogramm Call (Aktivierung) Prozedur A (Parameter) aufrufende aufgerufene Funktion Funktion Prozedur B Funktion C lokale (zurück- lokale Variable gegebener Variable Wert) gemeinsame Umgebung RA - WS 2024/2025 Befehlssätze 75 Umgebung einer Funktion (Aktivierungsblock) § Aufbau Explizite Parameter Implizite Parameter – Statischer Zeiger (auf umgebende Funktion) – Dynamischer Zeiger (auf aufrufende Funktion) – Rücksprungadresse – Sonstige Lokale Daten RA - WS 2024/2025 Befehlssätze 76 § Aktivierungsblöcke werden gemäß der Programmschachtelung auf den Stack gelegt. RA - WS 2024/2025 Befehlssätze 77 Struktur von Aktivierungsblöcken Stackpointer SP Richtung Lokale Datenstrukturen des Lokale Daten Lokale Skalare Stack Framepointer FP Dynamischer Zeiger DL Statischer Zeiger SL Rücksprungsadresse PC Implizite Parameter Andere implizite Parameter Aktueller Parameter N Explizite Parameter Aktueller Parameter 1 Vorhergehender Aktivierungsblock RA - WS 2024/2025 Befehlssätze 78 Entscheidungen beim Befehlssatzentwurf (3) Zusammenfassung § Adressierung § Unterstützung von Hochsprachen (insbesondere von Funktionsaufrufen) § Kodierung § Auswahl der Befehle RA - WS 2024/2025 Befehlssätze 79 Befehlsformat Opcode Operand 1 Operand N Datum 1 Datum N Weitere Felder z.B. für § Spezifikation des Datentyps § Richtung beim Datentransfer § Operationstyp RA - WS 2024/2025 Befehlssätze 80 RISC-V-Befehle Beispiel add addi, lw sw beq lui jal RA - WS 2024/2025 Befehlssätze 81 Weiteres Beispiel: Intel x86 § 1978: 8086, 16-bit Architektur, alle Register Spezialregister § 1980: 8087 FP Koprozessor liefert Erweiterung um 60 FP Befehle, stackbasiert § 1982: 80286, 24-bit Adressraum § 1985: 80386, Erweiterung auf 32-bit Architektur: 32-bit Register (“E”), teilweise als allgemeiner Registersatz nutzbar, 32-bit Adressraum RA - WS 2024/2025 Befehlssätze 82 § 1989-95: 80486, Pentium (1992) und PentiumPro (1995) mit nur wenigen zusätzlichen Befehlen § 1997: Zusätzlich 57 MMX Befehle für Multimedia und Kommunikationsbefehle, verwenden FP Stack § 1999: Streaming SIMD Extensions (SSE) SIMD: Single Instruction Multiple Data, Parallele Abarbeitung mehrerer Operationen in einem Befehl, hier Floating-Point Operationen mit einfacher Genauigkeit § 2001: SSE2, hauptsächlich Varianten von MMX- Befehlen mit doppelter Genauigkeit RA - WS 2024/2025 Befehlssätze 83 § 2003: Erweiterung durch AMD auf 64-bit Architektur § 2004: Intel übernimmt AMD-Erweiterungen (EM64T) § 2007: AMD kündigt SSE5 an § 2008: Advanced Vector Extensions (AVX) SSE Register werden von 128-bit Registern auf 256-bit Register erweitert § 2020: Advanced Matrix Extensions (Intel AMX) für Machine Learning RA - WS 2024/2025 Befehlssätze 84  Registersatz des Intel 80386 Name Use 31 0 EAX GPR0 ECX EDX EBX... ESP EBP ESI EDI GPR7 CS Code segment pointer SS Stack segment pointer DS Data segment pointer 0 ES... FS GS Data segment pointer 3 EIP Instruction pointer (PC) EFLAGS Condition codes RA - WS 2024/2025 Befehlssätze 85 Beispiele für Befehle Instruction Function JE name if equal (condition code) [EIP = name]; JMP name EIP = name; CALL name SP = SP-4; M[SP] = EIP + 5; EIP = name; MOVW EBX, [EDI+45] EBX = M[EDI + 45]; PUSH ESI SP = SP - 4; M[SP] = ESI; POP EDI EDI = M[SP]; SP = SP + 4; ADD EAX, #6765 EAX = EAX + 6765 TEST EDX, #42 Set condition code flags with EDX and 42hex MOVSL M[EDI] = M[ESI]; EDI = EDI + 4; ESI = ESI + 4; RA - WS 2024/2025 Befehlssätze 86 Befehlsformate a. JE EIP + Displacement 4 4 8 JE Cond. Displacement b. CALL 8 32 CALL Offset C. MOV EBX, [EDI+45] 6 1 1 8 8 w: word (32-bit) or byte MOV d w Postbyte (r/m) Displacement d: direction Postbyte: Addressing mode RA - WS 2024/2025 Befehlssätze 87 d. PUSH ESI 5 3 PUSH Reg. e. ADD EAX, #6765 4 3 1 32 ADD Reg. w Immediate f. TEST EDX, #42 Bitweises AND, Ergebnis -> Condition Code 7 1 8 32 TEST w Postbyte Immediate RA - WS 2024/2025 Befehlssätze 88 Kodierung der Adressinformation Postbyte mod reg r/m [aus Hennessy/Patterson] ENDE Beispiel RA - WS 2024/2025 Befehlssätze 89 Speichereffiziente Kodierung § Unterschiedliche Befehle kommen unterschiedlich häufig vor Kodiere die häufigsten Befehle am kürzesten (wie Morsealphabet) Huffman Kodierung (Übungsaufgabe) RA - WS 2024/2025 Befehlssätze 90 Geschwindigkeitseffiziente Kodierung (1) § Alle Befehle haben: Gleiche Länge Gleiches Format In jedem Feld die gleiche Bedeutung RA - WS 2024/2025 Befehlssätze 91 Geschwindigkeitseffiziente Kodierung (2) § “Fixed Field Decoding”: Bereits nach dem Lesen des Befehls sind Operandenadressen bekannt. Dekodierung und Operandenzugriff kann gleichzeitig erfolgen Überwiegend bei modernen Hochgewindigkeitsprozessoren (vgl. RISC-V) RA - WS 2024/2025 Befehlssätze 92 Registeradressen können direkt aus dem Befehlsregister abgelesen werden und sind immer an der gleichen Stelle im Befehl RA - WS 2024/2025 Befehlssätze 93 Entscheidungen beim Befehlssatzentwurf (3) Zusammenfassung § Adressierung § Unterstützung von Hochsprachen (insbesondere von Funktionsaufrufen) § Kodierung § Auswahl der Befehle RA - WS 2024/2025 Befehlssätze 94 Bisher verwendete RISC-V-Befehle add rd rs1 rs2 addi rd rs1 immediate Arithmetik mul rd rs1 rs2 beq rs1 rs2 label bne rs1 rs2 label Verzweigungen blt rs1 rs2 label bge rs1 rs2 label jal rd target Sprünge jalr rd rs offset lui rd imm Datentransfer lw rd rs1 offset sw rs1 rs2 offset RA - WS 2024/2025 Befehlssätze 95 Gleitkomma-Befehle in RISC-V FIGURE 3.17 RISC-V floating-point architecture revealed thus far. This information is also found in column 2 of the RISC-V Reference Data Card at the front of this book. Copyright © 2021 Elsevier Inc. All rights reserved. Grundprinzipien bei der Befehlsauswahl § Vollständigkeit für berechenbare Funktionen soll Maschinenprogramm mit vertretbarem Speicheraufwand erstellt werden können kann nicht einziges Kriterium sein, denn: 1-Befehl Rechner ist möglich § Effizienz häufig benötigte Funktionen sollen schnell ausgeführt werden (mit wenigen Befehlen) RA - WS 2024/2025 Befehlssätze 97 § Regularität erwartete Befehlsarten sollten vorhanden sein, z. B. “leftshift” lässt “rightshift” erwarten § Kompatibilität RA - WS 2024/2025 Befehlssätze 98 Befehlstypen § Arithmetische und logische Befehle § Gleitkommabefehle § Datentransferbefehle z. B. push, pop, load, store, move § Steuerungsbefehle z. B. goto, if … then … else § Ein- / Ausgabebefehle RA - WS 2024/2025 Befehlssätze 99 Bewertung von Befehlssätzen § Ziel: Implementiere häufigste Befehle am effizientesten statische Häufigkeit: Speichereffizienz dynamische Häufigkeit: Ausführungseffizienz § Vorgehen: a) Auswertung von Hochsprachen – Unterstützung häufiger Programmkonstrukte durch Befehle b) Auswertung der Maschinensprache RA - WS 2024/2025 Befehlssätze 100 Auswertung von Hochsprachen § Diskussionsthema der 70er Jahre § Lücke zwischen Möglichkeiten der Programmiersprachen und der Hardware (“Semantic Gap”) § Entwicklung von immer komplexeren Befehlen und Befehlssätzen § CISC (complex instruction set computer) Rechner RA - WS 2024/2025 Befehlssätze 101 § Entwicklungsprojekt HLLCA (High Level Language Computer Architecture): Ersetzen des Compilers durch Hardware § Beispiel: B5000 unterstützt ALGOL (aber: CD6600 schneller) RA - WS 2024/2025 Befehlssätze 102 Problem: Hohe Flexibilität und Variation der Hochsprachen Besser: Vielseitig verwendbare Konstrukte ® Kopplung von Compiler- und Hardwarentwicklung RA - WS 2024/2025 Befehlssätze 103 Auswertung der Maschinensprache Ungleichmäßige Verteilung von § Operationsarten § Adressierungsarten § Displacements § Konstanten RA - WS 2024/2025 Befehlssätze 104 Analyseergebnisse Einfache Operationen ausreichend Einfache Adressierungsarten ausreichend Kleine Werte für Konstante & Displacement ausreichend Wenig Datentypen Häufige Prozeduraufrufe Wenig Parameter in Prozedur Wenig lokale Daten in Prozedur Komplexe Befehle werden vom Compiler schlecht genutzt Emulation häufig schneller RA - WS 2024/2025 Befehlssätze 105 Resultierende Architektur: RISC Einfache Befehle (Ziel: CPI = 1) Kurze Zykluszeit LOAD/STORE-Maschine Großer Registersatz, um möglichst viel vom Aktivierungsblock aufzunehmen Feste Befehlslänge Wenig Befehlsformate Wenige, einfache Adressierungsarten Harvard-Architektur Ausgeprägtes Pipelining RA - WS 2024/2025 Befehlssätze 106 MIPS und RISC-V als Beispiele MIPS RISC-V § Register & Datentypen allgemeine Register R0,..., R31 (32 Bit) – Integer mit/ohne Vorzeichen (8/16/32 Bit) – R0 = #0 Fließkommaregister F0,..., F31 – 32 x einfache Genauigkeit (32 Bit) oder – 16 x doppelte Genauigkeit (64 Bit): F0, F2,... RA - WS 2024/2025 Befehlssätze 107 MIPS RISC-V § Adressierungsarten – unmittelbar – Register-indirekt mit Displacement – PC relativ – pseudodirekt § Befehlsformat – immer 32 Bit RA - WS 2024/2025 Befehlssätze 108 MIPS RISC-V § Befehlstypen Datentransfer – Zugriff auf Speicher (“Load” / ”Store”) – Transfer zwischen Registern Arithmetische & logische Befehle – ADD, SUB, AND, OR, SLT... Sprungbefehle – Verzweigung: BEQ, BNE – Unbedingter Sprung: J, JR, JAL Gleitkommarechnung – separate Gleitkommaeinheit – separater Registersatz RA - WS 2024/2025 Befehlssätze 109 RA - WS 2024/2025 Befehlssätze 110 RISC-V Hardware /64-bit Speicher - Instruktionsspeicher - Datenspeicher RA - WS 2024/2025 Befehlssätze 9 Programm-Zähler Program Counter (PC): Aktuelle Position im Programm - Jede Instruktion wird mit 4 Byte abgespeichert - Nächste Instruktion: PC add (ALUop) BEQ -> sub § Registerbefehle: funct7 und funct3 – add, – sub Vgl. HP “Opcode Map” – and – or RA - WS 2024/2025 Datenpfad und Steuerwerk 67  M U Add X 4 PC Shift_left(1) Add PCSrc Control ALUOp 5 ALU Control Instr[31:25|14:12] Read Read Address register 1 Read ALU Operation 5 4 Instruction data 1 Read register 2 Zero Instruction 5 Read memory M Result Write data 2 U ALU register 3 X Write MemRead MemWrite Imm. Gen. data Registers ALUSrc RegWrite Address Read Write data data M Data memory U X 0 M Konvention U MemtoReg für MUX: 1 X RA - WS 2024/2025 Datenpfad und Steuerwerk 68 ALU Steuersignale s0 s1 s2 s 3 Operation 0 0 0 0 AND 0 0 0 1 OR 0 0 1 0 add 0 1 1 0 sub RA - WS 2024/2025 Datenpfad und Steuerwerk 69 ALU Steuertabelle Opcode ALUOp Befehl Operation c 0c 1c 2c 2 LD 00 load add 0010 SD 00 store add 0010 BEQ 01 branch sub 0110 Register 10 add add 0010 Register 10 sub sub 0110 Register 10 and and 0000 Register 10 or or 0001 RA - WS 2024/2025 Datenpfad und Steuerwerk 70 Berechnung aus ALUOp, Funct7 und Funct3 RA - WS 2024/2025 Datenpfad und Steuerwerk 71 Steuerung des Prozessors § Alle Steuersignale eingezeichnet? RA - WS 2024/2025 Datenpfad und Steuerwerk 72  M U Add X 4 PC & Shift_left(1) Add Control ALUOp Branch 5 ALU Control Instr[31:25|14:12] Read Read Address register 1 Read ALU Operation 5 4 Instruction data 1 Read register 2 Zero Instruction 5 Read memory M Result Write data 2 U ALU register 3 X Write MemRead MemWrite Imm. Gen. data Registers ALUSrc RegWrite Address Read Write data data M Data memory U X 0 M Konvention U MemtoReg für MUX: 1 X RA - WS 2024/2025 Datenpfad und Steuerwerk 73 Steuertabelle Befehl ALUSrc Memto Reg Mem Mem Branch ALUOp1 ALUOp0 Reg Write Read Write Register 0 0 1 0 0 0 1 0 LD 1 1 1 1 0 0 0 0 SD 1 x 0 0 1 0 0 0 BEQ 0 x 0 0 0 1 0 1 RA - WS 2024/2025 Datenpfad und Steuerwerk 74 Steuertabelle Opcode ALUSrc Memto Reg Mem Mem Branch ALUOp1 ALUOp0 Op6…Op0 Reg Write Read Write 0110011 0 0 1 0 0 0 1 0 0000011 1 1 1 1 0 0 0 0 0100011 1 x 0 0 1 0 0 0 1100011 0 x 0 0 0 1 0 1 RA - WS 2024/2025 Datenpfad und Steuerwerk 75 Vergleich mit MIPS Datenpfad Load/Store Befehle, Verzweigungen 6 5 5 16 Gleiches Format opcode rs rt address für Load, Store und BEQ 31-26 25-21 20-16 15-0 Registerbefehle 6 5 5 5 5 6 opcode rs rt rd shamt func 31-26 25-21 20-16 15-11 10-6 5-0 Sprungbefehle 6 26 opcode address Fehlt bei RISC-V 31-26 25-0 RA - WS 2024/2025 Datenpfad und Steuerwerk 76  Datenpfad für Load, Store, BEQ und Registerbefehle