Preface

xxi

Introduction And Overview

(6)

The Importance Of Architecture

(1)

Learning The Essentials

(1)

Organization Of The Text

(1)

What We Will Omit

(1)

Terminology: Architecture And Design

(1)

Summary

(4)

PART I Basics

Fundamentals Of Digital Logic

(22)

Introduction

(1)

Electrical Terminology: Voltage And Current

(1)

The Transistor

(1)

Logic Gates

(1)

Symbols Used For Gates

(1)

Construction Of Gates From Transistors

(1)

Example Interconnection Of Gates

(2)

Multiple Gates Per Integrated Circuit

(1)

The Need For More Than Combinatorial Circuits

(1)

Circuits That Maintain State

(1)

Transition Diagrams

(1)

Binary Counters

(1)

Clocks And Sequences

(2)

The Important Concept Of Feedback

(2)

Starting A Sequence

(1)

Iteration In Software Vs. Replication In Hardware

(1)

Gate And Chip Minimization

(1)

Using Spare Gates

(1)

Power Distribution And Heat Dissipation

(1)

Timing

(1)

Physical Size And Process Technologies

(1)

Circuit Boards And Layers

(1)

Levels Of Abstraction

(1)

Summary

(1)

Data And Program Representation

(18)

Introduction

(1)

Digital Logic And Abstraction

(1)

Bits And Bytes

(1)

Byte Size And Possible Values

(1)

Binary Arithmetic

(1)

Hexadecimal Notation

(1)

Notation For Hexadecimal And Binary Constants

(1)

Character Sets

(1)

Unicode

(1)

Unsigned Integers, Overflow, And Underflow

(1)

Numbering Bits And Bytes

(1)

Signed Integers

(1)

An Example Of Two's Complement Numbers

(1)

Sign Extension

(1)

Floating Point

(2)

Special Values

(1)

Range Of IEEE Floating Point Values

(1)

Data Aggregates

(1)

Program Representation

(1)

Summary

(4)

PART II Processors

The Variety Of Processors And Computational Engines

(14)

Introduction

(1)

Von Neumann Architecture

(1)

Definition Of A Processor

(1)

The Range Of Processors

(1)

Hierarchical Structure And Computational Engines

(2)

Structure Of A Conventional Processor

(1)

Definition Of An Arithmetic Logic Unit (ALU)

(1)

Processor Categories And Roles

(2)

Processor Technologies

(1)

Stored Programs

(1)

The Fetch-Execute Cycle

(1)

Clock Rate And Instruction Rate

(1)

Control: Getting Started And Stopping

(1)

Starting The Fetch-Execute Cycle

(1)

Summary

(3)

Processor Types And Instruction Sets

(22)

Introduction

(1)

Mathematical Power, Convenience, And Cost

(1)

Instruction Set And Representation

(1)

Opcodes, Operands, And Results

(1)

Typical Instruction Format

(1)

Variable-Length Vs. Fixed-Length Instructions

(1)

General-Purpose Registers

(1)

Floating Point Registers And Register Identification

(1)

Programming With Registers

(1)

Complex And Reduced Instruction Sets

(1)

RISC Design And The Execution Pipeline

(1)

Pipelines And Instruction Stalls

(2)

Other Causes Of Pipeline Stalls

(1)

Consequences For Programmers

(1)

Programming, Stalls, And No-Op Instructions

(1)

Forwarding

(1)

Types Of Operations

(1)

Program Counter, Fetch-Execute, And Branching

(2)

Subroutine Calls, Arguments, And Register Windows

(1)

An Example Instruction Set

(2)

Minimalistic Instruction Set

(1)

The Principle Of Orthogonality

(1)

Condition Codes And Conditional Branching

(1)

Summary

(3)

Operand Addressing And Instruction Representation

(12)

Introduction

(1)

Zero, One, Two, Or Three Address Designs

(1)

Zero Operands Per Instruction

(1)

One Operand Per Instruction

(1)

Two Operands Per Instruction

(1)

Three Operands Per Instruction

(1)

Operand Sources And Immediate Values

(1)

The Von Neumann Bottleneck

(1)

Explicit And Implicit Operand Encoding

(1)

Operands That Combine Multiple Values

(1)

Tradeoffs In The Choice Of Operands

(1)

Values In Memory And Indirect Reference

(1)

Operand Addressing Modes

(1)

Summary

(2)

CPUs: Microcode, Protection, And Processor Modes

(20)

Introduction

(1)

A Central Processor

(1)

CPU Complexity

(1)

Modes Of Execution

(1)

Backward Compatibility

(1)

Changing Modes

(1)

Privilege And Protection

(1)

Multiple Levels Of Protection

(1)

Microcoded Instructions

100

(2)

Microcode Variations

102

(1)

The Advantage Of Microcode

102

(1)

Making Microcode Visible To Programmers

103

(1)

Vertical Microcode

103

(1)

Horizontal Microcode

104

(1)

Example Horizontal Microcode

105

(2)

A Horizontal Microcode Example

107

(1)

Operations That Require Multiple Cycles

108

(1)

Horizontal Microcode And Parallel Execution

109

(1)

Look-Ahead And High Performance Execution

110

(1)

Parallelism And Execution Order

111

(1)

Out-Of-Order Instruction Execution

111

(1)

Conditional Branches And Branch Prediction

112

(1)

Consequences For Programmers

113

(1)

Summary

113

(2)

Assembly Languages And Programming Paradigm

115

(22)

Introduction

115

(1)

Characteristics Of A High-level Programming Language

115

(1)

Characteristics Of A Low-Level Programming Language

116

(1)

Assembly Language

117

(1)

Assembly Language Syntax And Opcodes

118

(2)

Operand Order

120

(1)

121

(1)

Operand Types

122

(1)

Assembly Language Programming Paradigm And Idioms

122

(1)

Assembly Code For Conditional Execution

123

(1)

Assembly Code For A Conditional Alternative

124

(1)

Assembly Code For Definite Iteration

124

(1)

Assembly Code For Indefinite Iteration

125

(1)

Assembly Code For Procedure Invocation

125

(1)

Assembly Code For Parameterized Procedure Invocation

126

(1)

Consequence For Programmers

127

(1)

Assembly Code For Function Invocation

128

(1)

Interaction Between Assembly And High-Level Languages

128

(1)

Assembly Code For Variables And Storage

129

(1)

Two-Pass Assembler

130

(1)

Assembly Language Macros

131

(3)

Summary

134

(3)

PART III Memories

Memory And Storage

137

(6)

Introduction

137

(1)

Definition

137

(1)

The Key Aspects Of Memory

138

(1)

Characteristics Of Memory Technologies

138

(2)

The Important Concept Of A Memory Hierarchy

140

(1)

Instruction And Data Store

140

(1)

The Fetch-Store Paradigm

141

(1)

Summary

141

(2)

Physical Memory And Physical Addressing

143

(20)

Introduction

143

(1)

Characteristics Of Computer Memory

143

(1)

Static And Dynamic RAM Technologies

144

(1)

Measures Of Memory Technology

145

(1)

Density

146

(1)

Separation Of Read And Write Performance

146

(1)

Latency And Memory Controllers

146

(1)

Synchronized Memory Technologies

147

(1)

Multiple Data Rate Memory Technologies

148

(1)

Examples Of Memory Technologies

148

(1)

Memory Organization

148

(1)

Memory Access And Memory Bus

149

(1)

Memory Transfer Size

150

(1)

Physical Addresses And Words

150

(1)

Physical Memory Operations

150

(1)

Word Size And Other Data Types

151

(1)

An Extreme Case: Byte Addressing

151

(1)

Byte Addressing With Word Transfers

152

(1)

Using Powers Of Two

153

(1)

Byte Alignment And Programming

154

(1)

Memory Size And Address Space

154

(1)

Programming With Word Addressing

155

(1)

Measures Of Memory Size

155

(1)

Pointers And Data Structures

156

(1)

A Memory Dump

156

(2)

Indirection And Indirect Operands

158

(1)

Memory Banks And Interleaving

158

(1)

Content Addressable Memory

159

(1)

Ternary CAM

160

(1)

Summary

160

(3)

Virtual Memory Technologies And Virtual Addressing

163

(22)

Introduction

163

(1)

Definition

163

(1)

A Virtual Example: Byte Addressing

164

(1)

Virtual Memory Terminology

164

(1)

An Interface To Multiple Physical Memory Systems

164

(2)

Address Translation Or Address Mapping

166

(1)

Avoiding Arithmetic Calculation

167

(1)

Discontiguous Address Spaces

168

(1)

Other Memory Organizations

169

(1)

Motivation For Virtual Memory

169

(1)

Multiple Virtual Spaces And Multiprogramming

170

(1)

Multiple Levels Of Virtualization

171

(1)

Creating Virtual Spaces Dynamically

171

(1)

Base-Bound Registers

172

(1)

Changing The Virtual Space

172

(1)

Virtual Memory, Base-Bound, And Protection

173

(1)

Segmentation

174

(1)

Demand Paging

175

(1)

Hardware And Software For Demand Paging

175

(1)

Page Replacement

176

(1)

Paging Terminology And Data Structures

176

(1)

Address Translation In A Paging System

177

(1)

Using Powers Of Two

178

(1)

Presence, Use, And Modified Bits

179

(1)

Page Table Storage

180

(1)

Paging Efficiency And A Translation Lookaside Buffer

181

(1)

Consequences For Programmers

182

(1)

Summary

183

(2)

Caches And Caching

185

(22)

Introduction

185

(1)

Definition

185

(1)

Characteristics Of A Cache

186

(1)

The Importance Of Caching

187

(1)

Examples Of Caching

188

(1)

Cache Terminology

188

(1)

Best And Worst Case Cache Performance

189

(1)

Cache Performance On A Typical Sequence

190

(1)

Cache Replacement Policy

190

(1)

LRU Replacement

191

(1)

Multi-level Cache Hierarchy

191

(1)

Preloading Caches

192

(1)

Caches Used With Memory

192

(1)

TLB As A Cache

193

(1)

Demand Paging As A Form Of Caching

193

(1)

Physical Memory Cache

194

(1)

Write Through And Write Back

194

(1)

Cache Coherence

195

(1)

L1, L2, and L3 Caches

196

(1)

Sizes Of L1, L2, And L3 Caches

197

(1)

Instruction And Data Caches

197

(1)

Virtual Memory Caching And A Cache Flush

198

(1)

Implementation Of Memory Caching

199

(1)

Direct Mapping Memory Cache

200

(1)

Using Powers Of Two For Efficiency

201

(1)

Set Associative Memory Cache

202

(1)

Consequences For Programmers

203

(1)

Summary

204

(3)

PART IV I/O

Input/Output Concepts And Terminology

207

(8)

Introduction

207

(1)

Input And Output Devices

207

(1)

Control Of An External Device

208

(1)

Data Transfer

209

(1)

Serial And Parallel Data Transfers

209

(1)

Self-Clocking Data

210

(1)

Full-Duplex And Half-Duplex Interaction

210

(1)

Interface Latency And Throughput

211

(1)

The Fundamental Idea Of Multiplexing

211

(1)

Multiple Devices Per External Interface

212

(1)

A Processor's View Of I/O

213

(1)

Summary

213

(2)

Buses And Bus Architectures

215

(22)

Introduction

215

(1)

Definition Of A Bus

215

(1)

Processors, I/O Devices, And Buses

216

(1)

Proprietary And Standardized Buses

216

(1)

Shared Buses And An Access Protocol

217

(1)

Multiple Buses

217

(1)

A Parallel, Passive Mechanism

217

(1)

Physical Connections

217

(1)

Bus Interface

218

(1)

Address, Control, And Data Lines

219

(1)

The Fetch-Store Paradigm

220

(1)

Fetch-Store Over A Bus

220

(1)

The Width Of A Bus

220

(1)

Multiplexing

221

(1)

Bus Width And Size Of Data Items

222

(1)

Bus Address Space

223

(1)

Potential Errors

224

(1)

Address Configuration And Sockets

225

(1)

Many Buses Or One Bus

226

(1)

Using Fetch-Store With Devices

226

(1)

An Example Of Device Control Using Fetch-Store

226

(1)

Operation Of An Interface

227

(1)

Asymmetric Assignments

228

(1)

Unified Memory And Device Addressing

228

(2)

Holes In The Address Space

230

(1)

Address Map

230

(1)

Program Interface To A Bus

231

(1)

Bridging Between Two Buses

232

(1)

Main And Auxiliary Buses

232

(2)

Consequences For Programmers

234

(1)

Switching Fabrics

234

(1)

Summary

235

(2)

Programmed And Interrupt-Driven I/O

237

(18)

Introduction

237

(1)

I/O Paradigms

237

(1)

Programmed I/O

238

(1)

Synchronization

238

(1)

Polling

239

(1)

Code For Polling

239

(2)

Control And Status Registers

241

(1)

Processor Use And Polling

241

(1)

First, Second, And Third Generation Computers

242

(1)

Interrupt-Driven I/O

242

(1)

A Hardware Interrupt Mechanism

243

(1)

Interrupts And The Fetch-Execute Cycle

243

(1)

Handling An Interrupt

244

(1)

Interrupt Vectors

245

(1)

Initialization And Enabling And Disabling Interrupts

246

(1)

Preventing Interrupt Code From Being Interrupted

246

(1)

Multiple Levels Of Interrupts

246

(1)

Assignment Of Interrupt Vectors And Priorities

247

(1)

Dynamic Bus Connections And Pluggable Devices

248

(1)

The Advantage Of Interrupts

249

(1)

Smart Devices And Improved I/O Performance

249

(1)

Direct Memory Access (DMA)

250

(1)

Buffer Chaining

251

(1)

Scatter Read And Gather Write Operations

252

(1)

Operation Chaining

252

(1)

Summary

253

(2)

A Programmer's View Of Devices, I/O, And Buffering

255

(24)

Introduction

255

(1)

Definition Of A Device Driver

256

(1)

Device Independence, Encapsulation, And Hiding

256

(1)

Conceptual Parts Of A Device Driver

257

(1)

Two Types Of Devices

258

(1)

Example Flow Through A Device Driver

258

(1)

Queued Output Operations

259

(2)

Forcing An Interrupt

261

(1)

Queued Input Operations

261

(1)

Devices That Support Bi-Directional Transfer

262

(1)

Asynchronous Vs. Synchronous Programming Paradigm

263

(1)

Asynchrony, Smart Devices, And Mutual Exclusion

264

(1)

I/O As Viewed By An Application

264

(1)

Run-Time I/O Libraries

265

(1)

The Library/Operating System Dichotomy

266

(1)

I/O Operations The OS Supports

267

(1)

The Cost Of I/O Operations

268

(1)

Reducing The System Call Overhead

268

(1)

The Important Concept Of Buffering

269

(1)

Implementation of Buffering

270

(1)

Flushing A Buffer

271

(1)

Buffering On Input

272

(1)

Effectiveness Of Buffering

272

(1)

Buffering In An Operating System

273

(1)

Relation To Caching

274

(1)

An Example: The Unix Standard I/O Library

274

(1)

Summary

274

(5)

PART V Advanced Topics

Parallelism

279

(20)

Introduction

279

(1)

Parallel And Pipelined Architectures

279

(1)

Characterizations Of Parallelism

280

(1)

Microscopic Vs. Macroscopic

280

(1)

Examples Of Microscopic Parallelism

281

(1)

Examples Of Macroscopic Parallelism

281

(1)

Symmetric Vs. Asymmetric

282

(1)

Fine-grain Vs. Coarse-grain Parallelism

282

(1)

Explicit Vs. Implicit Parallelism

283

(1)

Parallel Architectures

283

(1)

Types Of Parallel Architectures (Flynn Classification)

283

(1)

Single Instruction Single Data (SISD)

284

(1)

Single Instruction Multiple Data (SIMD)

284

(2)

Multiple Instructions Multiple Data (MIMD)

286

(2)

Communication, Coordination, And Contention

288

(2)

Performance Of Multiprocessors

290

(2)

Consequences For Programmers

292

(2)

Redundant Parallel Architectures

294

(1)

Distributed And Cluster Computers

295

(1)

Summary

296

(3)

Pipelining

299

(12)

Introduction

299

(1)

The Concept Of Pipelining

299

(2)

Software Pipelining

301

(1)

Software Pipeline Performance And Overhead

302

(1)

Hardware Pipelining

303

(1)

How Hardware Pipelining Increases Performance

303

(3)

When Pipelining Can Be Used

306

(1)

The Conceptual Division Of Processing

307

(1)

Pipeline Architectures

307

(1)

Pipeline Setup, Stall, And Flush Times

308

(1)

Definition Of Superpipeline Architecture

308

(1)

Summary

309

(2)

Assessing Performance

311

(8)

Introduction

311

(1)

Measuring Power And Performance

311

(1)

Measures Of Computational Power

312

(1)

Application Specific Instruction Counts

313

(1)

Instruction Mix

314

(1)

Standardized Benchmarks

315

(1)

I/O And Memory Bottlenecks

316

(1)

Boundary Between Hardware And Software

316

(1)

Choosing Items To Optimize

317

(1)

Amdahl's Law And Parallel Systems

317

(1)

Summary

318

(1)

Architecture Examples And Hierarchy

319

(12)

Introduction

319

(1)

Architectural Levels

319

(1)

System-Level Architecture: A Personal Computer

320

(1)

Bus Interconnection And Bridging

321

(1)

Controller Chips And Physical Architecture

322

(1)

Virtual Buses

323

(2)

Connection Speeds

325

(1)

Bridging Functionality And Virtual Buses

325

(1)

Board-Level Architecture

325

(2)

Chip-Level Architecture

327

(1)

Structure Of Functional Units On A Chip

328

(1)

Summary

329

(1)

Hierarchy Beyond Computer Architectures

329

(2)

Appendix 1 Lab Exercises For A Computer Architecture Course

331

(28)

A1.1 Introduction

331

(1)

A1.2 Digital Hardware For A Lab

332

(1)

A1.3 Solderless Breadboard

332

(1)

A1.4 Using A Solderless Breadboard

333

(1)

A1.5 Testing

334

(1)

A1.6 Power And Ground Connections

334

(1)

A1.7 Lab Exercises

335

(24)

1 Introduction and account configuration

337

(2)

2 Digital Logic: Use of a breadboard

339

(2)

3 Digital Logic: Building an adder from gates

341

(2)

4 Digital Logic: Clocks and demultiplexing

343

(2)

5 Representation: Testing big endian vs. little endian

345

(2)

6 Representation: A hex dump program in C

347

(2)

7 Processors: Learn a RISC assembly language

349

(2)

8 Processors: Function that can be called from C

351

(2)

9 Memory: row-major and column-major array storage

353

(2)

10 Input/Output: a buffered I/O library

355

(2)

11 A hex dump program in assembly language

357

(2)

Bibliography

359

(2)

Index

361

This book began when I was assigned to help salvage an undergraduate computer organization course. The course had suffered years of neglect: it had been taught by a series of professors, mostly visitors, who had little or no interest or background in digital hardware, and the curriculum had deteriorated to a potpourri of topics that were only loosely related to hardware architectures. In some semesters, students spent the entire class studying Boolean Algebra, without even the slightest connection to actual hardware. In others, students learned the arcane details of one particular assembly language, without a notion of alternatives. Is a computer organization course worth saving? Absolutely! In many Computer Science programs, the computer organization course is the only time students are exposed to fundamental concepts that explain the structure of the computer they are programming. Understanding the hardware makes it possible to construct programs that are more efficient and less prone to errors. In a broad sense, a basic knowledge of architecture helps programmers improve program efficiency by understanding the consequences of programming choices. Knowing how the hardware works can also improve the programming process by allowing programmers to pinpoint the source of bugs quickly. Finally, graduates need to understand basic architectural concepts to pass job application tests given by firms like Intel and Microsoft. One of the steps in salvaging our architecture course consisted in looking at textbooks. We discovered the texts could be divided into roughly two types: texts aimed at beginning engineering students who would go on to design hardware, and texts written for CS students that attempt to include topics from compilers, operating systems, and (in at least one case) a complete explanation of how Internet protocols operate. Neither approach seemed appropriate for a single, introductory course on the subject. We wanted a book that (1) focused on the concepts rather than engineering details (because our students are not focused on hardware design); (2) explained the subject from a programmer''s point of view, and emphasized consequences for programmers; and (3) did not try to cover several courses'' worth of material. When no text was found, it seemed that the only solution was to create one. The text is divided into five parts. Part 1 covers the basics of digital logic, gates, and data representation. We emphasize the representation chapter because notions of two''s-compliment arithmetic and ranges of integer values are essential in programming. Parts 2, 3, and 4 cover the three essential areas of architecture: processors, memories, and I/O systems. In each case, the chapters give students enough background to understand how the mechanisms operate and the consequences for programmers. Finally, Part 5 covers advanced topics like parallelism, pipelining, and performance. An Appendix describes an important aspect of the course: a hands-on lab where students can learn by doing. Although most lab problems focus on programming, students should spend the first few weeks in lab wiring a few gates on a breadboard. The equipment is inexpensive (we spent less than fifteen dollars per student on permanent equipment; students purchase their own set of chips for under twenty dollars). We have set up a web site to accompany the book at: http://www.eca.cs.purdue.edu Rajesh Subraman has agreed to manage the site, which contains a set of class presentation materials created by the author as well as a set created by Rajesh. We invite other instructors to contribute their materials. The text and lab exercises have been used at Purdue; students have been extremely positive about both. We received notes of thanks for the text and course. For many students, the lab is their first experience with hardware, and they are enthusiastic. My thanks to the many individuals who contributed to the book. Bernd Wolfinger provided extensive reviews and made several important suggestions about topics and direction. Dan Ardelean, James Cernak, and Tim Korb gave detailed comments on many chapters. Dave Capka reviewed early chapters. Rajesh Subraman taught from the book and provided his thoughts about the content. In the CS 250 class at Purdue, the following students each identified one or more typos in the manuscript: Nitin Alreja, Alex Cox, David Ehrmann, Roger Maurice Elion, Andrew Lee, Stan Luban, Andrew L. Soderstrom, and Brandon Wuest. Finally, I thank my wife, Chris, for her patient and careful editing and valuable suggestions that improve and polish each book. Douglas E. Comer June, 2004