Definitionen, Fakten, Formeln und Faustregeln der Rechnerarchitektur

Definitionen Big Endian: Das Byte mit der binaren Adresse "x ... xOO" ist die Position hochster Wertigkeit ("groBes

Ende") eines 32-Bit-Wortes (Seite 95). TaktJrequenz: Reziproker Wert der Taktzykluszeit, gewohnlich in MHz gemessen (Seite 36). CPI (Clock cycles Per Instruction): Taktzyklen pro Befehl (Seite 36). TreJJerrate: AnteiI der im Cache gefundenen Speicherzugriffe; entspricht l-Fehlzugriffsrate (Scite

404). BeJehlsanzahl: Zahl der wahrend eines Programmlaufs abgearbeiteten Befehle (Seite 36). Little Endian: Das Byte mit der binaren Adresse "x ... xOO" ist die Position geringster Wertigkeit

("kleines Ende") eines 32-Bit-Wortes (Seite 95). MIMD (Multiple Instruction streams. Multiple Data streams): Ein Multiprozessor oder Multicomputer

(Seite 572). F ehlzugriJJszeit: Die Zeit zum Ersetzen eines Blocks in der oberen Ebene eines Cache-Systems durch

den korrespondierenden Block der unteren Ebene (Seite 405). F ehlzugr(ff~rate: AnteiI der nicht im Cache gefundenen Speicherzugriffe; entspricht 1-Trefferrate

(Seite 404). Nl/r Die erforderliche VektorIange, urn den halben Wert von Roo zu erreichen (Seite 384). Nx: Die erforderliche Vektorlange, damit der Vektormodus schneller als der Skalarmodus ist (Seite

384). Roo: Die MFLOPS-Rate eines unendlich langen Vektors (Seite 384). RA W-Daten (Read After Write)-Hasard: Ein Befehl versucht, eine Quelle zu lesen, die von einem vor­

angegangen Befehl noch nicht geschrieben wurde, so erhalt er den falschen alten Wert (Seite 264).

SIMD (Single Instruction stream, Multiple Data streams): Ein Array-Prozessor (Seite 572). SISD (Single Instruction stream, Single Data stream): Ein Uniprozessor (Seite 572). Raumliche Lokalitat: Wenn auf einen Eintrag zugegriffen wird, erfolgt mit hoher Wahrscheinlichkeit

bald ein Zugriff auf einen beliachbarten Eintrag (Seite 403). Zeitliche Lokalitat: Wenn auf einen Eintrag zugegriffen wird, erfolgt mit hoher Wahrscheinlichkeit

bald ein Zugriff auf ihn. WA W-Daten (Write After Write)-Hasard: Ein Befehl versucht einen Operanden zu schreiben, bevor er

von einem vorangegangenen Befehl geschrieben wurde. Das Schreiben erfolgt in der falschen Reihenfolge. Es verbleibt der falsche Wert des vorangegangenen Befehls im Zieloperanden (Seite 264).

WAR-Daten (Write After Read)-Hasard: Ein Befehl versucht einen Operanden zu schreiben, bevor er yom vorangegangenen Befehl gelesen wurde, so erhalt der vorangegangene Befehl den falschen neuen Wert (Seite 264).

Fakten

Bytereihenfolge von Maschinen (Seite 95)

Big Endian: IBM 360, MIPS, Motorola, SPARC, DLX Little Endian: DEC V AX, DEC RISC, Intel 80x86

Jahr und Nutzer-Adrefilange der Generationen von IBM- und Intel-Rechnerfamilien

.Jahr Modell Nutzer·AdreBUinge .Iahr Modell Nutzer·AdreflHinge

1964 IBM 360 24 1978 Intel W86 4+16

1971 IBM 370 24 1981 Intel 80186 4+16

1983 IBM 37()-XA 31 1982 Intel 80286 16t16

1986 IBM ESA/370 16t31 1985 Intel 80386 16t32oder32

I 1989 Intel 80486 16t32oder32

I

Formeln

1. Amdahlsches Gesetz: Beschleunigung = Ante'l .. d (Seite 8) . I veran ert

(l-AnteIlveranderd + Beschleunigungverandert

2. CPU-Zeit = Befehlsanzahl * CPU-Taktzyk!en pro Befeh! * Taktzyk!uszeit (Seite 36)

3. Mittlere Speicherzugriffszeit = Trefferzeit + Feh!zugriffsrate * Fehlzugriffszeit (Seite 405) 4. Mittel - arithmetisches (AM), gewichtetes arithmetisches (WAM), harmonisches (HM) und

gewichtetes harmonisches (WHM):

1 n n n AM=- ~Zeit· WAM= ~Wichte·*Zeit· HM= WHM=----n.£.. l' .£.. 1 l' n' n

1=1 1=1 I--l- L Wichte; Rate; Rate;

i= 1 ;= 1

wobei Zeiti die Ausfiihrungszeit des i-ten Programms einer Gesamtarbeits!ast von n Programmen, Wichte; der Gewichtsfaktor des i-ten Programmes der Gesamtarbeitslast und Ratei eine Funktion von l/Zeiti ist (Seite 50-51).

5 C K _ Chipkosten + Testkosten + Verkappungskosten . I - osten - Endtestausbeute (Seite 55)

{ Defekte pro Flacheneinheit * Chipflache } -u 6. Chipausbeute = Waferausbeute * 1 + u

wobei Waferausbeute auf komplett schlechte Wafer bezogen ist, die nicht mehr getestet werden; ex ist ein Parameter, der grob gesagt mit der flir die Ausbeute kritischen Maskenebene korrespondiert und yom FertigungsprozeB abhangt (Allgemein ist ex ~ 2,0, Seite 59).

. . . _ Taktzyk!uszeitohne Pipelining Ideal-CPI * Pipeline-Tiefe 7. Plpehne-Beschleumgung - Taktzykluszeitmit Pi elining * Ideal-CPI + Pipeline-Wartezyklen

die Pipeline-Wartezyklen entsprechen den durch Pipeline-Hasards verlorenen Taktzyklen (Seite 258)

8. System-Leistung:

. . _ Zeitcpu ZeitEiA ZeitUberlappt Zeltskahert - Beschleunigungcpu + BeschleunigungE/A Maximum(Beschl.cpu ,BeschI.E/A) Zeitcpu bedeutet, daB daB die CPU aktiv ist, ZeitE/A bedeutet, daB das E/A-System aktiv ist und ZeitUberlappt bedeutet, daB beide aktiv sind. Diese Formel geht davon aus, daB die Uberlappung linear mit der Beschleunigung skaliert ist (Seite 506)

Faustregeln

I. Amdahl/Case-Regel: Ein Rechnersystem mit 1 MIPS CPU-Leistung ist ausgewogen, wenn es eine Speicherkapazitat von 1 MB und eine EI A-Bandbreite von 1 MBitls hat (Seite 17).

2. 90/10 Leistungsregel: Ein Programm verbraucht 90% der Ausfiihrungszeit in 10% seines Befehlscodes (Seite 11-12).

3. DRAM-Wachstumsregel: Der Integrationsgrad steigt mit ca. 60% pro Jahr und vervierfacht sich in 3 Jahren (Seite 17).

4. Magnetplatten- Wachstumsregel: Die Dichte steigt um ca. 25% pro Jahr und verdoppelt sich in 3 J ahren (Seite 17)

5. Adrej3-Wachstumsregel: Der von einem durchschnittlichen Programm benotigte Speicher wachst mit einem Faktor von ca. 1,5 bis 2 pro Jahr. Damit wachst der Bedarf an AdreBbits um 112 bis 1 AdreBbit pro Jahr (Seite 16).

6. 90/50-Regel ausgefiihrter Verzweigungen: Es werden ungefahr 90% der Riickwartsverzweigungen ausgefiihrt, wahrend nur ca. 50% der Vorwartsverzweigungen ausgefiihrt werden (Seite 108).

7.2: 1-Cache -Regel: Die Fehlzugriffsrate eines einfach assoziativen Cache der GroBe X entspricht ungefahr der Halfte der eines 2-Wege-Caches der GrOBe X/2 (Seite 421).

John L. Hennessy David A. Patterson

Rechnerarchitektur

Analyse, Entwurf, Implementierung, Bewertung

John L. Hennessy David A. Patterson

Rechnerarchitektur Analyse, Entwurf, Implementierung, Bewertung

Mit einem Beitrag von David Goldberg

Ubersetzt und bearbeitet von Dieter J ungmann

II vleweg

Dieses Buch ist die deutsche Ubersetzung von: John L. Hennessy and David A. Patterson, Computer Architecture. A Quantitative Approach © 1990 by Morgan Kaufmann Publishers, Inc., San Mateo, California

Ubersetzung aus dem Amerikanischen und Bearbeitung: Dieter Jungmann, TU Dresden

Hinweise zum amerikanischen Original: All instruction sets and other design information of the DLX computer system contained herein is copyright by the publisher and may not be incorporated in other publications or distributed by media without formal acknowledgement and written consent from the publisher. Use of the DLX in other publications for educational purposes is encouraged and application for permission is welcomed. INSTRUCTOR SUPPORT: For information on classroom software and other instructor materials available to adopters, please contact the editorial offices of Morgan Kaufmann Publishers, Inc. (001) (415) 578-9911.

Aile Rechtc vorbchalten © Springer Fachmedien Wiesbaden, 1994 Urspriinglich erschienen bei Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, BraunschweiglWiesbaden 1994.

Das Werk einschlieBlich aller seiner Teile ist urheberrechtlich ge­schutz!. Jede Verwertung auBerhalb der engen Grenzen des Ur­heberrechtsgesetzes ist ohne Zustimmung des Verlags unzuUissig und strafbar. Das gilt insbesondere fUr VervieWiltigungen, Uber­setzungen, Mikroverfilmungen und die Einspeicherung und Ver­arbeitung in elektronischen Systemcn.

Gedruckt auf saurefreiem Papier

ISBN 978-3-528-05173-0 ISBN 978-3-663-13953-9 (eBook) DOI 10.1007/978-3-663-13953-9

Fur Andrea, Linda und unsere vier S6hne

Warenzeichen Die folgenden Warenzeichen sind eingetragen:

Alliam is a trademark of Alliant Computers. AMD 29000 is a trademark of AMD. TeX is a trademark of American Mathematical SOciety.

AMI 6502 is a trademark of AMI. Apple I, Apple II, and Macintosh are trademarks of Apple Computer, Inc.

ZS-I is a trademark of Astronautics. UNIX and UNIX Fl7 are trademarks of AT&T Bell Laboratories. Turbo C is a trademark of Borland International. The Cosmic Cube is a trademark of California Institute of Technology.

Warp, C.mmp, and Cm" are trademarks of Carnegie-Mellon University. CP3100 is a trademark of Conner Peripherals. CDC 6600, CDC 7600, CDC STAR-100, CYBER-180, CYBER 180/990, and CYDER-205 are trademarks of Control Data Corporation. Convex, C-I, C-2, and C series are trademarks of Convex. CRAY -3 is a trademark of Cray Computer Corporation. CRAY-I, CRAY-IS, CRAY-2, CRAY X-MP, CRAY X-MP/416, CRAY Y­MP, CFT77 V3.0, CFT, and CFT2 V1.3a are trademarks of Cray Research.

Cydra 5 is a trademark of Cydrome. CY7C601, 7C601, 7C604, and 7CI57 are trademarks of Cypress Semiconductor. Nova is a trademark of Data General Corporation.

HEP is a trademark of Denelcor. CVAX, DEC, DECsystem, DECstation, DECstation 3100, DECsystem 10/20, fort, LPlI, Massbus, MicroVAX-I, MicroVAX-II, PDP-8, PDP-IO, PDP-II, RS-IIM/IAS, Unibus, Ultrix, Ultrix 3.0, VAX, VAX station VAXstation 2000, VAXstation 3100, VAX-II, VAX-II/780, VAX: 111785, VAX Model 730, Model 750, Model 780, VAX 8600, VAX 8700, V AX 8800, VS FORTRAN V2.4, and VMS are trademarks of Digital Equipment Corporation. BINAC is a trademark of Eckert-Mauchly Computer Corporation.

Multimax is a trademark of Encore Computers. ETA lOis a trademark of the ETA Corporation.

SYMBOL is a trademark of Fairchild Corporation.

Pegasus is a trademark of Ferranti, Ltd. Ferrari and Testarossa are trademarks of Ferrari Motors.

AP-120B is a trademark of Floating Point Systems. Ford and Escort are trademarks Ford Motor Co. Gnu C Compiler is a trademark of Free Software Foundation. M2361A, Super Eagle, VPloo, and VP200 arc trademarks of Fujitsu Corporation. Chevrolet and Corvette are trademarks of General Motors Corporation. HP Precision Architecture, HP 850, HP 3000, HP 3000170, Apollo ON 300, Apollo ON 10000, and Precision are trademarks of Hewlett-Packard Company. S81O, S810/2OO, and S820 are trademarks of Hitachi Corporation.

Hyundai and Excel are trademarks of the Hyundai Corporation.

432, 960 CA, 4004, 8008, 8080, 8086, 8087, 8088, 80186, 80286, 80386, 80486, iAPX 432, i860, Intel, Multibus, Multibus II, and Intel Hypercube are trademarks of Intel Corporation. Inmos and Transputer are trademarks of Inmos.

Clipper C I 00 is a trademark of Intergraph. IBM, 360, 360/30, 360/40, 360150, 360/65, 360/85, 360/91, 370, 3701135, 3701138, 3701145, 3701155, 3701158, 3701165, 3701168, 370-XA, ESA/370, Systeml360, System/370, 701, 704, 709, 801, 3033, 3080, 3080 series, 3080 VF, 3081, 3090, 30901100, 3090/200, 3090/400, 3090/600, 3090/600S, 3090 VF, mo, 3380, 33800, 3380 Disk Model AK4, 3380J, 3390, 3880-23, 3990, 7030, 7090, 7094, IBM FORTRAN,

ISAM, MVS, IBM PC, IBM PC-AT, PL.8, RT-PC, SAGE Stretch IBM SVS, Vector Facility, and VM are trademarks of Internati'onal Bu~iness Machines Corporation. FutureBus is a trademark of the Institute of Electrical and Electronic Engineers.

Lamborghini and Countach are trademarks of Nuova Automobili Ferrucio Lamborghini, SPA. Lotus 1-2-3 is a trademark of Lotus Development Corporation.

MB8909 is a trademark of LSI Logic. NuBus is a trademark of Massachusetts Institute ofTechnology. Miata and Mazda are trademarks of Mazda.

MASM, Microsoft Macro Assembler, MS DOS, MS DOS 3.1, and OSI2 are trademarks of Microsoft Corporation.

MIPS, MIPS 120, MIPSII20A, M/500, Mil 000, RC6230, RC6280, R2oo0, R2oo0A, R2010, R3000, and R3010 are trademarks of MIPS Computer Systems. Delta Series 8608, System V/88 R32VI, VME bus, 6809, 68000, 68010, 68020, 68030, 68882, 880UO, 88000 1.8.4mI4, 88100, and 88200 are trademarks of Motorola Corporation. Multiflow is a trademark of Multiflow Corporation.

National 32032 and 32x32 are trademarks of National Semiconductor Corporation.

Ncube is a trademark of Ncube Corporation. SX/2, SX/3, and FORTRAN 771SX V.040 are trademarks of NEC Information Systems. NYU Ultracomputer is a trademark of New York University.

VAST-2 v.2.21 is a trademark of Pacific Sierra. Wren IV, Imprimis, Sabre, Sabre 97209, and IPI-2 are trademarks of Seagate Corporation. Sequent, Balance 800, Balance 21000, and Symmetry are trademarks of Sequent Computers. Silicon Graphics 40/60, 401240, and Silicon Graphics 40 Series are trademarks of Silicon Graphics. Stellar GS 1000, Stardent-1500, and Ardent Titan-I are trademarks of Stardent.

Sun 2, Sun 3, Sun 3175, Sun 3/260, Sun 3/280, Sun 4, Sun 41110, Sun 4/260, Sun 41280, SunOS 4.0.3c, Sun 1.2 FORTRAN compiler, SPARC, and SPARCstauon I are trademarks of Sun Microsystems.

Synapse Nt I is a trademark of Synapse. Tandem and Cyclone are trademarks of Tandem Computers. TI 8847 and TI ASC are trademarks of Texas Instruments Corporation.

Connection Machine and CM-2 are trademarks of Thinking Machines. Burroughs 6500, B5000, B5500, D-machine, UNIVAC, UNIVAC I, UNIVAC 1103 are trademarks of UNISYS.

Spice and 4.2 BSD UNIX are trademarks of University of California, Berkeley. lIIiac, lIIiae IV, and Cedar are trademarks of University of Illinois.

Ada is a trademark of the U.S. Government (Ada Joint Program Office).

Weitek 3364, Weitek 1167, WTL 3110, and WTL 3170 are trademarks of Weitek Computers.

Alto, Ethernet, PARC, Palo Alto Research Center, Smalltalk, and Xerox are trademarks of Xerox Corporation. Z-80 is a trademark of Zilog.

I Vorwort von C. Gordon Bell

Es ist mir cine Freudc und Ehre, das Vorwort flir dieses richtungwcisendc Buch zu schreiben.

Die Autoren sind Uber die bekannten Bcitrage von Thomas zum Calculus und Samuelson zur Wirtschaft weit hinausgegangcn. Sic haben ein Standardwcrk fUr Rcchncr­architcktur und -entwurf geschaffen. Zum Nutzen der lnfonllatik ermutigc ich die Ycricger, die vielen BUcher zu diesem Thema zurlickzuziehen, damit schnell cine neue Generation von lnformatikern und Systemingcnieuren herangebildet werden kann. Dieses Buch bcab­sichtigt nicht, die komplcxen und fehlerhaften Mikroprozessoren der Halbleiterfirmen zu bcscitigen, doch es wird die Ausbildung von lngenicurcn beschleunigen, die hcsscrc entwcrl"en konnen.

Das Buch bietet die kritischen Werkzcuge zur Analyse von Einprozessorcomputcrn. Es zeigt dem praktisch tiitigen Ingcnieur, wie sich die Technologic mit dcr Zeit vcrandert, und lielcrt die flir den Entwurf nOlwendigen cmpirischcn Konstanten. Leitender Gesichtspunkt beim Entwurf ist die Funktionalitat anstclle der stereotypen Aharheitung von Roulinen, mit denen ein uncrfahrcner Entwerfer versucht, cinen cinfachen Entwurf durchzufiihren.

Die Autoren schufen cine Ausgangsbasis rur Analysen und Ycrgleiche, indcm sic die wichtigsten Maschinen jeder Klasse hehandeln: Mainframe (IBM 360), Mini (DEC V AX) und MikrolPC (Intel 80x86). Darauf aulhaucnd zeigcn sic die kommenden Hauptentwick­lungslinien einfachcr Pipeline- und Parallclprozessoren. Dicsc ncuen Technologicn werden als Varianten ihrcs in didaktischcr Hinsichl nlitzlichcn, aher auch lals~ichlid' rcalisierharcn Prozcssors (DLX) vorgestellt. Die Autorcn betonen Technologieunahh~ingigkeit durch Mcssung der pro Takt ausgefiihrten Arheit (Parallclvcrarbcitung) und der Arheit pro Zciteinheit (Effcktivitat und Gesamldaucr). Diesc MClhoden solltcn auch die Qualiliit der Forschung zu neuen Architekluren und wr Parallclverarheitung wrhessern.

So sollte das Buch cine PJlichtlektiire flir jcdermann scin, dcr mit Architckturen und Hardware arbcilet. einschlidllich Architcklcn, Schaltkrcis- und Rcchncrsystemingcnicuren sowie Compilcr- und Betricbssystcmingcnicurcn. Es ist inshesondere niilzlich fUr Soft­wareingenieurc, die Programme fUr Pipcline-Vektorcomputer schreihen. Manager und Mar­kClinglcute werden aus dem Wissen der Ahschnitte "lrrllimer und Fallen" dicscs Buches N uVen ziehen. Ocr Miflerfolg von Compulern - und haufig ciner Firma - kann an den lngenieurcn liegen, die die Feinhcilen des Rechnercnlwurfs nieht hcherrschcn.

Die crsten lwci Kapitel vermitteln das Wescn des Rechncrcnlwurfs durch Mcssungcn und das Verstandnis des Prcis/Leistungs-Vcrhiiltnisscs. Dicsc KOn!eplC werden auf die Be­fchlssatz-Architeklur und ihre Messung angewendct. Es folgt cinc Diskllssion del' Irnplc­mentierung von Prozcssoren sowie eine umfangrciche Bctrachlun~ von EntwlIri"stechniken flir Pipelinc- unci Vcktorprolessorcn. Ganlc Kapitel sind der Speichcrhicrarchie lind der oft vernachIassigtcn Ein-I Ausgahe gewidmct. Das abschliclknde Kapilcl enthiilt Mliglichkei­ten und Fragen IU Maschinen und Enlwicklungsrichtungcn dcr Zukunft.

Ocr Grund daflir, dall dicscs Buch Wr eincn lihcrschaubaren Zcitraum cincn Slandard oherhalb aller andcrcn sct/l, bcslcht im V crstandnis, del' Frfahrung, dem Geschmack und

i x

x Vorwort

der Einmaligkeit der Autoren. Sie haben den Hauptwandel in der Architektur durch ihre Arbeit zu RISC (Patterson pragte dieses Wort) an der Universitat selbst eingeleitet. Ihre Forschung fUhrte zu Produktentwicklungen bei MIPS und Sun Microsystems, die fUr die 90er Jahre bedeutende Architekturen erstellten. So erarbeiteten sie Analysen, bewerteten Entscheidungen, schufen Compiler und Betriebssysteme und sahen, daB ihre Maschinen in der Anwendung Bedeutung erlangten. Ferner haben sie als Hochschullehrer feststellen konnen, daB das Buch didaktisch wohlfundiert ist (nicht zuletzt das Ergebnis eines bei­spiellosen "Beta-Testprogramms"). Ich weiB, es wird das Buch des Jahrzehnts auf dem Gebiet der Rechnersysteme sein. Vielleicht wird es auch eine Herausforderung fUr weitere groBe Architekten von Systemen hOherer Ebenen (Datenbanken, Kommunikationssysteme, Sprachen und Betriebssysteme) sein, ahnliche Werke zu schreiben. Dies ware mit Sicherheit eine willkommene Leistung.

Ich habe mich bereits am Buch erfreut und davon gelernt, und sicherlich wird es Ihnen genauso gehen.

C. Gordon Bell

I Vorwort zur Ubersetzung von D. Jungmann

Seit dem Wintersemester 1990 nutze ich fUr Lehrveranstaltungen des Hauptstudiums "Rechnerarchitekt;.ir" an der Fakultat Informatik der TU Dresden dieses aus methodischer Sicht einmalige Lehrbuch von Hennessy und Patterson. Der grundlegende Charakter dieses Werkes, d.h., der primaren Vermittlung von Prinzipien und Methoden der Analyse, des Entwurfs, der Implementierung und Bewertung von Rechnerarchitekturen gewahrleistet, daB es auch in den nachsten J ahren nichts von seiner Bedeutung verlieren wird.

Die Ubersetzung geht von der 3. korrigierten Auflage aus. Bei der Gestaltung des Layouts konnte eine I: I-Seitenzuordnung zum Original durch Zeilenverbreiterung erreicht werden.

Wenn auch nicht mit dem Entstehen des Originalbuches vergleichbar, so haben doch viele zur Herausgabe dieser deutschen Fassung beigetragen, denen ich auch auf diesem Wege herzlich danken mochte. Bei der Ubersetzung unterstiltzte mich Herr DLsc.techn. M. Auer. Die Erfassung und Korrektur des deutschen Textes wurde hauptsachlich von Frau K. Achtruht bewaltigt. Ich danke meiner Mitarbeiterin Frau Dipl.-Ing. A. Pockel sowie meinen Doktoranden Herrn Dr.-Ing. W. Suworow und Dipl.-Ing. G. Markwardt fUr das inhaltliche Lektorat. Die komplette Layout-Gestaltung iibernahm mein Sohn Claus mit Hingabe und Ausdauer. Die Bearbeitung der zahlreichen Bilder bewaltigte Herr Dipl.-Ing. H. Andreas. Das Gesamtlektorat, mit vielen Korrekturhinweisen, iibernahm freundlicher­weise Herr Prof. E. Jordan. SchlieBlich danke ich meiner FamiIie fUr das Verstandnis und die vieWiltige direkte und indirekte Unterstiltzung.

Dresden, im Juni /994, D. Jungmann

Rechnerarchitektur: Analyse, Entwurf, Implementierung und Bewertung xi

I Inhalt Vorwort ix

von C. Gordon Bell lUr deutschen Ubersetzung von D.Jungmann

Einleitung xvii

Danksagungen xxii

1 Grundlagen des Rechnerentwurfs 2 1.1 Einflihrung 3 1.2 Definitionen der Leistung 5 1.3 Quantitative Prinzipien des Rechnerentwurfs 8 1.4 Der Job des Rechnerentwerfers 13 1.5 Zusammenfassung:

Das Konzept der Speichcrhierarchie 18 1.6 irrtiimer und Fallen 21 1.7 SchluBbemerkungen 22 1.8 Historisches und Litcraturquellen 23

Ubungen 28

2 Leistung und Kosten 32 2.1 Einfilhrung 33 2.2 Leistung 35 2.3 Kosten 53 2.4 Zusammenfassung:

Preis/Leistungs-V crhaltnis von drei Maschinen 66 2.5 irrtiimer und Fallen 70 2.6 SchluBbemerkungen 76 2.7 Historisches und Litcraturquellen 77

Ubungen 81

3 Befehlssatzentwurf: Alternativen und Prinzipien 88 3.1 Einfiihrung 89 3.2 Klassifizierung von Befchlssatz-Architekturen 90 3.3 Operandenspeicherung:

Klassifizicrung von Universalregistermaschinen 92 3.4 S pei cheradressi erun g 94 3.5 Operationen des Befchlssatzes 103 3.6 Typ und Lange der Operanden 109 3.7 Die Rolle von hbhercn Programmiersprachen und Compilern 111 3.8 Zusammenfassung:

Wie Programme Befehlssatze nutzen 122 3.9 Irrtilmer und Fallen 124 3.10 SchluBbemerkungen 126 3.11 lIistorischcs und Literaturquellen 127

Obungen 132

xii Inhaltsverzeichnis

4 Befehlssatzbeispiele und Messung der Befehlsatznutzung 138 4.1 Befehlssatzmessungen: Was und warum? 139 4.2 Die VAX-Architektur 142 4.3 Die 360/370-Architektur 148 4.4 Die 8086-Architektur 153 4.5 Die DLX-Architektur 160 4.6 Zusammenfassung:

Messungen der Befehlssatznutzung 167 4.7 [rrtUmer und Fallen 183 4.8 SchluBbemerkungen 185 4.9 Historisches und Literaturquellen 186

Obungen 191

5 Die Grundlagen der Prozessorimplementierung 198 5.1 Einflihrung 199 5.2 Prozessor -Datenpfad 201 5.3 Ausftihrungsgrundschritte 202 5.4 Festverdrahtete Steuerung 204 5.5 Mikroprogrammierte Steuerung 208 5.6 Interrupts und andere Schwierigkeiten 214 5.7 Zusammenfassung:

Steuerung fOr die DLX 220 5.8 [rrtilmer und Fallen 238 5.9 SchluBbemerkungen 240 5.10 Historisches lind Literaturquellen 241

Obungen 244

6 Pipelining 250 6.1 Was ist Pipelining? 251 6.2 Die Basis-Pipeline fUr die DLX 252 6.3 Die Pipeline zum Laufen bringen 255 6.4 Die Haupthindernisse des Pipelining - Pipeline-Hasards 257 6.5 Warum ist Pipelining schwer zu implementieren? 278 6.6 Erweiterung der DLX-Pipeline zur Behandlung von

Mehrzyklusoperationen 284 6.7 Fortgeschrittenes Pipelining - Dynamisches Scheduling in Pipelines 290 6.8 Fortgeschrittenes Pipelining - Erweiterte Befehlsebenen-Parallelitat 314 6.9 Zusammenfassung:

Eine V AX mit Pipeline 328 6.10 [rrttimer und Fallen 334 6.11 SchluBbemerkungen 337 6.12 Historisches und Literaturquellen 338

Obungen 343

Rechnerarchitektur: Analyse, Entwurf, Implementierung und Bewertung xiii

7 Vektorprozessoren 350 7.1 Warum Vektormaschinen? 351 7.2 Die Basis-Vektorarchitektur 353 7.3 Zwei praktische Probleme:

VektorHinge und Schrittweite der Vektorelcmente 364 7.4 Ein einfaches Modell der Vektorleistung 369 7.5 Compilertechnologic fUr Vcktormaschinen 371 7.6 Steigerung der Vektorleistung 377 7.7 Zusammenfassung:

Leistungsbewertung von V cktorprozessoren 3R3 7.8 Irrtilmer und Fallen 390 7.9 SchluBbcmerkungen 392 7.10 Historischcs und Literaturquellen 393

Obungen 397

8 Speicherhierarchie-Entwurf 402 8.1 EinfUhrung:

Das Prinzip der Lokalittit 403 8.2 Allgemeine Prinzipicn der Spcicherhierarchie 404 8.3 Caches 408 8.4 Hauptspeicher 425 8.5 Virtueller Speicher 432 8.6 Zugriffsschutz und Beispiele virtueller Speicher 438 8.7 Weitere Optimierung auf der Grundlage des Programmvcrhaltens 449 8.8 Steigerung der Cache-Leistung 454 8.9 Zusammcnfassung:

Die Speicherhierarchie der VAX-I 1/780 475 8.10 Irrtilmer und Fallen 480 8.11 SchluBbemerkungcn 484 8.12 Historisches und Literaturquellen 485

Obungen 490

9 Ein·/ Ausgabe 498 9.1 Einfilhrung 499 9.2 Vorhersage der Systemleistung 501 9.3 EI A-Leistungsmessung 506 9.4 Arten von E/A-Geraten 512 9.5 Busse - Verbindungen zwischen E/A-Geraten und CPU/Speicher 528 9.6 Interface zur CPU 533 9.7 Interface zum Betriebssystem 535 9.8 Entwurf eines EI A-Systems 539 9.9 Zusammenfassung:

Das IBM 3990-Speichersubsystem 546 9.10 Irrtilmer und Fallen 554 9.11 SchluBbemerkungen 559 9.12 Historisches und Literaturquellen 560

Obungen 563

xiv Inhaltsverzeichnis

10 Entwicklungsrichtungen 570 10.1 Einfiihrung 571 10.2 Flynns Rechnerklassifizierung 572 10.3 SIMD-Rechner

Single Instruction Stream, Multiple Data Streams 572 10.4 MIMD-Rechner

Multiple Instruction Streams, Multiple Data Streams 574 10.5 Die Wege zum Eldorado 576 10.6 Spezialprozessoren 580 10.7 Entwicklungsrichtungen bei Compilern 581 10.8 Zusammenfassung:

Der Symmetry-Multiprozessor von Sequent 582 10.9 irrtiimcr und Fallen 585 10.10 SchluBbemerkungen:

Evolution oder Revolution in der Rechnerarchitektur 587 10.11 Historisches und Literaturquellen 588

Obungen 592

Anhang A: Rechnerarithmetik A·I von DAVID GOLDBERG Xerox Palo Alto Research Center

A.l Einflihrung A-I A.2 Grundlagen der Festkommaarithmetik A-2 AJ Gleitkomma A-12 A.4 Gleitkommaaddition A-16 A.5 Gleitkommamultiplikation A-20 A.6 Division unJ Rest A-23 A.7 Genauigkeiten und Ausnahmebehandlung A-28 A.8 Beschleunigung der Festkommaaddition A-31 A.9 Beschleunigung der Festkommamultiplikation und -division A-39 A.IO Zusammenfassung A-53 A.Il Irrtiimer und Fallen A-57 A.12 Historis~hes und Litcraturquellen A-58

Obungen A-63

Anhang B: Vollstandige Befehlssatztabellen B·I B.I VAX-Nutzerbefehlssatz B-2 B.2 System/360-Befehlssatz B-6 B.3 8086-Befehlssatz B-9

Anhang C: Detaillierte Befehlssatzmessungen C·I C.l Messungen an der V AX C-2 C.2 Messungen an der 360 C-3 C.3 Messungen am Intel 8086 C-4 C.4 DLX-Befchlssatzmessungcn C-5

Anhang D: Vergleich von Zeit· und Haufigkeitsmessungen D·I D.I Zcitverteilung der V AX 111780-Befehle D-2 D.2 Zeitverteilung der IBM 3701168-Befehle D-4 DJ Zeitverteilung des 8086-Befehle in einem IBM-PC D-6 D.4 Zcitverteilung der einer DLX-iihnlichen Maschine D-8

Rechnerarchitektur: Analyse, Entwurt, Implementierung und Bewertung xv

Anhang E: Uberblick zu RISC-Architekturen E-1 E.l Einfiihrung E-l E.2 Addressierungsarten und Befehlsformate E-2 EJ Die Befehle des DLX-Subset E-4 E.4 Allgemeine Erweiterungen der DLX-Befehle E-9 E.5 Spezielle MIPS-Befehle E-l2 E.6 Spezielle SPARC-Befehle E-l5 E.? Spezielle M88000-Befehle E-l? E.8 Spezielle i860-Befehle E-19 E.9 SchluBbemerkungen E-23 E.IO Literaturquellen E-24

Zusammenstellung der Literaturquellen L-1

Sachwortverzeichnis S-l

Rechnerarchitektur: Analyse, Entwurf, Implementierung und Bewertung xvii

I Einleitung

lch begann 1962 ein eillzelnes Buch mit der ublichen Kapitelfolge zu schreiben, merkte aber bald, daj3 es wichtiger ist, die Themell tiefgrundiger zu behandeln, anstelle .lie flur ZU

streifen. Daraus ergab sich, daj3 jedes Kapitel selbst genug Material fur eille einsemestrige Vorlesung enthalt, und e:; wurde nOtig, die Serie in separaten Banden zu veroffentlichen ...

Donald Knuth, The Art of COlllputer Programming, Vorworl zu Band I (von 7) (1968)

Warum wir dieses Buch geschrieben haben

Willkommen! Wir freuen uns, daB wir die Gelegenheit haben, mit Ihnen in Kontakt zu treten. Es gibt so viele aufregende Entwicklungen in der Rechnerarchitektur, aber die vorhandenen Materialicn vermittcln dariiber zu wenig Kenntnissc. Das ist keine trockene Wissenschaft, die nur Maschincn auf dem Papier entwirft. Nein l Es ist cine stark intellek­tuelle Disziplin, die die Bcachtung des Marktcs und des Kosten/Leistungs-Verhiiltnisses er­fordert und zu groBen MiHgriffen, aber auch beachtlichen Erioigcn flihrtc. Und es ist schwer, das Geflihl zu beschreiben, wenn Tausende von Menschcn spiiter mit der Maschine arbeiten, die Sie selbst moglicherweise entwickelt haben.

Das Hauptanliegen dieses Buches ist, Rcchncrarchitektur in neuer Weise zu vermittcln. Wir wollen weg von nur Definitionen und historischcn Informationen, hin zu realen Bei­spielen und realen Messungen. Wir halten das Buch sowohl fUr cine Vorlesung tiber Rechnerarchitektur als auch als Nachschlagewcrk fijr professionclle Ingenieurc und Rcch­nerentwerfer geeignet. Dieses Buch trag! vor allem wr Dernystifizicrung der Rechncrar­chitektur bei - es beton! den quantitativ orientierten Ansatz fiir den Kos[en/Leistungs­Kompromil3. Urn ein ingenieurmaHiges Herangehen zu erreichen, sind cine Menge von Daten tiber reale Maschincn cnthaltcn, so daB der Leser die Entwurl'skompromisse sowohl quantitativ als auch qualitativ verstcht. Ein wesentlicher Teil dieser Hcrangchcnsweise sind auch die Fragen am Ende jedcs Kapitels. Solche Ubungcn bilden scit langem den Kern der Wissenschaft und der Ingenieurausbildung.

xviii Einleitung

Themenauswahl und Organisation

Wir haben nieht versueht, dem Leser cinen vollstandigen Uberbliek iiber jede Arehitektur zu gebcn, die ihm in Literatur oder Praxis begegnen konnte, sondern die Grundkonzepte der Rechnerarchitektur ausgewahlt, die in fasl jeder neuen Maschine auftreten. Zum Beispiel konzentrieren wir uns auf Einprozessorsysteme, mit Ausnahme des letzten Kapitels, in dcm ein busorientiertes Multiprozessorsystem mit einem gemeinsamen Speicher bcschricben wird. Wir glauben zwar, daB diese Klasse von Rechnern an Popularitiit gewinnen wird, aber ungeachtet dessen sind sie zur Zeit nur eine Randerscheinung. Dicsc Architekturklasse wurde gerade jelZl so we it untersucht, daB wir sie hier in quantitativer Hinsicht diskutieren konnen; noch vor kurzem ware das nicht moglich gewesen. Obwohl groBe Parallelprozessoren sehr wichtig flir die Zukunft sind, glaubcn wir doch, daB solides Wissen auf dem Gebiet des Einprozessorentwurfs notig ist, ehe sich jeder praktische lngenieur an den Bau eines besseren Rechners, der insbesondere aus mehreren Ein­zelprozessoren hestcht, heranwagen kann.

Leser, die unsere Forschungsarbeit kennen, konnten glauben, daB in diesem Buch nur Reduced Instruction Set Computer (RISC) hesprochen werden. Das ist aber ein falseher Eindruck vom lnhalt dieses Buehes. Wir hoffen, daB - im Gegensatz zu bisherigen Dchattcn - die Entwurfsprinzipien und quantitativen Daten in dies em Buch die Diskussion zum Architekturstil auf Begriffe wie "schneller" und "billiger" richtct.

Den von uns ausgewahlten Stoff haben wir in einer bestimmten Slruktur aufbereitet, die sich in jedem Kapitel wiederholt. Nach der ErHiuterung der Hauptgedanken eines Kapitels folgt immer eine Zusammenfassung, in der zugleich die Anwendung in realen Maschinen demonstriert wird. ~s schlieBt sich an ein Abschnitt mit dem Titel "lrrtiimer und Fallen", in dem die Leser aus den Fehlern anderer lernen sollen. Wir zeigen Beispiele von ge­wohnlichen MiBverstandnissen und von Archilekturfallen, die schwer zu verhindern sind, sogar wenn man sic kennt. Jedes Kapitel endet mit SchluBbemerkungen, gefolgt yom Ab­schnitt "Historisches und Literaturquellen", der versucht, den historischen Hintergrund und das menschliche Dilemma des Rechnerentwurfs zu vennitteln. Es werden auch Literalur­quellen aufgefiihrt, die den Architekturstudenten zur Vertiefung dienen konnen. Wenn Sic Zeit haben, sollten Sie unbedingt einige der historischen VerOffentlichungen lesen, die in diesen Abschnitten aufgefiihrt sind. Es ist sowohl unterhaltsam als auch lehrreich, die ldeen direkt aus dem Munde ihrer Schopfer zu horen. Jedes Kapitel endet mit Ubungen, insgesamt mehr als 200, die von kurzen Fragcn bis zu groBeren Projekten reichen.

Ein Blick auf das Inhaltsverzeichnis zeigt, daB weder der Umfang noch die Tiefe des Materials in den Kapiteln gleich is!. Die ersten Kapitcl zum Beispiel enthalten mchr grundJegcndes Wissen zur Sicherung einer einheitlichen Terminologie und gleicher Voraussetzungen. In Gesprachen mit Kollegen gab es hreilgefiicherte Auffassungen zu den Voraussetzungen, die die Leser haben, dem Tempo, mit dem sie neues Wissen aufnehmen konnen, und auch der Reihenfolge, in der der Stoff dargelegt werden sollte. Wir setzen voraus, daB der Leser den Logikentwurf beherrscht und mindestens einen Befehlssatz und die grundlegenden Soflwarekonzcpte kennt. Das Tempo dcr Kapitel ist verschieden - in der crsten Hiilfte behutsamer als in der ktzten. Bei den Entscheidungen zur Reihenfolge wurden Hinweise der Lektoren beriicksichtigt. Die endgiiltige Anordnung der Kapitel wurde mit geringen Modi hkalionen passend zur Mehrhcit der Vorlesungen (iiber Berkeley und

Rechnerarchiteklur: Analyse, Entwurf,lmplementierung und Bewertung xix

Stanford hinaus!) gewahlt. In Abhangigkeit von Ihren Zielen sehen wir drei Wege durch den Stoff:

Einfohrendes Niveau:

Mittleres Niveau:

Kapitell, 2, 3, 4, 5, 6.1-6.5, 8.1-8.5,9.1-9.5,10 und A.3.

Kapitel 1,2,3,4,5,6.1-6.6,6.9-6.12,8.1-8.7,8.9-8.12,9, 10, A (mit Ausnahme des zu tiberspringenden markierten Teiles in Abschnitt A.9) und E.

Fortgeschrittenes Niveau: Lesen Sie alles, wobei die Kapitel 3 und 5 und die Abschnitte A.1-A.2 und 9.3-9.4 groBtenteils Wiederholung sein werden.

Leider gibt es keine absolut beste Reihenfolge der Kapitel; zum Beispiel ware es gut, etwas tiber Pipelining (Kapitel 6) zu wissen, ehe man Befehlssatze (Kapitel 3 und 4) dis­kutiert. Aber es ist schwer, Pipelining zu verstehen, ohne den ganzen Befehlssatz verstan­den zu haben, auf den es angewendet werden soIl. Wir selbst haben in frtiheren Fassungen des Textes eine etwas abweichende Reihenfolge versucht, doch jede hatte ihre Probleme. ledenfalls wurde der Stoff so geschrieben, daB er auf verschiedenen Wegen gelesen werden kann. Die Abfolge erwies sich im Beta-Test-Programm an 18 Hochschulen als hinreichend flexibel. Die einzige Einschrankung ist, daB einige Kapitel nacheinander gelesen werden soli ten und zwar:

Kapitel lund 2

Kapitel 3 und 4

Kapitel 5, 6, und 7

Kapitel 8 und 9

Man sollte mit den Kapiteln lund 2 beginnen und mit KapitellO enden, der Rest kann in jeder Reihenfolge studiert werden. Der einzige Vorbehalt ist, daB, falls Sie Kapitel 5, 6, und 7 vor Kapitel 3 und 41esen, Sie zunachst Abschnitt 4.5 tiberfliegen soil ten, da der dort dargestcllte Befehlssatz DLX in den drei Kapiteln genutzt wird. Eine zusammengefaBte Beschreibung von DLX und der Hardwarebeschreibungsnotation, die wir benutzen, linden Sie auf dem inneren Umschlag. (Wir wahlten eine modifizierte Version von C fUr un sere Hardwarebeschreibungssprache, wei I sie sehr kompakt ist, viele Menschen sie kennen und wei I es keine in Btichern genutzte Beschreibungssprache gibt, die Rticksicht auf Vorbedin­gungen nimmt.)

xx Einleitung

Wir raten jedem, die Kapitel lund 2 zu lesen. Dem Kapitell ist leicht zu folgen, so daB es sich auch fiir Anfiinger schnell liest. Es beinhaltet einige wiehtige Prinzipien, die Grundlage fiir spiitere Kapitel sind. Wahrend einige den Abschnitt Leistung in Kapitel 2 iiberspringen, werden andere den Kostenabschnitt iibergehen, urn sieh mehr den technischen Fragen in spateren Kapiteln zu widmen. Tun Sie dies bitte nieht! Rechnerentwurf is! fast immer eine Balance zwischen Kosten und Leistung, und nur wenige verstehen, wie sich der Preis zu den Kosten verhalt oder wie man Kosten und Preis urn \0% senkt, ohne einen wesentlichen Leistungsverlust zu haben. Mit dem Kostenabschnitt in Kapitel 2 wird die Grundlage fiir alle Aussagen in der zweiten Halfte des Buehes gelegt. Andererseits konnten auch einige Themen zum spateren Nachlesen zunachst iibergangen werden. Wird das Buch im Rahmen einer Vorlesung genutzt, kann in den Lektionen gezeigt werden, wie man die Daten aus diesen Kapiteln fiir Entscheidungen im Rechnerentwurf nutzt; Kapitel 4 ist wahrscheinlieh dafiir das beste Beispiel. Abhangig von Ihrem Vorwissen kennen Sie einen Teil des Stoffes sicherlich schon, aber wir haben versucht, zu jedem Thema ein paar neue Aspekte hinzuzufiigen. Der Abschnitt iiber Mikroprogrammierung in Kapitel 5 wird fiir viele Wiederholung sein, aber die Beschreibung des Einflusses von Interrupts auf die Steuerung findet man in anderen Biichem kaum.

Wir haben auch versucht, das Buch fiir praktische Ingenieure und in der fortgeschrittenen Graduierung befindliche Studenten interessant zu machen. So findet man weiterfiihrende Themen in:

Kapitel6 zu Pipe1ining (Abschnitte 6.7 und 6.8 mit etwa der Hiilfte des Kapitels)

Kapitel 7 zu Vektorprozessoren (ganzes Kapite1)

Kapitel8 zum Speicherhierarchie-Entwurf (Abschnitt 8.8 mit etwa einem Drittel des Kapitels)

KapitellO zu zukiinftigen Entwicklungsrichtungen (Abschnitt 10.7 mit etwa einem Viertel des Kapite1s)

So konnte man, falls unter Zeitdruck, einige dieser Abschnitte iiberspringen. Zum Beispiel kann man die Zusammenfassungen der Kapitel6 und 8 weglassen, weil sie von den spate­ren Themen unabhiingig sind.

Wie Sie bemerkt haben, wird Gleitkomma im Anhang behandelt und nicht in einem Kapitel. Da es ziemlich unabhangig von dem anderen Stoff ist, haben wir uns fiir den Anhang entschieden, weil nach un serer Kenntnis ein bedeutender Prozentsatz der Leser dieses Thema sowieso auslassen wiirde.

Die restlichen Anhiinge wurden sowohl zu Referenzwecken fiir den Computerspezia­listen als auch fiir Ubungen hinzugefiigt. Anhang B enthalt die Befehlssatze der drei klassischen Maschinen IBM 360, Intel 8086 und DEC V AX. Die Anhiinge C und D zei­gen den Befehlsmix in realen Programmen fiir diese Maschinen plus DLX, entweder als Befehlshiiufigkeit oder Zeitanteil gemessen. Anhang E gibt eincn detai11ierten verglei­chenden Uberblick iiber verschiedene aktuelle Architekturen.

Rechnerarchitektur: Entwurf, Implementierung und Bewertung xxi

Obungen. Projekte und Software

Die Auswahlmiiglichkeiten des Stoffes werden auch in den Ubungen deutlich. In Klammern ist zujeder Frage «Kapitel.Abschnitt» der wesentlichste Abschnitt im Text mit dem Stoff zur Beantwortung angegeben. Wir hoffen, daB das flir die Leser hilfreich ist. Wir haben Donald Knuths Technik zur Bewertung der Ubungen angewandt. Es wird angegeben, welcher Aufwand fUr die Liisung eines Problems niitig ist:

[10]1 Minute (lesen und verstehen)

[20]15-20 Minuten fUr die ganze Antwort

[25]1 Stunde fUr die geschriebene Antwort

[30] Kurzes Programmierprojekt: weniger als 1 Tag

[40] Bedeutendes Programmierprojekt: 2 Wochen

[50] Semesterprojekt (2-4 Wochen flir 2 Leute)

[Diskussion] Diskussionsthema mit anderen an Rcchnerarchitektur Interessierten.

Urn die Nutzung des Buches in Lehrveranstaltungen zu erleichtern, steht die Software und (in englischer Sprache) ein Instructors Manual zur VerfUgung. Die Software ist ein Unix-Tar-Band, das Benchmarks, Cache-traces, Cache- und Befehlssatzsimulatoren und einen Compiler enthtilt. Ftir interessierte Leser ist die Software mittels anonymen FTP tiber Internet von max.stanford.edu abrufbar. Kopien kann man auch tiber Morgan Kaufmann (415) 578-9911 erhalten. (Duplizierungs- und Versandkosten werden in Rechnung gestellt.)

SchluBbemerkungen

Wenn Sie die folgenden Danksagungen lesen, werden sie sehen, daB wir groBen Auf­wand in die Korrektur von Fehlern steckten. Wenn ein Buch mehrere Autlagen hat, hat man die gtinstige Gelegenheit, auch mehr Korrekturen zu machen. SoIl ten Sic restliche Fehler bemerken, inforrnieren Sie bittc den Verlag. Dcr erstc Leser, der cincn Fehler mitteilt, der in einer Folgeautlage noch enthalten ist, wird mit $1.00 belohnt.

SchlieSlich ist das Buch ungewiihnlich, weil es keine strikte Reihenfolge der Namen der Autoren gibt. Etwa in der Halfte der FaIle werden Sie Hennessy und Patterson sehen, in weiteren 50% der faIle Patterson und Hennessy. Sic werden cs auch in beiden Arten in bibliographischen Publikationen wie in Books in Print finden. Das verdeutlicht die wirk­lich gemeinsame Natur dieses Buches: Gemeinsam erdachten wir die Inhalte und die Methode der Darstellung, schrieben die Htilfte der Kapitel und waren Rezensent flir jcdcn

xxii Einieitung

Entwurf der anderen Halfte (Tatsachlich hat jeder von uns dieselbe Zahl von Seiten geschrieben!). Wir wissen keinen anderen fairen Weg, diese einmalige Zusammenarbeit darzustellen, als den, uns in der Doppeldeutigkeit zu verstecken - eine Praktik, die den Autoren hilft, aber die Bibliothekare verwirrt. SchlieBlich teilen wir auch die Verantwor­tung fiir das, was Sie gerade lesen.

John Hennessy David Patterson Januar 1990

Rechnerarchitektur: Analyse, Entwurf, Implementierung und Bewertung xxiii

I Danksagungen

Dieses Buch konnte nur mit der Hilfe sehr vieler Menschen geschrieben werden; tatsachlich so vieler, daB die meisten Autoren es mit dieser Feststellung be wenden lassen wiirden. Wir lehnen das ab, weil sonst der Wert dieser Hilfe verheimlicht wiirde. So nennen wir hier die 137 Personen und fiinfInstitutionen, denen unser Dank gilt.

Als wir uns entschieden, einen Anhang zum IEEE-Gleitkomma-Standard aufzunehmen, baten wir viele Kollegen, uns jemanden zu benennen, der diesen Standard beherrscht, gut schreiben kann und seine komplexen Gedanken auch einfach darzulegen verrnag. David Goldberg, von Xerox Palo Alto Research Center, erfiillte aile diese Anforderungen in bewundemswerter Weise und setzte damit MaBstabe fiir den Rest des Buches.

Margo Seltzer, U.c. Berkeley, verdient besonderes Lob. Sie war nicht nur die erste Assistentin des Kurses in Berkeley, die das Material nutzte, sondern sie trug auch all die Software, Benchmarks und AbHiufe zusammen, die wir mit dies em Buch vertreiben. Sie fiihrte auch die Cache- und Befehlssatzsimulationen aus Kapitel8 durch. Wir danken ihr fiir die prompte und zuverlassige Erledigung der Endbearbeitung der Software zu einem einheitlichen Ganzen.

Bryan Martin und Truman Joe aus Stanford verdienen ebenso unseren speziellen Dank fiir das schnelle Lesen der Ubungen der ersten Kapitel kurz vor SchluB der Heraus­gabe im Herbst. Ohne ihre Mitwirkung hatten die Ubungen nicht den letzten Schliff bekommen.

Unser Plan fiir das vorliegende Material sah zunachst vor, seine Grundgedanken in den Hcrbstsemestem 1988 in Berkeley und Stanford zu erproben. Wir erstellten Vorlesungs­skripte zunachst fUr die Studenten von Berkeley (weil das akademische Jahr dort vor Stanford beginnt), korrigierten noch einige Fehler und trugen dann den Studenten in Stan­ford diese Gedanken VOL Das war vielleicht nicht das beste Erlebnis ihres akademischen Lebens, und so wollen wir jenen danken, die sich gewisserrnaBen als Versuchskaninchen zur VerfUgung stellten. Ebenso den Assistenten Todd Narter, Margo Seltzer und Eric Williams, die die Konsequenzen dieses gewaltigen Experiments zu erdulden hatten.

Der nachste Schritt des Plans war, im Winter 1989 ein Konzept des Buches zu schrei­ben. Entgegen der urspriinglichen Auffassung, die Vorlesungsskripte nur in ein ordentli­ches Englisch zu setzen, wurde das aufgrund der Riickkopplung seitens der Studenten und der Erkenntnisse, die wir beim Schreiben sammeln konnten, zu einer wesentlich gr6Beren Aufgabe als wir je dachten. Diese Alphaversion wurde im Friihjahr 1989 den Rezensenten zugeschickt. Ein bcsonderer Dank geht an Anoop Gupta von der Stanford University und Forest Baskett von Silicon Graphics, die die Alphaversion fUr cine Klassc in Stanford im Herbst 1989 nutzten.

xxiv Danksagungen

Die Rechnerarchitektur hat sowohl eine akademische, als auch eine industrielle Seite. Wir holten daher Expertisen verschiedener Art ein. Zu den akademischen Rezensenten der Alphaversion gehorten Thomas Casavant, Purdue University, Jim Goodman, University of Wisconsin at Madison, Roger Kieckhafer, University of Nebraska, Hank Levy, University of Washington, Norman Matloff, University of California at Davis, David Meyer, Purdue University, Trevor Mudge, University of Michigan, Victor Nelson, Auburn University, Richard Reid, Michigan State University, und Mark Smotherman, Clemson University. Wir mochten auch jenen danken, die uns im Herbst 1989 eine Riickantwort gaben: Bill Dally, MIT, und Jim Goodman, Hank Levy, David Meyer, und Joseph Pfeiffer, New Mexico State. Anderungen in unseren Planen testete im April 1989 eine Diskussionsgruppe mit Paul Barr, Northeastern University, Susan Eggers, University of Washington, Jim Goodman und Mark Hill, University of Wisconsin, James Mooney, University of West Virginia, und Larry Wittie, SUNY Stony Brook. Wir schalzen ihre hilfreichen Ralschliige.

Bevor wir die Industrierezensenten nennen, geht unser spezieller Dank an Douglas Clark von DEC, der uns mehr Hinweise zur Alphaversion gab als aile anderen zusammen. Verschiedene Kapitel der Alphaversion wurden von David Douglas und David Wells, Thinking Machines, Joel Emer, DEC, Earl Killian, MIPS Computer Systems Inc., und Jim Smith, Cray Research, durchgesehen.

Dank auch an Maurice Wilkes, Olivetti Research, und C. Gordon Bell, Stardent, flir ihre Hilfe bei der Erstellung der historischen Abschnitte am Ende jedes Kapitels.

Zusatzlich zu jenen, die sich der Aufgabe unterzogen, mehrere Kapitcl zu lesen, moch­tcn wir auch den en danken, die uns Anregungen zur Aufnahme von Material iibermittelten:

Kapitel I: Danny Hillis, Thinking Machines, fUr seine Anregung zur Zuweisung von Ressourcen in Bezug auf ihre Wirkung auf die Leistung.

Kapitel 2: Andy Bechtolsheim, Sun Microsystems, fUr seinen Ratschlag zum Preis/Kosten­Verhaltnis und zur Kostenschatzung yon Workstations; David Hodges, University of California at Berkeley, Ed Hudson und Mark Johnson, MIPS, Al Marston und Jim Slager, Sun, Charles Stapper, IBM, und David Wells, Thinking Machines, fUr die Erlauterung der Chipherstellung und der Ausbeute; Ken Lutz, U.c. Berkeley, und der FAST chip service, USCIISI, fUr die Preise von Chips; Andy Bechtolsheim und Nhan Chu. Sun Microsystems, Don Lewine, Data General. und John Mashey und Chris Rowen, MIPS, die das Kapitel rezensierten.

Kapitel 4: Tom Adams, Apple und Richard Zimmermann, San Francisco State University, fUr ihre Statistik des Intel 8086 ; John Crawford, Intel, flir die Durchsicht des 80x86- und anderen Materials; Lloyd Dickman fUr die Durchsicht des IBM 360-Materials.

Kapitel 5: Paul Carrick and Peter Stoll, Intel, flir die Durchsicht.

Kapitel 7: David Bailey, NASA Ames, und Norm Jouppi, DEC, flir die Durchsicht.

Kapitel 8: Ed Kelly, Sun, fUr die Hilfe bei der ErkHirung von DRAM-Alternativen und Bob Cmelik, Sun, flir die SPIX Statistik; Anant Agarwal, MIT. Susan Eggers, University of Washington, Mark Hill, University of Wisconsin at Madison, und Steven Przybylski, MIPS. flir Material aus ihrcn Disscrtationen; und Susan Eggers und Mark Hill flir Durchsichten.

Rechnerarchitektur: Analyse, Entwurf, Implementierung und Bewertung xxv

Kapitel 9: Jim Brady, IBM, flir die Uberlassung quantitativer Daten zur Antwortzeit von IBM­Rechnern, sowie die Durchsicht des Kapitels; Garth Gibson, University of California at Berkeley, flir die Hilfe bei Verweisen zu Bussen und die Durchsicht des Kapitels; Fred Berkowitz, Omni Solutions, David Boggs, DEC, Pete Chen und Randy Katz, University of California at Berkeley, Mark Hill, University of Wisconsin, Robert Shomler, IBM, und Paul Taysom, AT&T Bell Laboratories, fUr Durchsichten.

Kapitel 10: C, Gordon Bell, Stardent, fUr seinen Vorschlag, einen Multiprozessor in die Zusammenfassung aufzunehmen; Susan Eggers, Danny Hillis, Thinking Machines, und Shreekant Thakkar, Sequent Computer fUr Durchsichten.

Anhang A: Die Aussagen zu IEEE REM und zur Argumentenreduktion im Abschnitt A.6, sowic dem p::; (ql)/2-Theorem entnahmen wir unveriiffentlichten Vorlesungsskripten von William Kahan, U.C. Berkeley (denn wir kennen keine verOffentlichtcn Quellen dazu). Die SDRWA VE Daten sind von David Hough, Sun Microsystems. Mark Birman, Weitek Corporation, Merrick Darley, Texas Instruments und Mark Johnson, MIPS, stellten Informationen tiber den 3364, 8847 und R3010 lur VerfUgung. William Kahan las cinen Entwurf dieses Kapitels und gab viele treffende Hinwcise. Wir danken auch Forrest Brewer, University of California at Santa Barbara, Milos Ercegovac, University of California at Los Angeles, Bill Shannon, Sun Microsystems und Behrooz Shirazi, Southern Methodist University, fUr Durchsichten.

Die zum Buch gehiirende Software wurde von Margo Seltzer, University of California at Berkeley, gesammelt und bearbeitet. Folgende Personen steHten ihre Software fUr uns zur VerfUgung:

C Compiler fUr DLX: Yong-dong Wang, U.c. Berkeley und die Free Software Foundation

Assembler fUr DLX: Jeff Sedayo, U.c. Berkeley

Cache Simulator (Dinero III): Mark Hill, University of Wisconsin

ATUM Traces: Digital Equipment Corporation, Anant Agarwal, und Richard Sites

Die erste Version des Simulators fUr DLX wurde von Wie Hong und Chu-Tsai Sun, U.c. Berkeley, entwickelt.

Obwohl viele uns rieten, uns zuviel MUhe zu ersparcn und lieber das Buch cher fcrtig­zusteHen, blieben wir dabei, cin ordentliches Buch zu veriiffentliehen, und hildeten cine zusatzliche Gruppe fUr die Endrunde. Das Buch ware nieht so nUtzlich gewcscn, wic es heute ist, wenn sich nicht Dozenten und Assistenten, aher auch Studentcn bcrcitgcfundcn hatten, in ihren Vorlesungen und Ubungcn"Betatcsts" luzulassen. Das Ergcbnis hestand in Hunderten von Anderungen. Die Betatest-Institutionen und -Dozenten waren:

xxvi Danksagungen

Carnegie-Mellon University Clemson University Cornell University Pennsylvania State University San Francisco State University Southeast Missouri State University Southern Methodist University Stanford University State University of New York at Stony Brook University of California at Berkeley University of California at Los Angeles University of California at Santa Cruz University of Nebraska University of North Carolina at Chapel Hill University of Texas at Austin University of Waterloo University of Wisconsin at Madison Washington University (St. Louis)

Daniel Siewiorek Mark Smotherman Keshav Pingali Mary Jane Irwin/Bob Owens Vojin Oklobdzija Anthony Duben Behrooz Shirazi John Hennessy Larry Wittie Vo.jin Oklobdzija David Rennels Daniel Helman Roger Kieckhafer Akhilesh Tyagi Joseph Rameh Bruno Preiss Mark Hill Mark Franklin

Besondere Erwahnung sollen Daniel Helman, Mark Hill, Mark Smotherman und Larry Wittie finden, die besonders viele Ratschlage erteilten. Die Zusammenstellung der Uisungen der Ubungen wurde sehr durch Beitragc von Evan Tick, University of Oregon, Susan Eggers, University of Washington, und Anoop Gupta, Stanford University, unlerstiitzt.

Die Klassen von SUNY Stony Brook sowie der Universitiiten Carnegie-Mellon, Stanford, Clemson und Wisconsin unterstiitzten uns mit der groBten Zahl von in der Beta­version gefundenen Fehlern. Allen, die sich im Rahmen des $1.00-Programms am Auffinden von Fehler beteiligten, sci gesagt: Ihre Schecks befinden sich in der Post. Wir mochten darauf hinweisen, daB besonders viele Fehler von: Michael Butler, Rohit Chandra, David Cummings, David Filo, Carl Feynman, John Heinlein, Jim Quinlan, Andras Radics, Peter Schnorf und Malcolm Wing cntdeckt und bcseitigt wurden.

Zusatzlich zu den Tests an den Hochschulen baten wir auch unsere Freunde in der lndustrie urn Hilfc. Ein besondcrer Dank geht an Jim Smith, Cray Research, fUr cine Gesamtdurchsicht des Bctatestes. Folgende Personen halfen uns, die Betaversion zu ver­bessern, und wir danken ihnen:

Ben Hao, Sun Microsystems, fur die Durchsicht der gesamten Betaversion.

Ruby Lee, Hewlett-Packard, lind Bob Supnik, DEC, fUr die Durchsicht verschiedener Kapitcl.

Kapitel 2: Steve Goldstein, Ross Semiconductor, und Sue Stone, Cypress Semiconductor, fUr Photographicn und den Wafer des CY7C601; John Crawford und Jacque Jarve, Intel, fUr die Photographien und den Wafer des Intel 80486; und Dileep Bhandarkar, DEC, fUr die Hilfc mit der VMS Version von Spice lind TeX in den Kapitcln 24.

Rechnerarchitektur: Analyse, Entwurt, Implementierung und Bewertung xxvii

Kapitel 6: John DeRosa, DEC, fiir die Hilfe mit der 8600-Pipeline.

Kapitel 7: Corinna Lee, University of California at Berkeley, fUr Messungen an der Cray X-MP und Y-MP und fUr Durchsichten.

Kapitel 8: Steven Przybylski, MIPS, fUr Durchsichten.

Kapitel 9: Dave Anderson, Imprimis, fUr Durchsichten und Material zu Plattenzugriffszeiten; Jim Brady und Robert Shomler, IBM, fiir Durchsichten und Pete Chen, Berkeley, fUr Anregungen zu den Systemleistungsformeln.

Kapitel 10: C. Gordon Bell fUr Durchsichten einschlieBlich verschiedener Anregungen zur Klassifizierung von MIMD-Maschinen und David Douglas und Danny Hillis, Thinking Machines, fUr Diskussionen zu zukiinftigen Parallelprozessoren.

Anhang A: Mark Birman, Weitek Corporation, Merrick Darley, Texas Instruments, und Mark Johnson, MIPS, fUr die Photographien und die Lageplane der Funktionselemente (floor plans) ihrer Chips; David Chenevert, Sun Microsystems, fUr Durchsichten.

Anhang E: Dieser wurde nach der Betaversion hinzugefiigt und wir danken fUr die Durchsicht: Mitch Alsup, Motorola, Robert Garner und David Weaver, Sun Microsystems, Earl Killian, MIPS Computer Systems, :Ind Les Kohn, Intel.

Wir haben unser Bestes gegeben, urn Fehler zu vermeiden und die von den Rezensenten gefundenen zu beseitigen. Jetzt sind wir allein verantwortlich fUr die Fehler, die noch iibrig geblieben sind!

Wir machten auch der Defense Advanced Research Projects Agency fUr die jahrelange Unterstiitzung unserer wissenschaftlichen Arbeit danken. Diese Arbeit war die Basis dcr vielen Gedanken, die jetzt im Buch verwirklicht wurden. Insbesondere machten wir den gegenwiirtigen und ehemaligen Programmanagern Duane Adams, Paul Losleben, Mark Pullen, Steve Squires, Bill Bandy und John Toole danken.

Dank gebiihrt Richard Swan und seinen Kollegen des DEC Western Research Laboratory fUr das Versteck wiihrend des Schreibens der Alpha- sowie der Betaversion, und John Ousterhout, U.c. Berkeley, der als reitender Bote zwischen Berkeley und Palo Alto unterwegs war. Dank auch an die Thinking Machines Corporation fUr die Gewiihrung eines Zufluchtsortes wahrend der Endrevision.

Dieses Buch hatte nicht vertiffentlicht werden kannen ohne einen Verleger. John Wakerley gab uns wertvolle Hinweise, wie man einen findet. Wir wiihIten Morgan Kaufmann Publishers, Inc. aus und haben diese Entscheidung nie bereu!. Beginnend mit den Vorlesungsskripten, gleich nach Neujahr 1989, beendeten wir die Alphaversion in vier Monaten. In den niichsten drei Monaten erhieIten wir Rezensionen von 55 Leuten und vollendeten die Betaversion. Nach dem Klassentest mit 750 Studenten im Herbst 1989 und weiteren Rezensionen aus der Industrie beendeten wir die Endversion genau vor Weihnachten 1989. Das Buch war verfiigbar ab Marz 1990. Uns ist kein anderer Verleger bekannt, der mit einem solchen Fahrplan hiitte Schritt halten kannen. Wir machten Shirley Jowell danken, die sich in

xxviii Danksagungen

die Probleme des Pipelining und der Pipeline-Hasards hineindachte und Vorschlage fUr die VerOffentlichung maehte. Unser innigster Dank gilt unserem Herausgeber Bruce Spatz flir seine Fiihrung und seinen Humor bei unserem schriftstellcrischen Abenteuer. Wir dan­ken ebenfalls den Mitgliedern der groBen Kaufmann-Familie: Walker Cunningham fUr teehnisehe Fragen, David Lance Goines flir die Umschlaggestaltung, Gary Head flir das Buchdesign, Linda Medoff fUr VervicWiltigung und Produktion, dem Fifth Street Computer Services fUr den Computcrsatz und Paul Medoff fUr Korrekturlesen und Produktionsassistenz.

Wir danken auch unserer Universitatsmannschaft, Darlene Hadding, Bob Miller, Margaret Rowland und Terry Lessard-Smith, flir die zahllosen Faxe und Eilsendungen sowie das Halten der Stcllung in Stanford und Berkeley, wahrend wir am Bueh arbeiteten. Linda Simko und Kim Barger, Thinking Machines, sorgten fUr zahllose Eilsendungen wahrend des Herbstes.

Und schlieBlich geht unser lctztcr Dank an un sere Familicn, dic nieht nur die langen Tage und Nachte des Lesens und Schreibcns, sondern auch die Zeit der Vernachlassigung ertrugen.