Computer Architecture

by Muller, Silvia M.; Paul, Wolfgang J.

• ISBN13: 9783540674818
• ISBN10: 3540674810
• Format: Hardcover
• Copyright: 2000-07-01
• Publisher: Springer-Verlag New York Inc

Summary

Computer Architecture: Complexity and Correctness develops, at the gat e level, the complete design of a pipelined RISC processor with delaye d branch, forwarding, hardware interlock, precise maskable nested inte rrupts, caches, and a fully IEEE-compliant floating point unit. In con trast to other design approaches applied in practice and unlike other textbooks available, the design presented here are modular, clean and complete up to the construction of entire complex machines. The author sF systematically basing their approach on rigorous mathematical forma lisms allows for rigorous correctness proofs, accurate hardware costs determination, and performance evaluation as well as, generally speaki ng, for coverage of a broad variety of relevant issues within a reason able number of pages. The book is written as a text for classes on com puter architecture and related topics and will serve as a valuable sou rce of reference for professionals in hardware design.

Table of Contents

Introduction	1	(6)
Basics	7	(56)
Hardware Model	7	(5)
Components	7	(2)
Cycle Times	9	(1)
Hierarchical Designs	10	(1)
Notations for Delay Formulae	10	(2)
Number Representations and Basic Circuits	12	(5)
Natural Numbers	12	(2)
Integers	14	(3)
Basic Circuits	17	(5)
Trivial Constructions	17	(2)
Testing for Zero or Equality	19	(1)
Decoders	19	(2)
Leading Zero Counter	21	(1)
Arithmetic Circuits	22	(12)
Carry Chain Adders	22	(2)
Conditional Sum Adders	24	(3)
Parallel Prefix Computation	27	(1)
Carry Lookahead Adders	28	(2)
Arithmetic Units	30	(1)
Shifter	31	(3)
Multipliers	34	(16)
School Method	34	(1)
Carry Save Adders	35	(1)
Multiplication Arrays	36	(1)
4/2-Trees	37	(5)
Multipliers with Booth Recoding	42	(5)
Cost and Delay of the Booth Multiplier	47	(3)
Control Automata	50	(11)
Finite State Transducers	50	(1)
Coding the State	51	(1)
Generating the Outputs	51	(1)
Computing the Next State	52	(2)
Moore Automata	54	(1)
Precomputing the Control Signals	55	(1)
Mealy Automata	56	(2)
Interaction with the Data Paths	58	(3)
Selected References and Further Reading	61	(1)
Exercises	61	(2)
A Sequential DLX Design	63	(42)
Instruction Set Architecture	63	(6)
Instruction Formats	64	(1)
Instruction Set Coding	64	(4)
Memory Organization	68	(1)
High Level Data Paths	69	(2)
Environments	71	(17)
General Purpose Register File	71	(2)
Instruction Register Environment	73	(1)
PC Environment	74	(1)
ALU Environment	75	(3)
Memory Environment	78	(3)
Shifter Environment SHenv	81	(4)
Shifter Environment SH4Lenv	85	(3)
Sequential Control	88	(11)
Sequential Control without Stalling	88	(7)
Parameters of the Control Automaton	95	(2)
A Simple Stall Engine	97	(2)
Hardware Cost and Cycle Time	99	(5)
Hardware Cost	99	(1)
Cycle Time	100	(4)
Selected References and Further Reading	104	(1)
Basic Pipelining	105	(66)
Delayed Branch and Delayed PC	107	(4)
Prepared Sequential Machines	111	(19)
Prepared DLX Data Paths	114	(6)
FSD for the Prepared Data Paths	120	(2)
Precomputed Control	122	(6)
A Basic Observation	128	(2)
Pipelining as a Transformation	130	(13)
Correctness	131	(8)
Hardware Cost and Cycle Time	139	(4)
Result Forwarding	143	(8)
Valid Flags	144	(1)
3-Stage Forwarding	145	(3)
Correctness	148	(3)
Hardware Interlock	151	(8)
Stall Engine	151	(3)
Scheduling Function	154	(3)
Simulation Theorem	157	(2)
Cost Performance Analysis	159	(9)
Hardware Cost and Cycle Time	159	(1)
Performance Model	160	(2)
Delay Slots of Branch/Jump Instructions	162	(1)
CPI Ratio of the DLX Designs	163	(3)
Design Evaluation	166	(2)
Selected References and Further Reading	168	(1)
Exercises	169	(2)
Interrupt Handling	171	(68)
Attempting a Rigorous Treatment of Interrupts	171	(3)
Extended Instruction Set Architecture	174	(3)
Interrupt Service Routines For Nested Interrupts	177	(3)
Admissible Interrupt Service Routines	180	(10)
Set of Constraints	180	(1)
Bracket Structures	181	(1)
Properties of Admissible Interrupt Service Routines	182	(8)
Interrupt Hardware	190	(24)
Environment PCenv	191	(2)
Circuit Daddr	193	(1)
Register File Environment RFenv	194	(4)
Modified Data Paths	198	(4)
Cause Environment CAenv	202	(2)
Control Unit	204	(10)
Pipelined Interrupt Hardware	214	(13)
PC Environment	214	(2)
Forwarding and Interlocking	216	(4)
Stall Engine	220	(5)
Cost and Delay of the DLXΠ Hardware	225	(2)
Correctness of the Interrupt Hardware	227	(8)
Selected References and Further Reading	235	(1)
Exercises	236	(3)
Memory System Design	239	(78)
A Monolithic Memory Design	239	(14)
The Limits of On-chip RAM	240	(1)
A Synchronous Bus Protocol	241	(4)
Sequential DLX with Off-Chip Main Memory	245	(8)
The Memory Hierarchy	253	(12)
The Principle of Locality	254	(1)
The Principles of Caches	255	(8)
Execution of Memory Transactions	263	(2)
A Cache Design	265	(15)
Design of a Direct Mapped Cache	266	(2)
Design of a Set Associative Cache	268	(8)
Design of a Cache Interface	276	(4)
Sequential DLX with Cache Memory	280	(19)
Changes in the DLX Design	280	(10)
Variations of the Cache Design	290	(9)
Pipelined DLX with Cache Memory	299	(15)
Changes in the DLX Data Paths	300	(4)
Memory Control	304	(5)
Design Evaluation	309	(5)
Selected References and Further Reading	314	(1)
Exercises	314	(3)
IEEE Floating Point Standard and Theory of Rounding	317	(34)
Number Formats	317	(6)
Binary Fractions	317	(1)
Two's Complement Fractions	318	(1)
Biased Integer Format	318	(2)
IEEE Floating Point Numbers	320	(1)
Geometry of Representable Numbers	321	(1)
Convention on Notation	322	(1)
Rounding	323	(12)
Rounding Modes	323	(2)
Two Central Concepts	325	(1)
Factorings and Normalization Shifts	325	(1)
Algebra of Rounding and Sticky Bits	326	(4)
Rounding with Unlimited Exponent Range	330	(1)
Decomposition Theorem for Rounding	330	(5)
Rounding Algorithms	335	(1)
Exceptions	335	(6)
Overflow	336	(1)
Underflow	336	(2)
Wrapped Exponents	338	(3)
Inexact Result	341	(1)
Arithmetic on Special Operands	341	(8)
Operations with NaNs	342	(1)
Addition and Subtraction	343	(1)
Multiplication	344	(1)
Division	344	(1)
Comparison	345	(2)
Format Conversions	347	(2)
Selected References and Further Reading	349	(1)
Exercises	349	(2)
Floating Point Algorithms and Data Paths	351	(88)
Unpacking	354	(5)
Addition and Subtraction	359	(13)
Addition Algorithm	359	(1)
Adder Circuitry	360	(12)
Multiplication and Division	372	(18)
Newton-Raphson Iteration	373	(2)
Initial Approximation	375	(2)
Newton-Raphson Iteration with Finite Precision	377	(2)
Table Size versus Number of Iterations	379	(1)
Computing the Representative of the Quotient	380	(1)
Multiplier and Divider Circuits	381	(9)
Floating Point Rounder	390	(22)
Specification and Overview	391	(3)
Normalization Shift	394	(11)
Selection of the Representative	405	(1)
Significand Rounding	406	(1)
Post Normalization	407	(1)
Exponent Adjustment	408	(1)
Exponent Rounding	409	(1)
Circuit SpecFPrnd	410	(2)
Circuit FCon	412	(6)
Floating Point Condition Test	414	(3)
Absolute Value and Negation	417	(1)
IEEE Floating Point Exceptions	418	(1)
Format Conversion	418	(14)
Specification of the Conversions	419	(4)
Implementation of the Conversions	423	(9)
Evaluation of the FPU Design	432	(3)
Selected References and Further Reading	435	(1)
Exercises	436	(3)
Pipelined DLX Machine with Floating Point Core	439	(80)
Extended Instruction Set Architecture	441	(4)
FPU Register Set	441	(2)
Interrupt Causes	443	(1)
FPU Instruction Set	444	(1)
Data Paths without Forwarding	445	(25)
Instruction Decode	448	(3)
Memory Stage	451	(4)
Write Back Stage	455	(6)
Execute Stage	461	(9)
Control of the Prepared Sequential Design	470	(15)
Precomputed Control without Division	474	(5)
Supporting Divisions	479	(6)
Pipelined DLX Design with FPU	485	(23)
PC Environment	485	(1)
Forwarding and Interlocking	486	(12)
Stall Engine	498	(5)
Cost and Delay of the Control	503	(4)
Simulation Theorem	507	(1)
Evaluation	508	(8)
Hardware Cost and Cycle Time	508	(3)
Variation of the Cache Size	511	(5)
Exercises	516	(3)
A DLX Instruction Set Architecture	519	(8)
A.1 DLX Fixed-Point Core: FXU	519	(2)
A.1.1 Instruction Formats	520	(1)
A.1.2 Instruction Set Coding	521	(1)
A.2 Floating-Point Extension	521	(6)
A.2.1 FPU Register Set	521	(1)
A.2.2 FPU Instruction Set	522	(5)
B Specification of the FDLX Design	527	(16)
B.1 RTL Instructions of the FDLX	527	(7)
B.1.1 Stage IF	527	(1)
B.1.2 Stage ID	527	(2)
B.1.3 Stage EX	529	(3)
B.1.4 Stage M	532	(2)
B.1.5 Stage WB	534	(1)
B.2 Control Automata of the FDLX Design	534	(9)
B.2.1 Automaton Controlling Stage ID	535	(1)
B.2.2 Precomputed Control	536	(7)
Bibliography	543	(6)
Index	549