Computer-Architektur/Rechner- · PDF fileTh. Risse, HSB: RST { SS15 4 0.1 zugrunde liegende Literatur John L. Hennessy, David A. Patterson: Rechnerarchitektur { Analyse, Ent-wurf,

Computer-Architektur/Rechner-Strukturen

Prof. Dr. Thomas Risse

www.weblearn.hs-bremen.de/risse/RST

Fakultat Elektrotechnik & InformatikHochschule Bremen

SS 2015

Inhaltsverzeichnis

Inhaltsverzeichnis 1

0.1 zugrunde liegende Literatur . . . . . . . . . . . . . . . . . . . . . . . . . 4

0.2 links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

0.3 weiterfuhrende Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1 Einfuhrung 10

1.1 Geschichte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2 Kosten zu Nutzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 Entwicklungsziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.4 Taxonomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.5 Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2 Compiler 19

2.1 Daten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2 Anweisungen und ihre Ausfuhrung . . . . . . . . . . . . . . . . . . . . . 27

3 Befehlssatze 30

3.1 Klassifikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2 Register-Architekturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.3 Adressierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1

http://www.weblearn.hs-bremen.de/risse/RST

Th. Risse, HSB: RST – SS15 2

3.4 Operationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.5 Anforderungen an Befehlssatze . . . . . . . . . . . . . . . . . . . . . . . 34

4 Prozessor-Architekturen 42

4.1 Prozessor-Datenpfad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2 Prozessor-Steuerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.3 single-cycle- vs multi-cycle-Implementierung . . . . . . . . . . . . . . . . 50

4.4 Realisieren der Steuerung . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.4.1 festverdrahtete Steuerung . . . . . . . . . . . . . . . . . . . . . . 62

4.4.2 Steuerung per sequencer . . . . . . . . . . . . . . . . . . . . . . . 63

4.4.3 Mikro-programmierte Steuerung . . . . . . . . . . . . . . . . . . 64

5 pipelining 66

5.1 Daten-Pfad einer pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.2 Steuerung einer pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.3 Daten-Hazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.4 Steuer-Hazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.5 arithmetische pipelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

5.6 Superskalares Pipelining . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.7 scheduling funktionaler Einheiten . . . . . . . . . . . . . . . . . . . . . . 86

5.8 pipeline-Vektor-Prozessoren . . . . . . . . . . . . . . . . . . . . . . . . . 87

5.9 RISC vs CISC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6 Speicher-Hierarchie 92

6.1 cache-Speicher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6.1.1 cache-Leistung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.1.2 caching und schreibende Speicher-Zugriffe . . . . . . . . . . . . . 101

6.1.3 logischer oder physikalischer cache . . . . . . . . . . . . . . . . . 102

6.2 Haupt-Speicher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

6.2.1 Speicher-Organisation . . . . . . . . . . . . . . . . . . . . . . . . 103

6.2.2 Virtueller Speicher . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.2.3 Schutzvorkehrungen . . . . . . . . . . . . . . . . . . . . . . . . . 110

6.2.4 Direct Memory Access (DMA) . . . . . . . . . . . . . . . . . . . 111

7 Parallelisierung des Gauß’schen Algorithmus 115

7.1 parallele Berechnung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115


7.1.1 Eliminieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

7.1.2 Auflosen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

7.2 Kommunikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

7.3 Parallelisierung des Gauß’schen Algorithmus durch den Compiler . . . . 119

8 Parallele Rechnerstrukturen 120

8.1 Verbindungsstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

8.2 SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

8.3 MIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

8.3.1 MIMD-Maschinen mit Bus . . . . . . . . . . . . . . . . . . . . . 133

8.3.2 MIMD-Maschinen mit Verbindungsnetzwerk . . . . . . . . . . . . 134

8.3.3 Entwicklungstrends bei Multi-Prozessor-Systemen . . . . . . . . 135

Index 137


0.1 zugrunde liegende Literatur

• John L. Hennessy, David A. Patterson: Rechnerarchitektur – Analyse, Ent-wurf, Implementierung, Bewertung; Vieweg 1994 vergriffen! n462/17

• John L. Hennessy, David A. Patterson: Computer Architecture – a Quanti-tative Approach; Morgan Kaufmann Publishers, San Mateo 2002, 3rd editi-on! ISBN: 1-55860-596-7 bzw. ISBN: 1-55860-724-2 (international studentedition) s. www.mkp.com n462/9004

• David A. Patterson, John L. Hennessy: Computer Organizaton and De-sign – The Hardware/Software Interface; Morgan Kaufmann Publishers,San Mateo 2004 3nd edition! ISBN 1-55860-604-1 bzw. ISBN 1-55860-491-X(international student edition) s. www.mkp.com n466/10

• David A. Patterson, John L. Hennessy: Rechnerorganisaton und -entwurf –Die Hardware/Software Schnittstelle; Elsevier, 3. Aufl. 2005 n466/???

weiterfuhrend

• Michel Dubois, Murali Annavaram, Per Stenstrom: Parallel Computer Or-ganization and Design; Cambridge University Press 2012

0.2 links

Das wichtigste Literatur-link ist www.mkp.com/cod2e.htm.Zum Verhaltnis der beiden der Veranstaltung zugrunde liegenden Werke, kurzCOD und CA, siehe www.mkp.com/books catalog/cod2/hpcomp.htm

Wer nicht selbst suchen will, findet weitere links veroffentlicht, z.B. c’t oder aufder RST-page www.weblearn.hs-bremen.de/risse/RST.

0.3 weiterfuhrende Literatur

A. Aho, R. Sethi, J. Ullman: Compiler – Principles, Techniques, and Tools; Addison-Wesley, Reading MA, 1985, Drachenbuch n425/195

Heidi Anlauff, Axel Bottcher, Martin Ruckert: Das MMIX-Buch – ein praxisnaherZugang zur Informatik; Springer, 2002 n440/521

Helmut Bahring: Mikrorechner-Systeme – Mikroprozessoren, Speicher, Peripherie;Springer, 1994 n462/5005

R. J. Baron, L. Higbie: Computer Architecture; Addison Wesley 1992 SBU London

M. Ben-Ari: Grundlagen der Parallel-Programmierung; Hanser Verlag, Munchen 1985n440/771

http://www.mkp.com

http://www.mkp.com

http://www.mkp.com/cod2e.htm

http://www.mkp.com/books_catalog/cod2/hpcomp.htm

http://www.weblearn.hs-bremen.de/risse/RST


Jayaram Bhasker: A VHDL Primer; Prentice Hall 1991

Arndt Bode (Hrsg): RISC Architekturen; BI 1990 RISC vs CISC, Compiler, z.B.Am29000, IBM RISC Power, INMOS, HP PA, Motorola 88000, SUN SPARC,MIPS R3000, Intel 80960, i860 und vielen Literatur-Hinweisen h8/82

Arndt Bode, W. Handler: Rechnerarchitektur - Band I und Band II; Springer, 1980und 1983

Rudiger Brause: Neuronale Netze; Teubner, Stuttgart, 1991 n478/47

Ulrich Bruning: Architecture of High-Performance Processors; Habilitationsschrift TUBerlin, 1993 Empfehlung Giloi

Nicholas P. Carter: Computer Architektur; mitp-Verlag, 2003, n462/230

Ben Catanzaro: Multiprocessor System Architectures – A Technical Survey of Mul-tiprocessor/Multithreaded Systems using SPARC, Multilevel Buis Architecturesand Solaris (SunOS); Sun Microsystems, Inc. 1994

Wolfgang Coy: Aufbau und Arbeitsweise von Rechenanlagen; Vieweg, 1992 incl. BS

David E. Culler, Jaswinder Pal Singh: Parallel Computer Architecture – A Hardwa-re/Software Approach; Morgan Kaufmann, 1999 n466/435

Hans Gunter Dahn: Iris INDIGO, der RISC PC der 90er Jahre; Addison Wesley, 1992

Michel Dubois, Murali Annavaram, Per Stenstrom: Parallel Computer Organizationand Design; Cambridge University Press 2012

Heinz Ebert: Transputer & OCCAM – Das Handbuch fur Systementwickler; Heise,1993 n462/719

Hermann Eichele: Multiprozessorsysteme; Teubner, Stuttgart, 1990 Cache, Bus, z.B.MULTIBUS, 680XX, Transputer, incl. BS n462/46

Werner Erhard: Rechnerarchitektur: Einfuhrung und Grundlagen; Teubner, Stuttgart,1990 formale Entwurfsmethoden, Petri-Netze, VHDL, CSP, optische Konzeptevergriffen! n462/13

Werner Erhard: Parallelrechnerstrukturen; Teubner, Stuttgart, 1990 pipeline, Feld-rechner, Bus, Netz, Algorithmen

Werner Erhard, Dietmar Fey: Parallele digitale optische Rechnereinheiten; Teubner,Stuttgart, 1994 systolische arrays, Feldrechner

W. Everling: Rechnerorganisation; BI, 1990 Boole’sche Algebra, Gatter, Rechensyste-me und Realisierung

James E. Feldman, Charles T. Retter: Computer Architecture – A Designers TextBased on a Generic RISC; McGraw Hill, 1994

Thomas Flik, Hans Liebig: Mikroprozessortechnik: CISC, RISC, Systemaufbau, As-sembler und C; Springer, 1998 Klassik, z.B., Bus, Cache, I/O n462


Uwe Gerlach: Das Transputer-Buch – Platine, Entwicklungssoftware, Programmie-rung; Markt & Technik, 1991 n462/74

Wolfgang K. Giloi: Rechnerarchitektur; Springer, 1993 RISC, CISC, Mem, Parallel,Skalar, SIMD, Datenfluß, MIMD

Thorsten Grotker, Stan Liao, Grant Martin, Stuart Swan: System Design with Sys-temC; Kluwer, 2002

Gerd Haeussler, Peter Guthseel: Transputer – Systemarchitektur und Maschinenspra-che; Franzis, 1990 n462/774

Patrick Hamilton: Kunstliche neuronale Netze – Grundprinzipien, Hintergrunde, An-wendungen; vde-Verlag, 1993 n478/22

Wolfgang A. Halang, Bernd J. Kramer, Jurgen Schormann: Grundlagen der Informa-tionstechnik; Fachbuchverlag Leipzig, 1998 Emulator ECO auf CD-ROM

V. C. Hamacher, Z. G. Vranesic, S. G. Zaky: Computer Organisation; McGraw Hill,1996 (4th ed.)

John P. Hayes: Computer Architecture and Organization; McGraw-Hill, 1998 (3rd ed.)Evolution, Design (CPU, mem, Sys), Parallel

John L. Hennessy, David A. Patterson: Rechnerarchitektur – Analyse, Entwurf, Im-plementierung, Bewertung; Vieweg, 1994 vergriffenn462/17

John L. Hennessy, David A. Patterson: Computer Architecture – a Quantitative Ap-proach; Morgan Kaufmann, San Mateo, 1995, 3nd edition n462/9004(2)

Paul Herrmann: Rechnerarchitektur – Aufbau, Organisation und Implementierung;Vieweg, 2002 Spruth: IBM, SSE2, IA-64, AMD-64, MIPS64, MIMD n462/411

Andre Hertwig, Rainer Bruck: Entwurf digitaler Systeme – Von den Grundlagen zumProzessorentwurf mit FPGAs; Hanser, 2000 Spice, Verilog

Norbert Hoffmann: Simulation Neuronaler Netze – Grundlagen, Modelle, Pascal-Pro-gramme; Vieweg, 1991 n478/59

Norbert Hoffmann: Kleines Handbuch Neuronaler Netze – AnwendungsorientiertesWissen; Vieweg, 1993 n478/6

Christian Horn, Immo O. Kerner: Lehr- und Ubungsbuch Informatik – Band IV:Technische Informatik und Systemgestaltung; Fachbuchverlag Leipzig, 1998 u.a.Hardwaregrundlagen, Rechnerarchitekur

Walter Huber: Paralleles Rechnen; Oldenbourg, Munchen, 1997 n477/41

Kai Hwang: Advanced Computer Architecture – Parallelism, Scalability, Programma-bility; McGraw-Hill, 1993

Kai Hwang, Fay A. Briggs: Computer Architecture and Parallel Processing; McGraw-Hill, 1984


INMOS: Transputer Development System (TDS); INMOS 1990 n462/24

Eike Jessen: Architektur digitaler Rechenanlagen; Springer, 1975 Empfehlung Giloi

Eike Jessen, Rudiger Valk: Rechensysteme – Grundlagen der Modellbildung; Springer,1987 Nebenlaufigkeit, Statistik, Speicherverwaltung n438/816

Horst Kastner: Architektur und Organisation digitaler Rechenanlagen; Teubner Ver-lag, Stuttgart, 1978 Maschinen-Sprache, Mikroprogrammierung n460/705

F. J. Kauffels: Rechnernetzwerksystemarchitekturen und Datenkommunikation; BI,1991 Netze, Verteilung, z.B. SNA, OSI, MAP ... UNIX, OS/2

Rainer Kelch: Rechnergrundlagen – vom Rechenwerk zum Universalrechner; Fach-buchverlag Leipzig, 2003

Jorg Keller, Wolfgang Paul: Hardware Design – Formaler Entwurf digitaler Schaltun-gen; Teubner, Stuttgart, 1997 n462/94

Rainer Klar et al.: Messung und Modellierung paralleler und verteilter Rechensysteme;Teubner, Stuttgart, 1995 n438/49

David J. Kuck: The Structure of Computers and Computations Vol.I; John Wiley &Sons, 1978 capacity, memory hierarchies, networks

H. Langendorfer, Bettina Schnor: Verteilte Systeme; Hanser, 1994 Kommunikation,Synchronisation, Prozesse, verteilte Verarbeitung, verteilte BS, z.B.

Christian Martin: Rechnerarchitektur – Struktur, Organisation, Implementierungs-technik; Hanser, 1994

Christian Martin: Rechnerarchitekturen – CPUs, Systeme, Software-Schnittstellen;Fachbuchverlag Leipzig, 2001

Christian Martin: Einfuhrung in die Rechnerarchitektur – Prozessoren und Systeme;Hanser, 2003

Helmut Malz: Rechnerarchitektur – Eine Einfuhrung fur Ingenieure und Informatiker;Vieweg 2004

Dietmar Moller: Rechnerstrukturen – Grundlagen der Technischen Informatik; Sprin-ger, 2003 500/517a

Miles J. Murdocca and Vincent P. Heuring: Computer Architecture and Organization– An Integrated Approach; John Wiley & Sons, 2006

D. Nauck, F. Klawonn, R. Kruse: Neuronale Netze und Fuzzy-Systeme; Vieweg, 1996n478/779

W. Oberschelp, G. Vossen: Rechneraufbau und Rechnerstrukturen; Oldenbourg, 1998Schaltungstechnik, RISC/CISC, Parallelverarbeitung n462/294

David A. Patterson, John L. Hennessy: Computer Organizaton and Design – TheHardware/Software Interface; Morgan Kaufmann, San Mateo, 1998 2nd edition!n466/10(2)


David A. Patterson, John L. Hennessy: Rechnerorganizaton und -entwurf – Die Hard-ware/Software Schnittstelle; Elsevier, 3. Aufl. 2005 n466/???

Thomas Rauber, Gudula Ruenger: Parallele und verteilte Programmierung; Springer,2000 n440/510

Heinrich Reineke, Joseph Schreiner: Transputer-Leitfaden; Hanser, 1991 n462/5265

Gerd Regenspurg: Hochleistungsrechner-Architekturprinzipien; McGraw-Hill, 1987 pi-pelining, RISC, Gallium Arsenid, Opto, z.B. Cray, GF11, CM, SUPRENUM,SIMPSON

Raul Rojas: Theorie der Neuronalen Netze; Springer, 1993 n478/38

Roland Rossler, Dietmar Dietrich, Karl-Friedrich Penning: Transputer – Grundlagen,Programmierung und Anwendung; Huthig, 1992 OCCAM n462/36

Philip M. Sailer, David R. Kaeli: The DLX Instruction Set Architecture Handbook;Morgan Kaufmann, 1996 n500/17

Udo Schendel: Einfuhrung in die parallele Numerik; Oldenbourg Verlag, Munchen,1981 b39/835

Klaus Schmidt: Programmierung von Vektorrechnern und Parallelrechnern; HarriDeutsch, Frankfurt a.M., 1994 n440/800

Eberhard Schoneburg (Hrsg.): Industrielle Anwendungen neuronaler Netze; Addison-Wesley, 1993 Diagnose, OCR, Bildverarbeitung, Neuronale Netze und Parallel-rechner (Transputer), Simulation, Demo n478/802

Christian Siemers: Prozessorbau – Eine konstruktive Einfuhrung in das Hardware/-Software-Interface; Hanser, 1999 n 462/41

Christian Siemers: Hardware-Modellierung – Einfuhrung in die Simulation und Syn-these von Hardware; Hanser, 2001 VHDL, ABEL

D. Sima, L. Polacsek, V. Koschek: Computer Architectures; Institute of Informatics,Kand Poytechnic of Technology, Budapest, 1992

Axel Sikora, Rolf Drechsler: Software-Engineering und Hardware-Design – eine syste-matische Einfuhrung; Hanser, 2002

William Stallings: Computer, Organization and Architecture: Designing for Perfor-mance; Prentice Hall, 1996 SBU London n466/926(4)

H. S. Stone: High Performance Computer Architecture; Addison Wesley, 1993 SBULondon

Andrew S. Tanenbaum: Computer-Netzwerke; Prentice Hall, 1998 n 478/27(3)d

Andrew S. Tanenbaum: Structured Computer Organization; Prentice-Hall, EnglewoodCliffs, 1990 n90/510(3)

Andrew S. Tanenbaum, James Goodman: Computer-Architektur – Strukturen, Kon-zepte, Grundlagen; Prentice Hall, 1999


Theo Ungerer: Datenflußrechner; Teubner, Stuttgart, 1993 Parallel, Statische vs Dy-namische Datenflußrechner, Hybride, z.B. n462/78

Kevin R. Wadleigh, Isom L. Crawford: High Performance Computing; Prentice HallPTR, 2000 Software Optimization

Klaus Waldschmidt (Hrsg.): Parallelrechner – Architekturen, Systeme, Werkzeuge;Teubner, Stuttgart, 1995 n462/334

Hartmut Wedekind (Hrsg.): Verteilte Systeme; BI, 1994 Architekturen, Objektorien-tierung, Anwendungen, Echtzeit

Niklaus Wirth: Compilerbau – eine Einfuhrung; Teubner, 1986

Niklaus Wirth: Logic Design for Computer Science Students; Springer, 1995 n500/362

Mehdi R. Zargham: Computer Architecture – Single and Parallel Systems; PrenticeHall, 1996

Andreas Zell: Simulation neuronaler Netze; Addison-Wesley, 1994 n478/24


1 Einfuhrung

Die Geschichte der Computer-Entwicklung ist die Geschichte der Leistungsstei-gerung (s. Vergleich mit Automobil).

1.1 Geschichte

1642 B. Pascal1: Addition und Subtraktion,

1666 S. Morland2, 1671 G. Leibniz3 Addition und Multiplikation

1812 Charles Babbage4: Difference Engine (Polynom-Auswertung), Analytical Engine(Lochkarten-Steuerung), Augusta Ada King, Countess of Lovelace5

1924 T.J. Watson:6 von NCR uber CTR zu IBM, Astronomical Computing Bureau,Hermann Hollerith:7 National Bureau of Census

1930 Howard H. Aiken,8 John Atanasoff,9 George Stibitz,10 Konrad Zuse:11 univer-selle, programmierbare, digitale (Relais-) Rechner

1939 Atanasoff: Rohren-Rechner (Lineare Gleichungssysteme)

1943 Mauchly12 und Eckert13: Electronic numerical Integrator and Calculator, ENIAC

1943 Max H. A. Newman14 und Alan M. Turing15: Colossus (Kryptographie), Enigma...

1945 John von Neuman16: Electronic Discrete Variable Automatic Computer, EDVAC,Magnetische Speicher, Atom-Bombe COD, pp315

s.a. timeline http://expert.cc.purdue.edu/ mundy/timeline.html

1 Blaise Pascal (1623-1662)2 Samuel Morland (1625-1695)3 Gottfried Leibniz (1646-1716)4 Charles Babbage (1791-1871)5 Augusta Ada King, Countess of Lovelace (1815-1852)6 Thomas J. Watson (1874-1956)7 Hermann Hollerith (1860-1929)8 Howard H. Aiken (1900-1973)9 John V. Atanasoff (1903-1995)

10 George Stibitz (1904-1995)11 Konrad Zuse (1910-1995)12 John William Mauchly (1907-1980)13 John P. Eckert (1919-1995)14 Max H. A. Newman (1897-1984)15 Alan M. Turing (1912-1954)16 John von Neuman (1903-1957)

http://www.wired.com/news/technology/0%2c1282%2c39198%2c00.html

http://www.math.arizona.edu/~dsl/enigma.htm

http://www.maxmon.com/1946ad.htm

http://expert.cc.purdue.edu/~mundy/timeline.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Pascal.html

http://es.rice.edu/ES/humsoc/Galileo/Catalog/Files/morland.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Leibniz.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Babbage.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Lovelace.html

http://www.watson.ibm.com/t_j_watson_history.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Hollerith.html

http://cc.kzoo.edu/~k98hj01/aiken.html

http://archive.comlab.ox.ac.uk/museums/computing/atanasoff.html

http://www.invent.org/book/book-text/100.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Zuse.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Mauchly.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Eckert_John.html

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Newman.html

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Turing.html

http://ei.cs.vt.edu/~history/VonNeumann.html


Zeit Technologie/Architektur SW/Anwendungen Systeme

1945-54Rohren, Relais, CPU mit PC undAccu, Festpunkt-Arithmetik

Assembler, singleuser, no linkage

ENIAC, PrincetonIAS, IBM 701

1955-64

diskrete Transistoren, Kern-Spei-cher, Gleitpunkt-Arithmetik,I/O-processors, multiplexedmemory access

HLL, compiler, li-braries, batch pro-cessing

IBM 7090, CDC1604, UnivacLARC

1965-74SSI/MSI-ICs, Mikroprogram-mierung, pipelining, cache,µ-processors

multiprogram-ming, time sha-ring, OS, multiuser

IBM 360/370,CDC 6600, TI-ASC, PDP-8

1975-90

LSI/VLSI-ICs, Halbleiter-Spei-cher, RISC vs17 CISC, multi pro-cessors, vector supercomputers,multicomputers

multiprocessor OS;languages, compi-lers etc. for parallelprocessing

Apple, PC,VAX 9000, CrayX-MP, IBM 3090

1991-ULSI/VHSI-ICs, high densitypackaging, scalable architectures

MPP, grandchallenges, hetero-geneous processing

Fujitsu VPP500,Cray MPP, CM-5,Intel Paragon

Hwang p5

s.a. auch Computer Museen im Internet, etwa http://ei.cs.vt.edu/ history/,http://archive.comlab.ox.ac.uk/other/museums/computing.html,http://www.museums.reading.ac.uk/vmoc/, http://www.weller.to/,http://www.computerhistory.org/, http://www.mos.org/tcm/tcm.html

1.2 Kosten zu Nutzen

Der Wettbewerb unter den Computer-Herstellern, Rechner-Systeme mit dem bes-ten Preis/Leistungsverhaltnis anzubieten, fuhrte in den letzten zehn Jahren zueiner jahrlichen Leistungsverdoppelung bei fallenden Preisen. Diese Leistungs-steigerung beruht auf Fortschritten der hardware-Technologie (etwa Schaltkreis-Integration), der software-Technologie (etwa optimierende Compiler) und derRechner-Architektur (pipelining, caching, RISC, Multi-Prozessor-Systeme).

Def. Rechner-Architektur18 ist die Organisation von Rechen-Systemen, die dasPreis/Leistungsverhaltnis fur bestimmte Einsatzbereiche und bei gegebener hard-ware- und software-Technologie optimiert.

Verschiedene Einsatzbereiche stellen verschiedene Anforderungen:

• an Große also Leistungsklasse, z.B. PC, workstation, Minicomputer, mainframeoder Supercomputer,

• an Rechner-Typ, z.B. Universal-Rechner, Prozess-Rechner, Rechner fur Wissen-schaft, Wirtschaft oder Verwaltung,

1710% der 200 Instruktionen einer IBM /360 reprasentieren mehr als 90% aller ausgefuhrtenInstruktionen.

18Amdahl, Blaauw, Brooks – Entwickler der IBM /360 – definierten 1964: Computer-Architektur ist die Struktur eines Computers, die ein Maschinen-Sprachen-Programmierer ver-stehen muß, um korrekte Programme fur eine Maschine schreiben zu konnen.

http://expert.cc.purdue.edu/~mundy/eniac.html

http://ei.cs.vt.edu/~history/

http://archive.comlab.ox.ac.uk/other/museums/computing.html

http://www.museums.reading.ac.uk/vmoc/

http://www.weller.to/

http://www.computerhistory.org/

http://www.mos.org/tcm/tcm.html


• durch vorhandene software, z.B. Programmiersprache oder Programm-Objektean den Befehlssatz

• durch Betriebssysteme an z.B. Große des Adressraumes, Art der Speicherverwal-tung, Kontext-Umschaltung bei interrupts und traps,

• und durch Standards an z.B. (Gleitkomma-) Zahldarstellung, Bus-Systeme, Be-triebssysteme, Netze, Programmiersprachen, Graphik usw.

Allerdings ist die Leistung eines Rechen-Systemes schwierig zu messen (vgl. Ant-wortszeit fur den Benutzer vs. Durchsatz fur den Betreiber).

Z.B. Was messen MIPS, MOPS, MFLOPS, CPI, Bus-Bandbreite, EA-Bandbrei-te, memory cycles, wait states, TPS, FPS, KLIPS? c CA, S.32ff

Z.B. Gibson Befehls-Mix, mittlere Befehlsausfuhrungszeit (gewichtete SummeCA, p56≈ CPI), 1970 etwa fur IBM 7090 c

Z.B. Whetstone, synthetischer benchmark mit genau 1 mio synthetischer Whet- Martin, S.52stone-Instruktionen, Ergebnis in MWIPS, 1976 in ALGOL60, spater in FORT-RAN, wissenschaftlich und engineering, zur Halfte in Laufzeit-Bibliotheken, daherzur Halfte Compiler-unabhangig, kleine Module, die ganz in caches passen... c

Z.B. Linpack (Dongarra), LGS A~x = ~b mit 100 Gleichungen in 100 Unbekannten Martin,S.54/55per verkettetem Gauß A = LU , 1976 in FORTRAN, spater auf n × n-Matrizen

skaliert (Vektor-Rechner), Ergebnis in MFLOPS/GFLOPS cZ.B. Dhrystones, synthetischer benchmark, 1984 in ADA, spater Pascal und C, Martin, S.53

nur 100 Instruktionen, modelliert Instruktionshaufigkeit und Lokalitat von Va-riablen, 50% Zuweisungen und Ausdrucke (no floats), 33% branch, 17% functioncalls, die insgesamt 1000 bytes passen ganz in caches . . . cZ.B. Livermore loops (21 small kernels), synthetische benchmarks, 1986 inFORTRAN, Ergebnis in MFLOPS, fur die damaligen Supercomputer, Datensatzemit max. 1K Elementen c B&H, p27

Z.B. SPECmarks (system performance evaluation cooperative19) von DEC, HP,MIPS, SUN etc., realistische benchmarks aus Physik, Chemie, Astronomie, Bio- Martin, S.55

logie sowie z.B. Go, gcc, compress, jpeg in C und Quanten- und Astro-Physik,FEM in FORTRAN, 1988 10 Programme in FORTRAN und C, 1992 korrigiertund um SPECint, SPECfp und SPEChpc erweitert, Ergebnis in SPECmark, i.e.geometrisches Mittel der VAX11/780-Vielfachen, Nachbesserungen in SPEC95wie etwa SDM (System Development, Multitasking mit edit, compile, execute,debug), SFS (System-level File Server) oder Web-Server-benchmark c COD, pp71

Z.B. Perfect Club (PERFormance Evaluation for Cost-effective Transforma-tions), 13 realistische kernels extrahiert aus Luft-Verschmutzung, Uberschall- B&H, pp27

Flug, fluid dynamics, Seismik, Schaltkreis-Simulation etc., besonders fur Vektor-Rechner! c

19 SPECulating about performance


Z.B. WinStone benchmark u.a. mit kernels bestehend aus klassischen Office-Anwendungen und daher mit Modellierung der Benutzung, aber auch CAD, PV-wave etc., s.a. http://www.ziffdavis.com cZ.B. SYSMark 2000 von Business Application Performance Corporation, BAP- c’t 16/2000,

S.124-139Co 2000, s. http://www.bapco.com3DMark 2000, demo download s. www.madonion.com, CPU2000 aus SPECrate c’t 16/2000,

S.140-142Transaction Processing Performance Council, TPC, www.tpc.org/, a non-profitcorporation founded to define transaction processing and database benchmarksand to disseminate objective, verifiable TPC performance data to the industrySAP Standard Application Benchmarks, www.sap.com/benchmark, bestehend u.a. c’t ???

aus Sales and Distribution, SD, Assemble To Order, ATO und Business Infor-mation Warehouse, BW. cz.H. Vergleiche Programm-Ausfuhrungszeiten und Ergebnisse geeigneter Bench-marks. Untersuche den Einfluß optimierender Compiler auf die Laufzeit eigenerBenchmark-Programme. oEinzig die Ausfuhrungszeit fur ein Programm mißt die Leistung zuverlassig.

SekundenProgramm = Instruktionen

Programm × Clock ZyklenInstruktion

× SekundenClock Zyklus

Durch Ubergang zu geeigneten Mittelwerten ergibt sich

SekundenProgramm = Instruktionen

Programm × CPI× 1

Taktrate

z.H. Welche Randbedingungen beeinflussen welche Parameter? o

Def. Leistung ist Arbeit pro Zeit, also Leistung = 1

Ausfuhrungszeit.

Der Beschleunigungsfaktor β durch eine Modifikation ergibt sich aus

β =Leistungmit ModifikationLeistungohne Modifikation

=AusfuhrungszeitohneAusfuhrungszeitmit

Der Leistungsgewinn γ durch eine Modifikation ergibt sich aus

1 + γ =Leistungmit ModifikationLeistungohne Modifikation

=AusfuhrungszeitohneAusfuhrungszeitmit

oder aufgelost

γ =Leistungmit−Leistungohne

Leistungohne=

Ausfuhrungszeitohne−AusfuhrungszeitmitAusfuhrungszeitmit

Prozentuale Leistungsgewinne ergeben sich durch Multiplikation mit 100.

Z.B. Ein Reduktion der Ausfuhrungszeit von 15s auf 10s entspricht einem pro-zentualen Leistungsgewinn von γ = 100 15−10

10also einer Leistungssteigerung um

50%. c

http://www.ziffdavis.com

http://www.bapco.com

http://www.madonion.com

http://www.tpc.org/

http://www.sap.com/benchmark/


Bem. Offensichtlich steht kein Programm (mit seiner Ausfuhrungszeit) fur alleanderen Programme, auch nicht das arithmetische Mittel AZ = 1

n

∑ni=1AZi der

Ausfuhrungszeiten AZi bzw. das harmonische Mittel 1AZ

= n∑ni=1

11/AZi

der Raten

1AZi

ausgewahlter Programme Pi.

Jedes Programm wird durch unterschiedliche Compiler in verschiedene Program-me in der Maschinen-Sprache der Ziel-Architektur ubersetzt. Spitzenleistungenentsprechen nicht Durchschnittsleistungen. Bei multi user systemen kann ein Pro-gramm unter ganz verschiedenen Lastbedingungen abgearbeitet werden. ◦Zur Berechnung der durchschnittlichen Rate r der Raten ri ist das harmonischeMittel r = n∑n

i=11ri

zu verwenden.

Z.B. Ein Zug brauche fur die ersten 100km Strecke 1h und fur die zweiten100km Strecke 2h. Die Durchschnittsgeschwindigkeit 200km/3h=200

3km/h berech-

net sich als harmonisches Mittel der Geschwindigkeiten 100km/h und 50km/hzu 2

1100

+ 150

= 21

100+ 2

100

= 2003

km/h. c

Z.B. Ein Rechner leiste in zwei Betriebszustanden zu gleichen Teilen entweder10 MFLOPS oder 30 MFLOPS. Die durchschnittliche Rate ergibt sich als har-monisches Mittel zu 2

1/10+1/30= 2

4/30= 1

230 = 15 MFLOPS.

Das arithmetische Mittel der Ausfuhrungszeiten fur float Operationen in den bei-den Zustanden 1

2( 1

10 M + 1

30 M) = 1

15 M s liefert gleichermaßen die durchschnitt-

liche Rate von 15 MFLOPS. cFur Gewichte wi mit 0 ≤ wi ≤ 1 und

∑ni=1wi = 1 berechnet sich das arithmeti-

sches Mittel der mit wi gewichteten Ausfuhrungszeiten AZi zu∑n

i=1 wiAZi unddas harmonisches Mittel der mit wi gewichteten Raten ri zu 1∑n

i=1wiri

.

Zum Mitteln normierter Ausfuhrungszeiten Ti/Si (bzgl. einer ’Standard’-Maschi- COD,pp80-82ne) ist das geometrische Mittel T/S =

√∏i Ti/Si zu verwenden.

I.a.R. werden nur Teile eines Rechen-Systemes schrittweise verbessert:

Bem. Beliebige Beschleunigungen sind nicht erzielbar, wenn man nur einenAnteil beschleunigt/beschleunigen kann: 100s Programm = 80s Arithmetik +20s Rest. Funffache Beschleunigung nur durch Beschleunigung β der Arithmetik20 = 100/5 = 80/β + 20, also 0 = 80/β ist unmoglich. ◦Satz (Amdahl’sches Gesetz ) Mit α = Anteilverandert und dem Beschleunigungs-faktor βverandert fur den durch die Veranderung betroffenen Anteil gilt

Ausfuhrungszeitneu = (1− α)Ausfuhrungszeitalt + αAusfuhrungszeitalt

βverandert

Damit ergibt sich der Beschleunigungsfaktor βgesamt fur das gesamte System

βgesamt =AusfuhrungszeitaltAusfuhrungszeitneu

= 1(1−α)+ α

βverandert

•


Z.B. Lohnt sich eine Verfunffachung der CPU-Geschwindigkeit bei funffachenKosten, wenn die CPU nur zu 50% ausgelastet ist und wenn die CPU ein Dritteldes Rechner kostet? Die erzielbare Beschleunigung um den Faktor 1

0.5+ 0.55

= 53

beiKostenneu

Kostenalt= 1

35 + 2

31 = 7

3-fachen Kosten rechnet sich also nicht. c

Z.B. Angenommen, MMX-Befehle werden zehnmal so schnell ausgefuhrt wie dieentsprechenden konventionellen Befehle, und angenommen, MMX-Substitutionsei in 10% des Codes moglich. Dann ergibt sich eine Beschleunigung um denFaktor β = 1

0.9+0.1/10= 1

0.91≈ 1.1 beim Einsatz eines MMX-Prozessors. c

z.H. Bestimme den Beschleunigungsfaktor durch die 3Dnow!-Technologie desAMD K6. o

1.3 Entwicklungsziele

Ziele: Kostenminimierung bei Steigerung der Leistung, Brauchbarkeit, Zuverlas-sigkeit und Qualitat (z.B. Skalierbarkeit)

Methoden: Verbessern der Hardware-Technologie, Optimieren der (Standard-)Komponenten (pipelining, caching, scheduling, ...?), Prozessoren unterstutzenbestimmte Funktionen des Betriebssystems (BS), Prozessoren unterstutzen be-stimmte Konstrukte von high level languages (HHL), Optimieren durch Ubergangzu ganz anderen Rechner-Architekturen, zu anderen Verarbeitungsprinzipien undzu anderen Programmier-Sprachen

MSI, LSI, VLSI, ULSI bis zu heutigen knapp TeraFLOPS-Rechnern bei Taktratenin der Großenordnung von mehreren 100MHz bei fallenden Preisen!

Giloi:Hochste Rechenleistung durch Parallelarbeit statt durchhochstmogliche Arbeitsgeschwindigkeit!

Technologie

Technik Gatterlaufzeit Integrationsgrad Verlustleistung/GatterCMOS 200ps...1000ps 100K...2M 10pW...10WECL 150ps...500ps 10K...200K 1mW...10mWGaAs 50ps...200ps 10K...200K 1mW...10mW

Alle drei Jahre: Halbierung der Kanallange der Transistoren auf CMOS-Chips,Verdoppelung der Taktfrequenz, Vervierfachung der Transistordichte


HP 9000/750

SUN-4/ 260

MIPS M2000

MIPS M/120

IBM RS6000

100

200

300

400

500

600

700

800

900

1100

DEC Alpha 5/500

DEC Alpha 21264/600

DEC Alpha 5/300

DEC Alpha 4/266

DEC AXP/500IBM POWER 100

Year

Per

form

ance

0

1000

1200

19971996199519941993199219911990198919881987

F120.pdfCOD, p30

Jahrliche Verdoppelung der Prozessor-Leistung (MIPS oder FLOPS):

Leistung= 2Jahr−1984 (Joy’sches Gesetz)

Alle drei Jahre: Vervierfachung der Speicher-Chip-Kapazitaten.

1992

100,000

Kbi

t ca

paci

ty

10,000

1000

100

1019901988198619841982198019781976

Year of introduction

16M

4M

1M

256K

16K

64K

1994 1996

64M

F114.pdfCOD, p22

Leistungsspektrum einiger Mikro-Prozessoren in CMOS-Technologie Giloi,S.11/12

Prozessor MHz MIPS MFLOPS W Stand 1992Intel i860XP >50 > 50 > 50 6Motorola 88110 >50 >100 > 50 8 2 Integer Units

MIPS R4000 100 100 50 9DEC Alpha 200 400 200 30


Trotzdem gibt es kaum Gewahrleistungsarchitekturen (Zuverlassigkeit, Wartbar-keit, Ausfallsicherheit), z.B. Tandem NonStop.

Die von-Neumann-Architektur erscheint als Architektur des minimalen Hard-ware-Aufwandes nicht mehr adaquat:andere Kostenverteilungen (HW zu SW zu Personal bzw. CPU zu Mem zu Peri-pherie), andere Benutzungsprofile (batch zu dialog bzw. Text zu Graphik, ...?)Heute brauchen die eigentlich Datentransformierenden Operationen kaum mehrZeit als die organisatorischen Maßnahmen (Holen, Interpretieren, Index- undAdressen-Rechnung).

Abkehr von der von-Neumann-Architektur erlaubt Leistungssteigerung, Fehler-toleranz, usw.

Bei all dem ist die Ausgewogenheit der Maßnahmen zu beachten:Satz (Amdahl’sche Faustregel) Eine ausgewogene Maschine hat pro 1 MIPSzugleich 1 MByte Speicher sowie 1 Mbit/sec E/A-Durchsatz. •

1.4 Taxonomie

Flynnsche Klassifikation von Rechen-Systemen

Klasse StrukturSISD single instruction single data Sequentielle RechnerSIMD single instruction multiple data Vektor-RechnerMIMD multiple instruction multiple data Multiprozessor-Systeme

und detaillierterer Klassifikation

Rechnerarchitektur := Operationsprinzip + Hardware-Struktur + Benutzer-Schnitt-stelle

Operationsprinzip := Informationsstruktur + KontrollstrukturDas Operationsprinzip definiert funktionelles Verhalten.Operationsprinzipien sind das von-Neumann-Prinzip oder die Prinzipien der Pro-gramm- oder Daten-Parallelitat. Dabei ist das Prinzip der Programm-Parallelitatdie Parallelitat der Operationen, der Anweisungen, der Prozesse oder der Pro-gramme.Daten-Parallelitat ist dann gegeben, wenn die Daten-Strukturen selbst standar-disiert sind, also z.B. als Felder angeordnet sind.

Die Informationsstruktur ist bestimmt duch die Informationskomponenten, ihre Dar-stellung und ihre Operationen (ADT).z.B. selbstbeschreibende Informationseinheiten.

Die Kontrollstruktur ist bestimmt durch die Interpretation und Transformationen derInformationskomponenten.z.B. sequentiell, sequentiell


Hardware-Struktur := Hardware-Betriebsmittel + Kommunikationsstruktur

Die Kommunikationsstruktur ist bestimmt durch die Kommunikations- und Koope-rationsregeln.

Def. Prozessoren steuern den Programmablauf und fuhren Daten-Transforma-tionen autonom aus. Im Gegensatz dazu sind Rechen-Einheiten oder -Elemente(RE) von außen gesteuert und fuhren Daten-Transformationen unter externerKontrolle aus.

Man unterscheidet also

Einprozessor-Systeme (SISD) sind die klassischen Rechner, wie z.B. PC, Work-station, µ-Controller, DSP, usw.

Feldrechner sind arrays homogener, universeller Rechen-Einheiten,

pipeline-Rechner (SIMD) sind eindimensionale Anordnungen spezialisierter Re-cheneinheiten,

Systolische Arrays (SIMD) sind sozusagen mehrdimensionale Pipelines,

Multiprozessor-Systeme (MIMD) sind homogene oder heterogene Systeme meh-rerer Prozessoren. Wenn alle Prozessoren dieselbe Funktion im System ha-ben, nennt man es symmetrisch sonst asymmetrisch. Unterschieden werdenSpeicher-gekoppelte (shared memory) und Nachrichten-gekoppelte (distribu-ted memory) Multiprozessor-Systeme.

1.5 AnwendungenGiloiS.427-429Hwangpp118

Zu den sogenannten großen Herausforderungen (vgl. Forschungsforderprogrammgrand challenges der US-Regierung Anfang der 90er Jahre oder Entwicklungspro-gramm real world computing in Japan seit 1993) gehoren

• Klima-Modelle der Erde: Treibhaus-Effekt, Ozon-Loch, Meeresstromungen, Um-weltverschmutzung, Versteppung, Verkarstung usw.

• Simulation hydrodynamischer Vorgange mit Turbulenzen und Viskositat

• Genom-Analyse

• Modellierung der Supraleitfahigkeit

• Nachbilden menschlicher Informationsverarbeitung z.B. bei Muster- oder Sprach-Erkennung: Losung unvollstandig spezifizierter Probleme


2 Compiler

Def. Ein Compiler uberfuhrt ein Programm in Quellsprache, etwa in einerProblem-orientierten Programmiersprache, in ein aquivalentes Programm in einerZielsprache, etwa Maschinensprache. Die Ubersetzung kann in mehreren passeserfolgen und Programme in Zwischensprachen erzeugen.

Assembler

Assembly language program

Compiler

C program

Linker

Executable: Machine language program

Loader

Memory

Object: Machine language module Object: Library routine (machine language)

F321.pdfCOD, p156

Bem. Die Ubersetzung erfolgt in mehreren Phasen: die lexikalische Analy- Wilke inBodese (P-->PP) erkennt Symbole, entfernt Kommentare usw., die Syntax-Analy-

se uberfuhrt das syntaktisch korrekte Programm in einen (abstrakten) Baum(PP-->A), die semantische Analyse uberpruft die kontextsensitive Korrektheitund erzeugt den attribuierten (abstrakten) Baum (A-->AA), der gegebenenfallsnach Optimierung (AA-->modA) in eine Maschinen-orientierte, aber Maschinen-unabhangige Zwischensprache ubersetzt wird (modA-->PZ). Aus dem Programmin dieser Zwischensprache erzeugt der Code-Generator ein ablauffahiges Objekt-Programm in der Maschinen-Sprache (PZ-->MP), das gegebenenfalls nochmal op-timiert werden kann (MP-->optMP). ◦


?

?

?

?

?

?

?

�

�

�

�

�

�

�

?

6

Fehler-Datei

Quellprogramm P

lexikalische Analyse

Folge PP vonGrundsymbolen

syntaktische Analyse

abstrakter Baum A

semantische Analyse

attributierter ab-strakter Baum AA

Optimierung

modifizierter attri-butierter Baum modA

Ubersetzung

Programm PZ inZwischensprache Z

Code-Erzeugung

ObjektprogrammMP

Optimierung

ObjektprogrammoptMP

Umgebung( ”-variable)

?

�

?

�

?

�

�

�

-

-

-

�

6

Symbol-tabelle

Konstanten-tabelle

Optimierungs-tabelle

. . .

?Testhilfen-Tabelle

Es gibt viele Moglichkeiten zu optimieren: Kontext-unabhangige lokale Optimie-rung, Registerzuteilung, Variablen-Zuweisung, Parameter-Ubergabe, Eliminati-on von redundanten Sprungen, von redundanten Ausdrucken, von totem Codeund von gemeinsamen Teilausdrucken, Verbreitung von Kopien von Konstan-ten und Variablen (constant oder variable propagation), Berechnung konstanterAusdrucke zur Compile-Zeit (constant expression folding), Reduktion der Starke(langsame Operationen durch schnellere ersetzen) (strength reduction), Optimie-ren von Prozedur-Aufrufen und -Rucksprung, usw. usf.

Z.B. Die lexikalische Analyse uberfuhrt das statement U = 2 * r * PI; desQuell-Programmes in die Folge

(Bez,U) (Sym,=) (Ziffer,2) (Sym,*) (Bez,r) (Sym,*) (Bez,PI) (Sym,;)


Dabei werden Kommentare entfernt, die Symbol-Tabelle gefullt, etc. Die syntak-tische Analyse erzeugt aus dieser Folge einen abstrakten Baum,

assign

ID MULU

MUL ID PI

ID ID2 r

den die semantische Analyse mit Attributen versieht.

assign

ID MUL

(TYPE, real)

(SYMBOL,$U)

(TYPE,real)

MUL ID

(TYPE,int)

(SYMBOL, $PI)(TYPE,real)

ID ID(SYMBOL,$2)

(TYPE,int)

(SYMBOL,$r)

(TYPE,int)

Gegebenenfalls nach einer Optimierung wird dieser Baum in eine Maschinen-unabhangige Zwischensprache ubersetzt:

mul_int, $2, $r, $tempint

conv_ir, $tempint, $tempreal1

mul_real, $tempreal1, $PI, $tempreal2

assign, $tempreal2, $U

Aus diesem Zwischencode wird nun der Maschinen-Code der Ziel-Maschine er-zeugt, etwa

LOAD, R1, 2

MULINT, R1, mem[ADR[r]]

CONV_IR, R1

MULREAL, R1, mem[ADR[PI]]

STORE, R1, ADR[U]

und gegebenenfalls optimiert. cWenn typischerweise 90% der Laufzeit in 10% des Codes verbracht wird, ist essinnvoll, diese 10% des Codes zuerst zu optimieren: z.B. innere Schleifen.

Z.B. Verschiedene Optimierungen seien am Beispiel von Quicksort demonstriert.Fur das folgende C-Programmvoid quicksort(m,n) // sortiere Feld a


int m,n;

{

int i,j; int v,x;

if (n<=m) return;

// Anfang des zu optimierenden Teilsi=m-1; j=n; v=a[i]; // B1while (1)

{

do i++; while (a[i]<v); // B2do j--; while (a[j]>v); // B3if (i>=j) break; // B4x=a[i]; a[i]=a[j]; a[j]=x;// B5

}

x=a[i]; a[i]=a[n]; a[n]=x; // B6// Ende des zu optimierenden Teilsquicksort(m,j); quicksort(i+1,n);

}

sei zunachst die Aufteilung des Programms in Blocke dargestellt.


nicht optimierter codei:=m-1

j:=n

t1:=4*n

v:=a[t1]

Block B1(init)

?

i:=i+1

t2:=4*i

t3:=a[t2]

if t3<v goto B2

Block B2(1. do loop)

?

�

j:=j-1

t4:=4*j

t5:=a[t4]

if t5>v goto B3


?

�

if i>=j goto B6}

Block B4 (break while)

? ?

t11:=4*i

x:=a[t11]

t12:=4*i

t13:=4*n

t14:=a[t13]

a[t12]:=t14

t15:=4*n

a[t15]:=x

Block B6

(swap)

?

t6:=4*i

x:=a[t6]

t7:=4*i

t8:=4*j

t9:=a[t8]

a[t7]:=t9

t10:=4*j

a[t10]:=x

goto B2

Block B5(swap)

�

Beispielsweise in Block B5 werden (Index-) Ausdrucke mehrfach berechnet: ver-wende also t6 bzw. t8, anstatt t7 bzw. t10 erneut zu berechnen.


in B5 und B6 lokal optimierter codei:=m-1

j:=n

t1:=4*n

v:=a[t1]

Block B1(init)

?

i:=i+1

t2:=4*i

t3:=a[t2]

if t3<v goto B2


?

�

j:=j-1

t4:=4*j

t5:=a[t4]

if t5>v goto B3


?

�

if i>=j goto B6}


? ?

t11:=4*i

x:=a[t11]

t13:=4*n

t14:=a[t13]

a[t11]:=t14

a[t13]:=x

Block B6

(swap)

?

t6:=4*i

x:=a[t6]

t8:=4*j

t9:=a[t8]

a[t6]:=t9

a[t8]:=x

goto B2

Block B5

(swap)

�

Blockubergreifend verwende t4 aus B3 (das laut Datenfluß-Analyse nicht veran-dert wurde) statt t8 erneut zu berechnen.


Block-ubergreifendesVerbreiten von Kopien

i:=m-1

j:=n

t1:=4*n

v:=a[t1]

Block B1(init)

?

i:=i+1

t2:=4*i

t3:=a[t2]

if t3<v goto B2


?

�

j:=j-1

t4:=4*j

t5:=a[t4]

if t5>v goto B3


?

�

if i>=j goto B6}

Block B4 (break)

? ?

x:=t3

t14:=a[t1]

a[t2]:=t14

a[t1]:=x

Block B6(swap)

?

x:=t3

a[t2]:=t5

a[t4]:=x

goto B2

Block B5(swap)

�

z.H. Wovon hangt der Beschleunigungsfaktor aufgrund dieses Optimierungs-schrittes ab? oVariable heißen zu einem Zeitpunkt lebendig, wenn auf sie zu einem spateren Zeit-punkt noch einmal zugegriffen wird. Die Eliminierung gemeinsamer Ausdruckekann tote Variable erzeugen, die eliminiert werden konnen.

Das Verbreiten von Kopien bereitet weitere Optimierung vor: im Programm-Textnach Ausdrucken der Form g := f ersetze g auf rechten Seiten durch f .Z.B. die Anweisung x:=t3 in B5 wird durch Verbreiten von t3 zu totem Code,der eliminiert werden kann.

Schleifen werden durch Code-Verschiebung (Schleifen-unabhangige Berechnun-gen vor die Schleife ziehen), Eliminieren von Schleifen-Variablen in Ausdruckenzusammen mit Reduktion der Starke (etwa Multiplikationen durch mehrfache Ad-ditionen ersetzen) optimiert, z.B. Ersetzen von t4:=4*j in B3 durch t4:=t4-4

mit der nun notwendigen Initialisierung t4:=4*j in B1.


Reduktion der Starkein Verbindung mit

Elimination der do loop Variablen

i:=m-1

j:=n

t1:=4*n

v:=a[t1]

t2:=4*i

t4:=4*j

Block B1

(init)

?

t2:=t2+4

t3:=a[t2]

if t3<v goto B2


?

�

t4:=t4-4

t5:=a[t4]

if t5>v goto B3


?

�

if t2>=t4 goto B6}


? ?

t14:=a[t1]

a[t2]:=t14

a[t1]:=t3

Block B6(swap)

?

a[t2]:=t5

a[t4]:=t3

goto B2

Block B5(swap)

�

Inwiefern ist dieser Optimierungsschritt (noch) nicht kontext-neutral? cz.H. Bestimme grundsatzliche Einflußfaktoren auf den Beschleunigungsfaktoraufgrund derartiger Optimierung. oOptimierende Compiler erzeugen also Code, dessen Struktur sich stark von der-jenigen des Quellprogrammes unterscheidet – mit der einen Folge, daß Fehlerschwieriger zu erkennen sind.

2.1 Daten

Ublicherweise unterstutzen Prozessor-Architektur und Befehlssatz nur die Da-tentypen ganze, Fest- und Gleitkomma-Zahlen durch entsprechende Operationenund schnellen Daten-Transfer. Der Zugriff auf strukturierte Daten wird durchdie hardware i.A. nicht unterstutzt. Der Compiler sollte also dafur sorgen, daßstrukturierte Daten zusammenhangend im Speicher abgelegt werden.

Register-Zuteilungsalgorithmen versuchen, haufig benutzte Daten, z.B. Schlei-fenvariable, in Registern zu halten. Compiler mussen also zugleich Befehlssatz


und Speicher-Zugriff wie auch die statistische Verteilung der Operanden in Aus-drucken mit 60% Skalaren (davon 80% lokale Variable), 20% Integer-Konstantenund 20% strukturierte Daten-Typen berucksichtigen (laut Patterson).

2.2 Anweisungen und ihre Ausfuhrung

Die verschiedenen Anweisungen und Programm-Konstrukte bieten unterschiedli-che Moglichkeiten, die Abarbeitung zu optimieren.

Verschiedene Quellsprachen haben recht verschiedenen Befehlsmix, was die Ab-stimmung von Compiler und Befehlssatz wesentlich erschwert. Zusatzlich beein-flussen Benutzungsprofil und Betriebssystem die folgenden Haufigkeiten

C-Programme Anweisungen in % Speicher-Zugriffe(Patterson 1982) Quellsprache Maschinensprache %Prozeduren 12 33 45Schleifen 3 32 26Zuweisungen 38 13 15Alternativen 43 21 13sonstige Befehle 4 1 1

Prozedur-Aufrufe und Schleifen sind also die Rechenzeit-intensivsten Sprach-Konstrukte, an denen Optimierung zuerst ansetzen sollte.

Weiterhin kann der Transfer zwischen Speicher-Zellen (M) und Registern (R1 undR2) etwa durch

statt besserR1 —> M —> R2 R1 —> M, R1 —> R2R1 <— M —> R2 M —> R1 —> R2

R1 —> M, R2 —> M R2 —> M

optimiert werden.

Gunstig ist es, Auswerten der Sprung-Bedingung und Sprung statt mit einemBefehl in getrennten Befehlen durchzufuhren, da dann z.B. das Ergebnis derAuswertung auch weiter zur Verfugung steht. Einfacher kann das Ergebnis dabeiin allgemeinen Registern als in Status-Registern gehandhabt werden.

Register-Inhalte in den Speicher auszulagern (register spilling), ist zu minimieren.Der Compiler versucht dazu etwa, (wenigstens die innersten) Schleifen-Variablenin Registern zu halten.

Die Bearbeitung von Prozedur-Aufrufen erfordert auf Maschinen-Sprach-Ebeneden aufwendigen Kontext-Wechsel: Ubergabe von Parametern und Ergebnissensowie Verwaltung von lokalen Variablen. Zur Optimierung konnen Compiler etwainline code erzeugen (fur kleine Prozeduren ohne weitere Prozedur-Aufrufe).


Prozeduren greifen vornehmlich auf lokale Daten zu (zu 80% auf lokale, globaleoder Daten aus der aufrufenden Prozedur). Sie haben im Mittel (nur) 6-8 Para-meter. Idee: multiple register sets, (MRS)Kontext-Wechsel kann daher durch Register-Fenster unterstutzt werden. Nebenz.B. 10 ‘globalen’ Registern werden eine Reihe dieser Fenster z.B. als Ring-Puffer(nur sinnvoll in hardware) verwaltet. Fenster von z.B. 32 Registern uberlappensich in z.B. 8 Registern, die fur die Parameter-Ubergabe reserviert sind.Die Ubergabe per Wert ist so einfach zu realisieren. Ein Parameter, der gera-de in einem Register abgelegt ist, hat keine Adresse und kann daher nicht perReferenz Ubergeben werden. Eine Losung des Problems besteht darin, bei derUbersetzung solche Parameter als nicht in Registern ablegbar zu kennzeichnen(Lampson 1982).

Z.B. Die RISC I verfugte uber einen Register-Satz von 138 = 10 + 8 ∗ 16 32bit- Giloi,S.70-71Registern, aufgeteilt in 8 Register-Fenster a 32 Register: 10 gemeinsame fur glo-

bale Daten, 10 Register fur lokale Daten und je 6 uberlappende Register furEingabe- bzw. Ausgabe-Parameter.

10 regs for global variables

6 regs for in/out params

10 regs for local vars















RISC I

8 Fenster a 32

32bit Register

SPARC

8 regs for global variables

















Der Register-Satz von z.B. 136 = 8 + 8∗16 Registern der SPARC ist in 8 Fenster H&P, S.452,E-15a 32 Register mit je 8 Registern fur globale und lokale Daten sowie uberlappende

Register fur Eingabe- und Ausgabe-Parameter aufgeteilt. cFolgen mehrere (z.B. rekursive) Prozedur-Aufrufe aufeinander, ist die (effiziente)


Registerzuteilung schwierig. Es ist dann im Allgemeinen nicht moglich, die Para-meter in Registern ohne Umordnung zu ubergeben.Nachteile entstehen also sicher durch zu große Aufruf-Tiefe – etwa bei rekursivenFunktionen – und dadurch, daß bei Prozeß-Wechsel oder Kontext switch immerder ganze Register-Satz gerettet werden muß (multiprogramming).

Jede Unterbrechung bedingt einen Prozeß-Wechsel: der aktuelle Status ist aufeinen Stapel zu retten. Je nach Architektur mussen dabei alle, einige oder keinRegister gerettet werden, je nachdem ob die Unterbrechungsbehandlung auf alle,einige oder kein Register schreibend zugreifen darf.

Def. Eine Register-Datei (register file) ist eine Menge von Registern zusammenmit Zugriffslogik. Register-Dateien unterstutzen typischerweise das gleichzeitigeLesen von zwei Operanden aus jedem beliebigen und Schreiben eines Ergebnissesin jedes beliebige Register der Register-Datei (ports).

Z.B. Es gibt Hochleistungsrechner mit Register-Dateien, die acht Operanden B&H, p.431

gleichzeitig zur Verfugung stellen. cDie Merkmale von Register-Dateien und cache-Speichern seien gegenubergestellt: Bode, S.106

Register-Datei cache-Speicher

schneller Zugriff auf skalare Daten Zugriff auf Befehle und Datenlokale Variable der letzten n Prozeduren zuletzt benutzte Variable (bei LRU)interner Verschnitt externer Verschnitt(Prozeduren benutzen nicht alle Register) (Block-Transfer)statische Vergabe der Register zur dynamische Verwendung des cache zur

Ubersetzungszeit Laufzeit

Folgerung: Register fur skalare Daten zusammen mit cache fur Befehle. Die gu-te Unterstutzung von Prozeduren durch Register-Dateien mit uberlappendenFenster wird durch schlechte Ausnutzung der Register und damit die vielen beiKontext-Wechsel zu rettenden Registern erkauft.

Die Zuteilung der Register, also das (temporare) Binden der Variablen an Registererfolgt durch Konstruktion eines Datenfluß-Graphen und durch Algorithmen zumFarben dieses Graphen. Bode, S.294

Variable t, u, v, w, x, y, zund ihre Lebensdauern

1 t u2 t u v3 t u v w4 t u v w x5 u v w x6 u v w x y7 u w x y8 u w x y z9 u y z

↓

Zeit

↓

vier Register in Speicherrot grun blau gelb auszulagern

1 t u2 t u v3 t u v w4 t u v w x5 u v w x6 y u v w x7 y u w x8 y u z w x9 y u z


3 Befehlssatze

Der Befehlsatz, (instruction set) eines Prozessors macht die Schnittstelle zwi-schen Programmierer und Rechner, zwischen Code-Erzeugung im Compiler undZiel-Maschine aus. Der Befehlsatz incl. der -Formate zeigt Teile der Prozessor-Architektur.

Z.B. Der single instruction computer (SIC) hat nur eine einzige Instruktion sub- COD, p206

tract and branch if negative sbn a,b,c; // M[a]-=M[b]; if(M[a]<0)goto c.Beispielsweise kopiert das SIC-Programm sbn tmp, tmp,.+1; sbn tmp,a,.+1;

sbn b,b,.+1; sbn b, tmp,.+1; den Inhalt der Speicherzelle a in die Speicher-zelle b, wo . die Adresse der aktuellen, .+1 die der Folge-Instruktion ist. cz.H. Inwiefern ist der SIC ein vollwertiger Computer? um welchen Preis? o

3.1 Klassifikation

Befehlssatze unterscheiden sich darin, wie und wieviele Operanden eines Befehlsin der CPU gespeichert werden, welche Operationen auf den Operanden aus-gefuhrt werden, wie die Operanden addressiert werden und welche Formate dieBefehle haben. Man unterscheidet

Akkumulator-Architektur : Ein Operand liegt implizit im Akkumulator, das Er-gebnis wird im Akkumulator abgelegt: minimale Anzahl interner Zustandeder CPU, kurzer Code; jedoch maximaler Speicherverkehr. Beispiele sindPDP8 oder Motorola 6809.Z.B. Die Zuweisung C = A+B lautet in Maschinen-Sprache

load A;

Add B;

Store C; c

Stack-Architektur : Operanden liegen implizit auf einem Stapel, Ergebnisse wer-den auf Stapel abgelegt: einfache Auswertung von arithmetischen Aus-drucken (polnische Notation), kurzer Code; jedoch kein wahlfreier Zugriffauf Stack, Stack ist Flaschenhals. Beispiele sind Burroughs B5500, HP3000oder Pascal-Engine (vor PC), Java-VM.Z.B. Die Zuweisung C = A+B lautet in Maschinen-Sprache

Push A;

Push B;

Add;

Pop C; c

Register-Architektur : Operanden und Ergebnisse liegen in Registern: wegen Re-gister-Adressierung sind die Befehle langer; diese Architektur bietet jedochgroßte Flexibilitat bei der Code-Erzeugung. Beispiele sind IBM /360 oder


DEC VAX20 oder aktueller Intel 80x86 mit 8, Motorola 68040 mit 16, Po-werPC mit 32, DLX und MIPS mit 32, RISC I mit 32 von 138 oder SPARCmit 32 von 136, pico-Java mit 64 Allzweck-Registern.Z.B. Die Zuweisung C=A+B lautet in Maschinen-Sprache

Load R1,A;

Add R1,B;

Store C,R1;

(register-memory) vs (load/store)

Load Ra,A;

Load Rb,B;

Add Rc,Ra,Rb;

Store C,Rc;

c

Z.B. Der Intel 80x86-Befehlssatz enthalt auch PUSH und POP-Befehle. Die 80x86-Register sind nur bedingt Allzweck-Register! cz.H. Klassifiziere die GK-Operationen der Intel 80x86-Prozessoren. oz.H. Klassifiziere bekannte µ-Controller- und DSP-Befehlssatze. o

3.2 Register-Architekturen

Wegen der Vorteile schneller Register wurden in den letzten zehn Jahren nurnoch Universal-Register-Maschinen entworfen oder weiterentwickelt mit – als ei-nem wichtigen Unterschied – dyadischen (mit zwei Operanden) oder triadischen(mit drei Operanden) ALU-Befehlen sowie mit verschiedener Lokalisation derOperanden: CA, S.93-94

COD, pp150

Register-Register-Operationen – auch load/store – mit einfacher Dekodierung,einfache Code-Erzeugung, ahnliche Ausfuhrungszeiten; jedoch mit großererAnzahl von abzuarbeitenden Befehlen

Register-Speicher-Operationen mit Zugriffen ohne Laden; jedoch unterschiedli-che Ausfuhrungszeiten

Speicher-Speicher-Operationen mit kompaktem Code; jedoch mit unterschiedli-chen Ausfuhrungszeiten und Speicher-Engpaß.

gpr Architektur Jahr gpr Architektur JahrEDSAC 1 accumulator 1949 Intel 8086 1 extended accu 1978IBM 701 1 accumulator 1953 Motorola 68000 16 reg–mem 1980CDC6600 8 load/store 1963 Intel 80386 8 reg–mem 1985IBM /360 16 reg–mem 1964 MIPS 32 load/store 1985DEC PDP-8 1 accumulator 1965 HP-PA RISC 32 load/store 1986DEC PDP-11 8 reg–mem 1970 SUN SPARC 32 load/store 1987Intel 8008 1 accumulator 1972 Power-PC 32 load/store 1992Motorola 6800 2 accumulator 1974 DEC Alpha 32 load/store 1992DEC VAX 16 reg/mem–mem 1977 JAVA-VM 0 stack 1995

und zwar ist die Anzahl der Argumente arithmetisch-logischer Instruktionenim Speicher bei DEC-Alpha, DLX, MIPS, HP PrecisionArchitecture, PowerPC CA, p72

20a Virtual Address eXtension of the PDP11


sowie SPARC jeweils 0 von maximal 3, bei Intel 80x86 sowie Motorola 68000jeweils 1 von maximal 2 und bei der VAX 2 von maximal 2 bzw. 3 von maximal3 Operanden.

z.H. Klassifiziere die Operationen bekannter µ-Controllern und DSPs. o

3.3 Adressierung

In aller Regel arbeiten heutige Rechner byte-adressiert, und zwar big endian(Byte mit Adresse x..x00 an der most significant position im Wort) bei z.B.IBM /360, MIPS, Motorola, SPARC, DLX bzw. little endian (Byte mit Adressex..x00 an der least significant position im Wort) bei z.B. DEC VAX, DEC RISC,Intel 80x86.

Def. Ein Zugriff auf ein Datum der Lange s Byte, ab der Byte-Adresse A istaligned genau dann, wenn A mod s = 0 sonst misaligned.

Eine Reihe Adressierungsarten zur Verfugung zu haben, reduziert die Anzahlder Befehle, macht aber gleichzeitig die Decodierung und damit den Prozessorkomplexer und langsamer. So braucht der Motorola MC68020 bis zu 12 Taktenur fur bestimmte Adressierungen.

Art Beispiel Bedeutung Bemerkungregister Add R4,R3 R4+=R3

immediate Add R4,#3 R4+=3 immediate-Große?displacement Add R4,10(R1) R4+=M[10+R1] lokale Variableregister indirect Add R4,(R1) R4+=M[R1] per pointerindexed Add R4,(R2+R3) R4+=M[R2+R3] Feld mit Base und Indexdirect/absolute Add R4,(1001) R4+=M[1001] static datamemory indirect Add R4,@(R3) R4+=M[M[R3]] linked listauto-increment Add R4,(R3)+ R4+=M[R3]; sequentieller Zugriff auf

R3+=d Feldelemente, push/popauto-decrement Add R4,-(R3) R3-=d; sequentieller Zugriff auf

R4+=M[R3] Feldelemente, push/popscaled Add R4,10(R2)[R3] R4+=M[10+R2+d*R3] sequentieller Zugriff auf

Daten der Lange d

Beim Entwurf ist festzulegen, wie groß Displacement oder Immediate werdendurfen, wieviele Bits also vorzusehen sind, wieviel Register zu adressieren sind,usw. Displacement und Immediate sind die haufigsten Adressierungsarten.

Z.B. Die Codierung der vielen Adressierungsarten der VAX illustriere eine CA, p89

ternaren oder triadische Instruktion: add13 r1, 737(r2), (r3) addiert zwei 32-bit integer bei einem OP-Code von 1byte. Address specifier enthalten in 4bit dieAdressierungsart, in weiteren 4bit das zu verwendende Register: also 1byte furr1, 3byte fur 737(r2), namlich 1byte specifier fur 16-bit displacement und 2bytedisplacement 737 und schließlich 1byte specifier fur indirect (r3) – insgesamtalso 6byte. Die maximale Lange von VAX-Befehlen ist 53byte! cZ.B. DSPs mit Zugriff auf Ring-Puffer, z.B. TI c


z.H. Klassifiziere die Addressierungsarten bekannter µ-Controllern. o

3.4 Operationen

Man unterscheidet verschiedene Typen von Befehlen:

arithmetisch/logische Befehle, wie integer add, sub oder and, or

Datentranfer, wie load, store oder move

Steuerung, wie Verzweigungen, Sprunge, Unterprogramm-Sprunge und -Ruck-sprunge, traps

Betriebssystem-Aufrufe, Speicher-Verwaltung

Gleitkomma-Befehle, d.h. arithmetisch/logische Operationen auf Gleitkomma-Zahlen, wie fadd, fmult oder fdiv oder Vergleiche vgl. B&H,

p.42IEEE 754Dezimal, d.h. arithmetische Operationen auf binary coded decimal (BCD)-

Zahlen

String, d.h. Operationen auf Zeichenketten

Varia, d.h. I/O, Graphik, transzendente Funktionen (80x86), insert/extract atresp. from head/tail of queue (VAX), Vektor-Instruktionen (Cray), Instruk-tionen, die Parallelitat auf Instruktionsebene nutzen (Intels MMX, AMDs3Dnow!, Intel 80x86!ISSE), Befehlssatz-Erweiterungen wie SUN-SPARC vi-sual instruction set (VISual)

Die Haufigkeiten der Befehle zusammen mit der Haufigkeit der Art ihrer Operan-den (Typ, Adressierung, Sprungziele, ...) hangen vom Programm, vom Compiler,von dessen Optimierung, vom Betriebssystem und von der Maschine ab. Sie sinddeshalb schwierig zu bestimmen. Hennessy/Patterson geben beispielsweise fur ei- DECstation:

CA, S.120IBM /360:CA, S.140Intel 8086:CA, B9, C4

ne DECstation ca. 10% Verzweigungen, 40% load/store- sowie 50% ALU-Befehlefur eine IBM /360 15% Verzweigungen, 20% load/store- und 65% ALU-Befehlean und prasentieren detaillierte Messungen fur Intel 8086 Prozessoren.

Befehle, die den Programmfluß verandern, sind zu zwei Dritteln bedingte Ver-zweigungen und zu je einem Sechstel Sprunge oder Unterprogramm-Sprunge bzw.-Rucksprunge.Ziele von Verzweigungen sind meist PC-relativ und in drei Vierteln der Fallevorwarts gerichtet. Der mittlere Verzweigungsabstand betragt weniger als 27 Be-fehle (abhangig von der mittleren Befehlslange).Die Verzweigungsbedingung ist zu zwei Dritteln EQ/NE (zero), gespeichert inBedingungscode-Bits (condition code etwa im Prozessor-Status-Wort), in allge-meinen Registern oder in komplexeren ‘test and branch’-Befehlen.


Wie beim Displacement bedingen sich auch die maximale Sprungweite bei unbe-dingten Sprungen und das Befehlsformat gegenseitig.Bei Unterprogramm-Sprungen muß zumindest die Ruckkehr-Adresse – zumeistauf dem Stack – gerettet werden, meist aber auch die Register (per caller sa-ving oder per callee saving), um diese innerhalb des Unterprogrammes zur freienVerfugung zu haben.

3.5 Anforderungen an Befehlssatze

Verschiedene Prozessoren haben teilweise sehr unterschiedliche Befehlssatze.

Z.B. Die IBM /370 hat 2-, 4- und 6-Byte-Befehle, die CDC Cyber Halb- und Giloi, S.65

Ganzwort-Befehle bei einer Wort-Lange von 16 (?) Byte; DEC PDP11 und Mo-torola MC68020 haben Ein-, Zwei- und u.U. auch Drei-Wort-Befehle bei 2-Byte-Worten. cZ.B. Der DLX und dem MIPS R2000 gemeinsam sind 32 Allzweck-Register a DLX CA,

S.160ff,S.E-1ffMIPS COD,pp106,ppA-49

32bit (R0 = $0 ≡ 0) und 32 GK-Register a 32bit, load/store Architektur, 32bitAdreß-Raum, linearer Speicher / flat memory

Byte Halfword Word

Registers

Memory

Memory

Word

Memory

Word

Register

Register

1. Immediate addressing

2. Register addressing

3. Base addressing

4. PC-relative addressing

5. Pseudodirect addressing

op rs rt

op rs rt

op rs rt

op

op

rs rt

Address

Address

Address

rd . . . funct

Immediate

PC

PC

+

+

F317.pdfCOD, p152

displacement als einzige Adressierungsart fur Daten per lw, lb bzw. sw, sb sowielhi (load high immediate der DLX) bzw. lui (load upper immediate des MIPS)zum Laden der oberen 2 byte eines 4 byte Wortes, ternare arithmetisch/logischeBefehle add, sub, s__ usw. mit immediate-Varianten addi, subi, s__i, wobei__ fur lt, le, eq, ne, ge, gt steht, ternare Verzweigungen wie beq, bne mit


immediate-Varianten beqz, bnez, sowie den Sprung-Anweisungen j, jr und jal.Alle Instruktionen sind 4byte lang, was etwa bei der Ermittlung des Sprungzielsausgenutzt wird. Es gibt i.W. nur drei Befehlsformate:

R-type OPcode6

Rs5

Rt5

Rd5

shamt5

func6

I-type OPcode6

Rs5

Rt5

immediate16

J-type OPcode6

jump offset26

Fig. A.19 stellt die MIPS OPcode map dar. Der OPcode spezifiziert die Instrukti-on vollstandig, außer fur die OPcodes 0, 1, 16-19. f (float) steht fur s (single) fallsrs=16 und op=17, f (float) steht fur d (double) falls rs=17 und op=17. Im Feldrs steht z fur 0, 1, 2 oder 3, falls op=17, 18, 19 bzw. 20. Falls z=0, so spezifiziertInstr[4-0] die Instruktion; falls z=1, so spezifiziert funct die Instruktion mitf=s; ...


10 0 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

10 0 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

10 0 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

0 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

0 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

0 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

16 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0 f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1 f 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2 f 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3 f

op(31:26) j jal beq bne blez bgtz addi addiu slti sltiu andi ori xori lui z = 0 z = 1 z = 2 z = 3 lb lh lwl lw lbu lhu lwr sb sh swl sw swr lwc0 lwc1 lwc2 lwc3 swc0 swc1 swc2 swc3

rs (25:21) mfcz cfcz mtcz ctcz copz copz

(16:16) bczt bczt

tlbr tlbwi tlbwr tlbp rte

rt (20:16)

bltz bgez bltzal bgezal

cvt.s.f cvt.d.f cvt.w.f c.f.f c.un.f c.eq.f c.ueq.f c.olt.f c.ult.f c.ole.f c.ule.f c.st.f c.ngle.f c.seq.f c.ngl.f c.lt.f c.nge.f c.le.f c.ngt.f

funct(5:0) add.f sub.f mul.f div.f abs.f mov.f neg.f

funct(5:0) sll srl sra srlv srav jr jalr syscall break mfhi mthi mflo mtlo mult multu div divu add addu sub subu and or xor nor slt sltu

if z = l, f = d

if z = l, f = s

if z = 0

0 1

funct (4:0)

FA19.pdfCOD, pA-54

DLX und MIPS R2000 und hoher sind typische RISC-Prozessoren. cZ.B. Jeder Prozessor der Intel 80x86-Prozessor-Familie ist abwartskompatibel zu Bahring und

Lieb et alCOD, pp177-185

seinen Vorgangern, damit dieselbe software weitergenutzt werden kann.


031

GPR 0EAX

GPR 3EBX

GPR 1ECX

GPR 2EDX

GPR 6ESI

Code segment pointerCS

Stack segment pointer (top of stack)SS

Data segment pointer 0DS

Data segment pointer 1 ES

Data segment pointer 2FS

Data segment pointer 3GS

GPR 7EDI

GPR 5EBP

GPR 4ESP

EIP Instruction pointer (PC)

EFLAGS Condition codes

Name Use

F329.pdfCOD, p179

1978 8086 16 bit Register, nicht Allzweck1980 8087 GK-co-Prozessor mit ca. 60 GK-Befehlen, stack orientiert1982 80286 24 bit Adreß-Raum, memory mapping, memory protection

1985 8038632 bit Register, 32 bit Adreß-Raumadded addressing modes, added operations ⇒ 8 Allzweck-Register

19891995

–80486 bisPentium (Pro)

nur 4 neue Befehle (multi processing, conditional move)

1997 MMX 57 neue Instruktionen (SIMD)199? ISSE Erweiterung von MMX um float-Operationen

Der Intel 8080 verfugte uber acht 8-bit-Register AL, AH, DL, DH, CL, CH, BL CA, D

und BH sowie 16-bit SP und IP-Register (accumulator machine).1978 wurden die 8-bit Register im 8086 zu 16-bit Registern AX, DX, CX und BXzusammengefaßt (AX = Akku, CX = count register (LOOP), DX = data register(mult/div), BX = base address register. Es gibt Segment-Register CS (code), SS(stack) und DS (data). Neben Registern wie IP (instruction pointer) und FLAGS(processor status) gibt es weitere 16bit-Register wie SP (stack pointer) oder BP(base pointer). Quell-Index-Register source index (SI) und Ziel-Index-Register


destination index (DI) verwendet etwa MOVSB: M[ES:DI]=M[DS:SI]; DI++; SI++,Wegen des dedizierten Gebrauchs der Register ist der 8086 zwischen accumulatorund general purpose register machine) zu plazieren, eine extended accumulatormachine laut CA.Aus Grunden der Abwartskompatibilitat mußte aber immer noch auch auf die8-bit Register zugegriffen werden konnen.1980 erganzt der 8087 coprocessor 8 floating point register a 80bit und den Be-fehlssatz um 60 floating point instructions (extended stack architecture).1982 bietet der 80286 einen 24bit Adreß-Raum mit memory mapping and pro-tection und dem real (addressing) mode fur die Abwartskompatibilitat mit dem8086.1985 erfullt dieselbe Anforderung auch der 80386 mit seinen 32-bit ErweiterungenEAX, ECX, EDX und EBX der Register AX, CX, DX bzw. BX. Weiterhin gibt eszusatzliche 16-bit Segment-Register FS und GS sowie 32bit-Erweiterungen EIP,EFLAGS, ESP, EBP, ESI bzw. EDI der Register IP, FLAGS, SP, BP, SI bzw.DI.

15 8 7 0 16 bitAH AL AXCH CL CXDH DL DXBH BL BX

CSSSDSESFSGS

16 bit 32 bit

AX EAXCX ECXDX EDXBX EBXSP ESPBP EBPSI ESIDI EDI

FLAGS EFLAGSIP EIP

Byte\bit 7 6 5 4 3 2 1 01a OP-Code1b (1 oder 2 byte)2a Mod Reg R/M2b Scl IReg BReg3a Address-Displacement...

...3d 0,1,2,3 oder 4 byte4a Immediates...

...4d 0,1,2,3 oder 4 byte

Das Register EFLAGS enthalt den Prozessor-Status (PSW) mit aligned, virtualmode, nested, i/o priviledge, overflow, direction, interrupt enable, trap, sign, zero,auxiliary carry, parity und carry flags; das Register EIP enthalt den Befehlszahler(instruction pointer, IP). ⇒ wenige (8) Allzweck-Register!Die 16-bit Segment-Register CS (Code), SS (Stack) sowie DS, ES, FS und GS(Daten) stehen fur die Adressierung SR:X entsprechend (SR<<4)+X

address =CS ... GSsegment +

je EAX, ..., EDX, ESP, EBP, ESI, EDI

base address + (index ∗1, 2, 4 oder 8

scale factor) +in 0, 8, 32 bit

displacement

zur Verfugung. ⇒ mindestens vier Addressierungsarten!

Intel terminology address = restrictionregister indirect register reg 6= ESP, EBPbased mode with displacement base+displacement reg 6= ESP, EBP

base plus scaled index base+2scaleindex index 6= ESP

base plus scaled index with displacement base+2scaleindex+displacement index 6= ESP

Die arithmetisch/logischen Befehle sind dyadisch (1.source=destination) mit al-len Kombinationen bis auf Speicher–Speicher. Dabei gibt es Befehle fur bit, byte,


16bit, 32bit, 64bit, bit-Felder bis 32bit, word strings, 8bit BCD Zahlen, gepacktund ungepackt. ⇒ dyadische Operationen auf diversen Datentypen!Instruktionen sind zwischen einem und 12 bytes lang (im Fall des Intel 80486 auchnoch langer). OP-Code (incl. der Angabe uber die Langen der folgenden Felder)und Register plus Adressierungsart (register, memory, scaled und index based)beanspruchen jeweils ein oder zwei Byte, Adress-Displacement und Immediatesjeweils 0, 1, 2, 3 oder 4 Byte.Es gibt optionale instruction-, address size-, operand size- und segment overrideprefixes von je 1 byte Lange: instruction prefix enthalt Wiederholungszahler in- s.a. Stallings

cl. Abbruchbedingung, address- und operand size prefix bestimmen Adreß- undOperanden-Lange (default ist 16bit im real und 32bit im protected mode), seg-ment override prefix hebt die implizite Segment-Register-Zuordnung fur den be-treffenden Befehl auf.

Beispiele fur 8086 Befehle COD, p182CA, D

ADD AX,#4711 AX+=4711

JZ name bzw JNZ name if (CC=0) IP=name; bzw if (CC!=0) IP=name;

JMP name bzw JMPF name IP=name; (near bzw far)CALLF name,seg SP-=2;M[SS:SP]=CS;SP-=2;M[SS:SP]=IP+5;IP=name;CS=seg;

MOVSB M[ES:DI]=M[DS:SI]; DI++; SI++;

MOVW BX, [DI+123] BX=M[DS:DI+123];

PUSH SI SP-=2; M[SS:SP]=SI;

POP DI DI=M[SS:SP]; SP+=2;

SHL BX,1 BX*=2;

TEST DX,#42 CCflags=DX & 42

Beispiele fur 80386 Befehle COD, p182CA, D

ADD EAX,#4711 EAX+=4711

JZ name bzw JNZ name if (CC=0) EIP=name; bzw if (CC!=0) EIP=name;

JMP name bzw JMPF name EIP=name; (near bzw far)CALL name SP-=4; M[SP]=EIP+5; EIP=name;

LOOP label ECX--; if (ECX) EIP+=label;

MOVSL M[EDI]=M[ESI]; EDI++; ESI++;

MOVW EBX, [EDI+123] EBX=M[EDI+123];

PUSH ESI SP-=4; M[SP]=ESI;

POP EDI EDI=M[SP]; SP+=4;

RET EIP=M[SP]; SP+=4; JMP EIP;

TEST EDX,#42 CCflags=EDX & 42

LES loads ES and one of the GPregisters from memory; ADD, SUB, CMP, OR, XOR,INC, DEC sind alles (auch) Register–Speicher-Befehle; CBW converts lsbyte of EAXto lsword of EAX (Akku); LODS loads a byte, word, double word of a string in EAX

(Akku) ...


JE

JE EIP + displacement

Offset

CALL

MOV EBX, [EDI + 45]

PUSH

PUSH ESI

ADD w

ADD EAX, #6765

Reg

4 4 8

6

8 32

5 3

4 13 32

Immediate

Condition

MOV

1

w

1

d

8 8

TEST EDX, #42

7 1 8 32

TEST Postbyte Immediatew

Reg

f.

e.

d.

c.

b.

a.

CALL

Displacementr-m

postbyte

Displacement

F334.pdfCOD, p184

Wie schwer Intel-Befehle zu decodieren sind, zeigen nicht nur die vielen Formatesondern auch die Interpretation des Postbyte m, reg, r/m, die von mode m undw-Feld (width) im OP-Code gesteuert wird (Fig. 3.35): COD, p185

w=1

reg

w=

0

16b 32b0 AL AX EAX1 CL CX ECX2 DL DX EDX3 BL BX EBX4 AH SP ESP5 CH BP EBP6 DH SI ESI7 BH DI EDI

m=0 m=1 m=2r/m 16bit 32bit 16bit 32bit 16bit 32bit

0 =BX+SI =EAX1 =BX+DI =ECX same addr as in m=0 with2 =BP+SI =EDX disp8 disp16 disp323 =BP+DI =EBX4 =SI =(sib) SI+disp16 (sib)+disp8 SI+disp8 (sib)+disp325 =DI =disp32 DI+disp8 EBP+disp8 DI+disp16 EBP+disp326 =disp16 =ESI BP+disp8 ESI+disp8 BP+disp16 ESI+disp327 =BX =EDI BX+disp8 EDI+disp8 BX+disp16 EDI+disp32

Im mode m=3 wird ein Register genau wie im reg-Feld adressiert. cZ.B. Der sledgehammer von AMD stellt eine 64bit Erweiterung des Pentium C’T, 2000,

Heft 18,22-23

dar und bewaltigt den Ubergang von 32bit zu 64bit abwartskompatibel wie wei-land der Intel 80386 den Ubergang von 16bit zu 32bit. Dazu werden die achtAllzweck-Register EAX, ECX, EDX, EBX, ESP, EPB, ESI und EDI erneut zu64bit Registern RAX, RCX, RDX, RBX, RSP, RPB, RSI und RDI erweitert.Zusatzlich spendiert AMD acht weitere 64bit Allzweck-Register R8 bis R15. ImGegensatz zu 80x86-Familie sind nunmehr auch die low-Bytes SPL, BPL, SILund DIL zugreifbar.Da alle 1byte OP-Codes vergeben sind, mussen die neuen Register per Prafix an-gesprochen werden. Die Kurzform der 16 Dekrement/Inkrement-Befehle werdendazu fur die sogneannten REX-Instruktionen umdefiniert. Ein paar andere In-struktionen werden im 64bit-Modus nicht mehr unterstutzt. MOVSXD erweitert32bit Daten vorzeichenrichtig auf 64bit.Wie bei der 80x86-Familie haben alle arithmetisch/logischen Operationen zweiOperanden.


3DNow! wurde zugunsten von ISSE2 der Kompatibilitat geopfert...Der Prozessor unterstutzt im legacy mode den real, virtual und protected mode,im long mode den 32bit compatibility mode und endlich den 64bit mode.Im 64bit mode greift der Prozessor ohne Segmentierung auf den Speicher zu (flatmemory), hierarchische Adress-Umsetzung, 4KB- oder 2MB-Seiten – im Gegen-satz zu den zwischen 4KB und 4GB variabel großen Seiten des iA64. cNeben technologischen Randbedingungen sind damit zwei fast kontroverse An-forderungen zu befriedigen.

Fur den Compiler (-Bauer) sind folgende Eigenschaften wunschenswert:

Wenn Operation, Datentyp und Adressierungsart orthogonal, d.h. unabhangigsind, vereinfacht sich die Code-Erzeugung!

Lieber Primitive als Konstrukte fur eine bestimmte Programmier-Sprache!

Leitlinie: einfachere Entscheidung zwischen Code-Alternativen!

Befehle, die zur Compile-Zeit vorhandene Information auch zu nutzen erlauben!Z.B. Fur die VAX enthalt eine Maske, welche Register bei Prozedur-Aufrufen zu retten sind. c

Z.B. Der VAX-Befehlssatz ist hoch-orthogonal, erlaubt einfache Zuordnung vonHochsprachen-Aweisungen zu Maschinen-Befehlen. Die Code-Lange ist optimiert,damit große Programme in den damals knappen Speicher passen. 1978 war dieVAX die erste Speicher-Speicher-Architektur. cFur den Prozessor (-Designer) sind folgende Eigenschaften wunschenswert:

leichte Dekodierbarkeit

leichtes pipelining

load/store Architektur

wenige Addressierungsarten

Z.B. Wie die ersten ausgesprochenen RISC-Maschinen (IBM 801, RISC I undRISC II in Berkeley sowie MIPS in Stanford) weist die DLX mit ihrer load/store-Architektur, mit 32-bit-Festformat-Befehlen und mit einem in der pipeline-Imple-mentierung CPI-Wert von kleiner als zwei einen exemplarischen RISC-Befehlssatzauf. c


4 Prozessor-Architekturen

Der minimale von-Neumann-Prozessor (um 1970) besteht aus arithmetisch/logi-scher Einheit (arithmetic logic unit, ALU), Akkumulator, gegebenenfalls Multi-plikator-Register (Akkumulator-Verlangerung) mit Multiplikanden-Register, Be-fehlszahler, Befehlsregister und Speicher-Adreß-Register.

Prozessor = Daten-Prozessor + Befehlsprozessor

Daten-Prozessor = ALU, Akkumulator, (Multiplikator-Register, Multiplikan-den-Register)

Befehlsprozessor = Befehlsdekodierung, Befehlszahler, Befehlsregister.

Der minimale von-Neumann-Prozessor ist ein Ein-Adreß-Rechner:entweder OP(Akku) oder OP(Akku,Speicher-Zelle).

Die technologischen Randbedingungen haben sich drastisch verandert: damalswar die Zeit fur einen Speicherzugriff klein gegenuber der Verarbeitungszeit; heutedauert ein Speicherzugriff lang verglichen mit der Verarbeitung im Prozessor.

Um den Speicherzugriff zu beschleunigen, werden einerseits mehrere Register mitim Verhaltnis zum Speicher sehr kurzer Zugriffszeit verwendet und Verfahrenwie caching und Aufteilen des Speichers in mehrere unabhangige Banke sowieload store-Architekturen (load, store und execute uberlappend, Operationen nurauf Operanden in Registern) eingesetzt. Um die organisatorischen Aufgaben imProzessor beschleunigt zu bewaltigen, werden Prozessoren mit einer Befehlspi-peline ausgerustet, in der Laden, Dekodieren, Ausfuhren und Ruckspeichern desErgebnisses uberlappend ausgefuhrt werden. COD, Ch.5

Stellen wir uns einen Prozessor aus Bausteinen zusammen, im ersten Schrittzunachst den Daten-Prozessor oder auch Daten-Pfad, im zweiten Schritt denBefehlsprozessor oder auch die Steuerung. Als Beispiel dient der MIPS R3000.

4.1 Prozessor-Datenpfad

Fig. 5.1 gibt einen Uberblick uber den Daten-Pfad.

Registers

Register #

Data

Register #

Data memory

Address

Data

Register #

PC Instruction ALU

Instruction memory

Address


F501.pdfCOD, p340

Die Bausteine zur Ausfuhrung von arithmetisch/logischen Befehlen wie beispiels-weise add R1, R2, R3 im sogenannten R-Format (Argumente in drei Registern)ergeben den Daten-Pfad fur solche Befehle in Fig. 5.7.

InstructionRegisters

Write register

Read data 1

Read data 2

Read register 1

Read register 2

Write data

ALU result

ALU

Zero

RegWrite

ALU operation3

F507.pdfCOD, p347

Die Bausteine zur Ausfuhrung von Lade-/Speicher-Befehlen (load/store-instruc-tions) zum Lesen aus bzw. Schreiben in den Speicher, wie load R1, offset(R2),im sogenannten immediate oder I-Format (im Befehl ist der Offset als Argumentdirekt enthalten) ergeben den Daten-Pfad fur solche Befehle in Fig. 5.9.

Instruction

16 32

RegistersWrite register

Read data 1

Read data 2

Read register 1

Read register 2

Data memory

Write data

Read data

Write data

Sign extend

ALU result

ZeroALU

Address

MemRead

MemWrite

RegWrite

ALU operation3

F509.pdfCOD, p348

Verzweigungsbefehle (branch instructions) wie beq R1, R2, offset arbeiten PC-relativ. Da die Befehle ausgerichtet (aligned) sind, ergibt sich der Daten-Pfad fursolche Befehle in Fig. 5.10.


16 32Sign

extend

ZeroALU

Sum

Shift left 2

To branch control logic

Branch target

PC + 4 from instruction datapath

Instruction

Add


Read data 1

Read data 2

Read register 1

Read register 2

Write data

RegWrite

ALU operation3

F510.pdfCOD, p350

Der Daten-Pfad fur diese drei Typen von Befehlen ist in Fig. 5.13 dargestellt.

PC

Instruction memory

Read address

Instruction

16 32

Add ALU result

M u x

Registers

Write register

Write data

Read data 1

Read data 2

Read register 1Read register 2

Shift left 2

4

M u x

ALU operation3

RegWrite

MemRead

MemWrite

PCSrc

ALUSrc

MemtoReg

ALU result

ZeroALU

Data memory

Address

Write data

Read data M

u x

Sign extend

Add

F513.pdfCOD, p354

Der Daten-Prozessor braucht allerdings eine Steuer-Einheit, also den Befehls-prozessor (control unit), der die farbig eingezeichneten Steuer-Signale erzeugt.

4.2 Prozessor-Steuerung

Zur Einfuhrung sei nur die Steuerung der ALU dargestellt (Fig. 5.14): COD, p355


OpCode ALUop InstrOp Funct ALUaction (ALU-) OperationLW 00 x add 010SW 00 x add 010

BEQ 01 x sub 110R-Type 10 add 100000 010

sub 100010 wie 110and 100100 in 000or 100101 InstrOp 001

s(et)LT 101010 111Die Erzeugung des 3bit Steuersignals (ALU-) Operation ubernimmt eine Mini-Steuer-Einheit der ALU, die ALUcontrol, die sich mit wenigen Gattern imple-mentieren laßt (s. Fig. C.3).

Operation2

Operation1

Operation0

Operation

ALUOp1

F3

F2

F1

F0

F (5–0)

ALUOp0

ALUOp

ALU control block

FC03.pdfCOD, pC-6

So wie die ALU aufgrund der Steuer-Signale in Fig. 5.14 verschiedene Operationendurchfuhrt, brauchen auch die anderen Bausteine in Fig. 5.17


MemtoReg

MemRead

MemWrite

ALUOp

ALUSrc

RegDst

PC

Instruction memory

Read address

Instruction [31–0]



Add

Instruction [5–0]

RegWrite

4

16 32Instruction [15–0]

0Registers

Write registerWrite data

Write data

Read data 1

Read data 2

Read register 1Read register 2

Sign extend

ALU result

Zero

Data memory

Address Read data M

u x

1

0

M u x

1

0

M u x

1

0

M u x

1


ALU control

Shift left 2

PCSrc

ALU

Add ALU result

F517.pdfCOD, p358

die Steuer-Signale aus Fig. 5.20 in Abhangigkeit von der auszufuhrenden Instruk-tion. COD, p361

OpCode RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOpR-Type 1 0 0 1 0 0 0 10

LW 0 1 1 1 1 0 0 00SW x 1 x 0 0 1 0 00

BEQ x 0 x 0 0 0 1 01

Die Abhangigkeit der Signale vom OP-Code der vier exemplarischen Befehle zeigtFig. 5.27. COD, p370

input output

OP

5

OP

4

OP

3

OP

2

OP

1

OP

0

Reg

Dst

AL

US

rc

Mem

toR

eg

Reg

Wri

te

Mem

Rea

d

Mem

Wri

te

bra

nch

AL

UO

p1

AL

UO

p0

R-Type 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0LW 1 0 0 0 1 1 0 1 1 1 1 0 0 0 0SW 1 0 1 0 1 1 x 1 x 0 0 1 0 0 0

BEQ 0 0 0 1 0 0 x 0 x 0 0 0 1 0 1

Der Daten-Pfad mit Steuerung ist in Fig. 5.19 dargestellt.


PC

Inst

ruct

ion

mem

ory

Rea

d ad

dres

s

Inst

ruct

ion

[31

–0]

Inst

ruct

ion

[20

1

6]

Inst

ruct

ion

[25

2

1]

Add

Inst

ruct

ion

[5

0]

Mem

toR

eg

ALU

Op

Mem

Write

Reg

Write

Mem

Rea

d

Bra

nch

Reg

Dst

ALU

Src

Inst

ruct

ion

[31

2

6]

4

16

32

Inst

ruct

ion

[15

0

]

0

0M

u x0 1Con

trol

Add

ALU

re

sult

M

u x0 1

Reg

iste

rsW

rite

re

gist

er

Write

da

ta

Rea

d da

ta 1

Rea

d da

ta 2

Rea

d re

gist

er 1

Rea

d re

gist

er 2

Sig

n ex

tend

M

u x 1

ALU

re

sult

Zero

PC

Src Dat

a m

emor

yW

rite

da

ta

Rea

d da

taM

u x1

Inst

ruct

ion

[15

1

1]

ALU

co

ntro

l

Shi

ft

left

2

ALU

Add

ress

F519.pdfCOD, p360


Die Steuerung setzt die Signale in Abhangigkeit der 6 OP-code-bits. Diese inFig. 5.27 zusammengefaßten Abhangigkeiten lassen sich direkt auf einem pro-grammable logic array (PLA) (s. Fig. C.5) implementieren.

R-format Iw sw beq

Op0

Op1

Op2

Op3

Op4

Op5

Inputs

Outputs

RegDst

ALUSrc

MemtoReg

RegWrite

MemRead

MemWrite

Branch

ALUOp1

ALUOpOFC05.pdfCOD, pC-8

Dabei werden auch gleich die don’t care Eintrage in Fig. 5.27 zur Reduktion deshardware-Aufwandes ausgenutzt.Geringfugige Erweiterungen (stepweise refinement) des Prozessor-Entwurfs erlau-ben auch die Abarbeitung von Sprung-Befehlen (Fig. 5.29).


Shi

ft

left

2

PC

Inst

ruct

ion

mem

ory

Rea

d ad

dres

s

Inst

ruct

ion

[31

–0]

Dat

a m

emor

yRea

d da

ta

Write

da

ta

Reg

iste

rsW

rite

re

gist

er

Write

da

ta

Rea

d da

ta 1

Rea

d da

ta 2

Rea

d re

gist

er 1

Rea

d re

gist

er 2

Inst

ruct

ion

[15

–11

]

Inst

ruct

ion

[20

–16

]

Inst

ruct

ion

[25

–21

]

Add

ALU

re

sult

Zero

Inst

ruct

ion

[5–0

]

Mem

toR

eg

ALU

Op

Mem

Write

Reg

Write

Mem

Rea

d

Bra

nch

Jum

pR

egD

st

ALU

Src

Inst

ruct

ion

[31

–26

]

4

M

u x

Inst

ruct

ion

[25

–0]

Jum

p ad

dres

s [3

1–0

]

PC

+4

[3

1–2

8]

Sig

n ex

tend

16

32

Inst

ruct

ion

[15

–0]

1

M

u x1 0

M

u x0 1

M

u x0 1

ALU

co

ntro

l

Con

trol

Add

ALU

re

sult

M

u x0 10

ALU

Shi

ft

left

226

28

Add

ress

F529.pdfCOD, p372


z.H. Erweitere wo notwendig Datenpfad und Stewuerung des Prozessors um denadd immediate Befehl addi Rt,Rs,#imm; Rt=Rs+#imm. oFur jeden Befehlstyp laßt sich die Dynamik, also das Verhalten des Prozessors inder Zeit in (sequentielle) Schritte aufteilen.

Arithmetisch/logische Befehle wie add Rd, Rs, Rt werden erstens in das in-struction memory geladen und der PC wird inkrementiert. Zweitens werdendie Register Rs sowie Rt ausgelesen und Control wertet den Funktionscodeaus. Drittens fuhrt die ALU die spezielle Operation aus. Schließlich wirddas Ergebnis viertens in das Zielregister Rd geschrieben.

Lade-/Speicher-Befehle wie LW Rt,offset(Rs) (load word) werden erstens indas instruction memory geladen und der PC wird inkrementiert. Zwei-tens wird Rs eingelesen. Drittens addiert die ALU Rs und den auf 32 bitVorzeichen-erweiterten Wert von offset. Diese Adresse wird viertes amSpeicher angelegt. Schließlich wird funftens der Inhalt der addressiertenSpeicher-Zellen in das Ziel-Register Rt kopiert.SW Rt,offset(Rs) (store word) wird entsprechend abgearbeitet.

Verzweigungsbefehle wie etwa BEQ Rs, Rt, offset (branch on equal) werdenerstens in das instruction memory geladen und der PC wird inkrementiert.Zweitens werden die beiden Register Rs und Rt eingelesen. Drittens subtra-hiert die ALU die beiden Register-Werte. Sie aktualisiert damit auch denBedingungscode zero. Außerdem wird die mogliche Zieladresse der Verzwei-gung durch Addition von PC +4 und dem auf 32 bit Vorzeichen-erweitertenWert von offset berechnet. Viertens entscheidet der Bedingungscode in ze-ro, welches Additionsergebnis in PC gespeichert wird.

Sprung-Befehle wie etwa J target (jump) werden erstens ins instruction me-mory geladen und der PC wird inkrementiert. Zweitens werden die nieder-wertigen 26 bit des PC durch target ersetzt. Drittens wird das Ergebnisum 2 nach links geschoben. Schließlich wird viertens der PC mit diesemErgebnis aktualisiert.

z.H. Erweiterung um Instruktionen wie addi, subi, sxx und sxxi mit xx=EQ,NE, LT, LE, GT und GE sowie LUI (load upper immediate), usw. o

4.3 single-cycle- vs multi-cycle-Implementierung

Bei der single-cycle-Implementierung bestimmt der Befehl mit der langsten Aus-fuhrungsdauer den Maschinen-Zyklus, in aller Regel der Lade-Befehl, da dieserin seinen funf Schritten nacheinander die funktionalen Einheiten instruction me-mory, register file, ALU, data memory und endlich nochmal register file aktiviert.


Die verschiedenen Befehle werden aber in unterschiedlich vielen, verschieden lan-gen Schritten ausgefuhrt. Die gewichtete Summe∑

Befehlstypi

Haufigkeiti × Daueri

bestimmt die mittlere Befehlsausfuhrungsdauer.

Z.B. Die Berechnung des Signums (in Rs) einer integer Zahl i benotigt in dersingle cycle implementation maximal, namlich abhangig vom Wert von i, sechs8ns-Zyklen, also 48ns

lw Rs,i beqz Rs,end slt Rs,Rs,R0 beqz Rs,pos addi Rs,R0,-1 j end

pos:

addi Rs,R0,1

end:

-lw beq slt bgez addi j

pos:

addi

end:

und maximal 8+5+6+5+6+2=32ns in der multi cycle implementation mit va-riablem clock-cycle und maximal 10+6+8+6+8+2=40ns bei festem clock-cycle.cEine multi-cycle-Implementierung beschleunigt also die Befehlsabarbeitung.

Z.B. Seien folgende Zugriffszeiten auf Register bzw. Speicher, Dauern von ALU-Operationen und Befehlshaufigkeiten des Befehls-Mix angenommen:

IF ID EX Mem WbInstr. Reg. ALU Data Reg. h t h · t t h · t

Befehl mem. read opr. mem. write % (ns) (ns) (ns) (ns)load 2 1 2 2 1 24 8 1.92 10 2.40store 2 1 2 2 12 7 0.84 8 0.96arith. 2 1 2 1 44 6 2.64 8 3.52branch 2 1 2 18 5 0.90 6 1.08jump 2 1 2 3 0.06 4 0.08∑

= 6.36∑

= 8.04

Dann ist fur die multi-cycle-Implementierung die mittlere Ausfuhrungsdauer mit6.36ns kleiner als die maximale Ausfuhrungsdauer von 8ns im Fall der single-cycle-Implementierung, was einem Beschleunigungsfaktor von 8/6.36 ≈ 1.26 ent-spricht. cZ.B. Aus Haufigkeit eines jeden Befehls und Anzahl von Zyklen zu

load store arith/log branch jump∑

n (cycles) 5 4 4 3 1h (%) 24 12 44 18 2n·h (cycles) 1.2 0.48 1.76 0.54 0.02 4.0


berechnet sich der mittlere CPI-Wert 4.0 Zyklen a 2ns im Gegensatz zu 1 Zyklusa 8ns fur die single-cycle-Implementierung. cz.H. Angenommen, fadd dauere 8ns (wie fsub und float-Vergleiche) und fmul

dauere 16ns (wie fdiv). Welche mittlere Befehlsausfuhrungsdauer ergibt sich bei31% loads, 21% stores, 27% arithmetisch-logischen Operationen, 5% Verzweigun-gen, 2% Sprungen und 7% fadd, sub oder float Vergleiche sowie 7% fmul oderfdiv? Welcher Beschleunigungsfaktor ergibt sich? oEs ist also sinnvoll, Befehle in unterschiedlich vielen Schritten auszufuhren, diealle genau einen Zyklus dauern. Gleichzeitig kann ein und dieselbe Ressourcemehrfach genutzt werden, solange dies nur in verschiedenen Schritten passiert.

Die multi-cycle-Implementierung des MIPS-Prozessors verwendet eine einzigeSpeicher-Einheit statt den Speicher etwas kunstlich in Befehls- und Daten-Spei-cher zu unterteilen (Fig. 5.30).

PC

Memory

Address

Instruction or data

Data

Instruction register

Registers

Register #

Data

Register #

Register #

ALU

Memory data

register

A

B

ALUOut

F530.pdfCOD, p378

z.H. Welche Instruktionen verarbeitet der Prozessor, dessen Datenpfade Fig. 5.31darstellt?

Shift left 2

PC

Memory

MemData

Write data

M u x

0

1


Write data

Read data 1

Read data 2

Read register 1

Read register 2

M u x

0

1

M u x

0

1

4


Sign extend

3216




Instruction register

1 M u x

0

3

2

M u x

ALU result

ALUZero

Memory data

register


A

B

ALUOut

0

1

Address

97108/Patterson Figure 05.31

o

F531.pdfCOD, p380

Weil auf den Speicher zugegriffen wird, sowohl um Befehle zu holen als auch um


Daten zu transferieren, wird jetzt ein Befehlsregister, instruction register notwen-dig. Solche Register sind immer dann notig, wenn ein Wert in einemcycle geschrieben und in einem anderen gelesen wird oder wenn einSignal sich andern kann, bevor es geschrieben wurde. Die notwendigenSignale zeigt Fig. 5.32.


Shi

ft

left

2

Mem

toR

eg

IorD

Mem

Rea

dM

emW

rite

PC

Mem

ory

Mem

Dat

a

Write

da

ta

M

u x0 1

Reg

iste

rsW

rite

re

gist

er

Write

da

ta

Rea

d da

ta 1

Rea

d da

ta 2

Rea

d re

gist

er 1

Rea

d re

gist

er 2

Inst

ruct

ion

[15–1

1]

M

u x0 1

M

u x0 1

4

ALU

Op

ALU

Src

B

Reg

Dst

Reg

Write

Inst

ruct

ion

[15–0

]

Inst

ruct

ion

[5–0

]

Sig

n ex

tend

32

16

Inst

ruct

ion

[25–2

1]

Inst

ruct

ion

[20–1

6]

Inst

ruct

ion

[15–0

]

Inst

ruct

ion

regi

ster

1M

u x

0 32

ALU

co

ntro

l

M

u x0 1ALU

re

sult

ALU

ALU

Src

A

Zero

A B

ALU

Out

IRW

rite

Add

ress

Mem

ory

data

re

gist

er

F532.pdfCOD, p381

Aus eben diesem Grund wird auch das ALUOut-Register notwendig, das beispiels-weise den Wert des im zweiten Zyklus prophylaktisch berechneten Sprungzieles


vorhalt (Fig. 5.33).

Shi

ft

left

2

PC

M

u x0 1

Reg

iste

rsW

rite

re

gist

er

Write

da

ta

Rea

d da

ta 1

Rea

d da

ta 2

Rea

d re

gist

er 1

Rea

d re

gist

er 2

Inst

ruct

ion

[15–1

1]

M

u x0 1

M

u x0 1

4

Inst

ruct

ion

[15–0

]

Sig

n ex

tend

32

16

Inst

ruct

ion

[25–2

1]

Inst

ruct

ion

[20–1

6]

Inst

ruct

ion

[15–0

]

Inst

ruct

ion

regi

ster

ALU

co

ntro

l

ALU

re

sult

ALU

Zero

Mem

ory

data

re

gist

er

A B

IorD

Mem

Rea

d

Mem

Write

Mem

toR

eg

PC

Write

Con

d

PC

Write

IRW

rite

ALU

Op

ALU

Src

B

ALU

Src

A

Reg

Dst

PC

Sou

rce

Reg

Write

Con

trol

Out

puts

Op

[5–0

]

Inst

ruct

ion

[31-2

6]

Inst

ruct

ion

[5–0

]

M

u x

0 2

Jum

p ad

dres

s [3

1-0

]In

stru

ctio

n [2

5–0

]2

62

8S

hift

le

ft 2

PC

[3

1-2

8]

1

1M

u x

0 32

M

u x0 1ALU

Out

Mem

ory

Mem

Dat

a

Write

da

ta

Add

ress

F533.pdfCOD, p383

Zudem werden zwei zusatzliche Multiplexer (liefert der PC oder die ALU dieAdresse; ist der erste ALU-Operand der PC oder ein Register) und eine Erwei-


terung des Multiplexers fur den zweiten ALU-Operanden (zu den bisherigen al-ternativen inputs zweiter arithmetisch-logischer Operand und offset fur Speicher-Adressen zusatzlich die Konstante 4 und das offset bei Verzweigungen) notwendig.Dafur werden zwei Addierer, namlich fur das Inkrementieren des PC und fur dieBerechnung der Verzweigungsadresse eingespart (s. Fig. 5.33).Insgesamt ergibt sich also sogar eine Reduktion des hardware-Aufwandes.

Die zusatzlichen Multiplexer brauchen zusatzliche Steuer-Signale, dargestellt inFig. 5.34.

In den funf Schritten werden folgende Operationen in Abhangigkeit vom jeweili-gen Befehl ausgefuhrt (s. Fig. 5.35). Dabei ist imm=IR[15-0].

step R-Type load/store branch jump

IFIR = Mem[PC]

PC += 4

IDA = Reg[IR[25-21]]; B = Reg[IR[20-16]]

ALUOut = PC+(sign ext(imm)<<2)

EX/BEQ & J

completion

ALUOut

= A op B

ALUOut = A

+sign ext(imm);

if (A-B==0)

PC = ALUOut

PC = PC[31-28]

||(IR[25-0]<<2)

Mem/ADD & SW

completion

Reg[IR[15-11]]

= ALUOut

MDR = Mem[ALUOut]

or Mem[ALUOut] = B

WBReg[IR[20-16]]

= MDR

1. instruction fetch, IF:ladt den Befehl in das Instruction Register IR; inkrementiert den PC um 4.

2. instruction decode and register fetch, ID:ladt ‘prophylaktisch’ zwei Quell-Register Rs und Rt in die beiden Eingangs-latches A und B der ALU und berechnet ebenfalls ‘prophylaktisch’ die Ver-zweigungszieladresse (branch target) als Summe aus PC und offset.

3. execution, memory address computation or branch/jump completion, EX:Falls ein arithmetisch-logischer Befehl auszufuhren ist, fuhrt die ALU dieim Funktionscode spezifizierte Operation aus.Falls ein load/store-Befehl auszufuhren ist, berechnet die ALU die Spei-cher-Adresse als Summe von Quell-Register plus Offset (Displacement).Falls ein Verzweigungsbefehl (branch on equal) auszufuhren ist, berech-net die ALU die Verzweigungsbedingung. Der PC wird auf die im zweitenSchritt berechnete Verzweigungszieladresse gesetzt.Im Fall (unbedingter) Sprunge wird innerhalb von durch die obersten Bitsdes PC vorgegebenen ’Speicher-Banken’ gesprungen.

4. memory access or ALU operation completion, MEM:Bei Lade-Befehlen wird Memory[ALUOut] in MDR zur Verfugung gestellt. BeiSpeicher-Befehlen wird das Quell-Register B in Memory[ALUOut] kopiert.Bei arithmetisch-logischen Befehlen wird das ALU-Ergebnis ALUOut in dasZiel-Register geschrieben.


5. write back, WB:schreibt ausschließlich bei Lade-Befehlen das aus dem Speicher geladeneDatum MDR in das Ziel-Register.

Die multi-cycle-Implementation mit allen Steuer-Signalen, deren Bedeutung inFig. 5.34 zusammengestellt ist, wird in Fig. 5.33 und in Fig. 5.48 dargestellt.Fig. 5.48 deutet zusatzlich die Behandlung von Exceptions an.


Shi

ft

left

2

Mem

ory

Mem

Dat

a

Write

da

ta

M

u x0 1

Inst

ruct

ion

[15–1

1]

M

u x0 1

4

Inst

ruct

ion

[15–0

]

Sig

n ex

tend

32

16

Inst

ruct

ion

[25–2

1]

Inst

ruct

ion

[20–1

6]

Inst

ruct

ion

[15–0

]

Inst

ruct

ion

regi

ster

ALU

co

ntro

l

ALU

re

sult

ALU

Zero

Mem

ory

data

re

gist

er

A B

IorD

Mem

Rea

d

Mem

Write

Mem

toR

eg

PC

Write

Con

d

PC

Write

IRW

rite

Con

trol

Out

puts

Op

[5–0

]

Inst

ruct

ion

[31-2

6]

Inst

ruct

ion

[5–0

]

M

u x

0 2

Jum

p ad

dres

s [3

1-0

]In

stru

ctio

n [2

5–0

]2

628

Shi

ft

left

2

PC

[3

1-2

8]

1

Add

ress

EP

C

C

O 0

0 0

0 0

03

Cau

se

ALU

Op

ALU

Src

B

ALU

Src

A

Reg

Dst

PC

Sou

rce

Reg

Write

EPC

Write

IntC

ause

Cau

seW

rite

10

1M

u x

0 32

M

u x0 1

M

u x0 1

PC

M

u x

0 1

Reg

iste

rsW

rite

re

gist

er

Write

da

ta

Rea

d da

ta 1

Rea

d da

ta 2

Rea

d re

gist

er 1

Rea

d re

gist

er 2

ALU

Out

F548.pdfCOD, p414


4.4 Realisieren der Steuerung

Zur Modellierung der Steuerung verwendet man endliche Automaten (finite au-tomata). Ein solches Modell ist vorteilhaft, weil es den Entwurf der Steuerungunabhangig von der Implementierung macht.

Z.B. Ein Zigaretten-Automat hat die Zustande ‘bereit’, ‘Schubladen entriegelt’und ‘i-te Schublade geoffnet’ mit Eingaben ‘Geld einwerfen’, ‘Ruckgabe-Knopfdrcken’, ‘i-te Schublade ziehen’ und ‘Packung entnehmen und Schublade schlie-ßen’

��

bereit

?

Geld einwerfen

��

Schubladenentriegelt

-

Geldruck-gabeknopf

drucken

Geld-ruck-gabe

��

��

��

Schub-lade 1offen

Schub-lade 2offen

Schub-lade noffen

��

��

��

��+

��

��

��

SSSSSSw

gewunschte Schublade ziehen

· · ·

�

Packung entnehmen, Schublade schließen

sowie den Ausgaben ‘Packung aus der i-ten Schublade’ und ‘Ruck-Geld’. cDer endliche Automat in Fig. 5.42 modelliert die Steuerung des Prozessors fur dieAbarbeitung arithmetisch/logischer, Lade/Speicher-, Verzweigungs- und Sprung-Befehle. Jeder Zustand des Automaten entspricht genau einem clock cycle.


PCWrite PCSource = 10

ALUSrcA = 1 ALUSrcB = 00 ALUOp = 01 PCWriteCond

PCSource = 01

ALUSrcA =1 ALUSrcB = 00 ALUOp= 10

RegDst = 1 RegWrite

MemtoReg = 0

MemWrite IorD = 1

MemRead IorD = 1

ALUSrcA = 1 ALUSrcB = 10 ALUOp = 00

RegDst= 0 RegWrite

MemtoReg=1


MemRead ALUSrcA = 0

IorD = 0 IRWrite

ALUSrcB = 01 ALUOp = 00


Instruction fetchInstruction decode/

register fetch

Jump completion

Branch completionExecution

Memory address computation

Memory access

Memory access R-type completion

Write-back step

(Op = 'LW') or (Op = 'SW') (Op = R-type)

(Op

= 'B

EQ')

(Op

= 'J'

) (Op = 'SW

')

(Op

= 'LW

')

4

01

9862

753

Start

F542.pdfCOD, p396

Die als endlicher Automat (in Fig. 5.42 oder um die Behandlung von Ausnahmen(exceptions) erweitert in Fig. 5.50)


ALUSrcA = 1 ALUSrcB = 00 ALUOp = 01 PCWriteCond

PCSource = 01


RegDst = 1 RegWrite

MemtoReg = 0

MemWrite IorD = 1

MemRead IorD = 1


RegWrite MemtoReg = 1

RegDst = 0


MemRead ALUSrcA = 0

IorD = 0 IRWrite

ALUSrcB = 01 ALUOp = 00


Instruction fetchInstruction decode/

Register fetch

Jump completion

Branch completionExecution

Memory address computation

Memory access

Memory access R-type completion

Write-back step

(Op = 'LW') or (Op = 'SW') (Op = R-type)

(Op

= 'B

EQ')

(Op

= '

J')

(Op = 'SW')

(Op

= '

LW')

4

01

9862

7 11 1053

Start

(Op = other)

Overflow

Overflow


EPCWrite PCWrite

PCSource = 11

IntCause = 0 CauseWrite


EPCWrite PCWrite

PCSource = 11

IntCause = 1 CauseWrite


F550.pdfCOD, p416

modellierte Steuerung kann nun entweder festverdrahtet unter Verwendung vonROM’s oder PLA’s oder durch Mikro-Programmierung realisiert werden.

Dabei ist grundsatzlich zu bedenken, daß schon der MIPS R3000 Prozessor guthundert verschiedene Befehle abarbeitet:

arithmetisch/logische Befehle abs, add, and, div, mul, neg, nor, not, or, rem(remainder), ror (rotate), rol, sl (shift), sr, sub, xor mit Varianten wieimmediate, unsigned, with overflow sowie Befehlen zum Initialisieren vonRegistern mit Konstanten (load: immediate li oder upper immediate lui)oder mit dem Ergebnis von Vergleichen (set: seq, sne, sge, gt, le, slt undjeweils unsigned),

Verzweigungs- und Sprung-Befehle b, beq, bge, bgt, le, lt, bne, j, jal, jr mitVarianten wie zero, and link (Retten einer Rucksprung-Adresse), unsignedoder register,

Lade-/Speicher-Befehle mit Varianten wie address (la load computed address),byte, word, double-word oder unaligned,

Transport-Befehle move, mf (from), mt (to) mit Varianten hi, lo fur die beiden


Ergebnis-Register von Multiplikationen, Divisionen und Rest-Berechnungensowie Transport-Befehlen von/zu Coprozessor-Registern,

Gleitkomma-Zahlen-Befehle abs, add, c.eq, c.le, c.lt, cvt, div, l (load), mov,mul, neg, s (store), sub mit Varianten wie single oder double sowie

Ausnahme- und Unterbrechungsbefehle rfe (return from exception), break,syscall und nop.

Z.B. Es gibt VAX-Befehle mit mehr als 20 Adressierungsarten bei bis zu funf COD, p.425

Operanden, codiert in mehr als 300 op codes! cz.H. Gruppiere die Befehle der Intel 80X86-Prozessoren zusammen mit ihrenVarianten. o

4.4.1 festverdrahtete Steuerung

Eine naheliegende Realisierung der Steuerung, wie in Fig. 5.43 bzw. Fig. C.5dargestellt, besteht in der Verwendung eines ROM’s, das die Wahrheitstafeln furalle Steuer-Signale in Abhangigkeit vom Operationscode und dem Zustand derSteuerung enthalt.

Z.B. Jede Zeile der Wahrheitstafel entspricht der Spezifizierung der Signale unddes Folgezustandes, wie sie sich in jedem Zustand bei jeder Eingabe ergeben.Zustande sind mit 4 bit kodiert. Der OP-code hat 6 bits und es sind 17 Signalezu setzen. Somit hat die Wahrheitstafel 24+6 = 210 = 1024 Zeilen a 17 + 4 = 21bit und damit eine Große von 21 Kbit. cIm Beispiel hangen die Signale nur vom Zustand des endlichen Automaten ab.Aufbrechen der 21Kbit großen Wahrheitstafel in zwei Wahrheitstafeln – die einefur die Signale und die andere fur den Folgezustand – reduziert den Speicherauf-wand auf zusammen 24 · 17 + 24+6 · 4 = 272 + 4096 bit oder etwa 4.3 Kbit (s.Fig. C.11 und Fig. C.13).

Bei Einsatz eines PLA’s kann das ROM weiter reduziert werden zu Lasten ei-ner aufwendigeren Kodierung. Jeder Ausgang eines PLA’s ist dabei die logischeSumme gewisser Produkte, namlich der Min-Terme der Eingange. Fig. C.14 zeigteine PLA-Implementierung.


Op5

Op4

Op3

Op2

Op1

Op0

S3

S2

S1

S0

IorD

IRWrite

MemReadMemWrite

PCWritePCWriteCond

MemtoRegPCSource1

ALUOp1

ALUSrcB0ALUSrcARegWriteRegDstNS3NS2NS1NS0

ALUSrcB1ALUOp0

PCSource0

FC14.pdfCOD, pC-20

4.4.2 Steuerung per sequencer

Wenn die Zustande des endlichen Automaten so numeriert sind, daß meist un-abhangig vom OPcode der Folgezustand gerade der numerisch folgende Zustandist (wie es bei realen Steuerungen in uber 90% der Fall ist), lohnt der Einsatzeines sogenannten sequencers, der den Folgezustand aus OPcode und aktuellemZustand bestimmt, indem Steuerbits fur jeden Zustand angeben, ob der nachs-te Befehl geladen (0), ob zum numerisch folgenden Zustand ubergegangen (3)werden soll oder welche dispatch-Tabelle den Folgezustand in Abhangigkeit vomOPcode enthalt (s. Fig. C.15 und Fig. C.16).

State

Op

Adder

1

PLA or ROM

Mux3 2 1 0

Dispatch ROM 1Dispatch ROM 2

0

AddrCtl

Address select logic

Instruction register opcode field


FC16.pdfCOD, pC-24

Der Folgezustand braucht dann nur noch fur die wirklichen Verzweigungen imendlichen Automaten codiert zu werden.

4.4.3 Mikro-programmierte Steuerung

Die Idee von Maurice Wilkes Anfang der funfziger Jahre bestand darin, dieSteuereinheit als einen Miniatur-Computer zu realisieren (s. Fig. 5.47).

Microprogram counter

Address select logic

Adder

1

Input

Datapath control outputs

Microcode storage

Inputs from instruction register opcode field

Outputs

Sequencing control

F547.pdfCOD, p409

Def. Mikro-Befehle spezifizieren alle Steuersignale des Datenpfades.Mikro-Programmierung bedeutet, die Steuereinheit durch Programmierung, so-zusagen als Interpreter fur den Befehlssatz, zu realisieren.

Z.B. Die IBM /360 war die erste bedeutende Maschine mit Mikro-program-mierter Steuerung. Die verschiedenen Modelle der IBM /360 und der DEC VAX- CA Bild 5.8

CA p.187Rechner haben Mikro-Befehlslangen von 20-120 bit und Mikro-Programm-Spei-cher von 200-500 Kbit. cFig. 5.46 enthalt in symbolischer Form das Mikro-Programm fur den Beispiel-Prozessor MIPS R3000.

ALU Register PC write sequen-

label cntrl SRC1 SRC2 control Memory control cing

Fetch Add PC 4 read PC ALU seq

Add PC Extshft read dispatch1

Mem1 Add A Extend dispatch2

LW2 read ALU seq

write MDR to Rt fetch

SW2 write ALU fetch

R-Type1 func A B seq

write ALU to Rd fetch

BEQ1 Sub A B ALU-zero fetch

JUMP1 jumpaddr fetch


Dabei sind dispatch1 und dispatch2 zwei sogenannte dispatch tables, also ”be-rechnete goto’s”, d.h. ROM-Tabellen, aus denen in Abhangigkeit von (bestimm-ten bits des) OPcodes der Instruktionen die Nummer der anzuspringenden Mikro-programm-Zeile gelesen wird.

Ein Mikro-Code-Assembler kann dann auch bestimmte Konsistenz-Checks (Spei-cher und ALU durfen nicht ‘gleichzeitig’ ein Register schreiben!) durchfuhren.

Vorteile der Mikro-Programmierung sind: Anderungsfreundlichkeit, die Moglich-keit, andere Befehlssatze in Mikro-Code zu emulieren (z.B. Pentium), und leichte COD, Ch.5.7

Erweiterbarkeit um weitere (komplexe) Befehle, soweit Platz im Mikro-Code-Speicher vorhanden ist.

Z.B. Mikrocode-Implementierungen sind nicht generell schneller als der Makro-Code: der VAX-Index-Befehl (Test auf Zulassigkeit eines Feld-Indexes) ist als CA, S.239

Makro-Befehl schneller als die Mikrocode-Implementierung.Der 80x86-Befehl MOVS zum Kopieren von Strings mit repeat-Prefix ist haufig COD, p185,

p420langsamer als die entsprechende macro code Schleife. Dasselbe gilt fur den 80x86-Befehl LOOP. Also werden Compiler diesen Befehl auch nicht erzeugen, so daßman diesen Befehl auch zukunftig nicht schneller machen wird, weil er so seltengebraucht wird! cNachteilig ist die Abhangigkeit der Mikro-Programmierung von der Speicher-Technologie: schnellere Halbleiter-Speicher bei langsameren Kern-Speichern mach-ten Mikro-Programmierung sinnvoll. U.a. schnelle cache-Speicher verdrangtenMikro-Programmierung. Sollten etwa ROM’s wesentlich schneller werden als Re-gister oder cache-Speicher, konnte dies zu einer Ruckkehr zur Mikro-Program-mierung fuhren (so Hennessy & Patterson).

Vertikale Verlagerung (vertical migration) heißt, Operationen der konventionellenMaschinen-Sprache ins Mikroprogramm zu verlagern, so z.B. BS-Funktionen oderHLL-Konstrukte (durch entsprechende Compiler). Vertikale Verlagerung lieferteinen zusatzlichen Sicherheitsgewinn (capabilities). Der Intel iAPX432 Prozessor Giloi,

S.133-140von 1981 hardware-maßig den Zugriff auf Speicher-Objekte mit software-maßigrealisierter Capability-Adressierung.

Die Erfahrung zeigt jedoch, daß die RISC-Prinzipien (’definitionsgemaß’ ohneMikro-Programmierung) großere Leistungssteigerungen erlauben.


5 pipelining

Parallelverarbeitung kann in verschiedener Weise zur Leistungssteigerung ein-gesetzt werden: etwa durch einen von der CPU unabhangig operierenden I/O-Prozessor, durch gleichzeitigen Zugriff auf multiported memory oder auf meh-rere Speicher-Banke, durch gleichzeitige Befehlsdekodierung und/oder Befehls-ausfuhrung in einer pipeline, durch gleichzeitige Ausfuhrung von Befehlen in meh-reren funktionalen Einheiten oder durch gleichzeitige Daten-Ubertragung ubermehrere Bus-Systeme.

pipelining: schneller durch Fließband- statt durch serielle Bearbeitung!

Z.B. Montage am Fließband: das Produkt (Ford Model T) durchlauft viele spe-zialisierte Montage-Inseln und wird so stuckweise zusammengesetzt. cZ.B. Skript zusammenlegen: dargestellt entweder orientiert am Material (Sta-pel von Script-Blattern; dabei steht i fur den Stapel der Blatter Nr. i und A furSchuler A)

Stapel 1 1 an A 1 an B 1 an C . . . 1 an ZStapel 2 2 an A 2 an B 2 an C . . . 2 an Z

.... . . . . .

Stapel n n an A n an B n an C . . . n an Z

oder orientiert an den Verarbeitungseinheiten (Lehrer und Schuler)

Lehrer 1 an A 2 an A 3 an A . . . n an ASchuler A 1 an B 2 an B 3 an B . . . n an B

.... . . . . .

Schuler Y 1 an Z 2 an Z 3 an Z . . . n an Z

Der serielle Aufwand ist also proportional zu Skript-Umfang × Schulerzahl, alsobei einem Script mit 15 Blattern und bei 40 Schulern 600 ZE.Der pipeline-Aufwand ist proportional zu Script-Umfang+(Schulerzahl−1), alsohier 15 + 39 = 54 ZE. cBem. Eine Aufgabe lasse sich in s Teilaufgaben der Lange Ts ZE zerlegen. Dieserielle Durchfuhrung von n dieser Berechnungen dauert dann n · s · Ts ZE, dieDurchfuhrung in einer s-stufigen pipeline nur s ·Ts+(n−1) ·Ts ZE. Damit ergibtsich ein Beschleunigungsfaktor von n sTs

(s+n−1)Ts= n s

s+n−1= s

1+ s−1n

≈ s fur genugend

große n. ◦Def. Eine s-stufige pipeline ist eine Reihe von s spezialisierten HW-Einrich-tungen, Stufen, die durch einen gemeinsamen Takt gesteuert werden und diedurch schnelle (Schiebe-) Register fur die Zwischenergebnisse verbunden sind.Die Stufen heißen auch Segmente.s ·Ts heißt Durchflußzeit oder Durchlaufzeit, also die Zeit von der Eingabe in die s.a. B&H,

Fig 6.2,p.288

anfangs leere pipeline bis zum ersten Ergebnis; die volle pipeline produziert alleTs Zeiteinheiten ein Ergebnis.


Man unterscheidet monofunktionale und multifunktionale pipelines, arithmetischepipelines (z.B. bei Vektor-Rechnern) und Befehls-pipelines (vor allem bei RISC-Rechnern).

DLX und MIPS R2000 sind Beispiele von klassischen RISC-Prozessoren mitBefehls-pipelines (Fig. 6.3).

Instruction fetch

Reg ALUData

accessReg

8 nsInstruction

fetchReg ALU

Data access

Reg

8 nsInstruction

fetch

8 ns

Time

lw $1, 100($0)

lw $2, 200($0)

lw $3, 300($0)

2 4 6 8 10 12 14 16 18

2 4 6 8 10 12 14

...

Program execution order (in instructions)

Instruction fetch

Reg ALUData

accessReg

Time

lw $1, 100($0)

lw $2, 200($0)

lw $3, 300($0)

2 nsInstruction

fetchReg ALU

Data access

Reg

2 nsInstruction

fetchReg ALU

Data access

Reg

2 ns 2 ns 2 ns 2 ns 2 ns


F603.pdfCOD, p439

Z.B. Befehls-pipelines: CDC 6600 mit zwei Stufen; SPARC und picoJava Imit vier Stufen; DLX, MIPS R2000/R3000 und Intel 80486 mit funf Stufen;picoJava II mit sechs Stufen; DEC Alpha oder DEC 21064 mit sieben Stufen; Liebig/Flik,

S.402SPARC IIIcu mit 14 pipeline Stufen; Intel Pentium mit zwei Befehlspipelinesmit je sechs Stufen (PF, IF, D1, D2, EX, WB), mit einer zusatzlichen floatpipeline mit drei/sechs Stufen (FR, FE, FM1, FM2, FM3, FW), zwei MMXpipelines mit drei Stufen (RW read, MEX, MWB) und mit einer drei-stufigenMMX-Multiplikationspipeline; Intel Pentium 4E mit 32 pipeline Stufen . . . c c’t 4/2004,

S.266Z.B. Fur den MIPS R3000-Prozessor ergibt sich bei folgenden Ausfuhrungszeiten

Befehl Instruction Register ALU Data Register Total(ns) fetch read Operation memory write (ns)load 10 5 10 10 5 40store 10 5 10 10 35arith. 10 5 10 5 30branch 10 5 10 25

und einer 5-stufigen pipeline eine Durchflußzeit von 5 · 10 = 50ns. Die pipelinearbeitet allerdings alle 10ns einen Befehl ab. Bei n load-Befehlen ergibt dies einenBeschleunigungsfaktor von β = n·40

50+(n−1)·10= 1

40+10n40n

= 11n

+ 14

, also fur große n eine


Beschleunigung naherungsweise um den Faktor 4 (Verschnitt). cz.H. Berechne den Beschleunigungsfaktor bei einer der bekannten Befehlsvertei-lungen. oBem. Diese Berechnungen unterstellen, daß die pipeline idealerweise immergefullt ist – jede Stufe hat immer etwas zu tun. Gerade diese Annahme ist i.a.R.aufgrund von sogenannten hazards nicht erfullt. Man unterscheidet Struktur-,Daten- und Steuer-Hazards (s.u.). ◦

5.1 Daten-Pfad einer pipelineCOD, Ch.6

Die hardware der MIPS R3000-pipeline ist in Fig. 6.10,

Instruction memory

Address

4

32

0

Add Add result

Shift left 2

Instruction

M u x

0

1

Add

PC

0Write data

M u x

1Registers

Read data 1

Read data 2

Read register 1

Read register 2

16Sign

extend

Write register

Write data

Read dataAddress

Data memory

1

ALU result

M u x

ALUZero

IF: Instruction fetch ID: Instruction decode/ register file read

EX: Execute/ address calculation

MEM: Memory access WB: Write back

F610.pdfCOD, p450

ihre Arbeitsweise in Fig. 6.11 dargestellt.


IM Reg DM RegALU

IM Reg DM RegALU

CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7

Time (in clock cycles)

lw $2, 200($0)

lw $3, 300($0)


lw $1, 100($0) IM Reg DM RegALU

F611.pdfCOD, p451

Die funf pipeline-Stufen IF, ID, EX, MEM und WB entsprechen genau den funfSchritten der multi-cycle-Implementierung des Prozessors. Zwischen den Stufensind pipeline-Register, also IF/ID-, ID/EX-, EX/MEM- und MEM/WB-Registeranzuordnen, um die Zwischenergebnisse zu speichern (Fig. 6.12).

Instruction memory

Address

4

32

0

Add Add result

Shift left 2

Inst

ruct

ion

IF/ID EX/MEM MEM/WB

M u x

0

1

Add

PC

0Write data

M u x

1Registers

Read data 1

Read data 2

Read register 1

Read register 2

16Sign

extend

Write register

Write data

Read data

1

ALU result

M u x

ALUZero

ID/EX

Data memory

Address


F612.pdfCOD, p452

z.H. Wieso sind neben der ALU jetzt wieder zwei zusatzliche Adder notwendig?(structure hazard21) oz.H. Vollziehe die pipeline-Bearbeitung von Befehlen der vier Typen nach. oz.H. Worin besteht in Fig. 6.18 die Korrektur des pipeline-Entwurfes?

21Wagnis, Gefahr fur die korrekte Programmausfuhrung


Instruction memory

Address

4

32

0

Add Add result

Shift left 2

Inst

ruct

ion

IF/ID EX/MEM MEM/WB

M u x

0

1

Add

PC

0

Address

Write data

M u x

1Registers

Read data 1

Read data 2

Read register 1

Read register 2

16Sign

extend

Write register

Write data

Read data

Data memory

1

ALU result

M u x

ALUZero

ID/EX

F618.pdfCOD, p460

oz.H. Verifiziere Entsprechungen in den beiden Darstellungen der multiple clockcycle Implementierung (Fig. 5.17) und der pipelining Implementierung (Fig. 6.10).

o

5.2 Steuerung einer pipeline

PC und pipeline-Register brauchen keine eigenen write-Signale, da sie in jedemclock-Zyklus geschrieben werden.In IF- und ID-Stufe werden in jedem clock-Zyklus Befehle geholt und dekodiert,so daß keine weitere Steuerung notwendig ist.In der EX-Stufe sind die RegDst-, ALUop- und ALUsrc-Signale, in der MEM-Stufedie branch-, MemRead- und MemWrite-Signale und in der WB-Stufe schließlichsind die MemToReg- und RegWrite-Signale zu setzen. Die Bedeutung der Signalehat sich nicht geandert (vgl. Prozessor mit Signalen in Fig. 6.25 sowie Bedeutungder Signale in Fig. 6.27 und Fig. 6.28).

z.H. Welche Instruktionen kann der Prozessor abarbeiten, dessen DatenpfadFig. 6.25 zeigt?


PC

Instruction memory

Address

Inst

ruct

ion


MemtoReg

ALUOp

Branch

RegDst

ALUSrc

4


0

0Registers

Write register

Write data

Read data 1

Read data 2

Read register 1

Read register 2

Sign extend

M u x1

Write

data

Read

data M u x

1

ALU control

RegWrite

MemRead


6

IF/ID ID/EX EX/MEM MEM/WB

MemWrite

Address

Data memory

PCSrc

Zero

AddAdd

result

Shift left 2

ALU result

ALU

Zero

Add

0

1

M u x

0

1

M u x

F625.pdfCOD, p467

oDa ein und derselbe Befehl nacheinander in jeder pipeline-Stufe bearbeitet wird,mussen die Steuer-Informationen wie die Zwischenergebnisse durchgereicht wer-den. Das Schema zeigt Fig. 6.29.

Control

EX

M

WB

M

WB

WB

IF/ID ID/EX EX/MEM MEM/WB

Instruction

F629.pdfCOD, p469

Die pipeline-Register ID/EX, EX/MEM und MEM/WB sind entsprechend zuerweitern. Der Prozessor mit Steuerung ist in Fig. 6.30 dargestellt.


PC

Instruction memory

Inst

ruct

ion

Add


Mem

toR

eg

ALUOp

Branch

RegDst

ALUSrc

4


0

0

M u x

0

1

Add Add result


Write data

Read data 1

Read data 2

Read register 1

Read register 2

Sign extend

M u x1

ALU result

Zero

Write data

Read data

M u x

1

ALU control

Shift left 2

Reg

Write

MemRead

Control

ALU


6

EX

M

WB

M

WB

WBIF/ID

PCSrc

ID/EX

EX/MEM

MEM/WB

M u x

0

1

Mem

Write

AddressData

memory

Address

F630.pdfCOD, p470

5.3 Daten-Hazards

Daten-Abhangigkeiten konnen Daten-Hazards22 entstehen lassen.

Z.B. Fig. 6.36 zeigt, welche Gefahren bei der Abarbeitung Daten-abhangigerBefehle in einer pipeline lauern.

sub $2, $1, $3 sub $2, $1, $3

and $12, $2, $5 nop

or $13, $6, $2 nop

add $14, $2, $2 nop

sw $15,100($2) and $12, $2, $5

or $13, $6, $2

add $14, $2, $2

sw $15,100($2)

22Wagnis, Gefahr fur die korrekte Programmausfuhrung


IM Reg

IM Reg

CC 1 CC 2 CC 3 CC 4 CC 5 CC 6


sub $2, $1, $3


and $12, $2, $5

IM Reg DM Reg

IM DM Reg

IM DM Reg

CC 7 CC 8 CC 9

10 10 10 10 10/–20 –20 –20 –20 –20

or $13, $6, $2

add $14, $2, $2

sw $15, 100($2)

Value of register $2:

DM Reg

Reg

Reg

Reg

DM

F636.pdfCOD, p477

Das Ergebnis des sub-Befehls mußte fur den folgenden and-Befehl in $2 zurVerfugung stehen, bevor es vom sub-Befehl in $2 geschrieben wird. cz.H. Untersuche (Unter-) Programme wie String- oder Listen-Operationen, Ska-larprodukt oder LGS auf mogliche Daten-Abhangigkeiten. oEs gibt grundsatzlich drei Moglichkeiten, Daten-Hazards zu beseitigen:

1. der Compiler fugt in den Code nops ein,

2. die pipeline-Steuerung fugt stalls in die pipeline ein, d.h. bestimmte Stufender pipeline haben vorubergehend keine Wirkung, oder

3. die pipeline stellt Zwischenergebnisse durch Weiterleiten (forwarding, by-passing oder short circuiting) bereit.

Der Compiler kann Daten-Hazards (z.B. Aufsummieren von Feld-Elementen ineinem Register) erkennen und beseitigen – entweder durch Einfugen von nop

oder durch (zulassiges) Vertauschen Daten-abhangiger Befehle, so daß Ergebnisseimmer schon in Registern vorliegen, wenn sie gebraucht werden.

Ein Daten-Hazard liegt vor, wenn ein Befehl in seiner ID-Stufe ein Register liest,das ein vorhergehender Befehl in seiner WB-Stufe schreiben wird:

zu lesendes Register=zu schreibendes Register Typ

IF/ID.ReadRegister1=ID/EX.WriteRegister 1a oder EXIF/ID.ReadRegister2=ID/EX.WriteRegister 1b oder EXIF/ID.ReadRegister1=EX/MEM.WriteRegister 2a oder MEMIF/ID.ReadRegister2=EX/MEM.WriteRegister 2b oder MEMIF/ID.ReadRegister1=MEM/WB.WriteRegister 3a oder WBIF/ID.ReadRegister2=MEM/WB.WriteRegister 3b oder WB


z.H. Diese Spezifikation von Daten-Hazards ist konservativ, da bestimmte Befeh-le uberhaupt nicht in Register schreiben (z.B. beq). Berucksichtigen der SignaleRegWrite und RegDst kann die Hazard-Erkennung verbessern. oWenn ein Daten-Hazard erkannt wurde, ist die Ausfuhrung des Befehls solangeaufzuhalten, bis das zu lesende Register geschrieben wurde. Dem Einfugen vonnops entspricht das Einfugen von bubbles in die pipeline. bubbles sind Stufen, dienichts bewirken. Dazu wird der aktuelle Befehl immer wieder geholt, indem derPC nicht aktualisiert und das IF/ID-pipeline-Register beibehalten wird. Zudemwerden die Steuer-Signale im ID/EX-Register deaktiviert, so daß in den EX-,MEM- und WB-Stufen nichts geschrieben werden kann: diese Stufen bewirkenalso nichts. Fig. 6.45 zeigt dies am Beispiel. 1.Aufl.

Fig. 6.33Die Hazard-Erkennungseinheit (hazard detection unit, HDU ) in der ID-Stufe fugtstalls in die pipeline ein, wenn einer der drei Typen von Hazards vorliegt:

EX-Hazard (der letzte Befehl – load oder arith./log (s. RegDst in Fig. 6.47-49) – wird inein Ziel-Register schreiben, das Quell-Register des aktuellen Befehls ist. ) falls

ID/EX.RegWrite and

((ID/EX.RegDst=0 and IF/ID.ReadRegister1=ID/EX.WriteRegisterRt) or

(ID/EX.RegDst=1 and IF/ID.ReadRegister1=ID/EX.WriteRegisterRd) or

(ID/EX.RegDst=0 and IF/ID.ReadRegister2=ID/EX.WriteRegisterRt) or

(ID/EX.RegDst=1 and IF/ID.ReadRegister2=ID/EX.WriteRegisterRd))

MEM-Hazard (der vorletzte Befehl wird in ein Ziel-Register schreiben, das Quell-Registerdes aktuellen Befehls ist. ) falls

EX/MEM.RegWrite and

(IF/ID.ReadRegister1=EX/MEM.WriteRegister or

IF/ID.ReadRegister2=EX/MEM.WriteRegister)

WB-Hazard (der vorvorletzte Befehl schreibt in ein Ziel-Register, das Quell-Register desaktuellen Befehls ist. ) falls

MEM/WB.RegWrite and

(IF/ID.ReadRegister1=MEM/WB.WriteRegister or

IF/ID.ReadRegister2=MEM/WB.WriteRegister)

Bem. WB-Hazards verschwinden, wenn – wie meist gegeben – ein Registerimmer fruh geschrieben und spat ausgelesen wird, so daß ein und dasselbe Registerin einem clock-Zyklus sowohl geschrieben als auch – aktualisiert – ausgelesenwerden kann. ◦In der HDU ist genau diese Logik implementiert (s. Fig. 6.47-49). 1.Aufl.

Fig. 6.34Schließlich macht forwarding, bypassing oder auch short circuiting Gebrauch da-von, daß bestimmte Ergebnisse schon in pipeline-Registern vorliegen.Wenn also nur eine Weiterleit-Einheit (forwarding unit, FU ) in der EX-Stufe dierichtigen Werte aus den pipeline-Registern zur Verfugung stellt, konnen arith-metische oder logische Befehle ohne stalls abgearbeitet werden. Fig. 6.37 zeigt,wie Ergebnisse in pipeline-Registern nachfolgenden Stufen zur Verfugung gestelltwerden.


IM Reg

IM Reg

CC 1 CC 2 CC 3 CC 4 CC 5 CC 6


sub $2, $1, $3


and $12, $2, $5

IM Reg DM Reg

IM DM Reg

IM DM Reg

CC 7 CC 8 CC 9

10 10 10 10 10/–20 –20 –20 –20 –20

or $13, $6, $2

add $14, $2, $2

sw $15, 100($2)

Value of register $2 :

DM Reg

Reg

Reg

Reg

X X X –20 X X X X XValue of EX/MEM :X X X X –20 X X X XValue of MEM/WB :

DM

F637.pdfCOD, p481

Fig. 6.38 zeigt den grundsatzlichen Aufbau einer FU.

Registers

M u x M

u x

ALU

ID/EX MEM/WB

Data memory

M u x

Forwarding unit

EX/MEM

b. With forwarding

ForwardB

RdEX/MEM.RegisterRd

MEM/WB.RegisterRd

RtRtRs

ForwardA

M u x

ALU

ID/EX MEM/WB

Data memory

EX/MEM

a. No forwarding

Registers

M u x

F638.pdfCOD, p482

z.H. Wie sind die Steuersignale fur den erweiterten Multiplexor in Fig. 6.40 zusetzen?


PCInstruction

memory

Registers

M u x

M u x

Control

ALU

EX

M

WB

M

WB

WB

ID/EX

EX/MEM

MEM/WB

Data memory

M u x

Forwarding unit

IF/ID

Inst

ruct

ion

M u x

RdEX/MEM.RegisterRd

MEM/WB.RegisterRd

Rt

Rt

Rs

IF/ID.RegisterRd

IF/ID.RegisterRt

IF/ID.RegisterRt

IF/ID.RegisterRs

o

F640.pdfCOD, p484

EX-Hazard: (der letzte Befehl wird in ein Ziel-Register schreiben, das Quell-Register des aktuellen Befehls ist.)

if (EX/MEM.RegWrite and

ID/EX.ReadRegister1==EX/MEM.WriteRegister) ALUSelA := 2 = 10(2)

if (EX/MEM.RegWrite and

ID/EX.ReadRegister2==EX/MEM.WriteRegister) ALUSelB := 1 = 01(2)

MEM-Hazard: (der vorletzte Befehl wird in ein Ziel-Register schreiben, das Quell-Register des aktuellen Befehls ist)

if (MEM/WB.RegWrite and

ID/EX.ReadRegister1 6=EX/MEM.WriteRegisterRt and

ID/EX.ReadRegister1==MEM/WB.WriteRegister) ALUSelA := 1 = 01(2)

if (MEM/WB.RegWrite and

ID/EX.ReadRegister2 6=EX/MEM.WriteRegisterRt and

ID/EX.ReadRegister2==MEM/WB.WriteRegister) ALUSelB := 2 = 10(2)

EX-Hazards sind so gegenuber MEM-Hazards priorisiert!Vgl. z.B. sum+=a[i], wo die a[i] in Registern vorliegen: mit sum in R4 unda[1] in R1, a[2] in R2, a[3] in R3 also etwa add R4,R4,R1; add R4,R4,R2;

add R4,R4,R3;

Wenn Register in einem clock-Zyklus sowohl geschrieben als auch gelesen werdenkonnen, entfallen WB-Hazards. Fig. 6.46 zeigt die pipeline mit Steuerung, hazarddetection unit und forwarding unit.

Z.B. Der Beschleunigungsfaktor β aufgrund forwarding errechnet sich aus demQuotienten von Ausfuhrungszeit Tohne eines Programms ohne forwarding durchAusfuhrungszeit Tmit mit forwarding. Sei n die Anzahl der Instruktionen einesProgramms, α der Anteil von Instruktionen mit Daten-Abhangigkeiten und Tcdie Ausfuhrungszeit einer pipline-Stufe. Wenn im Mittel zwei stalls einzufugensind, um data hazards aufzulosen, und forwarding alle data hazards beseitigt,gilt β =

TohneTmit

= n (1−α)Tc+nα 3TcnTc

= 1 + 2α. c

Falls auf einen load-Befehl ein arithmetisch/logischer Befehl folgt, dessen eines


Quellregister das Ziel-Register des load-Befehls ist, hilft nur ein sogenanntes loadstall der pipeline. Die modifizierte Version der HDU ist spezifiziert durch

if (ID/EX.RegWrite and ID/EX.RegDst=0 and (vorangehendes load)

(IF/ID.ReadRegister1=ID/EX.WriteRegisterRt or

IF/ID.ReadRegister2=ID/EX.WriteRegisterRt)) stall

Die aufgrund solcher Daten-Abhangigkeiten unumganglichen stalls heißen loadstalls. Fig. 6.46 zeigt die pipeline mit Steuerung, hazard detection unit und for-warding unit.

PCInstruction

memory

Registers

M u x

M u x

M u x

Control

ALU

EX

M

WB

M

WB

WB

ID/EX

EX/MEM

MEM/WB

Data memory

M u x

Hazard detection

unit

Forwarding unit

0

M u x

IF/ID

Inst

ruct

ion

ID/EX.MemRead

IF/I

DW

rite

PC

Write

ID/EX.RegisterRt

IF/ID.RegisterRd

IF/ID.RegisterRt

IF/ID.RegisterRt

IF/ID.RegisterRs

RtRs

Rd

Rt EX/MEM.RegisterRd

MEM/WB.RegisterRd

F646.pdfCOD, p492

z.H. Berechne die Beschleunigung durch forwarding bei einem Anteil α vonInstruktionen mit Daten-Abhangigkeiten. Unter diesen Instruktionen sei λ derAnteil von loads. o

5.4 Steuer-Hazards

Def. Bedingte Verzweigungen und unbedingte Sprunge stellen sogenannte Steu-er-Hazards (branch- oder control-hazard) dar: die Verzweigungsbedingung liegterst am Ende der EX-Stufe vor, der neue PC erst in der MEM-Stufe (s. Fig. 6.50).


Reg

Reg

CC 1


40 beq $1, $3, 7


IM Reg

IM DM

IM DM

IM DM

DM

DM Reg

Reg Reg

Reg

Reg

RegIM

44 and $12, $2, $5

48 or $13, $6, $2

52 add $14, $2, $2

72 lw $4, 50($7)

CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9

RegF650.pdfCOD, p497

Diese Verzogerung heißt branch delay, die pipeline-Stufen wahrend des branchdelay heißen auch branch delay slots23.

Z.B. Der Prozessor MIPS R3000 hat ein branch delay von 3 clock-Zyklen (s.Fig. 6.50). cWieder gibt es verschiedene Moglichkeiten, Steuer-Hazards (Fig. 6.50) zu besei-tigen:

1. der Compiler kann die branch delay slots mit nop oder durch (zulassi-ges) Vertauschen von Befehlen mit sinnvollen Anweisungen fullen, falls diepipeline-Steuerung dies unterstutzt;

2. die pipeline-Steuerung fugt nach Verzweigungsbefehlen grundsatzlich stallsein; oder 1.Aufl. (vgl.

Fig. 6.51)3. die pipeline kann unter der Annahme, daß die Verzweigung nicht ausgefuhrt

wird, (branch not taken) ‘ungeruhrt’ weiterarbeiten. Die pipeline-Steuerungannulliert dann die sich im Nachhinein als unzutreffend herausstellendenBefehle in den branch delay slots, wenn doch verzweigt wird.

Z.B. Die derartige Abarbeitung einer nicht ausgefuhrten Verzweigung dauert inder MIPS R3000 pipeline einen clock-Zyklus, die einer ausgefuhrten Verzweigungdagegen vier clock-Zyklen. cz.H. Berechne den Beschleunigungsfaktor β durch die Sprungvorhersage ‘branchnot taken’ bei einem Anteil α von Verzweigungen. λ sei der Anteil der Fallezutreffender Sprungvorhersagen. oz.H. Wie muß die pipeline-Steuerung delayed branches unterstutzten? o

23Analog gibt es load delays und load delay slots, wenn das Speicher-System mit dem Prozessornicht Schritt halten kann.


z.H. Fur welche Sorte bedingter Verzweigungen ist die Annahme ‘branch nottaken’ angemessen und fur welche eher nicht? Abhilfen? oz.H. Wie bestimmt sich die branch penalty, also die durchschnittliche Anzahlvon clock-Zyklen zur Ausfuhrung einer bedingten Verzweigung? oJe nachdem, in welcher Stufe die Verzweigungsbedingung ausgewertet wird, mußdie pipeline-Steuerung ein bis drei zusatzliche(s) Signal(e) IF.Flush, ID.Flush undEX.Flush erzeugen, um die Befehle in den branch delay slots zu annullieren, fallsdie Verzweigung ausgefuhrt wird. Fig. 6.51 zeigt die notwendigen Erganzungen.

PCInstruction

memory

4

Registers

M u x

M u x

M u x

ALU

EX

M

WB

M

WB

WB

ID/EX

0

EX/MEM

MEM/WB

Data memory

M u x

Hazard detection

unit

Forwarding unit

IF.Flush

IF/ID

Sign extend

Control

M u x

=

Shift left 2

M u x

F651.pdfCOD, p499

z.H. Wie wird in Fig. 6.51 die Verzweigungsbedingung ausgewertet? WievieleBefehle mussen annuliert werden, falls die Verzeigung ausgefuhrt wird? oZ.B. Die offene SPARC-Architektur ist gekennzeichnet durch einheitliche Be-fehlslange von 32bit, load/store-Architektur, uberlappende Register-Fenster undeine vier-stufige Befehls-Pipeline (1. fetch, 2. decode & compute addresses & getoperands, 3. execute und 4. store), die Verzweigungsbefehle unter der Annahme‘branch taken’ mit delayed control transfer abarbeitet:

Sprungziel bekannt

Sprungbedingung bekannt

Sprungbefehl i load decode execute storedelay slot i+1 load decode execute storeSprungziel load decode execute storeif T Sprungziel+1 else i+2 load decode executeif T Sprungziel+2 else i+3 load decode

load


d.h. nach jedem Sprungbefehl wird ein delay slot eingefugt, zunachst der Sprungdurchgefuhrt und – falls sich im nachsten Schritt die Sprungvorhersage als falscherweist – die Instruktion im delay slot annulliert, d.h. in der store-Stufe nichtsgeschrieben. Giloi, S.92

Wenn der Compiler gunstigenfalls den delay slot mit einer nutzlichen Operationunabhangig von der Sprungbedingung fullen kann, setzt er das Annullierungs-bit auf 0, so daß auch bei falscher Sprungvorhersage die Anweisung im delayslot normal abgearbeitet wird; wenn die Operation aber von der Sprungbedin-gung abhangt, so bewirkt das auf 1 gesetzte Annullierungsbit, daß bei falscherSprungvorhersage auch die Anweisung im delay slot annulliert wird. cEs gibt bessere Methoden, Steuer-Hazards zu begegnen. Man unterscheidet stati- COD, ch.6.6

CA, S.307ffGiloi, S.153ff

sche (zur Compile-Zeit) und dynamische Vorhersagen (zur Lauf-Zeit) des Sprung-verhaltens (branch prediction). Verbesserungen bestehen sowohl in einer verbes-serten Vorhersage (branch prediction), ob verzweigt wird, (z.B. durch Speichern,ob diese Verzweigung beim letzten Mal ausgefuhrt wurde, im branch predictionbuffer) als auch in einer verbesserten Vorhersage, wohin gesprungen wird, (z.B.durch Speichern der Sprungziele im branch target buffer).

Taken

Taken

Taken

Taken

Not taken

Not taken

Not taken

Not taken

Predict taken Predict taken

Predict not taken Predict not taken


F653.pdfCOD, p502

Auch Compiler konnen Steuer-Hazards reduzieren, etwa durch loop unrolling/un-folding : ausgefuhrte Befehle und branch delays werden zu Lasten langeren Codeseingespart.Fig. 6.54 zeigt, wie der Compiler branch delay slots fullen kann:


a. From before b. From target c. From fall through

sub $t4, $t5, $t6 … add $s1, $s2, $s3 if $s1 = 0 then

add $s1, $s2, $s3 if $s1 = 0 then

add $s1, $s2, $s3 if $s1 = 0 then sub $t4, $t5, $t6

add $s1, $s2, $s3 if $s1 = 0 then sub $t4, $t5, $t6

add $s1, $s2, $s3 if $s2 = 0 then

BecomesBecomesBecomes

Delay slot

Delay slot

Delay slot

sub $t4, $t5, $t6

if $s2 = 0 then add $s1, $s2, $s3

F654.pdfCOD, p503


5.5 arithmetische pipelines

pipelining kann auch die Abarbeitung arithmetischer Operationen beschleunigen:

Z.B. Die Multiplikation einer 8-bit mit einer 4-bit unsigned integer kann kon- B&H,p.291/292ventionell mit drei Addierern und vier Bus-gates (Fig. 6.3)multiplicand multiplier

@@�� @

@@

8bit adder

@@�� @

@@

8bit adder

@@�� @

@@

8bit adder

bus gate????????

bus gate????????

bus gate????????

????????

????????

????????

????????

????????

???????? ?

bus gate

???????? 0

????????�

�

�

�

???︸︷︷︸12 bit product

und ‘pipelined’ nur mit zusatzlichen latches (Fig. 6.4) durchgefuhrt werden.


multiplicand

????????

multiplier

????input latches

????????1st/2nd stage latches

????????2nd/3rd stage latches

@@�� @

@@

8bit adder

@@�� @

@@

8bit adder

@@�� @

@@

8bit adder

bus gate????????

bus gate????????

bus gate????????

????????

????????

????????

????????

????????

????????

????????

???????? ?

bus gate

???????? 0

????????�

�

??

�

?

�

??

???

???output latch 12 bit product

Implementierungen der Multiplikation von ’breiteren’ Faktoren liegen auf derHand. cz.H. Welche Vorteile/Nachteile ergeben sich zu welchen Kosten? oDef. Die Auflosung einer Operation in pipeline-Stufen heißt Granularitat.

Z.B. Multiplikation durch Partitionieren des Multiplikators, uberlappende Mul- B&HFig.6.5,p.293

tiplikation der Teile mit dem Multiplikanden und Summation der gewichtetenResultate, also etwa x · 123.456.789 = (x · 123)106 + (x · 456)103 + x · 789, liefertMultiplikations-pipelines unterschiedlicher Granularitat. cDef. Die Menge der verschiedenen Funktionen, die eine multifunktionale pipelineausfuhren kann, bestimmt die Variabilitat einer pipeline.

Z.B. Der Texas Instruments Advanced Scientific Computer (TI ASC) verfugt B&HFig.6.6,p.294Giloi S.84

uber eine dynamisch zu konfigurierende pipeline zur Abarbeitung arithmetischerOperationen: etwa fur Gleitkomma-Zahlen-Addition, Festkomma-Zahlen-Multi-plikation und deren Skalar-Produkt-Bildung werden Stufen zum Register-Lesen,Normalisieren oder Denormalisieren, Additieren oder zum Bilden des Skalar-Produktes gemeinsam genutzt. c


5.6 Superskalares Pipelining

Def. Superskalare Prozessoren sind gekennzeichnet durch mehrere funktionaleEinheiten, die gleichzeitig und unabhangig den Befehlsstrom unter Berucksich-tigung von Datenabhangigkeiten abarbeiten. Befehle und Daten werden einemBefehls- bzw. Daten-cache entnommen. Der Compiler sorgt fur optimale Aus-nutzung der funktionalen Einheiten (FUs), spezielle HW (scoreboard) fur dieSynchronisation der FUs. Die Befehlsausfuhrung erfolgt durch eine pipeline.Die Programm-Parallelitat auf Anweisungsebene wird in Parallelarbeit von funk-tionalen Einheiten umgesetzt.

Z.B. Eine superskalare Version des MIPS Prozessors entsteht durch Verdop-pelung der Befehlspipeline: die ’obere’ pipeline fuhrt arithmetisch/logische Ope-rationen und Verzweigungen aus, die ’untere’ parallel dazu nur load und storeOperationen. Den Datenpfad zeigt Fig. 6.58.

PCInstruction

memory

4

RegistersM u x

M u x

ALU

M u x

Data memory

M u x

40000040

Sign extend Sign

extend

ALU Address

Write data

F658.pdfCOD, p512

Der superskalaren MIPS-Prozessor bearbeitet Befehlspaare in einer 5-stufigenBefehlspipeline. Derartige Paare bestehen aus zwei Instruktionen, namlich aus

• einer arithmetisch-logischen oder einer branch-Instruktion

• und einer load- oder einer store-Instruktion,

hier etwa aus den prototypischen ADD/BEQ und LW/SW. Die Befehlsabarbeitung ist– wie gehabt – auf die 5 Stufen verteilt:


Instruktionen

arith./log. load/store

ADD BEQ LW SW

IF IRa=Mem[PC]; IRm=Mem[PC+4]; PC+=8;

ID Aa=Reg[IRa[25-21]] Am=Reg[IRm[25-21]]

Ba=Reg[IRa[20-16]] Bm=Reg[IRm[20-16]]

target=PC+SignExt(IRa[15-0])

EX ALUouta IF (Aa==Ba) ALUoutm=Am+SignExt(IRm[15-0])

= Aa op Ba PC = target

MEM MDR=Mem[ALUoutm] Mem[ALUoutm]=Bm

WB Reg[IRa[15-11] Reg[IRa[20-16]

= ALUout = MDR

Fur die Bearbeitung der ADD/BEQ- bzw. der LW/SW-Instruktionen notige, ansons-ten aber gleichnamige Register sind hier durch die Suffixe a bzw. m voneinanderunterschieden.

Aufgrund dieser Beschreibung wird – wie fur multi cycle- und pipeline-Implemen-tierung – ein endlicher Automat spezifiziert, der die control unit des superskala-ren MIPS modelliert. Dieser endliche Automat erlaubt dann wieder verschiede-ne Realisierungen der Steuerung: Logik, PLA, Sequencer, Mikro-programmierteSteuerung.

Das folgende Beispiel-Assembler-Programm addiert auf jedes Element eines Fel-des einen Skalar:

loop: lw Rt,0(Rp) // load array element at address Rp into temporary Rt

add Rt,Rt,Rs // increment element by scalar in Rs

sw Rt,0(Rp) // store result at Rpaddi Rp,Rp,4 // increment pointer Rpbne Rp,Re,loop // if (Rp!=Re) goto loop

Wenn der Compiler nun folgende Paare von Instruktionen erzeugt,

ALU/branch load/store cycle

loop: lw Rt,0(Rp) 1

add Rt,Rt,Rs 2

addi Rp,Rp,4 3

bne Rp,Re,loop sw Rt,-4(Rp) 4

ergibt sich fur diese superskalare Version des Prozessors ein CPI von 45

= 0.8. cz.H. Welcher Beschleunigungsfaktor mit welchen Abhangigkeiten ergibt sich? oz.H. Berucksichtigen Sie branch penalties. oz.H. Wie laßt sich das obige Programm weiter optimieren? o


5.7 scheduling funktionaler Einheiten

Etwa Gleitkomma-Zahlen-Rechenwerke operieren nicht im (pipeline-) Takt desProzessors. Erst recht mehrere solcher Rechenwerke mussen aufeinander abge-stimmt, synchronisiert eingesetzt werden, da Daten-Abhangigkeiten zu beruck-sichtigen sind.Das scheduling funktionaler Einheiten (functional unit, FU ) besteht darin, eineFU zu reservieren, den OP-Code zu senden und ein Register fur das Ergebnis zureservieren. Daten-Abhangigkeiten sind zu berucksichtigen. So durfen Ergebnissefur dasselbe Ergebnis-Register nicht in vertauschter Reihenfolge abgelegt wer-den, auch wenn die Ergebnisse einzelner FUs zu unterschiedlichen Zeitpunktenzur Verfugung stehen.

Z.B. Die CDC6600 – 1964 der erste Super-Computer – hat mehrere unabhangig B&H, p.303

operierende funktionale Einheiten: u.a. 2 Addierer, 2 Inkrementierer, 2 Multipli-zierer, 1 Dividierer sowie je eine branch, Boolean und shift unit. Zu jeder dieserFUs gehoren zwei Operanden-Register Fj und Fk, ein Ergebnis-Register Fi, Ope-rationsmodus Fm, busy flag, read flags Rj und Rk (falls Rj bzw. Rk gesetzt sind,sind die Daten in Fj bzw. Fk valide) sowie Zeiger Qj und Qk auf die die Operan-den produzierenden FUs.Die CDC6600 hat acht (Basis-) Adreß-Register A0, . . . , A7, acht Index-RegisterB0, . . . , B7 und acht Akkumulatoren X0, . . . , X7.Die control unit (CU) der CDC6600 heißt scoreboard und verwaltet XBA resultregister designators (welche FU beliefert welches XBA-Register), entry operandregister designators (welches XBA-Register enthalt Werte fur welchen Operan-den einer FU) und function unit designators Qj bzw. Qk (welche FU produzierteinen Operanden fur Fj bzw. Fk), Fig. 6.9. mit X3=F1(X1,X4), X4=F2(X5,X6)und X6=F5(.,.).Die CDC6600 hat eine 2-stufige Befehls-pipeline: zunachst dekodiere, welche FUliefert ihr Ergebnis an welches Register, schließlich warte, bis FU frei ist (busyflag) und dieses Register frei ist (es ist nicht Ergebnis-Register einer Instruktion,die noch bearbeitet wird), dann ubergib Befehl an FU.Ergebnisse werden unter der Kontrolle des scoreboards in die Register geschrie-ben. Die CU, also das scoreboard stellt so sicher, daß jede FU valide Operandenbekommt und daß Ergebnisse nicht Register-Werte uberschreiben, die noch ge-braucht werden.

FUs mussen moglicherweise auf Operanden warten, auch wenn verschiedene FUsihre Ergebnisse in verschiedene Register liefern (read after write (RAW) hazard).Z.B. muß wegen der Datenabhangigkeit der Addierer auf das Ergebnis des Mul-tiplizierers warten:

X6:=X1*X2 X3:=X1/X2

X5:=X6+X4 (X6: RAW) X5:=X4*X3 (X3: RAW)

X4:=X0+X6 (X4: WAR)


Ergebnisse durfen Register-Werte, die noch gebraucht werden, nicht uberschrei-ben (write after read (WAR) hazard). Z.B. darf der Addierer sein Ergebnis erstablegen, wenn der Multiplizierer X4 ausgelesen hat: s. Fig. 6.10, Fig. 6.11 cDie CDC6600 ist das erste Beispiel eines superskalaren Prozessors.

Bem. Da bei |FUs| FUs pro Takt |FUs| Operationen gleichzeitig ausgefuhrtwerden konnen, ist Pmax = |FUs| · f die theoretisch maximal erzielbare Leistungbei Taktrate f – daher die Bezeichnung.Fig. 6.58 zeigt einen ‘superskalaren’ MIPS-Prozessor mit zwei ALUs. ◦Z.B. Weitere Beispiele superskalarer Prozessoren sind DEC21064 und DEC21264 (Alpha), Intel i80860XP, IBM RS/6000, Motorola MC88110, MIPS R4000 Giloi, S.116

COD, ch.6.8oder SUN SuperSPARC. cBem. superpipeline-Architekturen sind durch tiefe Befehls- (10 und mehr pipe-line-Stufen) und Funktions-pipelines charakterisiert. Der Compiler muß in diesemFall also große load und branch delays ausgleichen, wahrend der Compiler fursuperskalar-Architekturen moglichst keine Paare, Tripel o.a. abhangiger Befehleerzeugen sollte, damit die funktionalen Einheiten stets ausgelastet sind. ◦Z.B. DEC 21064 (Alpha) und MIPS R4000 gelten als sowohl superskalar als Giloi, S.116

COD, p.441auch als superpipelined. c

5.8 pipeline-Vektor-ProzessorenGiloi, S.211CA, Kap.7Eine Vektor-Operation wie ~z = ~a · ~x + ~y mit ~a, ~x, ~y, ~z ∈ Rn laßt sich grundsatz-

lich entweder durch n Rechen-Elemente – das i-te Rechen-Element berechnet~zi = ~ai · ~xi + ~yi – effektiv ausfuhren oder eben durch pipeline-Multiplizierer mitnachgeschaltetem pipeline-Addierer.

∗ +

ai

xi

yi

FUi

zi+

∗ai

xi

yi

zi

Wichtigste Beispiele fur derartige Vektor-Operationen sind die SAXPY- bzw.DAXPY-Benchmarks, d.h. single/double a*X[i]+Y[i].

Def. pipeline-Vektor-Prozessoren bestehen aus einzelnen spezialisierten pipeli-nes, die dynamisch konfigurierbar sind. Sie sind darauf zugeschnitten, Vektor-Operationen effizient auszufuhren, z.B. komponentenweise arithmetische Opera-tionen, compress(~v,~b), expand(~v,~b), merge(~v, ~w,~b), gather(~v,~i) mit Boole’schen

Vektoren ~b und Index-Vektoren ~i oder spezielle triadische Operationen wie etwaD[i]:=A[i]*B[i]+C[i].


Bem. Spezielle Vektor-Register, caches und haufig verschrankte Speicher un-terstutzen die Vektor-Verarbeitung in Vektor-Maschinen.Typische Vektor-Anwendungen sind LGS (z.B. per Gauß oder Gauß-Seidel), Dif-ferentialgleichungssysteme (DGlS z.B. per Runge-Kutta), finite Elemente Metho-de (FEM) usw. ◦Z.B. Beispiele fur pipeline-Vektor-Prozessoren sind ILLIAC-IV, (CDC-) Star- CA, S.350

100, TI ASC, CRAY 1 sowie die NEC SX-, Siemens VPx und Fujitsu VPx-EX-Familien mit den gemeinsamen Merkmalen: Befehls-pipeline, mehrere pipeline-FUs, verschrankter Speicher (interleaved memory), unabhangige Befehls-caches(instruction cache) und Daten-caches (data cache) sowie mehrfache Bus-Systeme(multiple buses).

JahrAnzahlVektor-Register

Vektor-RegisterLange

funktionale Vector Einheitenloadstoreunits

Cray 1 1976 8 64 6× (+, ∗, inv, logic, shift) 1

Cray X-MPY-MP

19831988

8 64 8× (+, ∗, inv, 2× logic, shift) 2×load1×store

Cray 2 1985 8 64 5× (+, ∗,√, inv, logic) 1

FujitsuVP100/200

1982 8–256 32–1024 3× (+, ∗, /) je GK und FK 2

HitachiS810/820

1983 32 256 4× (2× (FK+, logic), ∗+, ∗/+) 4

Convex C1 1985 8 128 4× (+, ∗, /, FK-logic) 1

NEC SX/2 198488K

256konfig

16× (4× (+, ∗, /, shift, FK+, logic)) 8

DLXV 1990 8 64 5× (+, ∗, /, FK+, logic) 1

Die DLX kann uber Kommando-Zeilen-Parameter zur Vektor-Maschine DLXV CA, S.356ff

mit Vektor-Vektor-Operationen (+,−, ∗, /), z.B. ADDV V1,V2,V3, Skalar-Vektor-Operationen (+,−, ∗, /), z.B. ADDSV V1, F1, V2, sowie den Lade-Vektor-Opera-tionen, z.B. LV V1,R1 (load V1 aus dem Speicher ab Adresse R1) und Speicher-Vektor-Operationen, z.B. SV V1,R1 (store V1 im Speicher ab Adresse R1) konfi-guriert werden. Weitere Operationen erlauben beispielsweise Boole’sche Vektor-Operationen oder das Setzen und Auslesen von Vektor-Langen- bzw. Vektor-Masken-Registers. cBem. Untersuche das CNAPS coprozessor board mit 64 Prozessoren. ◦ Labor ELKA

Vektorisierung erzielt verhaltnismaßig große Leistungssteigerungen mit verhalt-nismaßig geringen Mehrkosten fur HW und Compiler.

Vektor-Instruktionen im Mikro-Programm reduzieren Speicher-Zugriffe;Schleifen werden im Mikro-Programm i.a.R. schneller ausgefuhrt als solche imAssembler-Programm.

HW-Verarbeitung entsprechender Vektor-Instruktionen reduziert ebenso Spei-cher-Zugriffe und eliminiert daruberhinaus den Schleifen-Overhead.

Z.B. Beispiele fruher Vektor-Maschinen sind STAR100 und in der Folge dieCYBER203 – mit verschrankten Speichern, multiplen Bussen, E/A-Prozessoren


und Strom-Einheit, stream unit (Mikro-Controller, Register-Banke, Befehlskel-ler, Dekoder, Steuer-Vektor(?)) und zwei pipeline-Prozessoren, einem GK-Adderund -Multiplier sowie einem GK-Adder und -Divider. Die Adder sind 6-stufig,der Multiplier ist 7-stufig bei einer Zykluszeit von 40ns und n1/2 ≈ 200! DerBefehlskeller speichert 16 128bit Worter; Nachladen z.B. bei Sprungen aus demBefehlskeller hinaus dauert 1280ns. Pipeline-Inhalte werden in spezielle Unter-brechungsregister gerettet24. cZ.B. Die CRAY 1 hat eine load/store-Architektur und verfugt u.a. uber achtVektor-Register (V), acht Skalar-Register (S) und acht Adreß-Regsister (A) miteinem Adreß-Multiplizierer, z.B. fur mehrdimensionale Felder, und uber Funkti-onseinheiten als pipelines mit 2 bis 14 Stufen. Das Verketten von Operationen,also mehrere Operationen nacheinander auf einem Datenstrom auszufuhren, wirdunterstutzt (z.B. fur LGS). Es gibt vier Befehlspuffer fur je 64 Befehle; eine sco-reboard Einheit sorgt durch Register-Verriegelung fur die Synchronisation derFunktionseinheiten. cLeistungsbewertung: Sei tcond die fur die Konditionierung der pipeline notwen- Giloi,

S.214-215B&H, p.305

dige Zeit, tflush die Durchflußzeit (flushing time), d.h. die Zeit fur den Durchlaufdurch die (konditionierte) pipeline, also die Zeit vom Holen der Argumente biszum Wegspeichern der Ergebnisse, und tclock die Zyklus-Zeit (clock time) der Ver-arbeitungselemente, also die Verarbeitungszeit einer jeden Stufe der pipeline.Dann ist tcond + tflush die Ausfuhrungszeit einer Skalar-Operation und n Skalar-Operationen dauern tcond+n·tflush. Also ergibt sich eine Ausfuhrungszeit Tscal(n) =tflush +

tcondn

pro Operation bei n Operationen.

Falls die pipeline in jedem Zyklus, also alle tclock Zeiteinheiten ein Ergebnisproduziert und falls in jedem Zyklus Operanden geholt und Ergebnisse abge-speichert werden, so ist tcond + tflush + (n − 1) · tclock = tconf + n · tclock mittconf = tcond + tflush − tclock die Zeit fur die Bearbeitung eines Vektors der Langen durch eine Vektor-Operation und damit

Tvect(n) = tclock +tconf

n

die Ausfuhrungszeit pro Vektor-Element bei Vektor-Lange n. Die Leistung P derpipeline, also die Anzahl von Operationen pro Zeiteinheit ist dann

P = P (n) =1

Tvect(n)=

1

tclock(1 +tconftclock

1n)

Fur n → ∞ ergibt sich die theoretische Maximal-Leistung P∞ = 1tclock

und fur

n1/2 =tconftclock

die halbe Maximal-Leistung P (n1/2) = P (tconftclock

) = 1tclock(1+1)

= 12P∞

und somit auch P = P (n) = P∞n

n+n1/2.

24Heute dagegen sind Vektor-Operationen ununterbrechbar; bei Unterbrechungen ubernimmtdas exception handling z.B. ein roll back.


Def. nx und n1/2 messen die Nutzlichkeit von Vektor-Prozessoren:

nx =Vektor-Lange, so daß Skalar-

= Vektor-Geschwindigkeit, Tscal(nx) = Tvect(nx)

n1/2 =Vektor-Lange, so daß Vektor-Geschwindigkeit

= 12 asymptotische Vektor-Geschwindigkeit

, Tvect(n1/2)= Tvect(∞)

2

nx ist der break even point der Vektorisierung.

Je kleiner nx und n1/2 ausfallen, um so nutzlicher ist Vektorisierung. Wie schonbei pipeline-Rechnern muß hier das Speicher-System erst recht mithalten konnen(Daumen-Regel: Speicher-Bandbreite = dreifache pipeline-Rate).

Z.B. Die Vektor-Ausfuhrung fur n Elemente brauche tconf +n tclock Zeiteinheitenoder Zyklen, die Skalar-Ausfuhrung n tscal. Vektorisierung empfiehlt sich also furtconf + n tclock < n tscal oder eben falls n > tconf/(tscal − tclock).Fur die CRAY 1 gilt tconf = 5, tclock = 1 sowie tscal = 2 und damit n > 5. c B&H, p.316

5.9 RISC vs CISC

Seit Anfang der 80er Jahre konkurrieren RISC-Architekturen (Reduced Instruc-tion Set Computer) mit den ‘herkommlichen’ CISC-Architekturen (Complex In-struction Set Computer). Merkmale von RISC-Architekturen sind:

• einfacher, kleiner Befehlssatz, d.h. moglichst wenige Befehle mit identischerLange und wenigen Formaten (also leicht zu dekodieren)

• weitgehend orthogonaler Befehlssatz, d.h. wenig Uberlappung hinsichtlichder Funktionalitat der Befehle (wenige Code-Alternativen, also einfachereCompiler)

• moglichst wenige Adressierungsarten

• load/store-Architektur und

• arithmetisch/logische Befehle nur fur wenige Datentypen (meist nur int undfloat)

Z.B. CDC6600 ist ein klassischer RISC-Rechner (weniger als hundert Befeh- B&H, S.308

le incl. der verschiedenen Adressierungen), VAX ein klassischer CISC-Rechner(mehrere hundert Befehle mit jeweils diversen Adressierungen). Auch Prozesso-ren wie MIPS R2000, Motorola 88000 oder Sun SPARC sind RISC-Rechner, dieProzessoren der Intel-Familie 80x86 dagegen CISC-Rechner. cVon den Charakteristiken der RISC-Prozessoren – einfacher load/store Befehls-satz, Einzyklus-Operationsbefehle durch pipelining und feste Ablaufsteuerung(kein Mikro-Programm) – weisen die ersten beiden heute auch die CISC-Pro-zessoren auf. Etwa fur Gleitkomma-Arithmetik sind manche RISC-Prozessoren


auch wieder mikro-programmiert. Giloi schlagt daher statt RISC-Prozessor dieBezeichnung Pipeline-Skalar-Prozessor vor.


6 Speicher-Hierarchie

Die Anforderungen an Speicher-Kapazitat nehmen exponentiell zu: die Speicher- Beispiele inB&H,p.178,179

große ≈ 223

(Jahr−1979)MB fur Mini- und ≈ 212

(Jahr−1966)MB fur Super-Computer.

Gleichzeitig fuhren (RISC-) Prozessoren inzwischen eine Operation pro Takt aus,das sind 100 Mio Operationen pro Sekunde bei Taktraten von einigen 100MHz,also Taktlangen von 10 ns. Speicher (DRAM) konnen da nicht mithalten: diesogenannte Speicher-Hierarchie soll dem abhelfen: der Prozessor greift auf jeweilskleineren, schnelleren und daher teureren Speicher zu, der Kopien von Daten ausder nachsten Speicher Ebene halt, die aus großerem, langsameren und daherbilligeren Speicher besteht:

Typ (Giloi, S.100 fur 1991) Kapazitat Zugriff hit (%)Register 256...1024KB 10ns 60

Caches (SRAM) 16 ... 64KB 10 ... 20ns 38Hauptspeicher (DRAM) 16 ... 128M 35...100ns 2

Sekundar-Speicher (Winchester) 100MB ... 2GB 16 ... 50ms 0.0005Archive (Bander, optische Platten) 1 ... 100GB 500ms

Z.B. Beliebig große register files verbieten sich, da Kosten und Zugriffszeit linearmit der Große zunehmen. Es gibt also meist durchschnittlich nur etwa 32 Regis-ter sowie on chip caches, d.h. primare caches (fur Befehle und/oder Daten) inder Großenordnung von KB und/oder wesentlich großere externe, d.h. sekundarecache-Speicher (s.u.). cDie Speicher-Hierarchie beruht also auf den wesentlich unterschiedlichen Zugriffs-zeit und -Haufigkeit sowie Kosten der Speicher auf jeder Ebene:

Typ CA, p.455 fur 1993 Zugriffszeit hit (%) Kosten ($/MB)Caches (SRAM) 8 ... 35ns 38 100 ... 400

Hauptspeicher (DRAM) 90 ... 120ns 2 25 ... 50Sekundar-Speicher (Winchester) 10 ... 20ms 0.0005 1 ... 2

basierend auf den verschiedenen Speicher-Technologien:

destr. data write read write PowerTyp read life time time cycles requ. Bem.ROM nein Dekaden 1 mal 100ns 1 neinPROM nein Jahre h 100ns viele neinEPROM nein Jahre ms 100ns 1000e neinSRAM nein power 10ns 10ns ∞ ja flip flop: Register

DRAM ja 4ms 100ns 200ns ∞ 10% Kondensator: RAM

Der Nutzen der Speicher-Hierarchie beruht wieder auf einer 90/10-Faustregel: einProgramm verbraucht 90% der Laufzeit in 10% des Codes. Zugriffe auf Befehleund Daten sind dem Prinzip der Lokalitat unterworfen:


zeitliche Lokalitat: auf den Zugriff auf ein Datum folgt mit hoher Wahrschein-lichkeit bald ein erneuter Zugriff.

raumliche Lokalitat: auf den Zugriff auf ein Datum folgt mit hoher Wahrschein-lichkeit bald ein Zugriff auf ein benachbartes Datum.

z.H. Welche Daten- und Kontroll-Strukturen weisen zeitliche bzw. raumlicheLokalitat auf? Welche Lokalitat weist Programm-Code vornehmlich auf? oReines Vorhalten von Kopien der zuletzt referenzierten Daten nutzt also nur diezeitliche Lokalitat. Vorhalten von Kopien ganzer Blocke, die die zuletzt referen-zierten Daten enthalten, nutzt zusatzlich auch die raumliche Lokalitat. Dazu wirdjede Adresse aufgeteilt in Blockadresse und Block-Offset, z.B. fur 32-bit-Adressenund 1024-bit-Blocke in

22-bit-Blockadresse 10-bit-Block-Offset

Wenn ein referenziertes Datum in einem Block der oberen Speicher-Ebene vor-handen ist (hit), fallt fur den Speicherzugriff nur die Trefferzeit an. Wenn einBlock in der oberen Speicher-Ebene nicht gefunden wird (miss), muß er aus derfolgenden unteren Ebene nachgeladen werden (Fehlzugriffszeit). Also ergibt sichmit Fehlzugriffsrate := 1− Trefferrate

mittlere Speicherzugriffszeit = Trefferzeit + Fehlzugriffsrate * Fehlzugriffszeit

z.H. Wie beeinflußt die Blockgroße die mittlere Speicherzugriffszeit? oBei kleiner Fehlzugriffszeit (cache miss) wartet der Prozessor i.a.R., bei großerFehlzugriffszeit (page fault) fuhrt das Betriebssystem i.a.R. einen Prozeß-Wechseldurch.

Grundsatzlich ist also fur jede Ebene der Speicher-Hierarchie festzulegen, wieBlocke platziert, gefunden, ersetzt und geschrieben werden.

6.1 cache-Speicher

cache25-Speicher beschleunigen den Zugriff des Prozessors auf den Speicher durchAusnutzen der Befehls- und Daten-Lokalitat. Sie liegen in der Speicher-Hierarchiezwischen den Registern und dem Hauptspeicher (langsamer als Register undschneller als Hauptspeicher). Sie enthalten als Befehls- und/oder Daten-cacheKopien der jeweils aktuellen Befehle und/oder Daten eines Programmes (wor-king set). Getrennte Befehls- und Daten-caches heißen auch Havard-Architektur.

cache-Speicher werden genauso adressiert wie der Hauptspeicher: sie sind fur denProzessor i.a.R. transparent.

25cache: ein sicherer Platz zum Verstecken und Aufbewahren, Websters 1976


Die effektive Zugriffszeit Teff ergibt sich bei einer (cache-) Trefferrate (hit ra-tio) h und einer Zugriffszeit Tcache fur den cache- und Tmem fur den Hauptspei-cher als Teff = hTcache + (1 − h)Tmem. Der Beschleunigungsfaktor β aufgrund wie in Giloi,

S.103,B&H, p.198,aber imWiderspruchzu CA, S.405

des Einsatzes eines cache-Speichers betragt β = TmemTeff

= TmemhTcache+(1−h)Tmem

=

TmemTmem+h(Tcache−Tmem)

= 1

1−h(1−TcacheTmem

). Es gilt β ↗ falls h↘ oder falls

TcacheTmem

↘.

Z.B. Ein cache-Speicher bringt also bei einer realistischen Hit-Rate von 0.9 undbei einem neunmal schnelleren cache-Speicher eine 1

1−0.9(1− 19

)= 1

1− 910

89

= funffache

Steigerung der Zugriffsgeschwindigkeit. cIn jedem Fall ist man bemuht, die Treffer-Rate zu erhohen (großtmoglicher cache-Speicher, optimierende Compiler), die cache-Zugriffszeit unter die Zyklus-Zeitdes Prozessors zu senken, das Nachladen aus dem Hauptspeicher bei cache misszu beschleunigen und den Verwaltungsaufwand (cache-Konsistenz oder cache-Koharenz, d.h. Ubereinstimmung mit dem Hauptspeicher) zu minimieren.

Es gibt unterschiedlich aufwandige cache Verwaltungen, d.h. Strategien, Spei- COD,ch. 7.2,ch. 7.4CA, S.409

cher-Blocke im cache zu platzieren (Fig. 7.16):

Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data

Eight-way set associative (fully associative)

Tag Data Tag Data Tag Data Tag Data

Four-way set associative

Set

0

1

Tag Data

One-way set associative (direct mapped)

Block

0

7

1

2

3

4

5

6

Tag Data

Two-way set associative

Set

0

1

2

3

Tag Data

F716.pdfCOD, p570

direct mapping oder einfach oder 1- assoziativ : einer jeden Block-Adresse ent-spricht genau eine cache-Zeile (Fig. 7.7 fur 1-Wort-Blocke)


Address (showing bit positions)

20 10

Byte offset

Valid Tag DataIndex

0

1

2

1021

1022

1023

Tag

Index

Hit Data

20 32

31 30 13 12 11 2 1 0

F707.pdfCOD, p549

und Fig. 7.10 fur 4-Wort-Blocke

Address (showing bit positions)

16 12 Byte offset

V Tag Data

Hit Data

16 32

4K entries

16 bits 128 bits

Mux

32 32 32

2

32

Block offsetIndex

Tag

31 16 15 4 32 1 0


F710.pdfCOD, p557

Eine Hauptspeicher-Adresse wird zerlegt in (tag, index, Block-Offset). indexindiziert die cache-Zeilen, die neben den Daten noch den zugehorigen tag(= Blockadresse) speichern. Die Zerlegung von 32-bit-Adressen fur einen8KB großen cache mit 1024 Blocken a 8 byte beispielsweise ist

29 bit block address 3 bit block offset19 bit tag 10 bit index 3 bit block offset

mit cache address = block address mod (number of blocks in cache) . Bei

jedem Hauptspeicher-Zugriff anhand der Block-Adresse (tag,index) mußder tag der index-ten cache-Zeile mit dem Adress-Teil tag verglichen wer-den. Bei Ubereinstimmung enthalt der cache-Block die gesuchten Daten,sonst wird genau diese cache-Zeile mit Adresse und Daten der gesuchtenHauptspeicher-Zelle uberschrieben – insgesamt ein sehr einfaches Verfah-ren mit einem einzigen Komparator, ohne Assoziativ-Vergleich und ohneErsetzungs- oder Verdrangungsstrategie (s.u.).Dieser 8KB-cache hat einen overhead von 1K Zeilen a 19bit ≈ 2.5KB odereine brutto Kapazitat von ca. 10.5KB.

Z.B. Ein cache mit netto 64KB Daten in 4Byte Blocken hat 214 Zeilen atag+data = (32-14-2)+32=48bit bei 32bit Adressen. Der cache beanspruchtalso brutto 48 · 214bit = 6 · 24KB = 96KB. c

fully associative oder vollassoziativ : ein Block kann in jeder cache-Zeile platziertwerden. Die Zerlegung block address block offset der Haupt-speicher-Adressen ist somit unabhangig von der cache-Adresse, d.h. dercache-Zeile.Ein 8KB-cache mit 8Byte Blocken hat vollassoziativ einen overhead von 1KZeilen a 29bit ≈ 3.5KB oder eine brutto Kapazitat von ca. 11.5KB.

Z.B. Ein vollassoziativer cache mit netto 64KB Daten in 4Byte Blockenhat 214 Zeilen a tag+data = (32-2)+32=62bit. Der cache beansprucht alsobrutto 62 · 214bit = 31 · 25Kbit = 31 · 4KB = 124KB. cErstens mussen alle tags im cache mit der gegebenen Block-Adresse ver-glichen werden, um festzustellen, ob sich der betreffende Block im cachebefindet. Aus Geschwindigkeitsgrunden wird der Vergleich in aller Regelparallel ausgefuhrt. Dafur sind soviel Komparatoren notig, wie cache-Zeilenvorhanden sind.Zweitens wird eine Ersetzungs- oder Verdrangungsstrategie notwendig:

random, i.e. ‘der zu uberschreibende Eintrag wird pseudo-zufallig aus-gewahlt’.

fifo, first in first out, i.e. ‘der alteste Eintrag im cache wird uberschrieben’(Ringpuffer).


lru, least recently used, i.e. ‘der am langsten nicht referenzierte Eintragwird uberschrieben’.

Z.B. Die Realisierung eines vollassoziativen caches mit 256 32-bit-Wortern Giloi, S.105

und lru Ersetzung bei 18bit Hauptspeicher-Adressen zeigt Bild 4-6.Der cache-Speicher besteht aus CAD (content addressable data), CAA (con-tent addressable addresses) und 256 7bit UCs (utilization counters). Wirddie Adresse einer Speicher-Zelle in CAA gefunden, so stehen die Datenin CAD. Sonst werden Adresse und Daten aus dem Hauptspeicher in diecache-Zellen geladen, deren letzte Referenzierung am langsten her ist (lru) –bekannt aus UC. MA und MD bzw. AMA und AMD sind die Memory bzw.Assoziativ-Speicher Adreß- und Daten-Register; der 8bit Zahler space coun-ter SPC zeigt auf UCi mit UCi = 0; r=1 bzw. ro=1 und entsprechend w=1bzw. wo=1 bedeuten, daß ein Wort im Hauptspeicher bzw. cache zu lesenoder zu schreiben ist; immer wenn die i-te Zeile CAMi referenziert wird,wird UCi = 27 − 1 gesetzt und alle anderen UCj werden dekrementiert:UCj = max(UCj,0). Die j-te Zelle wurde also mindestens 127–UCj mal inFolge nicht referenziert. Falls also 127-mal immer andere Zeilen referenziertwerden, sind die Halfte aller UCi Null. Falls 127-mal immer dieselbe Zellereferenziert wird, sind alle anderen UCj Null. Daher sind zwischen diesenbeiden Extremen also immer mindestens die Halfte der UCi Null, d.h. min-destens die letzten 127 Referenzen betrafen nicht die i-te Zelle.Beim Nachladen aus dem Hauptspeicher wird MA und MD in die SPC-teZelle des cache geladen, also in eine Zelle, die wenigestens die letzten 127-mal nicht referenziert wurde, und danach der SPC solange inkrementiert,bis er auf ein UCi = 0 zeigt. Dies implementiert die last recently used (lru)Strategie. c

set-associative oder m-fach assoziativ: jeder Block kann an jede Stelle genaueines sets mit jeweils m Blocken plaziert werden (s. Fig. 7.19).


Address

22 8

V TagIndex

012

253254255

Data V Tag Data V Tag Data V Tag Data

3222

4-to-1 multiplexor

Hit Data

123891011123031 0

F719.pdfCOD, p574

set-assoziative caches stellen eine Mischung aus assoziativem und directmapped cache dar. Eine Hauptspeicher-Adresse wird zerlegt in (tag,index,Block-Offset). index indiziert die cache-Mengen (sets). Die Zerlegung von 32-bit-Adressen fur einen 8KB großen 4-assoziativen cache mit 1024 Blocken a8Byte beispielsweise bedingt einen 8-bit-Index zur Adressierung der 256sets mit je 4 Blocken

29 bit block address 3 bit block offset21 bit tag 8 bit index 3 bit block offset

mit cache address = block address mod (number of sets) . Bei jedem Zu-

griff auf den Hauptspeicher anhand der Block-Adresse (tag,index) muß derAdreß-Teil tag mit den tags der m Blocke im index-ten cache set vergli-chen werden. Entsprechend dem Fall des vollassoziativen caches sind dazum Komparatoren notig.Wie beim vollassoziativen cache konnen auch beim set-assoziativen cacheeine der drei Ersetzungsstrategien random, fifo und lru eingesetzt werden.Ein 8KB-cache mit Blocken a 8Byte hat 4-assoziativ einen overhead von 4tags a 21bit in 256 sets = 21Kbit ≈ 2.5KB.

Z.B. Ein 4-assoziativer cache mit netto 64KB Daten in 4Byte Blocken hat212 sets a 4 Blocke, d.h. 212 Zeilen a 4(tag+data) = 4[(32− 12− 2) + 32] =4 · 50bit. Der cache braucht also brutto 50 · 214bit = 50 · 2KB = 100KB. c


Bem. Ein vollassoziativer cache-Speicher mit insgesamt m Blocken hat ein setmit m Blocken und ist daher m-fach assoziativ, ein direct mapped cache hat einenBlock pro set und ist daher 1-fach assoziativ. ◦Z.B. Der cache controller Intel 82385 fur Intel 80386 Prozessoren verwaltet einen Bahring,

S.30232KB cache wahlweise (per hardware Signal) als direct mapped oder als 2-fachassoziativen (mit lru) cache (mit write through/write around, s.u.). Den 4ByteBlocken entsprechen vier 8KB SRAM-Banke. Die Blocke werden aligned geladen.

direct mapped31 1514 21 0

17 bit tag 13 bit index← block offset

In der 2-assoziativen Version wird jede 8KB-Bank als zwei 4KB-Banke betrieben:

2-assoziativ31 1413 21 0

18 bit tag 12 bit index← block offset

Durch Blockung wird der 8K·17bit = 17KB (direct mapped) bzw. 8K·18bit =18KB (2-assoziativ) große Adreß- oder tag-Speicher reduziert: die 32KB werdenzu 1024 4× 8 = 32Bytes großen Super-Blocks (=sets) zusammengefaßt. cBem. Die meisten caches speichern in jeder Zeile ein zusatzliches valdity bit unddirty bit. Damit werden einerseits nach einem reset alle cache-Zeilen invalidiertund mussen in jedem Fall erst geladen werden; und andererseits mussen nur sol-che Blocke in den Hauptspeicher zuruckgeschrieben werden, die auch tatsachlichim cache verandert wurden: Das dirty bit wird gesetzt, wenn die cache-Zeileverandert wurde. ◦Z.B. Die Blocke mit den Adressen 0,8,0,6,8 sollen in einem 4-Block cache platziertwerden. Der direct mapped cache erzeugt 5 misses, der 2-assoziative erzeugt 4misses und der voll-assoziative erzeugt 3 misses. c

6.1.1 cache-Leistung

Die cache-Leistung (Fig. 7.12) wird gesteigert, wenn es gelingt,


1 KB

8 KB

16 KB

64 KB

256 KB

256

40%

35%

30%

25%

20%

15%

10%

5%

0%

Mis

s ra

te

64164

Block size (bytes)

F712.pdfCOD, p559

0%

3%

6%

9%

12%

15%

Eight-wayFour-wayTwo-wayOne-way

1 KB

2 KB

4 KB

8 KB

Mis

s ra

te

Associativity 16 KB

32 KB

64 KB

128 KB

F729.pdfCOD, p604


• moglichst viel aus dem cache, moglichst wenig aus dem Hauptspeicher zulesen (also moglichst großer, zugleich moglichst schneller cache)

• Hauptspeicherzugriffe mit anderen Operationen zu uberlappen (Laden mitlook ahead, z.B. bei cache miss nicht nur fehlendes Wort sondern eben gleichganzen Block laden)

• den cache mit cache- und nicht Hauptspeicher-Geschwindigkeit zu laden(wenn der cache typischerweise viermal so schnell wie der Hauptspeicherist, durch ‘Hauptspeicher-Breite gleich viermal cache-Breite’, so daß in ei-nem Hauptspeicherzugriff parallel vier Worte in den cache geladen wer-den – bei ausreichender Busbandbreite!, oder durch vierfach verschranktenHauptspeicher – bei ausreichender Busbandbreite! (Fig. 7.13)

CPU

Cache

Bus

Memory

a. One-word-wide memory organization

CPU

Bus

b. Wide memory organization

Memory

Multiplexor

Cache

CPU

Cache

Bus

Memory bank 1

Memory bank 2

Memory bank 3

Memory bank 0

c. Interleaved memory organization

F713.pdfCOD, p561

6.1.2 caching und schreibende Speicher-Zugriffe

Je nach Befehlsmix, Anwendung etc. ist jeder dritte Speicher-Zugriff schreibend.Prozessor, DMA-hardware, EA-Prozessoren und erst recht andere Prozessoren ineinem Multiprozessor-System konnen unabhangig auf einen gemeinsamen Spei-cher zugreifen. ⇒ (lokale) cache Inhalte, d.h. kopierte Speicher-Bereicheund Speicher stimmen nicht notwendig uberein!

Def. Datenkonsistenz von cache und Speicher heißt, daß cache und Haupt-speicher-Ausschnitt zu jedem Zeitpunkt ubereinstimmen.Def. Datenkoharenz von cache und Speicher heißt, daß beim Lesen immer derzuletzt geschriebene Wert gelesen wird.

Bem. Koharenz ist gefahrdet, wenn ein Prozessor neue Daten in den cacheschreibt oder ein anderer neue Daten in den Hauptspeicher schreibt. ◦


write through (immer zugleich in den cache wie auch in den Speicher schreiben)garantiert Konsistenz!

copy back (Ruckschreiben in den Speicher erst beim Verdrangen der modifizier-ten Daten aus dem cache) garantiert Koharenz!26

z.H. Vergleiche jeweils Hauptspeicher-Zugriffe und Implementierungsaufwandder beiden Schreib-Strategien write through und copy back. oWenn beim Schreiben ein cache miss auftritt, konnen zwei Strategien zum Einsatzkommen: entweder

fetch on write oder write allocate: der entsprechende Block wird geladen unddanach (ohne miss) geschrieben – oder

write around oder no write allocate: der entsprechende Block wird unter Umge-hung des cache in den Hauptspeicher geschrieben.

z.H. Warum verwenden caches mit write through meist no write allocate? Warumverwenden caches mit write back meist write allocate? oz.H. Berechne Beschleunigungsfaktor aufgrund des Verzichts auf Konsistenz zu-gunsten von Koharenz. o

6.1.3 logischer oder physikalischer cache

Ein cache-Speicher zwischen Prozessor und Adressen-Umsetzer arbeitet mit logi-schen Adressen (logischer cache-Speicher), ein cache-Speicher zwischen Adressen-Umsetzer und Hauptspeicher arbeitet mit physikalischen Adressen (physikalischercache-Speicher). Der Zugriff auf einen logischen cache-Speicher erfolgt direkt undnicht durch einen Adressen-Umsetzer. Schnuffeln kann man allerdings nur phy-sikalische Adressen. Am besten ist somit, im Kennteil (tag) des cache-Speicherslogische und physikalische Adressen zu speichern.

Z.B. Der Intel 80486 hat einen 4-fach assoziativen 128·4·16B= 213B=8KB cache, Flik/Liebig,S.409gemeinsam fur Daten und Instruktionen, mit 128 sets a 4 Blocken a 16Byte. Der

tag enthalt physikalische Adressen. Ein Block wird entweder durch vier-Wort-Transport oder schnellen Block-Transport (burst) geladen. Die write-Strategiebei cache hit ist ‘write through’, bei cache miss ‘write around’. cZ.B. In Cache-Hierarchien von L1-, L2- usw. Ln-caches werden verschiedene c’t 4/2003,

S.106Ersetzungsstrategien eingesetzt, etwa sogenannten victim caches. c

26 per Verwaltung der valid bits: eine Schnuffel-Logik erkennt, daß eine Adresse einer zubeschreibenden Hauptspeicher-Zelle am Bus anlag. Kommen solche Adressen auch im cache vor,so werden die Daten durch Setzen des zugehorigen bits invalidiert. Invalidierte Daten werdendann wie cache misses behandelt. Ebenso werden bei Prozeß-Wechsel alle cache-Eintrage (cacheflushing) oder per Prozeß-Kennung nur die des noch aktuellen Prozesses invalidiert.


6.2 Haupt-Speicher

Die wichtigsten Parameter eines dynamischen Speicher-Bausteins mit Seiten-adressierung sind (mit RAS – row address strobe und CAS – column addressstrobe)

RAS-Adressierung: Zeitdauer zwischen Anlegen der Seiten-Adresse und Lesendes Zelleninhaltes (typisch 50–80ns)

CAS-Adressierung: Zeitdauer zwischen Anlegen der Zellen-Adresse und Lesendes Zelleninhaltes (typisch 20ns)

RAS-Erholzeit: Zeit fur das Zuruckschreiben – Lesen ist zerstorend (typisch 50–80ns)

RAS-Zyklus: RAS-Adressierung + RAS-Erholzeit

CAS-Zyklus: Zeitdauer zwischen Anlegen der Zellen-Adresse und Lesen des Zel-leninhaltes bei unveranderter Seiten-Adresse (typisch 35–45ns)

6.2.1 Speicher-Organisation

Prozessor- und Speicher-Bandbreite konnen durch wait states, Verbreiterung vonBus (sowie gegebenenfalls cache-Speicher) und Speicher (nachteilig ist der Mul-tiplexer im zeitkritischen Pfad zwischen CPU und cache und die Probleme durchECC) oder besser durch Speicher-Verschrankung (allerdings Speicher-Erweite-rungen nur durch Vervielfachen) angepaßt werden (s. COD, Fig. 7.12).

Def. Speicher-Verschrankung heißt, den Speicher in verschiedene Speicher-Bankeaufzuteilen, die durch einen Teil der Hauptspeicher-Adresse adressiert werden.Speicher-Banke sind unabhangige Speicher-Einheiten mit eigenen Registern furAdressen und Daten.

Z.B. µJava hat vier und NEC SX/3 bis zu 128 Speicher-Banke. cDef. Bei einer Speicher-Verschrankung anhand des hoher- bzw. des nieder-werti-gen Teils (high bzw. low order interleave) dient der hoher- bzw. der nieder-wertigeTeil der Adresse zur Identifikation der Speicher-Bank.

Z.B. Ein 2-fach verschrankter 1MB Speicher enthalt bei high order interleavein Bank 0 die Speicher-Zellen zu Adressen 0..511 sowie in Bank 1 diejenigen zuAdressen 512..1023. Bei low order iterleave enthalt Bank 0 die Speicher-Zellen zugeraden und Bank 1 diejenigen zu ungeraden Adressen. cSpeicher mit high order interleave unterstutzen gut den gleichzeitigen Zugriffmehrerer unabhangiger Einheiten wie Prozessoren, E/A-Einheiten usw. auf ver-schiedene Speicher-Banke.Speicher mit low order interleave unterstutzen gut den konsekutiven Zugriff des


Prozessors auf die Elemente von Feldern, wenn der Compiler die Elemente ein-dimensionaler Felder zyklisch in den Speicher-Banken ablegt. (Probleme ergebensich allerdings bei Zugriffen auf mehrdimensionale Felder.)

Bem. Der theoretisch mogliche Beschleunigungsfaktor aufgrund Einsatzes einesn-fach verschrankten Speichers reduziert sich aus obigen Grunden auf ≈

√n. ◦

6.2.2 Virtueller Speicher

Statt program overlay oder separate Adreß-Raume fur jeden Prozeß, lieber einenvirtuellen Speicher! Unabhangigkeit von Speicher-Ausbau! Speicher nachtraglichaufrustbar!

Das Konzept des virtuellen Speichers erlaubt Schutz-Mechanismen und eine ein-heitliche Adressierung des gesamten Sekundar-Speicherraumes: jeweils im Haupt-speicher fehlende Information (page fault) wird aus dem Sekundar-Speicher nach-geladen. Logische Adressen im virtuellen Speicher werden von spezieller Hardwa-re (memory management unit) in physikalische Adressen umgewandelt (Adress-Translation). Zugriffe auf bestimmte logische Adress-Bereiche konnen etwa demBetriebssystem vorbehalten sein.

Def. Ein virtueller Speicher27 ist der einem (großen) logischen Adreß-Raumzugeordnete Speicher, der durch einen kleineren physikalischen Speicher realisiertwird.

Z.B. Der Intel 80486 kann uber 32bit Adressen 4GB adressieren – meist sindjedoch nur vielleicht 16MB Hauptspeicher tatsachlich verfugbar. cBeispielsweise muß also zu einer logischen 32bit Adresse die zugehorige physika-lische 24bit Adresse bestimmt werden. Die Verhaltnisse:

CA cache/memory physical/virtual 1990block 4-128B 512B-8KB pagehit time 1 cycle 110 cycles hit timemiss time 8-32 cycles 100K-600K cycles miss timeaccess time 6-10 cycles 100K-500K cycles access timetransfer time 2-22 cycles 10K-100K cycles transfer timemiss rate 10−2 – 2 · 10−1 10−7 – 10−5 miss ratecache size 1KB – 256KB 4MB – 2GB memory size

Nur die jeweils gerade gebrauchten Daten befinden sich also im physikalischen

27 Giloi, S.127Def. Virtueller Speicher heißt das Konzept, Primar- und Sekundar-Speicher in einem gemein-samen einheitlichen Adreßraum einheitlich anzusprechen. Der physikalische Hauptspeicher wirdzum cache-Speicher des virtuellen Speichers. Der virtuelle Speicher wird in Seiten oder Kachelnaufgeteilt. Eine angesprochene Kachel, die sich nicht im Hauptspeicher befindet (page fault),wird aus dem Sekundar-Speicher nachgeladen und verdrangt dabei die Kachel, die am langstennicht mehr referenziert wurde (lru).


Speicher – alle anderen auf einem Hintergrund-Speicher, meist auf Disk. DasPrinzip zeigt Fig. 7.20.

Physical addresses

Disk addresses

Virtual addresses

Address translation

F720.pdfCOD, p581

Bei Bedarf mussen diese Daten von Disk in den Hauptspeicher nachgeladenwerden. Bei page, segment oder address fault veranlaßt das Betriebssystem dasNachladen der fehlenden Daten(-Blocke) und uberschreibt damit nach einer Ver-drangungsstrategie wie etwa FIFO oder meist LRU gegebenenfalls schon vorhan-dene Daten (-Blocke) im physikalischen Speicher.

Bem. Der Unterschied der Zugriffszeiten auf memory bzw. hard disk ist mitetwa drei Großenordnungen gigantisch: die miss penalty ist also extrem hoch. ◦Seiten- (paging) und Segment-Einteilung (segmentation) unterscheiden sich durchfeste oder variable Große der nachzuladenden Daten-Blocke.

Def. Fur die Seiten-Einteilung (paging) wird die logische Adresse in (page no,page offset) aufgeteilt. Die Umsetzung einer virtuellen Adresse

virtual page no page offset =⇒ physical page no page offset

auf eine phsikalische Adresse basiert auf der Seiten-Tabelle (page table). DieSeiten-Tabelle enthalt im Eintrag fur eine jede Seite mindestens

virtual page no −→ validity bit dirty bit protection page frame no . . .

mit physikalische Adresse = (page frame no, page offset) .

Bem. Die Adreß-Umsetzung zeigt Fig. 7.21.


3 2 1 011 10 9 815 14 13 1231 30 29 28 27

Page offsetVirtual page number

Virtual address

3 2 1 011 10 9 815 14 13 1229 28 27

Page offsetPhysical page number

Physical address

Translation

F721.pdfCOD, p582

Fig. 7.22 zeigt die Implementierung einer Seiten-Tabelle.

Page offsetVirtual page number

Virtual address

Page offsetPhysical page number

Physical address

Physical page numberValid

If 0 then page is not present in memory

Page table register

Page table

20 12

18

31 30 29 28 27 15 14 13 12 11 10 9 8 3 2 1 0

29 28 27 15 14 13 12 11 10 9 8 3 2 1 0F722.pdfCOD, p584

Seiten sind typischerweise wenige KB groß. Je kleiner die Seiten desto großer sinddie Seiten-Tabelle. Je großer die Seiten desto effizienter die Ubertragung von undzum Hintergrund-Speicher. ◦


Bem. aber etwa page thrashing beim Zugriff auf Felder, z.B. auf die Spalteneiner n× n-Matrix bei Seiten von n bytes! ◦Bem. Der erste Teil der Operanden z.B. einer Vektor-Instruktion kann in ei-ner Seite verfugbar, der restliche Teil nicht verfugbar sein: entweder wird dieVerfugbarkeit aller Operanden vor der Ausfuhrung gepruft, ein roll back vorge-sehen (reset points) oder interrupts zugelassen (save context in registers). ◦Das validity bit zeigt an, ob sich eine Seite im Haupt-Speicher befindet.Das dirty bit zeigt an, ob eine Seite verandert wurde und ob daher diese Seitebeim Verdrangen erst in den Hintergrund-Speicher zuruckzuschreiben ist.Die protection bits zeigen an, wer wie auf die Seite zugreifen darf.Weitere Felder zeigen etwa an, wann die Seite zuletzt referenziert wurde.

Z.B. Bei 32bit virtuellen Adressen also 4GB virtuellem Speicher und 4KB Seitenhat die Seiten-Tabelle 232/212 = 220 Eintrage. Bei 4Byte pro Eintrag ist die Seiten-Tabelle 4MB groß. cZ.B. Bei 28 bit virtuellen Adressen, 2KB Seiten und 4Byte Tabellen-Eintrag proSeite ergibt sich eine Seiten-Tabelle von 512KB. cBem. Die Große der Seiten-Tabelle laßt sich durch hashing reduzieren: Grundsatz-lich sind immer nur Teile der Seiten-Tabelle uberhaupt belegt. Eine hash-Funktionf bestimmt aus der virtual page number v die Nummer des Eintrags in einer hashtable, etwa f(v) = v mod p fur eine genugend große Primzahl p. Fur beispielsweisep = 13 ergibt sich

virtual page number 112 213 217 312 399 766 777 888 901hash table entry number 8 5 9 0 9 12 10 4 4

Bei Adress-Kollisionen wird der nachst hohere, freie Eintrag verwendet. ◦Bem. Die Große von inverted page tables ist proportional zur Große des physi-kalischen Speichers. Oder paging the page table ... ◦z.H. Vergleiche die verschiedenen Organisationen der Seiten-Tabelle. oBem. Zur Beschleunigung der Verwaltung wird oft ein Teil der Seiten-Tabellein einem cache-Speicher, dem translation lookaside buffer (TLB) gehalten.


Valid

1

1

1

1

0

1

1

0

1

1

0

1

Page table

Physical page addressValid

TLB

1

1

1

1

0

1

TagVirtual page

number

Physical page or disk address

Physical memory

Disk storage

F724.pdfCOD, p591

Jeder TLB-Eintrag enthalt also im Adreß-Teil einen Teil der virtuellen Adres-se und im Daten-Teil validity bit, dirty bit, protection und page frame number.Solche TLBs sind typischerweise 32B–8KB groß bei 4–8B Blocken = Tabellen-Eintragen, Trefferzeit von etwa einem Taktyklus, Fehlzugriffszeit von 20–30 Takt-zyklen und Fehlzugriffsraten von 0.01–1%. CA, S.437

TLBs sind haufig voll assoziativ organisiert, aus Geschwindigkeitsgrunden nichtnotwendig mit lru, meist mit write back.Beim Zusammenspiel von cache und virtuellem Speicher muß die virtuelle Adresseerst den TLB passieren, bevor per physikalischer Adresse auf den cache zuge-griffen werden kann. Fig. 7.25 zeigt TLB (vollassoziativ), address mapping undcache (direct mapped) der DECstation 3100: der cache wird uber physikalischeAdressen angesprochen.


Valid Tag Data

Page offset

Page offset

Virtual page number

Virtual address

Physical page numberValid

1220

20

16 14

Cache index

32

Cache

DataCache hit

2

Byte offset

Dirty Tag

TLB hit

Physical page number

Physical address tag

TLB

Physical address

31 30 29 15 14 13 12 11 10 9 8 3 2 1 0

F725.pdfCOD, p593

In welchen Rechnern wird der cache uber virtuelle Adressen angesprochen? ◦Def. Fur die Segment-Einteilung (segmentation) wird die logische Adresse durchzwei Anteile als (segment no, segment offset) dargestellt. Die Segment-Tabelle(segment table) enthalt fur jedes Segment mindestens

validity bit dirty bit protection segment base address length . . .

mit physikalische Adresse = segment base address + segment offset .

Bem. Segmente sind typischerweise mehrere KB bis MB groß. In der Segment-Tabelle konnen neben der Segment-Große auch Typ (Code, Daten oder Keller)abgelegt werden. Verschiedene Programme konnen auf dasselbe Segment, also aufetwa dieselbe Subroutine zugreifen (code sharing). ◦Vergleich von Seiten- und Segment-Einteilung


paging segmentation1-Wort-Adressen 2-Wort-AdressenHW-orientiert SW-orientiertSeiten fester Große Segmente variabler Große (code/data)daher einfache Blockersetzung daher schwierige Blockersetzunginterne Fragmentierung externe Fragmentierungungenutzter Teil einer Seite ungenutzte Teile des HauptspeichersNachteil: thrashing Nachteil: splinters, zusatzlicher Adder

Bem. Es gibt selbstverstandlich Mischformen: paged segments bestehen auseiner variablen Anzahl von Seiten (s. Fig. 4.20 in Verbindung mit Fig. 4.18 undFig. 4.19). Bei Seitenadressierung und Segmentierung besteht eine Hauptspei-cher-Adresse dann aus den drei Komponenten Segmentnummer, Seitenadresse(innerhalb des Segmentes) und Wortadresse (innerhalb der Seite). Meist wirddurch look up in einer Segment- und in einer Seiten-Tabelle adressiert, damit dieSeiten eines Segmentes im Speicher physikalisch nicht zusammenhangend seinmussen. ◦Z.B. MULTICS auf GE645, Honeywell 645 oder 6180 verwendete Ende der 60er Kuck, p.338

Jahre 18bit Segment- und 6bit Seiten-Nummern sowie 10bit Seiten-Offsets. c

6.2.3 Schutzvorkehrungen

In einer multi-programming Umgebung uberwacht am besten eine geeignete HW-Einheit die Zulassigkeit der Adressen, um sicherzustellen, daß jedes Programmnur auf Speicher-Bereiche zugreift, auf die es zugreifen darf. Falls die HW un-zulassige Adressen feststellt, wird eine memory protection exception ausgelost,also page ? oder segmentation violation.Sowohl in der Seiten- als auch in der Segment-Tabelle konnen zusatzlich Zugriffs-rechte (Lesen, Schreiben, Ausfuhren) etwa fur System oder Benutzer abgelegtund von geeigneter HW uberpruft werden.

Z.B. IBM/360 verwendete Schlussel-kontrollierten Speicherschutz: das Betriebs-system ordnet jedem Prozeß und seinem Speicherbereich genau einen access keyzu. Eine Speicherschutz-HW uberpruft diese Schlussel bei Speicher-Zugriffen. cZ.B. Die CDC6000 verfugte uber ein relocation address register (RA) und einfield length register (FL), so daß die Speicherschutz-HW prufen kann, ob die ef-fektiven Adressen im Intervall [RA,RA+ FL] liegen. cDef. Das capability addressing, also die Adressierung von Objekten im Speicheranstelle von Speicherzellen, erlaubt, den Zugriffsschutz zu verbessern, indem je-dem eindeutig durch seinen Namen zu identifizierenden Objekt eine Spezifikationder Zugriffsrechte zugeordnet wird.Z.B. Capability machine Plessey 250 (1972), Provable Secure Operating SystemPSOS (1979) oder Intel iAPX432 als Objekt-orientierter Prozessor. c


6.2.4 Direct Memory Access (DMA)

DMA-Hardware ermoglicht den Block-Transfer von Daten ohne CPU. CA, S.534,535, 537Def. DMA-Hardware ist ein spezieller Prozessor, der Daten zwischen Haupt-

speicher und E/A-Gerat unabhangig von der CPU ubertragt.

Die CPU ladt die DMA-Register mit der Speicheradresse und der Anzahl der zuubertragenden Bytes, die DMA-Hardware besorgt die Ubertragung und meldetder CPU die Erledigung der Ubertragung.Es kann mehrere DMA-Gerate geben, die DMA-HW ist oft Teil des Controllerseines E/A-Gerates.

Werden in einem System mit virtuellem Speicher bei der Ubertragung physikali-sche Adressen verwendet, ergeben sich Probleme, da die zu ubertragenen Seitennicht notwendig sequentiell im physikalischen Speicher abgelegt sind (worauf dieDMA-HW getrimmt ist). Daher benutzt das virtuelle DMA logische Adressen,die wahrend der Ubertragung in physikalische Adressen umgesetzt werden. Dannmussen die zu ubertragenen Puffer nur ‘virtuell’ sequentiell sein und konnen ver-streut im physikalischen Speicher abgelegt sein.

Z.B. Speicherverwaltung des Intel 80286 (segments)Segmente spiegeln die logische Struktur eines Programmes wider: Im 80286 gibt Bahring,

S.332ffCA, 8.6

es die vier 2byte Segment-Register CS, SS, DS, ES (code, stack, data und extradata), deren Attribute (6byte) im hidden segment descriptor cache vorgehaltenwerden.CS zeigt auf das aktuelle code segment und SS auf das stack segment. DS wie ESzeigen auf Daten-Segmente.Instruktionen werden aus dem code segment mit der Adresse CS:IP geladen. DasCS Register kann nur indirekt durch interrupts, exceptions, traps oder far jumpsverandert werden.Parameter, Rucksprungadressen usw. werden auf dem stack mit der AdresseSS:SP abgelegt. Das Register SS laßt sich explizit laden.DS zeigt auf das default data segment. Strings werden generell im extra data seg-ment abgelegt, auf das ES zeigt. DS und ES lassen sich explizit laden. Segmente,deren Anfangsadresse in einem Segment-Register vorliegt, befinden sich auch imHauptspeicher. Der 80386 hat FS und GS als weitere data segment register.Anhand des protection enable (PE) bit im machine status word (MSW) odergleichermaßen im controll register CR0 unterscheidet der Prozessor real (address)mode und protected (virtual address) mode.real mode: Der 80286 verhalt sich wie ein 8086 mit 20bit Adressen (fur maximal1MB Hauptspeicher).

physical address = (segment selector << 4) + 16bit offset

fur 16bit segment selectors. Segmente sind also maximal 64KB groß (16bit offset).protected mode: der 80286 erlaubt multitasking in einem 1GB großen virtuellenAdressraum, abgebildet auf einen maximal 16MB großen physikalischen Haupt-speicher (24 Adress-Leitungen). Selector verweist auf einen segment descriptor,


der Große und base address des Segmentes enthalt:

physical address = segment descriptor.base address +16bit offset

Ein 8byte segment descriptor umfaßt limit (Große), 3byte base address (alsomaximal 16MB physikalischer Speicher) und access rights (protection):

80386 base address31−24 G |D/B| 0 | AV | limit19−16 7,680286 access rights base address23−16 5,4

base address15−0 3,2limit15−0 1,0

wobei 1byte access rights aus dem bit P = ‘segment present in memory’, dem2bit descriptor privilege level (DPL) 0–3, dem bit S=1 fur segment descriptor(im Gegensatz zu S=0 fur control descriptor), dem bit E=1 fur executable (code)bzw. E=0 fur data, dem bit C/ED=1/0 fur conforming/non conforming fur codesegments (E=1) bzw. C/ED=1 fur expand down fur data segments (E=0), etwastacks, dem bit R/W, also read bit fur code segments und write bit fur datasegments und dem A = accessed bit (fur ‘lru’) besteht.

Zur Beschreibung der Segmente gibt es die global descriptor table (GDT) fur Seg-mente, auf die alle Prozesse zugreifen durfen, und Prozess-private local descriptortables (LDTs). Deskriptoren sind 8byte lang: maximal 64KB große (286) Seg-mente halten DTs mit maximal 8K Eintragen.Der Zugriff auf die GDT erfolgt uber das 5byte global descriptor table register(GDTR) mit 3byte base address und 2byte limit, d.h. Große.LDTs enthalten Deskriptoren der Prozess-privaten Code- und Daten-Segmente.Prozesse greifen normalerweise (es gibt Ausnahmen) nur auf eigene, d.h. privateSegmente zu.Fur neue Prozesse erzeugt das Betriebssystem eine LDT mit P=0: fur einen ak-tivierten Prozess ladt es zunachst alle Segmente mit P=0 von der disk, ermitteltdabei die base address (passende Speicher-Lucke) und setzt P=1. Damit das Be-triebssystem LDTs uberhaupt wiederfinden kann, wird fur jede LDT ein Eintragin der GDT angelegt. Fur deren access rights sind S=0 (control), E=0 (data),C/ED=0 (expand down), R/W=1 (zu schreiben) und initial A=0 zu setzen.Das 7byte local descriptor table register (LDTR) mit sichtbarem 2byte selectorund unsichtbarer 3byte LDT base address sowie unsichtbarem 2byte LDT limit(hidden descriptor cache) zeigt auf die LDT des aktiven Prozesses. Der Selektorin LDTR zeigt auf eine DT, aus der automatisch base address und limit in dasLDTR zur Beschleunigung des Zugriffes geladen werden.2byte Selektoren bestehen aus 13bit Indizes in eben DTs mit maximal 8K Ein-tragen, dem 1bit table indicator (TI) mit TI=1 fur Segment in LDT und TI=0fur Segment in GDT sowie dem 2bit requested privilege level (RPL), der mit demim DT-Eintrag abgelegten DPL verglichen werden muß. cZ.B. Seitenverwaltung des Intel 80386 (paged segments)paging ist wegen der Kompatibilitat auf segmentation aufgesetzt und kann ab- Bahring,

S.343geschaltet werden: im MSW ist bei paging das bit PG=1.


pages sind 4KB groß. (schnellere Adress-Rechnung, da Addition entfallt; aller-dings keine Entsprechung mehr zur logischen Struktur der Programme). Es gibtdrei Arten von Adressen:

virtual address = (2byte selector: 4byte offset)wird – wie gehabt – umgesetzt in

linear address = selector.DT.base address + offsetfalls der Prozessor kein paging durchfuhrt, gilt linear address = physicaladdress. Sonst wird die physikalische Adresse aus page aus 4KB page tableaus 4KB page table directory mit jeweils 1K 4byte Eintragen ermittelt,wobeilinear address = (10bit directory index, 10bit table index, 12bit offset)

directory index indiziert ein page table directory, dessen base address dascontroll register CR3 zur Verfugung stellt.

Im entsprechendem page table directory entry ist die base address einerpage table abgelegt.

page table index indiziert einen Eintrag dieser Seiten-Tabelle.

Im entsprechendem page table entry ist die base address einer page abge-legt.

physical address = (page base address, offset)

Da jede table 1K 4byte Eintrage aufweist, konnen alle Adressen durch Konkate-nation gebildet werden: Wenn jeder Prozess uber ein eigenes page table directorymit base address in den obersten 20bit von CR3 verfugt, ergibt sich

page table directory address = (20bit CR3, 10bit directory index aus linear ad-dress)

Der entsprechende page table directory entry enthalt die 20bit page table baseaddress, an Position 5 das accessed bit A, an Position 2 das user/supervisor bitU/S mit U/S=1 im user mode und U/S=0 im supervisor mode, an Position 1das read/write bit R/W mit R/W=write flag im user mode, sonst wildcard undan Position 0 das present bit P.

page table address = (20bit page table base address, 10bit page table index auslinear address)

Der entsprechende page table entry enthalt die 20bit page base address und istansonsten wie der page table directory entry aufgebaut. Nur an Position 6 gibtes noch ein dirty bit D mit D=1, falls die zugehorige Seite verandert wurde unddaher vor dem Verdrangen in den Hauptspeicher zuruckgeschrieben werden muß.

physical address = (page base address, offset)

page table directory und page table werden im assoziativen translation lookasidebuffer (TLB) vorgehalten. Dieser halt die letzten 32 zuletzt benutzen Eintrage


aus page table directory und page table. Falls also eine lineare Adresse bei ei-ner hit rate von > 90% im TLB vorhanden ist, so stehen die oberen 20bit derphysical address direkt im TLB zur Verfugung. Sonst muß die Adresse – wiegehabt – aus page table directory und page table Eintragen zusammengesetztwerden: P=0 oder page fault lost eine page fault exception aus: als Ausnahme-behandlung ladt das Betriebssystem entweder bei P=0 im LDT das Verzeichnisder Seiten-Tabellen, oder bei P=0 in einem Eintrag im page table directory eineSeiten-Tabelle oder bei P=0 in einem Eintrag einer page table eine Seite von disknach. Dabei steht in CR2 die Adresse der Seite zur Verfugung, die das page faultausgelost hat. cZ.B. Seitenverwaltung des Intel 80486 Der TLB ist 4-assoziativ. etc c Flik/Liebig,

1994, S.411Z.B. Protection des Intel Pentium call gates etc. c

Bahring,1991, S.372ffCA,pp453-456


7 Parallelisierung des Gauß’schen Algorithmus

Als einfuhrendes Beispiel dient der Gauß’sche Algorithmus zur Losung linearerGleichungssysteme. Die Losung erfolgt durch sukzessives Eliminieren von Unbe-kannten, d.h. durch Uberfuhren der Koeffizienten-Matrix A in Dreiecksgestalt.Das lineare Gleichungssystem A~x = ~b bestehe aus n Gleichungen in n Unbekann-ten; die Koeffizienten-Matrix A ist also quadratisch. Numerische Stabilitat wirdhier nicht berucksichtigt.

for(i=1; i<n; i++) // eliminiere die Unbekannte xi fur i = 1, . . . , nfor(j=i+1; j<=n; j++) // in der j-ten Gleichung, fur j = i+ 1, . . . , n

{ const double pivot=A[j][i]/A[i][i];

A[j][i]=0.0; // xi in j-ter Gleichung eliminieren// restliche Koeffizienten der j-ten Gleichung aktualisierenfor(k=i+1; k<=n; k++) A[j][k]-=pivot*A[i][k];

b[j]-=pivot*b[i]; // Koeffizienten der rechte Seite aktualisieren}

// Gleichungssystem hat jetzt Dreiecksgestalt: die Unbekannten xi// lassen sich aus

∑nj=iAij xj = bi von unten nach oben bestimmen.

for(i=n; i>0; i--) // bestimme xi fur i = n, n− 1, . . . , 1{ double tmp=b[i]; // berechne bi −

∑nj=i+1 Aij xj in tmp

for(j=n; j>i; j--) tmp-=A[i][j]*x[j];

x[i]=tmp/A[i][j];

}

Mehrere Fragen sind zu beantworten: Welche Operationen lassen sich – unterBerucksichtigung von Daten-Abhangigkeiten – uberhaupt parallelisieren? Wie-viele Prozessoren oder processing elements (PE) sollen zur Verfugung stehen?Wie kommen die PEs an die von ihnen benotigten Daten und wie werden – so-weit notwendig – Zwischenergebnisse ausgetauscht?Die Bewertung der Antworten erfolgt dann anhand von Kenngroßen wie Beschleu-nigung durch Parallelisierung, Auslastung der PEs und Kommunikationsaufwandin Abhangigkeit von der Art der angenommen Vernetzung.

7.1 parallele Berechnung

Wir unterstellen im Folgenden, daß A~x = ~b eindeutig losbar ist.

7.1.1 Eliminieren

Stellen wir zunachst n+ 1 PEs zur Verfugung, um x1 in der zweiten, dritten, . . . ,n-ten Gleichung, also in den n− 1 Gleichungen

∑nk=1 Ajk xk = bj fur j = 2, . . . , n

zu eliminieren. Dazu mussen die n Koeffizienten Ajk fur k = 1, . . . , n und der


Koeffizient bj der rechten Seite aktualisiert werden. Wegen

Ajk = Ajk − pAik und bj = bj − p bi mit pivot = p =AjiAii

und i = 1

sind diese Operationen Daten-unabhangig und konnen von den n+1 PEs parallelausgefuhrt werden. Bei jeder der Eliminationen von x1 in den n− 1 Gleichungensind ubrigens alle n+ 1 PEs (voll) beschaftigt.Die Elimination von x2 in der dritten bis n-ten Gleichung kann genauso parallelerledigt werden. Jetzt aktualisieren also jeweils nur n PEs n Koeffizienten in n−2Gleichungen. Allgemein gilt:

Fur i = 1, . . . , n− 1 wird xi eliminiert

durch Aktualisieren von jeweils n− i+ 2 Koeffizienten parallel durcheben n− i+ 2 der n+ 1 PEs, nacheinander in (n− i) Gleichungen.

n+1 PEs uberfuhren also die Koeffizienten-Matrix in Dreiecksgestalt und aktua-lisieren die rechte Seite in insgesamt (n−1)+(n−2)+. . .+1 =

∑n−1i=1 i = 1

2(n−1)n

ZE, wenn ein PE in einer Zeiteinheit (ZE) gerade einen Koeffizienten aktualisiert.Ein Mono-Prozessor-System braucht dafur (n+1)(n−1)+n(n−2)+(n−1)(n−3)+. . .+3·1 = 2(n−1)+(n−1)2+2(n−2)+(n−2)2+2(n−3)+(n−3)2+. . .+2+1 =2∑n−1

i=1 i+∑n−1

i=1 i2 = n(n−1) + 1

6(n−1)n(2n−1) = 1

6(n−1)n (2n+ 5) ZE. Der

Beschleunigungsfaktor β fur das Eliminieren durch diese Art der Parallelisierungist also

β =16

(n− 1)n (2n+ 5)12n (n− 1)

=2n+ 5

3=

2

3n

(1 +

5

2n

)≈ 2

3n fur n→∞

Dabei sind insgesamt 16(n − 1)n (2n + 5) PEs von insgesamt (PE-Anzahl ×

Eliminierungsschritte) = (n + 1) 12

(n − 1)n = 12

(n − 1)n (n + 1) PEs aktiv:die Auslastung α wahrend des Eliminierens betragt also

α =16

(n− 1)n (2n+ 5)12

(n− 1)n (n+ 1)=

1

3

2n+ 5

n+ 1≈ 2

3fur n→∞

Bem. Wenn PEs gleichzeitig lesend auf ein Datum zugreifen konnen, gibt eskeine Zugriffskonflikte (no memory contention)! ◦z.H. Bestimme obige Kenngroßen fur eine entsprechende parallele Version derEliminierung im Gauß’schen Algorithmus durch nunmehr (n− 1)(n+ 1) PEs. oz.H. Bestimme obige Kenngroßen fur die Eliminierung im Gaußschen Algorith-mus, wenn n ein Vielfaches der Anzahl der PEs ist. o

7.1.2 Auflosen

Die n + 1 PEs bestimmen nun parallel nacheinander xn, xn−1, . . . , x1. Sie be-rechnen also sukzessive bi

Aii−∑n

j=i+1AijAii

xj fur i = n, n − 1, . . . , 1 und zwar in


großenordnungsmaßig n + c∑n−1

i=1 ld i = n + c ld∏n−1

i=1 i = n + c ld((n − 1)!) ZE,

wenn jedes PE den AusdruckAijAii

xj bzw. biAii

gerade in einer ZE berechnet undfur das Aufsummieren eines eigenen mit einem fremden Zwischenergebnis gera-de c ZE braucht. Sequentiell sind dagegen 1 + (2 + d) + (3 + 2d) + . . . + (n +d(n− 1)) =

∑ni=1 i+ d

∑n−1i=1 i = 1

2((n+ 1)n+ d n (n− 1)) = n2(n+ 1 + d n− d)

ZE erforderlich, wenn eine (lokale) Summation gerade d ZE braucht. Da wegenn! ≈

√2π nn e−n

√n (Stirling) ld(n!) = ld

√2π + (n + 1

2) ldn + ln(e−n) ld e ≈

n ldn−n ld e gilt, ist der Beschleunigungsfaktor β aufgrund der Parallelisierung

β ≈ n

2

(n+ 1 + d n− d)

n+ c ld((n− 1)!)≈ 1

2

n (1+d) + 1−d1 + c (ldn−ld e)

≈ n

2

1 + d+ 1−dn

1 + c ld(ne)

fur n→∞

also β ≈ n2

1+d1+c ld(n/e)

und die Auslastung α der PEs ist

α =1

2

n (n+ 1 + c n− c)(n+ 1)(n+ c ldn)

=1

2

(1 + c

n− 1

n+ 1

)n

n+ c ldn≈ 1 + c

2fur n→∞

Bem. Wegen∑n−1

i=1 ld i = n ldn− 1ln 2

(n− 1) + g(n) fur ein g(n) ∈ O(ldn) gilt

β ≈ 1

2

n (n (1 + d) + 1− d)

n+ c (n ldn− n−1ln 2

)≈ 1

2

n (1 + d) + 1− d1 + c (ldn− 1

ln 2)≈ n

2

1 + d

1 + c ldnfur n→∞

asymptotisch fur β. ◦z.H. Bestimme obige Kenngroßen fur eine entsprechende parallele Version furdas Auflosen im Gauß’schen Algorithmus durch nunmehr (n− 1)(n+ 1) PEs. oz.H. Bestimme obige Kenngroßen fur das Auflosen im Gauß’schen Algorithmus,wenn n ein Vielfaches der PE-Anzahl ist. o

7.2 Kommunikation

Implizit ist bislang unterstellt, daß jedes PE uneingeschrankt auf alle Daten zu-greifen kann: die Daten liegen in einem gemeinsamen globalen Speicher (sharedglobal memory) vor und der aktualisierende Zugriff von zwei PEs auf dassel-be Datum muß synchronisiert werden. Aufgrund dieser Annahme konnten obigeKenngroßen insbesondere fur das Auflosen bestimmt werden.Wenn allerdings aus Grunden der Geschwindigkeit, des Zugriffsschutzes, der Kos-ten oder auch der Ausfallssicherheit lokale Speicher und spezielle Verbindungs-strukturen fur die PEs vorgesehen werden, mussen auch die Kosten fur die Inter-Prozessor-Kommunikation in Rechnung gestellt werden.

memory

PE1

6?

PE2

6?

· · · PEn+1

6?


Gesetzt den gunstigsten Fall, daß die PEs so angeordnet sind, daß die Koeffizi-enten Ajk bzw. bj dem k-ten PE direkt zugefuhrt werden. Dann kommt zu jedemSchritt der Eliminierung noch der Kommunikationsoverhead: initial werden dieKoeffizienten A1k und b1 der ersten Gleichung geladen, dann werden A2k und b2

der zweiten Gleichung geladen und aktualisiert, dann A3k und b3 usw. bis zuletztdie Koeffizienten Ank und bn der n-ten Gleichung geladen und aktualisiert wer-den.Entweder legen die PEs die aktualisierten Koeffizienten in genugend großen loka-len Speichern ab oder sie schreiben sie (zugleich) wieder in den globalen Speicherzuruck.Angenommen, die mit einer Aktualisierung verbundene Kommunikation koste cZE. Dann ist 1

2c (n− 1)n ZE der Kommunikationsaufwand fur die parallele und

16c (n − 1)n (2n + 5) ZE derjenige der sequentiellen Eliminierung und fur die

Beschleunigung folgt wieder

β =16c (n−1)n (2n+5)

12c n (n−1)

= 2n+53

= 23n(1 + 5

2n

)≈ 2

3n fur n→∞

In diesem gunstigsten Fall, wo die Speicherzugriffsbreite so wie die Anzahl derPEs gesteigert werden kann, bleibt auch die Auslastung α ≈ 2

3unverandert.

Gesetzt der ungunstige Fall, daß die PEs Ketten-formig angeordnet sind und dieKoeffizienten – wie etwa in Transputer-Netzen – nur uber genau ein Interface-Prozessor PEo durch die Kette der verarbeitenden PEs durchgereicht werdenkonnen.

PE0-PEn+1

- PEn - · · · - PE1

6

Wenn wie bislang PEs den Spalten der Koeffizienten-Matrix fest zugeordnet sind(PEk bearbeitet Ajk bzw. bj) und wenn alle PEs zu einem Zeitpunkt dieselbe,j-te Gleichung bearbeiten, dauert es (n+ 1) c ZE, bis die Koeffizienten der erstenGleichung in die vorgesehenen PEs geladen sind. Der auf Null zu setzende Koef-fizient werde im folgenden nicht extra geladen. Die n Koeffizienten fur die zweitebis n-te Gleichung werden jeweils in n ZE geladen, also in insgesamt n (n − 1) cZE. Zur Elimination von x2 mussen in n − 2 Gleichungen jeweils n − 1 Koeffi-zienten geladen werden, in insgesamt (n − 1)(n − 2) c ZE, usw. bis zuletzt nurnoch ein Matrix-Koeffizient und der Koeffizient der rechten Seite zu laden sind,in insgesamt 2 · 1 c ZE. Zusammen ergibt sich ein Kommunikationsaufwand vonc((n + 1) + n(n − 1) + (n − 1)(n − 2) + · · · + 2 · 1) = c((n + 1) + (n − 1) +

(n− 1)2 + (n− 2) + (n− 2)2 + · · ·+ 1 + 12) = c((n+ 1) +∑n−1

i=1 i+∑n−1

i=1 i2) =

c (n+ 1) + c2

(n− 1)n+ c6

(n− 1)n (2n− 1) = c (n+ 1) + c6

(n− 1)n (2n+ 5).Wenn der Mono-Prozessor c1 ZE fur einen Speicherzugriff braucht, ist die Be-schleunigung β aufgrund Parallelisierung

β =1+c1

6(n−1)n (2n+5)

12n (n−1)+c (n+1)+ c

6(n−1)n (2n+5)

= 112 n (n−1)+c (n+1)

1+c16 (n−1)n (2n+5)

+ c1+c1

≈ 1+c1c

fur n→∞.


Bei dieser Verbindungsstruktur der PEs wird der Geschwindigkeitsgewinn durchParallelisierung der Eliminierung in diesem (schlechten) Fall durch den Kommu-nikationsaufwand zunichte gemacht.

z.H. Auf einem Chip lassen sich PEs gunstig Gitter-formig anordnen. Berechne

β und α fur quadratisch angeordnete (n+12 )

2PEs. o

7.3 Parallelisierung des Gauß’schen Algorithmus durchden Compiler

Compiler sind grundsatzlich in der Lage, code zu vektorisieren bzw. zu paral-lelisieren. Grundlage ist – wie im Beispiel – eine Datenfluß-Analyse, die Daten-Abhangigkeiten erkennt, soweit moglich auflost und Vektor-Operationen oder so-gar parallelen Code erzeugt.

Z.B. vektorisierende FORTRAN-compiler etwa auf der Convex C1 c


8 Parallele Rechnerstrukturen

Parallele Rechner-Strukturen werden grob als SIMD (single instruction – mul- B&H, Ch.7COD, Ch.9tiple data), MIMD (multiple instructions – multiple data) und alternative Rech-

nerstrukturen wie z.B. Datenfluß-Maschinen oder Neuronale Netze klassifiziert(Flynn).Beispiele fur SIMD-Rechner sind assoziative Prozessoren, Feld-Rechner (arrayprocessors), hypercube-Rechner usw. Im Gegensatz zu pipeline-Strukturen mitihrer Reihe von Stufen verschiedener spezialisierter Verarbeitungseinheiten wirdeine Berechnung in einem SIMD-Rechner uber mehrere gleichartige Verarbei-tungseinheiten (processing elements (PEs)) verteilt.MIMD-Rechner sind Multi-Prozessor-Systeme, die entweder uber einen gemein-samen, globalen Speicher (common, global memory) Daten austauschen und da-mit eng gekoppelt sind oder die uber eigenen, lokalen Speicher (local memory)verfugen, nur uber Botschaften kommunizieren und damit lose gekoppelt sind.

Schon CPU und eigenstandige E/A-Einheit stellen eigentlich eine parallele Rech-ner-Architektur dar. Bei Großrechnern sind Doppel-, Vierfach- oder Mehrfach-Prozessoren gebrauchlich. Seit etwa 1970 gibt es die ersten Feld-Rechner, z.B.DAP von ICL.

Z.B. Zum Addieren von 217 Zahlen auf 128 = 27 PEs berechnet jedes PE dieSumme von 1024 = 210 Zahlen.

sum=0.0; for(i=0; i<1024; i++) sum+=local_array[i];

Dann sendet eine Halfte der PEs der anderen Halfte die eigenen Ergebnisse zumAufaddieren, von denen wieder eine Halfte die eigenen Teilsummen der anderenHalfte sendet, bis auf diese Weise schließlich ein PE die Gesamt-Summe bestimmt.

limit=128; half=128;

repeat

half=half/2; // send vs receive dividing line

if (half<=Pn && Pn<limit) send(Pn-half,sum);

if (Pn<half) sum=sum+receive();

limit=half; // upper limit of senders

until (half==1)

Pn ist die betrachtete der ausfuhrenden PEs, send(p,v) sendet den Wert v uberdas Verbindungsnetzwerk an Prozessor p, wahrend receive() die betreffendePE veranlaßt, einen Wert uber das Netz entgegenzunehmen. cz.H. Jedes PE entspreche einem MIPS R2000. Welcher Beschleunigungsfaktorergibt sich beim parallelen Einsatz von 2, 4, · · · , 28 PEs? Welche Annahmen sinddabei uber die Inter-Prozessor-Kommunikation, den Zugriff auf globalen Speicherusw. zu treffen? o


z.H. Welche Interprozessor-Kommunikation ergibt sich alternativ, wenn dieBinar-Darstellung von Pn verwendet wird? oz.H. Wie werden n Zahlen summiert, wenn n kein Vielfaches der Anzahl derProzessoren ist? oDie bestandig wachsenden Anforderungen an Rechenleistung (s. ‘grand challan-ges’) konnen trotz der immensen Leistungssteigerung aufgrund von technologi-schen Verbesserungen, insbesondere also Steigerung der Taktraten und des Inte-grationsgrades und damit der Schaltgeschwindigkeiten, mit konventionellen Rech-nern nicht befriedigt werden. Grund dafur ist der strukturell bedingte Fla-schenhals der von-Neumann-Architektur. Daher ist man an anderen Rechner-Strukturen, etwa den ‘massiv parallelen’ Rechnern mit z.B. 65536=256×256 Re-chen-Elementen interessiert. Moglich werden solche Rechner aber erst durch dietechnologische Entwicklung, also Integration ↗, Stromverbrauch ↘, Geschwin-digkeit ↗, Zuverlassigkeit ↗ und Kosten ↘.

Z.B. Sequents Multi-Prozessor-System Sequent Symmetry bestand 1986 aus P&H, p.616,fig. 9.112...32 gangigen 80386-CPUs jeweils mit FPU, mit eigenem elaborierten 64KB

cache und aus 1...6 zweifach verschrankten Speicher-Modulen mit 8...40MB undjeweils eigenem memory controller an einem 64bit breiten, 53MB/sec schnellenBus. Unter UNIX ergab sich eine fast lineare Beschleunigung durch Einsatz vonbis zu 28 Prozessoren. cZ.B. Thinking Machines’ CM-2 (Connection Machine), z.Zt. des MIPS R2000,besteht aus bis zu 216 = 65536 PE’s, jedes PE aus 1-bit-ALU, 4 1-bit-Registern P&H, p.599,

fig. 9.3und 64Kbit Speicher. Je 32 PE’s kann ein FPA (floating point accelerator) zuge-ordnet werden. Die CM-2 kann dann sowohl als System von 216 einfachsten PE’soder als System von 211 = 2K 32-bit-Rechnern jeweils mit Floating Point Unitaufgefaßt werden.Nur vier verschiedenen Chip-Typen werden gebraucht: erstens ein Chip mit 161-bit-PE’s, zweitens ein DRAM-Chip, drittens ein Interface-Chip zum FPA undviertens ein FPA-Chip. Die CM-2 besteht also aus 4K PE-Chips, 22528 DRAM-Chips (wegen ECC) und aus je 2K Interface- und FPA-Chips.Die 16 1-bit PE’s sind auf dem PE-Chip vollstandig verbunden, die 4K PE-Chipsals Boolean 12-cube (s.u.).Die typische Instruktion operiert auf Register und lokalem Speicher. Das Ergeb-nis wird je nach Inhalt eines weiteren Registers in ein Register oder in den lokalenSpeicher geschrieben.Eine 32-bit Addition dauert auf einem PE ca. 21µsec, auf einem MIPS R20000.066µsec (register) oder 0.198µsec (cache). Fur eine einzelne Addition ist alsoder MIPS R2000 100 bis 200 mal schneller als ein PE der CM-2. Die CM-2 weistallerdings eine 200 bis 600-fache hohere Rate von 32-bit Additionen auf als derMIPS R2000.


front end(SISD)

sequencer

16K processorsplus 512 FPAs




Data

vault

disk

array

Der Sequencer entspricht einem Mikro-Programm-Controller. Es gibt 8K I/O-channels zum frame buffer und zum Disk-System. c

8.1 Verbindungsstrukturen

Die Verarbeitungseinheiten eines SIMD-Rechners, die Prozessoren eines Multi-Prozessor-MIMD-Systemes genauso wie die Verarbeitungseinheiten einer Datenfluß-Maschine, einer Reduktionsmaschine, eines Transputers oder die Neuronen einesNeuronalen Netzes mussen Daten austauschen konnen. Verbindungsnetzwerke(interconnection networks) ermoglichen Steuerung (Signalisierung) und Aus-tausch von Daten oder Botschaften.

Die Knoten in einem abstrakten Multiprozessor-Netz bestehen aus Prozessoren,Speicher und links.

Prozessoren konnen im master/slave-Verhaltnis stehen; Kommunikationsverbin-dungen konnen Leitungs- oder Paket-vermittelt sein; mehrstufige Vermittlungerlaubt einfachere Vermittlungsstellen zulasten der Ubertragungsdauer; zentrali-sierte Kontrolle mit synchroner Kommunikation steht dezentralisierte Kontrollemit asynchroner Kommunikation (bei Bedarf) gegenuber.

Merkmale von Verbindungsnetzwerken sind etwa Kommunikationsdurchmesser(maximale Anzahl von Vermittlungsrechnern und damit maximale Laufzeit ei-ner Nachricht zwischen je zwei Knoten), Erweiterbarkeit (gemessen an Kostenfur einen zusatzlichen Knoten: fix im Ring, linear im Stern, quadratisch imKreuzschienen-Verteiler, logarithmisch im Baum), Redundanz (Anzahl verschie-dener Kommunikationspfade zwischen je zwei Netz-Knoten), Verbindungsgrad(Eingangs-/Ausgangsgrad pro Knoten, z.B. 4 fur Gitter, 12 fur CM-1 usw.),Bandbreite und Latenz (minimale, maximale oder durchschnittliche Zeit zwi-schen Absenden und Empfang).

Beispiele fur Verbindungsstrukturen sind


single bus ist einfach, erlaubt aber nur einen Kommunikationsvorgang zu einerZeiteinheit, z.B. Sequent Symmetry.

multiple bus erkauft parallele Kommunikation mit hoherem Aufwand fur sche-duling und Sicherung der (cache-) Koharenz;

Stern weist mit dem zentralen Verteiler (hub) einen Daten- und Steuer-Flaschen-hals sowie eine Schwachstelle auf.

Kreuzschiene etwa zwischen p Prozessoren und m Speicher-Einheiten erlaubenbei einem Aufwand≈ p·m gleichzeitig min(p,m) Kommunikationsvorgange.Kreuzschienen-Verteiler werden z.B. in Transputer-Netzen (s.u.) eingesetzt.bit/Kanal n× n Taktrate Ubertragung Technologie

1 16×16 – 64×64 .4–2.4Ghz 50–300MB/s GaAs8 16×16 50–70MHz 50MB/s CMOS

Volle Vernetzung von etwa p Prozessoren erfordert einen Aufwand ≈(p2

). Pro-

blematisch hinsichtlich der Erweiterbarkeit ist der durch die Prozessorenfest vorgegebene maximale Verbindungsgrad.

Ringe haben eine Ubertragungszeit ≈ p bei p Prozessoren im Ring.

Baume werden entweder mit Knoten mit einem Verbindungsgrad von 2 durch lo-kale Busse in jeder Ebene oder mit Knoten eben mit hoherem Verbindungs-grad, beispielsweise 3 fur binare Baume (moglicherweise sind Teilbaumedurch Kreuzschienen-Verteiler zu clustern verbunden, z.B. Goodyear’s mas-sively parallel processor MPP )

Gitter bilden die klassische Verbindungstopologie etwa in Transputer-Systemen,aber z.B. auch in Systemen wie ILLIAC IV, MPP, CM-1 usw.

Z.B. Der Transputer ist ein Computer-Bauelement zum Aufbau komplexerComputer-Systeme aus (sehr) einfachen Computern.Das Programmier-Paradigma ist das der kommunizierenden sequentiellenSoftware-Prozesse von Hoare (CSP), realisiert in OCCAM oder C-Erweite-rungen. Prozesse kommunizieren unidirektional uber Kanale. Es ist Aufgabedes Programmierers, Blockaden oder Verklemmungen (deadlocks) auszu-schließen.Ein Transputer besteht aus Prozessor-Chip mit On-Chip-RAM, gegebe-nenfalls Interfaces zu Speicher, Disk oder Graphik und den Link-Interfaces.Links sind schnelle serielle Kommunikationskanale zwischen den Transpu-tern mit Ubertragungsraten von 5Mbit/s, 10Mbit/s oder 20Mbit/s (nur furkurze Entfernungen). Jeder Transputer kommuniziert uber die vier linksmit seinen vier Nachbarn im N, W, S und O.


INMOS Typ Architektur On-Chip-RAM Links

T414 32 bit 2KB 4

T800 32 bit 4KB 4 + floating point unit

T212 16 bit 4

M212 16 bit 4KB 2 + disk controller

Die naheliegende Verbindungsstruktur bei vier Links ist das Gitter mitdirekter Kommunikation nur zwischen benachbarten Transputern. (JederGitter-Knoten kann selbst wieder aus vier vollstandig miteinander ver-bundenen Transputern bestehen.) Uber Router-Prozesse konnen auch Pro-zesse auf nicht benachbarten Transputern miteinander kommunizieren. Eskonnen auch andere Topologien (Felder, Ringe, Baume usw.) aufgebautwerden. Transputersysteme variabler Topologie erlaubt der Einsatz der ein-stellbaren Kreuzschienenverteiler C004.

Der Prozessor mit drei 32bit Arbeitsregistern, RISC-Befehlssatz mit 16Grundbefehlen und weiteren ‘erweiterten’ Befehlen fuhrt mit den BefehlenSTART PROCESS, RUN PROCESS usw. Prozess-Verwaltung sowie die Kommu-nikation zwischen Prozessen uber Kanale durch. Fur den Programmierer isttransparent, ob es sich um Prozessor-lokale Kommunikation (im Speicher)oder um Inter-Prozessor-Kommunikation (uber links) handelt!

Aktuelle Transputer-Systeme, wie etwa das GC-System (Grand Challenges)von Parsytec mit seiner dreidimensionalen regularen Gitter-Topologie, ver-wenden etwa den T9000, einen ausgewachsenen Risc-Prozessor mit 50MHz,5-stufiger pipeline mit Integer-ALU, 64bit-FPU, 200MIPS, 25MFLOPS undeiner Kommunikationsbandbreite von insgesamt 100MB/s.Die Knoten im GC-System, die sogenannten GigaCubes, bestehen aus 16+1T9000, 4 routing switches C104 und bis zu 512MB RAM. Jeder der bis zu256 GigaCubes leistet mehr als 1GFLOP. c

staged networks brauchen zur Verbindung von etwa n = 2e Prozessoren mitn Speichern ≈ n

2log2 n Vermittlungsstellen mit zwei Eingangen und zwei

Ausgangen. Verbindungen werden aber auch uber kleine Kreuzschienen-Verteiler (2×2 bis 8×8 mit oder ohne broadcast) hergestellt.

hypercubes sind rekursiv definiert: ein (d+1)-cube besteht aus zwei d-cubes: dielabel (Adresse) der Knoten des ersten d-cubes werden vorne um 0, die deszweiten um 1 erweitert. Die 0-label Knoten sind mit den 1-label Knotenverbunden. Der 0-cube besteht aus einem (20) isolierten Knoten, der 1-cube aus 21 verbundenen Knoten 0 und 1, der 2-cube aus 22 Knoten 00,01, 10 und 11, verbunden wie die Ecken eines Quadrates. der 3-cube aus 23

Knoten, verbunden wie die Ecken eines Wurfels der 4-cube aus 24 Knoten,verbunden wie die Ecken eines 4-dimensionalen Wurfels usw. (s. Fig. 7.11bis Fig. 7.13)Knoten (pd−1, . . . , p0) und (qd−1, . . . , q0) im d-cube sind also verbunden ge-nau dann, wenn |{i : pi 6= qi}| = 1. Zu den 2d Knoten gibt es insgesamt


d 2d−1 Verbindungen. Information wird im d-cube vom Knoten (pd−1, . . . , p0)zum Knoten (qd−1, . . . , q0) mit {i : pi 6= qi} = {i1, . . . , ir} etwa uber dier − 1 Zwischen-Knoten (pd−1, . . . , qi1 , . . . , p0), (qd−1, . . . , qi1 , . . . , qi2 . . . , q0)

usw. ubermittelt. Statt der im Gitter mit 2d Knoten maximal 2(√

2d − 1)Kommunikationsschritte sind im hypercube maximal log2(d) Schritte notig.Z.B. Die 4096 PE-Chips der Connection Machine CM-2 von Thinking Ma-chines sind als 12-cube verbunden. c

shuffle exchange network: aus Quell- und Zieladresse kann direkt die Schalter-Stellung (routing information) abgeleitet werden. Wenn der Zustand ei-nes 2×2-switches mit 1 fur ‘crossed’ und 0 fur ‘not crossed’ codiert ist, somussen, um p2p1p0 mit m2m1m0 zu verbinden, die drei 2×2-switches aufp2 XOR m2, p1 XOR m1 und p0 XOR m0 gesetzt werden (s. Fig. 7.14 undFig. 7.15 mit der Verbindung P6 nach M3). B&H, p.335

delta networks sind eine hierarchische, gestufte Erweiterung der shuffle exchangenetworks durch Verwendung von Kreuzschienen-Verteilern und durch dieMoglichkeit des broadcasting. Ein delta network mit k Stufen, von denenjede aus m×n-Kreuzschienen-Verteilern mit m Eingangen und n Ausgangenbesteht, weist zwischen jedem der insgesamt mk Ein- und nk Ausgangegenau einen Verbindungspfad auf. Die Zieladresse zur Basis n bestimmtauch hier die Stellung der Kreuzschienen-Verteiler.

Die Charakteristika der verschiedenen Verbindungsstrukturen seien nun gegen-ubergestellt (s. Giloi, Tabelle 10-4, N ist die Gesamtzahl an PEs, Durchmesserist die Anzahl der Zwischenstufen auf dem langsten Weg).

Topologie skalierbar Durchmesser #ports #switches # links

Bus ja 1 1 – N

Ring ja N − 1 2 – N

2D-Gitter ja 2√N − 2 4 N ? 2N ?

mehr-stufig ja logN 1 N logN N logN

Benes ja 2 logN − 1 1 N(logN − 1/2) N(2 logN − 1)

hypercube nein logN logN N logN N logN/2

crossbar ja 1 1 1 N ×N -crossbar 2N

crossbarh stages

ja 2h+ 1 hhC fur C = h

√N

C × C-crossbars2hC

Anwendungen sind etwa Losen von (großen) Gleichungssystemen (FEM) oderBildverarbeitung. Probleme enstehen, falls mehr Matrix-Elemente oder mehr pi-xel zu verarbeiten sind, als Verarbeitungseinheiten vorhanden sind.

Forderung: die Anzahl der Verarbeitungseinheiten sollte fur den Programmierertransparent sein (vgl. Datenfluß-Maschinen, in gewisser Weise auch Transputer).

Heuristik beim Aufbau von Verbindungsstrukturen:Verarbeitungseinheiten werden in mehrere Cluster gruppiert, die ihrerseits alspipeline-Baum oder hypercube verbunden sind, weil


• die Block-Struktur von Programmen mit geringer Parallelitat zwischen denBlocken am ehesten kleinen Gruppen eng zusammenarbeitender Prozesso-ren entspricht

• und weil die vom Compiler auf Block-Ebene erzeugte Parallelitat am bestendurch pipeline-Verarbeitung ausgenutzt wird.

8.2 SIMD

Def. SIMD liegt dann vor, wenn mehrere gleichartige Verarbeitungseinheiten –gesteuert durch eine einzige Kontroll-Einheit auf einem Befehlsstrom – mehrereDatenstrome abarbeiten.

Z.B. Gangige Organisationsformen fur SIMD-Maschinen sind bit slice und bitplane (s. Fig. 7.18).

Institution Name #PE a bit MHz #FPU MB/PE MB/s JahrUniv.IL Illiac IV 64 64 5 64 0.125 2560 1972ICL DAP 4K 1 5 0 2 2560 1980Goodyear MPP 16K 1 10 0 2 20480 1982ThinkingMachines

CM-2 64K 1 72K

(opt).512 16K 1987

Maspar MP-1216 16K 4 25 0256/1024

23000 1989

cZ.B. Prozessoren in bit slice Technologie durchsuchen Datenbanken assoziativ,d.h. uber vorgegebene Feld-Inhalte und nicht uber etwa einen Index.bit slice Prozessoren fuhren Vektor-Operationen durch; processor arrays (PA)operieren auf zwei-dimensionalen Daten, wie Matrizen oder Bildern. cEs gibt diverse Organsisationen des Zugriffs der PEs auf den Speicher. Fig. 7.19schematisiert beispielsweise a) MPP von Goodyear, b) STARAN von Goodyearund c) ILLIAC IV.Erstens, die Kontroll-Einheit verfugt uber einen eigenen Programm-Speicher, dieVerarbeitungseinheiten verfugen uber lokale Speicher oder zweitens, die Verar-beitungseinheiten teilen sich den oder Teile des gemeinsamen Speichers (sharedmemory) oder drittens, Kontroll-Einheit und Verarbeitungseinheiten greifen aufdenselben Speicher zu, die Verarbeitungseinheiten schreiben moglicherweise nurin eigene Speicher-Bereiche.

Z.B. STARAN wurde 1972 von Goodyear Aerospace als Prozessor fur assozia-tive Speicher Operationen in bit slice Technik entwickelt. Jedes PE in STARANkonnte auf den Speicher wortweise und bit slice-weise zugreifen. STARAN ist derVorlaufer zu MPP. c


Z.B. Die connection machine CM-2 ist LM-SIMD (local memory) mit 16 PE-Moduln als Knoten von hypercubes, also z.B. 9-cube mit 29 Knoten a 16 PEsund damit insgesamt 29 · 24 = 213 = 8192 PEs oder z.B. 12-cube mit 212 · 24 =216 = 65536 PEs. cEinige Anwendungen seien angedeutet: B&H, p344ff

1. assoziative Suche heißt, Datenbank-Eintrage uber vorgegebene Merkmalezu finden. Bei ebenso vielen PEs wie Datensatzen, ist die Laufzeitdes Algorithmus unabhangig von der Große der Datenbank! (s. Fig. 7.24)

R1 = search argument (pattern);

R3 = (1,...,1); // initialize ‘=’ register

R4 = (0,...,0); // initialize ‘>’ register

for (i=0; i<k; i++)

{ R2 = Memory[i]; // load bit slice i

if (!leftbit(R1)) // leftbit(R1)==0

{ R4 = R4 | (R3 & R2); // set ‘>’ register

R2 = !R2; // invert for equality test

}

R3 = R3 & R2; // set ‘=’ register

R1 = R1 << 1; // shift left argument

}

Am Ende des Schleifenrumpfes markiert R3 jeweils die Worte, deren Anfangmit dem Anfang des Argumentes ubereinstimmen – invariantR3=(slice[0]==R1[0])&(slice[1]==R1[1])&...&(slice[i]==R1[i]),wo == fur die komponentenweise Gleichheit eines bit-Vektors mit einem bitsteht. R4 markiert dagegen jeweils die Worte, deren Anfang lexikographischgroßer als der Anfang des Arguments ist.

2. Vektor-Addition in bit slice Technologie: Um zwei N bit integer Felder Aund B zu addieren und das Ergebnis im Feld C zu speichern (s. Fig. 7.25),kann folgender Algorithmus fur die Register R2, R3 R4 dienen:

R4 = (0,...,0); // initialize carry register

for (i=N-1; i>=0; i--)

{ R2 = A[i]; R3 = B[i]; // load args

// C[i] = A[i]+B[i]+carry = result

// = (not R4 and (R3 xor R2)) or (R4 and not(R3 xor R4))

C[i] = (~R4 & (R3 ^ R2))+(R4 & ~(R3 ^ R2));

// carry

// = (not R4 and (R3 xor R2)) or (R4 and not (R3 xor R2))

R4 = (~R4 & (R2 & R3))+(R4 & ~(R2 ^ R3));

}


Der Laufzeit-Aufwand des Algorithmus ist proportional zu N .

3. blurring ist ein Beispiel aus der Bildverarbeitung: durch Filtern soll derRausch-Anteil in Raster-Bildern (entstanden etwa bei der Ubertragung)reduziert werden. Dazu wird ein Eingabe-Bild (Ii,j) i = 0, ..., n− 1

j = 0, ...,m− 1

unter Ver-

wendung von quadratischen Filter-Masken (Mi,j) i = −r, ..., rj = −r, ..., r

in ein Ausgabe-

Bild (Oi,j) i = r, ..., n− rj = r, ...,m− r

mit Oi,j =∑r

ν=−r∑r

µ=−rMν,µ · Ii+ν,j+µ uberfuhrt

(s. Fig. 7.27). Typische Werte fur r sind r = 1, . . . , 5.

Z.B. Fur Mi,j = 1(2r+1)2

entspricht der Grauwert eines jeden pixel imOutput-Bild dem Mittelwert der Grauwerte der pixel im Eingabe-Bild, dieinnerhalb der am pixel zentrierten Maske liegen. cZ.B. Um ein 1K×1K Eingabe-Bild mit einer (−2..2)×(−2..2)-Filter-Maske(r=2) zu filtern, sind 1M pixel ×(2r+1)2 = 25M Multiplikationen und Addi-tionen durchzufuhren, bei 30 Bildern pro Sekunde also ca. 1.5G Operationenpro Sekunde. cAngenommen, es gibt ebenso viele PEs wie pixel im Eingabe-Bild.Das PE Pi,j halt das pixel Ii,j im Eingabe-Bild und berechnet genau ein pixelim Ausgabe-Bild. Die PEs kommunizieren dazu mit ihren – entsprechendder Bild-Topologie – vier Nachbarn (s. Fig. 7.28: PE11 berechnet O11).In der ersten Phase des blurring-Algorithmus versendet die Kontroll-EinheitCU alle Masken-Elemente nacheinander an jedes PE. Das PE Pi,j berechnetdamit die Produkte Ii,j ·Mν,µ. In der zweiten Phase des blurring-Algorithmustauschen die PEs die Produkte ‘Maske*pixel’ aus, die sie zur Berechnungdes eigenen Output-pixels brauchen. Beispielsweise fur r = 1 empfangt etwadie PE Pi,j

von Pi−1,j das Produkt M−1,0 · Ii−1,j

uber Pi−1,j die Produkte M−1,−1 · Ii−1,j−1 bzw. M−1,1 · Ii−1,j+1 von Pi−1,j−1

bzw. Pi−1,j+1

die Produkte M0,−1 · Ii,j−1 bzw. M0,1 · Ii,j+1 von Pi,j−1 bzw. Pi,j+1

von Pi+1,j das Produkt M+1,0 · Ii+1,j unduber Pi+1,j die Produkte M+1,−1 · Ii+1,j−1 bzw. M+1,1 · Ii+1,j+1 von Pi+1,j−1

bzw. Pi+1,j+1.

Die Laufzeit des blurring-Algorithmus ist so proportional zur Große derMaske, nicht zu der des Eingabe-Bildes.

4. Matrix-Multiplikation durch ein lineares Feld von PEs: Seien zwei N ×N -Matrizen X und Y gegeben; Z = XY sei zu berechnen. Angenommen, esstehen N PEs zur Verfugung, die Kontroll-Einheit kann die lokalen Speicherlesen und Pj halt die Matrix-Elemente X.,j, Y.,j und Z.,j (initial 0). DerAlgorithmus laßt die PEs die Matrix Z zeilenweise berechnen (s. Fig. 7.30):


for (i=0; i<N; i++) for (j=0; j<N; j++)

{CU liest X = Xi,j von Pj und versendet X an alle PEsPEs berechnen Zeilen von Z parfor (k=1; k<=N; k++)

Pk berechnet und setzt Zi,k := Zi,k +X · Yj,k}

Die Laufzeit des Algorithmus ist so proportional zu N2 statt N3. EineAnwendung stellt beispielsweise der Gauß-Seidel-Algorithmus zur approxi-mativen Losung von LGS dar.

5. Bestimmung des maximalen Elementes (Wert und Index) in einem Feld mitn = 2e Zahlen durch 2e PEs in einem e-cube:Def. Zwei Knoten im e-cube heißen i-buddies genau dann, wenn sich ihreAdressen nur im i-ten bit unterscheiden.

for all PEs if (own_address mod 2 == 1)

send own_value, own_address to buddy(1, own_address);

for all PEs if (own_address mod 2 == 0)

receive buddy_value, buddy_address

from buddy(1, own_address);

n=1;

while (n < hypercube dimension)

{

for all PEs if (own_address mod 2**n == 0)

{

if (own_value>buddy_value) max=own_value;

else max=buddy_value;

if (own_value>buddy_value) adr=own_address;

else adr=buddy_address;

n++;

for all PEs

if (own_address mod 2**n == 2**(n-1))

send max, adr to buddy(n, own_address);

for all PEs if (own_address mod 2**n == 0)

receive buddy_value, buddy_address

from buddy(n, own_address);

}

}

for PE 0

{

if (own_value>buddy_value) max=own_value;

else max=buddy_value;

if (own_value>buddy_value) adr=own_address;

else adr=buddy_address;

}


Der Algorithmus nutzt also die Verbindungsstruktur im hypercube so, daßder Zeitaufwand nur e = log2 n statt n Zeiteinheiten betragt (s. Fig. 7.32).

Z.B. Das CNAPS Coprozessor-Board in einem PC als host stellt einen Vektor-Rechner dar, der speziell auf die Emulation von Neuronalen Netzen zugeschnittenist. c Labor ELKA


8.3 MIMD

Def. MIMD-Architekturen sind Multi-Prozessor-Systeme mit autonom arbeiten-den Prozessoren. Es gibt also keine zentrale Kontroll-Einheit.

Man unterscheidet GM-MIMD-Architekturen, d.h. Multiprozessor-Systeme mitProzessoren, die durch Zugriff – meist uber ein schnelles leitungsvermitteltes Ver-bindungsnetz – auf einen gemeinsamen Speicher (global memory) kommunizierenund daher eng gekoppelt sind, und LM-MIMD-Architekturen, d.h. Multiprozessor-Systeme mit Prozessoren, die nur uber lokale Speicher (local memory) verfugenund nur durch Botschaften (message based) – meist uber ein langsames Paket-vermitteltes Verbindungsnetz – miteinander kommunizieren und daher lose ge-koppelt sind. Es hangt im wesentlichen vom Verbindungsnetzwerk ab, ob derZugriff von Prozessoren auf den Speicher fur alle Prozessoren gleich schnell (uni-form) ist oder nicht (non uniform).

MIMD-Architekturen

central common memory distributed memory

Systeme mitwenigen Proz.

hochparallelmit zentralem

Speicher

distr.commonmemory

messagebased

multithreadedfine grain

virtualcommonmemory

Alliant

HEP

TERA

PRAM

DASH SUPRENUM *T MANNA

Z.B. Die Alliant FX/2800 bestand 1990 aus bis zu 7 Prozessor-Moduln, i.e. Giloi, S.399

Clustern von jeweils 4 Intel i860XL, die uber einen Kreuzschienen-Verteiler mit1.28GB/s auf bis zu 8 sekundare set-assoziative caches von 512KB und mit640MB/s auf bis zu 16 Speicher-Moduln mit je 64MB zugreifen. Der Speicherist zweifach verschrankt. Daher gibt es auch 2 Speicher-Busse. Weitere i860XLfungieren als IO-Prozessoren oder als Graphik-Subsystem (s. Bild 11-3). c Giloi, S.417

Wenn idealerweise moglichst viele Prozessoren auf einen zentralen Speicher mitfur die Programmierung globalen Adressraum zugreifen, stellt der Speicher mitden sich ergebenden Zugriffskonflikten einen Flaschenhals dar.

Abhilfe versprechen vielfadige Architekturen (multi threaded architectures): esgibt viele Daten-getriebene Akteure (Prozesse) in den Zustanden schlafend oderdormant und bereit oder ready. Kein Akteur wartet, sondern falls Argumente feh-len, wird sofort zum nachsten Akteur mit vorhanden Argumenten umgeschaltet.Bei derartig haufigen Kontext-switches sollen nur moglichst wenig Register zu


sichern sein, also sollen die Prozesse moglichst leichtgewichtig sein (light weigh-ted), so daß ein Prozess-Wechsel oder process switch typischerweise nur 10 Taktedauert.

Z.B. HEP steht fur den kommerziellen Heterogeneous Element Processor (1978-1985): bis zu 16 Process Execution Modules mit 8-stufigen pipelines fur integer-, Giloi, S.401

float-, load/store-Operationen usw. greifen uber ein dynamisch konfigurierbaresPaket-Vermittlungsnetz auf bis zu 128 Data Memory Modules zu (s. Bild 11-4).HEP ist eine vielfadige Architektur mit gemeinsamem Speicher. Eine Task hatmaximal 64 Kontroll-Faden. Der Prozess-Wechsel dauert 100ns, da nur zwischenden 64 Registersatzen in der 64×32=2048 Register-Datei umgeschaltet werdenmuß. Die Prozesse arbeiten Daten-getrieben; fur Register und Speicher wird derZugriffszustand full und empty in HW verwaltet. HEP wurde in einem Fortran77-Dialekt programmiert.Die TERA-Maschine von 1991 stellt eine Weiterentwicklung der HEP-Maschinedar. cPRAMs sind der Versuch, ideale MIMD-Maschinen mit gemeinsamen Speicherzu realisieren, i.e. alle Prozessoren konnen beliebig/gleichzeitig auf den gmein-samen Speicher zugreifen. Synchronisation erfolgt durch das Programm oder dieUberwachung kritischer Bereiche (critical regions).

Z.B. Parallel Random Access Machines, PRAMs (1990) stellen eine Familievon Multi-Prozessor-Systemen dar, u.a. unterschieden durch EREW, CREW Giloi, S.407

oder CRCW (exclusive/concurrent read/write), d.h. zu einem Zeitpunkt kann nurein/konnen mehrere Knoten eine Speicher-Zelle lesen/schreiben (vgl. Transputer-Systeme z.B. mit T9000). cBei Verwendung eines verteilten gemeinsamen Speichers ist die Konsistenz oderKoharenz der caches der einzelnen Prozesoren zu gewahrleisten, per broadcast,bus snooping oder per Invalidieren. In einem directory kann dabei vermerkt sein,in welchem cache welchen Knotens sich welche Daten befinden.

Z.B. Die Directory Architecture for SHared memory (DASH) von 1992 besteht Giloi, S.412

aus Clustern von Prozessoren, caches und Cluster-Speicher. Das directory dientzur Gewahrleistung der Konsistenz von Speicher-Objekten in den Zustanden un-cached, shared und dirty (s. Bild 11-7). cZ.B. Die *T-Maschinen (‘star t’ ) sind massiv parallele multi threaded architec- Giloi, S.419

tures mit verteiltem Speicher und globalem Adreßraum. Neben dem lokalen load

gibt es das remote rload, das durch ein fork erzeugt wird. Es gibt Arbeits- undSynchronisationsprozessoren, z.B. den Motorola 88110MP von 1992 mit seinerMessage and Synchronization Unit (MSU) (s. Bild 11-11). Entweder lost die MSUeinen Software-Interrupt aus und stoßt damit den Empfangsprozess an oder aberdas Benutzer-Programm testet durch polling der MSU, ob Nachrichten eingetrof-fen sind. cZ.B. Der SUPRENUM-Rechner der GMD von (1989-1992) besteht aus Vektor- Giloi, S.431

prozessor-Rechnerknoten mit 9MB=8MB+1MB ECC (s. Bild 12-3). 16 Arbeits-


, 2 Kommunikations-, ein IO- und ein Diagnose-Knoten sind uber 2 Parallel-Busse, die cluster-Busse A und B mit zusammen 320MB/s, zu einem clusterzusammengefaßt. 20 derartige Cluster sind durch ein doppeltes Ringbus-Systemmit je 20MB/s verbunden, i.e. 2D-Torus oder 4-cube (s. Bild 10-11). cZ.B. Ein Knoten im Manna-Rechner (Massively parallel Architecture for Nu- Giloi, S.434

merical and Non-numerical Applications) der GMD von 1992 besteht aus zweisuperskalaren Intel i80860XP (50MHz), dynamisch je als Communication- und alsApplication-Processor (s. Bild 12-5). Die Knoten arbeiten auf einem virtuellen ge-meinsamen Speicher (virtual shared memory) und sind uber eine konfigurierbareHierarchie von 16×16 Kreuzschienen-Verteilern mit je 50MB/s verbunden. Da-mit konnen etwa Clusterverbunde mit 40, Supercluster mit 192 oder Hyperclustermit 3000 Knoten aufgebaut werden. Manna-Rechner sind fur Anwendungen et-wa der Computer-Graphik (ray tracing) oder der Bildanalyse (Mustererkennung)entwickelt. c

8.3.1 MIMD-Maschinen mit Bus

Ausgefeilte caches sorgen fur geringe Latenz und geringen Bus-Verkehr bei meh-reren Mikro-Prozessoren (!) an einem Bus. P&H,

Fig. 9.17

Firma Name #PE a bit MHz #FPU SysMB MB/s JahrSequent Symmetry 30 32 16 30 240 53 1988SGI 4/360 16 32 40 16 512 320 1990Sun 4/640 4 32 40 4 768 320 1991

Z.B. Zum Addieren von 105 Zahlen auf einem MIMD-Rechner mit 102 (un-realistisch) uber einen Bus verbundenen Prozessoren berechnet jeder Prozessorzunachst die Summe von 103 Zahlen.

sum[pN]=0.0;

for(i=1000*Pn; i<1000*(Pn+1); i++) sum[Pn]+=global_array[i];

half=100;

repeat

sync(); // wait for completion of partial sums


if (half<=Pn && Pn<limit) send(Pn/2,sum);

if (Pn<half) sum+=sum[2*Pn];

until (half==1) // result in sum[0]

Diese Art der Synchronisation heißt barrier-Synchronisation. ccache Koharenz: Probleme entstehen, wenn mehrere unabhangige Einheiten wieetwa CPU und IO-Prozessor in den Speicher schreiben, ohne den cache-Speicherzu aktualisieren. Abhilfe schaffen Maßnahmen wie


in alle caches und Speicher zugleich schreiben – zu ineffizient –,

cache-Eintrage invalidieren dann, wenn per bus snooping festgestellt wurde, daßDaten in den Speicher geschrieben wurden, die auch im cache vorliegen(z.B. uber einen invalidation bus wird fur set associative caches bei jedemSchreiben in den Speicher die set number des zugehorigen Blocks zum In-validieren an alle anderen caches geschickt)

oder Speicher-Bereiche, die von mehreren Einheiten unabhangig voneinandergeschrieben werden, als non cachable kennzeichnen.

Z.B. In Sequents Symmetry (seit 1986) sind die Multi-Prozessor uber einen P&H, p.616

einzigen Bus verbunden. Dieser muß eine genugend große Bandbreite aufweisen,wenn Skalierbarkeit gegeben sein soll. Beim redesign wurden deshalb erstens diecaches auf 64KB vergoßert, zweitens die cache-Schreib-Strategie ‘write through’durch ‘write back’ mit Invalidierung verbessert, drittens der Bus von 32bit auf64bit verbreitert und so die Bus-Bandbreite auf 53MB/s gesteigert und viertensder Speicher in zwei Banke aufgeteilt, um das Speicher-System dem jetzt doppeltso breiten Bus anzupassen (s. Fig. 9.11). c

8.3.2 MIMD-Maschinen mit Verbindungsnetzwerk

Mehr-Prozessor-Systeme mit einem einzigen Bus haben zu geringe Bandbreite, zuhohe Latenz und sind durch die (kleine) Bus-Lange im Ausbau begrenzt. Darumsetzte man leistungsfahigere Verbindungsnetzwerke ein.

Z.B. Zum Addieren von 105 Zahlen auf einem MIMD-Rechner mit 102 uber einNetz verbundenen Prozessoren berechnet jeder Prozessor zunachst die Summevon 103 Zahlen. Die Ergebnisse werden im Speicher abgelegt und ausgetauscht.

sum=0.0; for(i=0; i<1000; i++) sum+=local_array[i];

limit=100; half=100; // no of processors

repeat


if (half<=Pn && Pn<limit) send(Pn/2,sum);

if (Pn<half) sum+=receive(); limit=half;

until (half==1) // result in sum[0]

Hier ubernehmen send und receive die Synchronisation. c


Firma Name #PE a bit MHz #FPU Topology MB/PE MB/s JahrUniv.IL Illiac IV 64 64 5 64 2D–grid 0.125 2560 1972ICL DAP 4K 1 5 0 2D–grid 2 2560 1980Goodyear MPP 16K 1 10 0 2D–grid 2 20480 1982ThinkingMachines

CM-2 4/64K 1 72K

(opt).12–cube 512 16K 1987

nCube nCube/ten -1024 10 10–cube 1987Intel iPSC/2 16-128 16 7–cube 896 1988

Maspar MP-1216 32-512 4 25 02D–gridOmega

256/1024

23000 1989

Intel Delta 540 40 2D–grid 21600 1991ThinkingMachines

CM-5 -1024 40 fat tree 20480 1991

Dabei befinden sich im MP-1216 32 4bit Prozessoren und in der CM-2 16 1bitProzessoren auf einem Knoten-chip. Das 2D-Gitter des Delta-Rechners hat 16Zeilen und 35 Spalten (=560 PEs ?!?).

Z.B. Hervorragendste Eigenschaft der CM-5 – entworfen fur den TFLOP-Bereich– ist ihre Skalierbarkeit: die CM-5 hat entweder bis zu 1024 Prozessoren und biszu 32 disk systems oder bis zu 32 Prozessoren und bis zu 1024 disk systems.Die CM-5 ist wegen eines eigenen control network sowohl eine SIMD- als aucheine MIMD-Maschine: sie unterstutzt somit SIMD-software (etwa fur die CM-2entwickelt) als auch MIMD-software.CM-5 ist fehlertolerant (processor-/network-failures, diagnostic network, ecc, testmessages).Ein CM-5-Knoten besteht aus einem SPARC-Prozessor, bis zu 32MB Speicher,network interface und aus einer optionalen Vektor-Einheit (s. Fig. 9.18).Die CM-5-Knoten sind als fat tree verbunden (s. Fig. 9.19). c

8.3.3 Entwicklungstrends bei Multi-Prozessor-Systemen

Gordon Bell prognostizierte 1989 den 1 TFLOP-Rechner fur 1995 – entwederals Multi-Computer mit 4K bis 32K Rechnern oder als Connection Machine miteinigen Millionen Verarbeitungselementen.Jahrlich wurdigt der Gordon-Bell-Preis die Rechner/Programme mit der hochstenFLOP-Rate: 1988 erreichte eine Cray X-MP mit 4 Prozessoren und 8 FPUs 400MFLOPS,1989 eine eine Cray Y-MP mit 8 Prozessoren und 16 FPUs 1680 MFLOPS,1990 CM-2 mit 65536 Prozessoren und 2048 FPUs 5600 MFLOPS und1991 eine identisch ausgelegte CM-2 14200 MFLOPS.

Unter http://www.top500.org/ findet sich eine gewartete Liste der top 500Rechner-Systeme mit folgendem Selbstverstandnis:


Introduction and Objectives

Linpack TOP500 Description

Statistics on high-performance computers are of major interest to manufacturers, users,and potential users. These people wish to know not only the number of systems instal-led, but also the location of the various supercomputers within the high-performancecomputing community and the applications for which a computer system is being used.Such statistics can facilitate the establishment of collaborations, the exchange of dataand software, and provide a better understanding of the high-performance computermarket.

Statistical lists of supercomputers are not new. Every year since 1986 Hans Meuerpublished system counts has published system counts of the major vector computer ma-nufacturers, based principally on those at the Mannheim Supercomputer Seminar. Stati-stics based merely on the name of the manufacturer are no longer useful, however. Newstatistics are required that reflect the diversification of supercomputers, the enormousperformance difference between low-end and high-end models, the increasing availabilityof massively parallel processing (MPP) systems, and the strong increase in computingpower of the high-end models of workstation suppliers (SMP).

To provide this new statistical foundation, we have decided in 1993 to assemble andmaintain a list of the 500 most powerful computer systems. Our list has been compi-led twice a year since June 1993 with the help of high-performance computer experts,computational scientists, manufacturers, and the Internet community in general whoresponded to a questionnaire we sent out; we thank all the contributors for their co-operation. We have also used parts of statistical lists published by others for differentpurposes.

In the present list (which we call the TOP500), we list computers ranked by their

performance on the LINPACK Benchmark. While we make every attempt to verify the

results obtained from users and vendors, errors are bound to exist and should be brought

to our attention. We intend to continue to update this list half-yearly and, in this way,

to keep track with the evolution of computers. Hence, we welcome any comments and

information; please send electronic mail to [email protected].

The list is freely available by anonymous ftp to ftp.uni-mannheim.de/top500/ or to

www.netlib.org/benchmark/top500.ps.

The interested reader can additionally create sublists out of the TOP500 database and

can make statistics on his own by using the WWW interface at

http://www.top500.org/ or http://www.netlib.org/benchmark/top500.html.

Here you also have access to postscript versions of slides dealing with the interpretation

of the present situation as well as with the evolution over time since we started this

project.

Index

accumulator, 42Adaptive Solutions

CNAPS, 88, 130Addressierung

Displacement-, 32, 34Immediate-, 32

Aiken, Howard, 10Akkumulator, 42Algorithmus

assoziative Suche, 127blurring, 128Gauß, 115–117

Auflosen, 116Eliminieren, 115Kommunikation, 117parallel, 115, 119

Gauß-Seidel, 129Matrix-Multiplikation, 128Maximumssuche, 129Vektor-Addition, 127

aligned, 32, 43Alliant

FX/2800, 131ALU, 42

control unit, 45Steuer-Einheit, 45

AMD, 403Dnow, 15, 33, 41

Amdahl, 14, 17Analyse

Datenfluß-, 24, 119lexikalische, 19, 20semantische, 21syntaktische, 19, 21

Apple, 11architecture, siehe auch Architektur

connection, 125load/store, 42multi threaded, 131

ArchitekturAkkumulator-, 30alternativ, 120GM-MIMD, 131

Havard-, 93load/store, 34, 41, 42, 89massiv parallel, 121parallel, 120Prozessor-, 26, 30Register-, 30, 31skalierbar, 11Speicher-Speicher-, 41Stack-, 30superpipeline, 87superskalar, 84Verbindungs-, 125vielfadig, 131von-Neumann, 17, 121

arithmetic/logic unit, 42arithmetisch/logische Einheit, 42array processors, 120Atanasoff, John, 10Automat, endlicher, 59automaton, finite, 59

Babbage, Charles, 10BAPCo SYSmark, 13Baum

abstrakter, 19, 21abstrakter attributierter, 19, 21

Bedingungscode, 33Befehle

arithmetisch/logisch, 31, 33, 38, 43,50, 61

BCD-, 33Gleitkomma-, 33Lade-/Speicher-, 43, 50, 61Sprung-, 33, 48, 50, 61Transport-, 33Vektor-, 33Verzweigungs-, 33, 43, 50, 61

Befehls-Mix, 27, 51Gibson, 12

Befehlsdekodierung, 40, 41Befehlsformat, 35Befehlspipeline, 42Befehlsregister, 42, 53

137


Befehlssatz, siehe instruction set, 30, 34orthogonal, 41

Befehlszahler, 42benchmark, 12Beschleunigung

lineare, 121Beschleunigungsfaktor, 13

aufgrund caching, 94aufgrund code-Optimierung, 25, 26aufgrund forwarding, 76aufgrund multi cycle implementati-

on, 51aufgrund Parallelisierung, 116–118,

120aufgrund piplining, 67aufgrund Sprungvorhersage, 78aufgrund superscalar implementati-

on, 85aufgrund Verschrankung, 104

branchdelay, 78delay slots, 78penalties, 85prediction, 80

dynamic, 80static, 80

prediction buffer, 80target, 56target buffer, 80

Bus-Bandbreite, 12multiple, 88

bypassing, 73

cache, 29, 93, 121m-associative, 971-associative, 941st level, 922nd level, 92coherency, 132, 133consistency, 132copy back, 102data, 88, 92, 93direct mapped, 94dirty bit, 99

extern, 92fetch on write, 102flush, 102fully associative, 96hit, 93instruction, 88, 92, 93Koharenz, 94, 101Konsistenz, 94, 101Leistung, 99logic addressing, 102miss, 93no write allocate, 102on chip, 92physical addressing, 102primary, 92set-associative, 97, 131valid bit, 99vollassoziativ, 96write allocate, 102write around, 102write back, 134write through, 102, 134

caching, 11, 15, 42, 88transparent, 93

callee saving, 34caller saving, 34capabilities, 65CDC

1604, 116000, 1106600, 11, 86, 87, 90Cyber, 34Cyber203, 88Star-100, 88

CDC 6600, 67CISC, 11, 90cluster, 123CNAPS, 88code

object, 19Optimierung

Block-ubergreifend, 24constant expression folding, 20constant propagation, 20copy propagation, 25


Elimination dead codes, 25Elimination redundanter Ausdrucke,

20Elimination redundanter Sprunge,

20Elimination toten codes, 25Elimination von Schleifen-Varia-

blen, 25kontext-neutral, 26lokal, 20Parameter-Ubergabe, 20Prozedur-overhead, 20reduction of strength, 20Reduktion der Starke, 20variable propagation, 20Verbreiten von Kopien, 25Verschiebung, 25

parallel, 119Parallelisierung, 115sharing, 109source, 19Vektorisierung, 88

coherency, 123Colossus, 10communicating sequential processes (CSP),

123communication

deadlock, 123compiler, 19, 119

optimerend, 19parallelisierend, 115, 119pass, 19vektorisierend, 119

computersmulti-, 11vector-, 11

condition code, 33context switch, 27–29, 131control, 42, 70control unit, 44Convex C1, 88, 119CPI, 85CPI – cycles/instruction, 12Cray, 11, 33

Cray 1, 88–90

Cray 2, 88Cray X-MP, 88, 135Cray Y-MP, 88, 135

DAG, siehe Parallelisierung, DAGdata path, 42, 68Daten-Abhangigkeit, 115Daten-Pfad, 42, 68Datenfluß-Rechner, 120, 122, 125DAXPY, 87DEC

21064, 67Alpha, 67alpha, 31, 32, 87DECstation, 33, 108PDP, 11, 30, 34VAX, 11, 31–33, 41, 90

Dhrystones, 12directed acyclic graph, siehe Paralleli-

sierung, DAGDirectory Architecture for SHared me-

mory (DASH), 132DLX, 31, 32, 34, 41, 67

DLXV(ector), 88dont’t care, 48

EA-Bandbreite, 12EA-Prozessor, 88Eckert, John P., 10EDVAC, 10Einheit

funktional, 84, 88, 89scheduling, 86

ENIAC, 10, 11Enigma, 10exception, 57

Fehlzugriffsrate, 93Feld-Rechner, 120finite Elemente Methode (FEM), 125Flynn, 17, 120forwarding, 73, 74FPS – frames/sec, 12Fragmentierung

externe, 110interne, 110


FujitsuVP100/200, 88VPP500, 11

GMDMassively parallel Architecture for

Numerical and Non-numerical Ap-plications (MANNA), 133

SUPRENUM, 132Goodyear

MPP, 123, 126, 135STARAN, 126

GraphDatenfluß-, 29Farben, 29

hazard, 68control, 77data, 72Daten-, 68, 72detection, 74RAW, 86Steuer-, 68, 77Struktur-, 68WAR, 87

Heterogeneous Element Processor (HEP),132

hit rate, 93Hitachi

S810/820, 88Hoare, 123Hollerith, Hermann, 10HP Precision Architecture (PA), 31hypercube-Rechner, 120

IBM, 10/360, 11, 32, 33, 110/370, 11, 34701, 11801, 413090, 117090, 11, 12RS/6000, 87

ICLDAP, 120, 135

Illiac IV, 88, 123, 126, 135

implementationmulti-cycle, 51single-cycle, 50

Implementierungmulti-cycle-, 51single-cycle-, 50

instructioncounter, 42format, 35pipeline, 42register, 42, 53

instruction set, siehe Befehlssatz, 30, 34orthogonal, 41

instruction set architecture, siehe ISAinstructions

arithmetic/logic, 31, 33, 38, 43, 50,61

binary coded decimal (BCD), 33branch, 33, 43, 50, 61float, 33jump, 33, 48, 50, 61load/store, 43, 50, 61transport, 33vector, 33

integrationlarge scale, 11medium scale, 11small scale, 11ultra large scale, 11very large scale, 11

Intel80860XP, 8780286, 11180386, 99, 11280486, 67, 102, 104, 11482385, 99Delta, 135i80860XP, 133i860XL, 131iAPX432, 110iPSC/2, 135Paragon, 11Pentium, 67, 114

Intel 80x86, 31–33, 36, 90call gates, 114


code segment, 111global descriptor table (GDT), 112hidden segment descriptor cache, 111ISSE, 41local descriptor table (LDT), 112MMX, 15, 33, 67page table, 113page table directory, 113protected mode, 111real mode, 111segment descriptor, 112SSE, 33translation lookaside buffer (TLB),

113interrupt, 29ISA, siehe instruction set architecture

Java virtual machine (VM), 30Java-Prozessoren

MikroJava, 103picoJava, 31picoJava I, 67picoJava II, 67

Joy, 16

KLIPS – kilo logical inferences/sec, 12Koharenz, 123Kommunikation

Blockade, 123master/slave, 122per Botschaft, 120, 122, 131zwischen PEs, 117, 120

Kommunikationsdurchmesser, 122Kontext-Wechsel, 27, 28, 131Koppelung

eng, 120, 131lose, 120, 131

Leibniz, Gottfried, 10Linpack, 12Livermore loops, 12load stall, 77Lokalitat, 92

raumlich, 93zeitlich, 93

Lovelace, Augusta Ada King countessof, 10

MasparMP-1216, 135

Mauchly, John William, 10mean

arithmetic, 14geometric, 14harmonic, 14

memory, siehe Speicher, 103address fault, 105bank, 42, 103, 134CAS, 103contention, 116cycles, 12flat, 34global, 118, 120, 131hierarchy, 92interleaved, 88, 103, 121, 131, 134local, 118, 120, 126, 127, 131miss penalty, 105non uniform, 131organisation, 103paged segments, 110protection, 104, 110

access key, 110capabilities, 110

RAS, 103shared, 126uniform, 131virtual, 104virtual shared, 133wait states, 12

memory management unit, 104MFLOPS – mio float operations/sec, 12migration, vertical, 65Mikroprogrammierung, 11MIMD, 18, 120, 122, 131MIPS

superskalar, 84MIPS – mio instructions/sec, 12MIPS R2000 etc, 31, 32, 34, 41, 67, 78,

84, 90, 120MIPS R3000, 42, 61


MIPS R4000, 87misaligned, 32miss rate, 93Mittel

arithmetisch, 14geometrisch, 14harmonisch, 14

MOPS – mio operations/sec, 12Morland, Samuel, 10Motorola

88000, 90MC6809, 30MC680x0, 31, 32, 34MC88110, 87

Multiprocessor-Systeme, 11multiprogramming, 29Multiprozessor-Systeme, 18

asymmetrisch, 18distributed memory, 18heterogen, 18homogen, 18shared memory, 18symmetrisch, 18

MWIPS – mio Whetstones/sec, 12

nCubenCube/ten, 135

NECSX, 88SX/2, 88SX/3, 103

netconnection, 120, 122

band width, 122bus, 123, 125cross bar, 122–125, 131, 133delta, 125extendability, 122grid, 123–125hub, 123hypercube, 124, 125, 127, 133latency, 122multiple bus, 123redundancy, 122ring, 122, 123, 125

shuffle exchange, 125staged networks, 124star, 122, 123torus, 133tree, 122, 123, 125

neuronal, 120, 122, 130Netz

neuronal, 120, 122, 130Verbindungs-, 120, 122

Bandbreite, 122Baum, 122, 123, 125Bus, 123, 125delta, 125Erweiterbarkeit, 122gestuft, 124Gitter, 123–125Hub, 123Hyper-Wurfel, 124, 125, 127, 133Kreuzschiene, 122–125, 131, 133Latenz, 122multipler Bus, 123Redundanz, 122Ring, 122, 123, 125shuffle exchange, 125Stern, 122, 123Torus, 133

Neumann, John von, 10Newman, Max H. A., 10

OCCAM, 123Operationen

dyadisch, 31, 38, 40Register-Register-, 31Register-Speicher-, 31Skalar-, 89Speicher-Speicher-, 31triadisch, 31, 32, 34, 87Vektor-, 87–89, 107, 119, 126

paging, 105, 112dirty bit, 107hashing the page table, 107inverted page tables, 107page fault, 104, 105page table, 106


paging the page table, 107protection bits, 107roll back, 107thrashing, 110translation lookaside buffer (TLB),

107validity bit, 107

Parallel Random Access Machine (PRAM),132

Parallelisierung, 115Parallelitat

auf Anweisungsebene, 84parallelity

instruction level, 84Parsytec

GigaCubes, 124Grand Challenges (GC), 124

Pascal, Blaise, 10PC, IBM-kompatibler, 11Perfect Club, 12pipeline, 66, 120

arithmetisch, 67, 82Befehls-, 67granularity, 83instruction, 67monofunktionale, 67multifunktionale, 67stage, 66Stufe, 66superskalar, 84variability, 83

pipelining, 11, 15, 41, 66process, 131

dormant, 131light weighted, 132ready, 131switch, 132

processing element (PE), 115, 120processor, 42

control, 44control unit, 85instruction set, 26, 30status word, 33, 38

programmable logic array (PLA), 48Prozessor, 42

-Array, 126-Status-Wort, 33, 38assoziativ, 120Befehlssatz, 26, 30bit slice, 126, 127pipelined Vektor-, 87RISC, 92Steuerung, 44, 85superskalar, 84, 133von-Neumann-, 42

Prozeß, 131bereit, 131leichtgewichtig, 132schlafend, 131Wechsel, 29, 132

Quicksort, 21

R-Format, 43reduction of strength, 20Reduktion der Starke, 20Register, 26, 92

Adreß-, 89Datei, 29

port, 29Fenster, 28, 79file, 29reorder, 29Skalar-, 89Umordnung, 29Vektor-, 88, 89Zuteilung, 20, 26

register, 26allocation, 26

register spilling, 27RISC, 11, 36, 41, 90, 124RISC I, 28, 31, 41RISC II, 41

SAXPY, 87scoreboard, 84, 86, 89Segment-Einteilung, siehe segmentati-

onsegmentation, 105, 109, 111, 112

dirty bit, 107paged segments, 110


protection bits, 107roll back, 107segment fault, 105segment table, 109splinters, 110validity bit, 107

segments, paged, 112Seiten-Einteilung, siehe paging, 112Sequent

Symmetry, 121, 123, 133, 134SGI

4/360, 133short circuiting, 73Sicherheit, 65Siemens

VPx, 88Signalisierung, 122SIMD, 18, 120, 122, 126, 127single instruction computer (SIC), 30SISD, 18SPECfp, 12SPEChpc, 12SPECint, 12SPECmark, 12Speicher, siehe memory, 103

Address-Umsetzung, 104Bank, 42, 103, 134CAS, 103global, 118, 120, 126, 131Hierarchie, 92linear, 34logische Addressen, 104lokal, 118, 120, 126, 127, 131non uniform, 131Organisation, 103physikalische Addressen, 104RAS, 103Schutz, 104, 110

Zugriffsschlussel, 110uniform, 131verschrankt, 88, 103, 121, 131, 134virtuell, 104

Speicher-Addressierung, 32, 41big endian, 32little endian, 32

Sprungvorhersagedynamisch, 80statisch, 80

stall, 73Steuer-Einheit, 44Steuerung, 42, 70

ALU, 44festverdrahtet, 61, 62mikro-programmiert, 61, 64per Sequencer, 63Prozessor, 44

Stibitz, George, 10Strategie

Ersetzungs-, 96fifo, 96, 105lru, 97, 105random, 96Verdrangungs-, 96, 105

SUN4/640, 133SPARC, 28, 31, 32, 67, 79, 90, 135

VISual, 33SuperSPARC, 87

TERA, 132Texas Instruments, 32

ASC, 11, 83, 88Thinking Machines

Connection Machine, 11CM-1, 122, 123CM-2, 121, 125, 127, 135CM-5, 135

TLB, siehe memoryTPS – transactions/sec, 12Transputer, 122, 123, 125

channel, 123link, 123

Trefferrate, 93Turing, Alan M., 10

unitfunctional, 84, 88, 89stream, 89

Univac LARC, 11Unterbrechung, 29


Verarbeitungseinheiten, 120Verlagerung, vertikale, 65Verzweigungszieladresse, 56von Neumann

bottle neck, 121Flaschenhals, 121

Watson, T.J., 10Whetstone, 12WinStone, 13

Zuse, Konrad, 10

Documents

Computer-Architektur/Rechner- · PDF fileTh. Risse, HSB: RST { SS15 4 0.1 zugrunde liegende Literatur John L. Hennessy, David A. Patterson: Rechnerarchitektur { Analyse, Ent-wurf,