Microprocessor Design/Print Version

From Wikibooks, open books for an open world
< Microprocessor Design
Jump to: navigation, search

Microprocessor Design/Cover




About This Book




How Will This Book Be Organized?










Who Is This Book For?


What This Book Will Not Cover




Microprocessor Basics



Microprocessors are the devices in a computer which make things happen. Microprocessors are capable of performing basic arithmetic operations, moving data from place to place, and making basic decisions based on the quantity of certain values.


Types of Processors

The vast majority of microprocessors can be found in embedded high microcontrollers. The second most common type of processors are common desktop processors, such as Intel's Pentium or AMD's Athlon. Less common are the extremely powerful processors used in high-end servers, such as Sun's SPARC, IBM's Power, or Intel's Itanium.



General Purpose Versus Specific Use


General Purpose
Embedded Controller
Programmable State Machines
Graphics Processing Units

Types of Use


Signal Processing
Real Time Applications
Some tasks need to be performed so quickly that even the slightest delay or inefficiency can be detrimental. These applications are known as "real time systems", and timing is of the utmost importance. An example of a real-time system is the anti-lock braking system (ABS) controller in modern automobiles.
Throughput and Routing
Sensor monitoring
General Computing

Abstraction Layers


  1. Application
  2. Operating System
  3. Firmware
  4. Instruction Set Architecture
  5. Microprocessor Control Logic
  6. Physical Circuit Layout

This book will be mostly concerned with the Instruction Set Architecture (ISA), and the Microprocessor Control Logic but we will also describe the Operating System (OS) in brief. Topics above these are typically the realm of computer programmers. The bottom layer, the Physical Circuit Layout is the job of hardware and VLSI engineers.

Operating System

Operating System is a program which acts as an interface between the system user and the computer hardware and controls the execution of application programs. It is the program running at all times on the computer, usually called the Kernel.



Assembly Language


Common ISAs



  • ARM
  • IA-32 (Intel x86)
  • MIPS
  • Motorola 68K
  • PowerPC
  • Hitachi SH

Moore's Law


—Gordon Moore



  1. Smaller Transistors typically switch faster than larger transistors.
Moore Law diagram (2004).png


Clock Rates

Microprocessors are typically discussed in terms of their clock speed. The clock speed is measured in hertz (or megahertz, or gigahertz). A hertz is a "cycle per second". Each cycle, a microprocessor will perform certain tasks, although the amount of work performed in a single cycle will be different for different types of processors. The amount of work that a processor can complete in a single cycle is measured in "instructions per cycle" . For some systems, such as MIPS, there is 1 instruction per cycle. For other systems, such as modern x86 chips, there are typically very many instructions per cycle. The clock rate is equated as such:


Basic Elements of a Computer


  • CPU
  • Memory
  • Input Devices
  • Output Devices


Computer Architecture

Von Neumann Architecture


John von Neumann suggested that data and programs should be stored together in memory. This is now called Von Neumann architecture. Programs are fetched from memory for execution by a central unit that we call the CPU. Basically programs and data are represented in memory in the same way. The program is just data encoded with special meaning. The main criticism of this approach is, that security problems can arise when instructions can be manipulated as if they were data, and vice-versa.

A Von Neumann microprocessor is a processor that follows this pattern:

An instruction and the necessary data are obtained from memory.
The instruction and data are separated, and the components and pathways required to execute the instruction are activated.





The datapath is the pathway that the data takes through the microprocessor. As the data travels to different parts of the datapath, the command signals from the control unit cause the data to be manipulated in specific ways, according to the instruction. The datapath consists of the circuitry for transforming data and for storing temporary data. It contains ALUs capable of transforming data through operations such as addition, subtraction, logical AND, OR, inverting, and shifting.

We discuss the control and datapath in far more detail in a later section, Control and Datapath.

Harvard Architecture

In a Harvard Architecture machine, the computer system's memory is separated into two discrete parts: data and instructions. In a pure Harvard system, the two different memories occupy separate memory modules, and instructions can only be executed from the instruction memory.

Many DSPs are modified Harvard architectures, designed to simultaneously access three distinct memory areas: the program instructions, the signal data samples, and the filter coefficients (often called the P, X, and Y memories).

In theory, such three-way Harvard architectures can be three times as fast as a Von Neumann architecture that is forced to read the instruction, the data sample, and the filter coefficient, one at a time.

Modern Computers





Some people group stack machines with the RISC machines; others[8] group stack machines with the CISC machines; some people [9], [10] describe stack machines as neither RISC nor CISC.

Other ISA types include DSPs, stack machines, VLIW machines, MISC machines, TTA architectures, massively parallel processor arrays, etc.

We will discuss these terms and concepts in more detail later.

Microprocessor Components

Some of the common components of a microprocessor are:

  • Control Unit
  • I/O Units
  • Arithmetic Logic Unit (ALU)
  • Registers
  • Cache

A brief introduction to these components is placed below.

Control Unit


I/O Units


Arithmetic Logic Unit


ALU will be discussed in far more detail in a later chapter, ALU.


This book, includes data about different kinds of registers. Hopefully it will be obvious which kind of register we are talking about from the context.



programmer-visible registers



There are several factors limiting the number of registers, including:






microarchitectural registers


These registers include:

  • memory address register
  • memory data register
  • instruction register
  • microinstruction register
  • microprogram counter
  • pipeline registers
  • extra physical registers to support register renaming



Most CPUs manufactured do not have any cache.


smallest largest
Registers cache RAM
fastest slowest


We discuss cache in far more detail in a later chapter, Cache.





With a big-endian 68K sort of machine,

       address increases > ------ >
       data   : 74 65 73 74 00 00 00 05







Some people claim that a processor must have a hardware stack in order to run C programs.[1]

Most computer architectures have hardware support for a recursive "call" instruction in their Assembly Language. Some architectures (such as the ARM, the Freescale RS08, etc.) implement "call" like this:

  • the "call" instruction pushes a return address into a link register and jumps to the subroutine. A separate instruction near the beginning of the subroutine pushes the contents of the link register to a stack in main memory, to free up the link register so that subroutine can then recursively call other subroutines.

Some architectures (such as the 6502, the x86, etc.) implement "call" like this:

  • the "call" instruction pushes a return address onto the stack in main memory and jumps to the subroutine.

A few architectures (such as the PIC16, the RISC I processor, the Novix NC4016, many LISP machines, etc.) implement "call" like this:

  • The "call" instruction pushes a return address into a dedicated return stack, separate from main memory, and jumps to the subroutine.

further reading

Instruction Set Architectures









  • compilers were easier to write (easier to optimize)
  • performance is increased for programs that did simple operations



We will discuss VLIW Processors in a later section.

Vector processors

We will discuss Vector Processors in a later section.

Computational RAM

Computational RAM (C-RAM) is semiconductor random access memory with processors incorporated into the design to build an inexpensive massively-parallel computer.

Memory Arrangement



Common Instructions

Move, Load, Store


Instructions that move (or copy) data from one place to another are the #1 most-frequently-used instructions in most programs.[3]

Branch and Jump

Branching and Jumping is the ability to load the PC register with a new address that is not the next sequential address. In general, a "jump" or "call" occurs unconditionally, and a "branch" occurs on a given condition. In this book we will generally refer to both as being branches, with a "jump" being an unconditional branch.

A "call" instruction is a branch instruction with the additional effect of storing the current address in a specific location, e.g. pushing it on the stack, to allow for easy return to continue execution. A "call" instruction is generally matches with a "return" instruction which retrieves the stored address and resumes execution where it left off.

An "interrupt" instruction is a call to a preset location, generally one encoded somehow in the instruction itself. This is often used to reach commonly-used resources such as the operating system. Generally, a routine entered via an interrupt instruction is left via an interrupt return instruction, which, similarly to the return instruction, retrieves the stored address and resumes execution.

In many programs, "call" is the second-most-frequently used instruction (after "move").[3]

Arithmetic Instructions

The Arithmetic Logic Unit (ALU) is used to perform arithmetic and logical instructions. The capability of the ALU typically is greater with more advanced central processors, but RISC machines' ALUs are deliberately kept simple and so have only some of these functions. An ALU will, at minimum, perform addition, subtraction, NOT, AND, OR, and XOR, and usually also single-bit rotates and shifts. Many CISC machine ALUs can also perform multi-bit rotates and shifts (with a barrel shifter) and integer multiplication and division. While many modern CPUs can also do floating point mathematical operations, these are usually handled by the FPU, a different part of the machine. We describe the ALU in more detail in the ALU design chapter.

Input / Output



NOP, short for "no operation" is an instruction that produces no result and causes no side effects. NOPs are useful for timing and preventing hazards.

Instruction Length

There are several different ways people balance the various advantages and disadvantages of various instruction lengths.

A MIPS "add immediate" instruction includes the opcode (logical operation), the destination register specifier, the source register specifier, and a constant value, all in the same 32 bits that are used for every MIPS instruction.

Fixed-length instructions are less complicated for a CPU to handle than variable-width instructions for several reasons, and are therefore somewhat easier to optimize for speed. Such reasons include: CPUs with variable-length instructions have to check whether each instruction straddles a cache line or virtual memory page boundary; CPUs with fixed-length instructions can skip all that. [4]

There simply are not enough bits in a 16 bit instruction to accommodate 32 general-purpose registers, and also do "Ra = Rb (op) Rc" -- i.e., independently select 2 source and 1 destination register out of a general purpose register bank of 32 registers, and also independently select one of several ALU operations.

And so people who design instruction sets must make one or more of the following compromises:

  • sacrifice code density and use longer fixed-width instructions, typically 32 bit, such as the MIPS and DLX and ARM.
  • sacrifice fixed-width instructions, requiring a more complicated decoder to handle both short 16 bit instructions and longer 3-operand instructions, such as ARM Thumb
  • sacrifice 3-operands, using no more than 2 operands in all instructions for everything, such as the Atmel AVR. 3-operand instructions allow better reuse of data[4]; without 3-operand instructions, programs occasionally require extra copy instructions when both variable input operands to some ALU operation need to be preserved for some later instruction(s).
  • sacrifice registers, so only 16 or 8 programmer-visible registers.
  • sacrifice the concept of general purpose register -- perhaps only 16 or 8 "data registers" are visible to 3-operand ALU instructions, as in the 68000, or the destination is restricted to one or two "accumulators", but other registers (such as "address registers") are visible to other instructions.

Instruction format

Any one particular machine-language instruction for any one particular CPU can typically be divided up into fields. For example, certain bits in a "ADD" instruction indicate the operation -- that this is actually an "ADD" rather than a "XOR" or "subtract" instruction. Other bits indicate which register is the source, other bits indicate which register is the destination, etc.

A few processors not only have fixed instruction widths but also have single instruction format -- a fixed set of fields that is the same for every instruction.

Many processors have fixed instruction widths but have several instruction formats. The actual bits stored in a special fixed-location "instruction type" field (that is in the same place in every instruction for that CPU) indicates which of those instruction format is used by this specific instruction -- which particular field layout is used by this instruction. For example, the MIPS processors have R-type, I-type, J-type, FR-type, and FI-type instruction formats.[5] For example, the J1 processor has 3 instruction formats: Literal, Branch, and ALU.[6] For example, the Microchip PIC mid-range has 4 instruction formats: byte-oriented register operations, bit-oriented register operations, 8-bit literal operations, and branch instructions with an 11-bit literal. [7]

Occasionally some new CPU has a different instruction set formats from some other CPU, making it "not binary-compatible" with that other CPU. However, sometimes this new CPU can be designed to have "source code backward-compatibility" with some other CPU -- it is "assembly-language compatible but not binary-compatible" with programs written some other CPU. (Such as, for example, the 8080 which was source-compatible but not binary-compatible with the 8008). (Such as, for example, the 8086 which was source-compatible but not binary-compatible with programs written for the 8085, the 8080, and the 8008[citation needed]).

Further reading

  1. Walter Banks. "The Stack Controversy". 2009.
  2. Practically all modern CPUs maintain the illusion of a program counter sequentially walking through code one instruction at a time. However, a few complex modern CPUs internally execute several instructions simultaneously (superscalar), or execute instructions out-of-order, or even speculatively pre-execute instructions down the "wrong" path, then back up and take the right path. When designing and testing such internal structures, the concept of "the" PC is a bit fuzzy. Some processor architectures, for instance the CDP1802, do not have a single Program Counter; instead, one of the general purpose registers is used as a program counter, and which register that is can be changed under program control.
  3. a b Peter Kankowski. "x86 Machine Code Statistics"
  4. a b The evolution of RISC technology at IBM by John Cocke – IBM Journal of R&D, Volume 44, Numbers 1/2, p.48 (2000)
  5. MIPS Assembly/Instruction Formats
  7. "PICmicro MID-RANGE MCU FAMILY: Section 29. Instruction Set" Section 29.2 Instruction Formats.



Memory Hierarchy


Hard Disk Drives




To do:





A single bit of storage in SRAM, showing 6 transistors.






Other RAM





Control and Datapath



The width of the data path ...

Gordon Bell and Bill Strecker, 1975[1]
Hollingsworth, Sachs, and Smith. 1987.[2]



  • etc.





Clock Cycles




Clock frequency is measured in units of cycles per second.

Cycles per Instruction




Instruction count




CPU Time




Amdahls Law








Assembly Language


Assemblers take in human-readable assembly code and produce machine code. Assembler.png

Assembly Language Constructs


CPU instruction set 
Instruction Code operand 1 operand 2

How many instructions there are depends on the CPU.


MOV A, 0x0020




Load and Store

These instructions tell the CPU to move data from memory to a CPU's register, or move data from one of the CPU's register to memory.



Arithmetic operations can be performed using the CPU's registers:

  • Increment the value of one of the CPU's registers
  • Decrement the value of one of the CPU's registers
  • Add a value to the register
  • Subtract value from the register
  • Multiply the register value
  • Divide the register value
  • Shift the register value
  • Rotate the register value



Relative jump 
Absolute jump 




Further reading

Design Steps


  1. Determine the capabilities the new processor should have.
  2. Lay out the datapath to handle the necessary capabilities.
  3. Define the machine code instruction format (ISA).
  4. Construct the necessary logic to control the datapath.

We will discuss each of these steps below:

Determine Machine Capabilities


Some questions to start:



  2. Does it have scalar or vector operation abilities?



  • Addition/Subtraction
  • Multiplication
  • Division
  • Shifting and Rotating

List other capabilities that your machine has:

  • Unconditional jumps
  • Conditional Jumps (and what conditions?)
  • Stack operations (Push, pop)


Design the Datapath


  • Accumulator
  • Stack
  • Register
  • A combination of the above 3


Create ISA


  1. Is this processor RISC, CISC, or VLIW?
  2. How long is a machine word?





Example: MIPS R-Type



Instruction Set Design




Build Control Logic



Design the Address Path





Verify the design


Further reading

  • Kong and Patterson. "Instruction set design". 1995.[11]


Microprocessor Components

Basic Components

Basic Components





Register File

A register file is a whole collection of registers, typically all of which are the same length. A register file takes three inputs, an index address value, a data value, and an enable signal. A signal decoder is used to pass the data value from the register file input to the particular register with the specified address. We talk more about register files in a later section of this book, Register File.


Multiplexer 2-to-1.svg




Multiplexer 4-to-1.svg
Multiplexer 8-to-1.svg
Multiplexer 16-to-1.svg
A 16 input Multiplexer with 4 control wires

There can be decoders implemented in the components.


For a 2 input decoder there will be 4 output signals.

       /|- O0
 i0---| |- O1
 i1---| |- O2
       \|- O3
 suppose input i is having value 00  then output signal O0 will go high and remaining other three lines O1 to O3 will be low.


Program Counter


Updating the PC

The PC can be updated by making the enable signal high. After each instruction cycle the PC needs to be updated to point to the next instruction in memory. It is important to know how the memory is arranged before constructing your PC update circuit.


PC Simple.svg


Example: MIPS


Example: Intel IA32





Non-Offset Branching


PC Branch.svg


Offset Branching


PC Offset Branch.svg


PC Offset Branch 2.svg

These are just two possible configurations for this circuit.

Offset and Non-Offset Branching

Many systems have capabilities to use both offset and non-offset branching. Some systems may differentiate between the two as "near jump" and "far jump" respectively, although this terminology is archaic.

PC Branch Jump.svg

Instruction Decoder


For each machine-language instruction, the control unit produces the sequence of pulses on each control signal line required to implement that instruction (and to fetch the next instruction).

If you are lucky, when you design a processor you will find that many of those control signals can be "directly decoded" from the instruction register. For example, sometimes a few output bits from the instruction register IR can be directly wired to the "which function" inputs of the ALU. Even if those bits mean something completely unrelated in non-ALU instructions, it's OK if the ALU performs, say, a bogus SUBTRACT, while the rest of the processor is executing a STORE instruction.

The remaining control signals that cannot be decoded from the instruction register -- if you are unlucky, all the control signals -- are generated by the control unit, which is implemented as a [Moore machine][2] or a [Mealy machine][3]. There are many different ways to implement the control unit.

If you design a processor with a Princeton architecture -- your processor normally pulls instructions from the same single-ported memory used to read and write data -- then you are forced to have at least LOAD and STORE take more than one clock cycle to execute. (One cycle for the data, and another cycle to read the next instruction). (Many processors are designed with "single-cycle execution", either very simple Harvard architecture processors, or complicated high-performance processors with a separate instruction cache).

RISC Instruction Decoder

The RISC instruction decoder is typically a very simple device. Because RISC instruction words are a fixed length, the positions of the fields are fixed, and processor reads in the entire instruction into the instruction register. We can decode an instruction, therefore, by simply separating the machine word in the instruction register into small parts using wire slices.

CISC Instruction Decoder



Perhaps the conceptually simplest and most general-purpose approach is to implement the control unit with a very wide control store ROM holding the microprogram. A pipeline register latches all the output bits of the control store ROM every clock cycle.

Each clock cycle the pipeline register latches a new set of bits.

The output of the pipeline register has 2 sections: Control bits that go out to all the other bits and pieces of the processor. The "microPC" that feeds back to some of the address inputs of the control store ROM. Some people hardwire the carry flag to one of the address inputs of the control store ROM.

Every time a new opcode is fetched from main memory, typically the high bits of the microPC are loaded with the opcode, and the low bits of the microPC reset to zero. (To make things easier to debug, some designers load the opcode into both a separate instruction register IR as well as the microPC register, at least in the initial prototypes. Once the design is debugged, it might turn out that some or all the bits from the IR or the microPC register or both are never used, and so can be left out of the final design). During execution of the instruction, each clock cycle the pipeline register loads a new microPC address from the control store and a new set of control bits from the control store. Typically the person who writes the microprogram -- burned into the control store ROM -- designs the next-address output bits of that ROM to sequentially increment for the first few cycles of the implementation of that opcode. Then the microprogram for every "normal" opcode eventually jumps to one common section of the control store ROM that handles fetch-next-instruction.

Register File

Registers are temporary storage locations inside the CPU that hold data and addresses.

The register file is the component that contains all the general purpose registers of the microprocessor. A few CPUs also place special registers such as the PC and the status register in the register file. Other CPUs keep them separate.

When designing a CPU, some people distinguish between "architectural features" and the "implementation details". The "architectural features" are the programmer visible parts; if someone makes a new system where any of these parts are different from the old CPU, then suddenly all the old software won't work on the new CPU. The "implementation details" are the parts that, although we put even more time and effort into getting them to work, one can make a new system that has a different way of implementing them, and still keep software compatibility -- some programs may run a little faster, other programs may run a little slower, but they all produce the same results as on the earlier machine.

The programmer-visible register set has more impact on software compatibility than any other part of the datapath, and perhaps more than any other part in the entire computer. The architectural features of the programmer-visible register set are the number of registers, the number of bits in each register, and the logical organization of the registers. Assembly language programmers like to have many registers. Early microprocessors had painfully few registers, limited by the area of the chip. Today, many chips have room for huge numbers of registers, so the number of programmer-registers is limited by other constraints: More programmer-visible registers requires bigger operand fields. More programmer-visible registers requires more time saving and restoring registers on an interrupt or context switch. Software compatibility requires keeping exactly the same number, size, and organization of programmer-visible registers. Assembly language programmers like a "flat" address space, where the full address of any location in (virtual) memory fits in a single address register. And so the amount of (virtual) memory desired by an architect sets a minimum width to each address register. [1]

The idea of "general registers" -- a group of registers, any one of which can, at different times, operate as a stack pointer, index register, accumulator, program counter, etc. was invented around 1971.[2]

While registers can be implemented as a bank of flip-flop registers, SRAM-based full-custom register files use less area and power.[3][4]

The overall performance of many single-chip CPUs is limited by the speed of the read operation of the register file.[3]

Register File


Register File Simple.svg



Register File Medium.svg
Register File Medium.svg


Register File Large.svg

Many people choose to use a 3-port register file for their pipelined microprocessor so it can execute such an ALU instructions every cycle. Every cycle the CPU reads values from 2 registers in the register file to prepare for operating on them as directed by one instruction, and simultaneously the CPU writes the results from some previous instruction into some other register in the register file. (Superscalar Processors and VLIW require a register file with 6 or more ports).

(Does a microprocessor with operand forwarding ever read from a register and write to the same register during the same clock cycle?)

Full-custom register files often start with a SRAM design. Like SRAM chips, SRAM-based register files include a differential pair of bit-lines for each port -- but instead of a single SRAM read/write port, register files typically have at least one dedicated write port and several dedicated read ports. A typical register file repeats this process every instruction cycle: First, the two bit-lines of a differential pair of each read port are shorted to each other and charged to Vdd/2 during a pre-charge phase. Then the word-line connects one bit cell to those lines -- slightly imbalancing the charge on those long bit lines. Finally, the CPU enables the sense amplifier which magnifies the slight imbalance to normal digital logic levels.[5][3][6][4]

More registers than you can shake a stick at

Consider a situation where the machine word is very small, and therefore the available address space for registers is very limited. If we have a machine word that can only accommodate 2 bits of register address, we can only address 4 registers. However, register files are small to implement, so we have enough space for 32 registers. There are several solutions to this dilemma -- several ways of increasing performance by using many registers, even though we don't quite have enough bits in the instruction word to directly address all of them.

Some of those solutions include:

  • special-purpose registers that are always used for some specific instruction, and so that instruction doesn't need any bits to specify that register.
    • In almost every CPU, the program counter PC and the status register are treated differently than the other registers, with their own special set of instructions.
  • separating registers into two groups, "address registers" and "data registers", so an instruction that uses an address needs enough bits to select one out of all the address registers, which is 1 less bit than one out of every register.
  • register windowing as on SPARC

[1] and

  • using a "register bank".

To do:
say a few words about "shadow registers"


To do:
say a few words about "register renaming"

Register Bank



Register Bank.svg




Register Bank Address.svg



  1. a b "Computer architecture: fundamentals and principles of computer design" by Joseph D. Dumas 2006 page 111.
  2. "general registers" were invented by C. Gordon Bell and Allen Newell as they were working on their book, Computer Structures: Readings and Examples (1971). -- Frederik Nebeker. "More Treasured Texts" article. "IEEE Spectrum" 2003 July.
  3. a b c Larry R. Fenstermaker. "Current mode sense amplifiers applied to dual port register files by Larry R. Fenstermaker". 1998.
  4. a b Akshay Vijayashekar and Hasan Ali. "Optimized Register File Implementation". quote: "The purpose of this thesis is to implement a full custom, low power and area efficient register file for an Atmel 32-bit microcontroller. ... The size of the register file is 32 words of 32 bits each with two write ports and four read ports."
  5. Norman P. Jouppi and Jeffrey Y. F. Tang "A 20-MIPS Sustained 32-bit CMOS Microprocessor with High Ratio of Sustained to Peak Performance". doi: 1989. Section "4.2. The Register File Sense Amplifier". p. 10-12.
  6. Robert Reese. "Register Files". 1999.

Memory Unit


Memory Unit

Memory Unit.svg

Actions of the Memory Unit

All von Neumann CPUs store their instructions in memory.

In a Harvard architecture, the data memory unit and the instruction memory unit are two different units. However, in a Princeton architecture the two memory units are combined into a single module. Most modern PC computer systems are Princeton, not Harvard, so the memory unit must handle all instruction and data transactions. This can serve as a bottleneck in the design.

Timing Issues

The memory unit is typically one of the slowest components of a microcontroller, because the external interface with RAM is typically much slower than the speed of the processor.


ALU symbol.svg



Tasks of an ALU

ALU units typically need to be able to perform the basic logical operations (AND, OR) and the addition operation. The inclusion of inverters on the inputs enables the same ALU hardware to perform the subtraction operation (adding an inverted operand), and the operations NAND and NOR.


ALU Slice

Example: 2-Bit ALU


2-bit ALU.svg


Example: 4-Bit ALU

Here is a circuit diagram of a 4 bit ALU.


Additional Operations



ALU Configurations









Register Stack









Complicated Structures


Example: IA-32


A typical IA-32 instruction is written as:



Example: MIPS


An example of a MIPS instruction is:

ADD R1, R2, R3



  1. CPU designers have used a variety of names for the arithmetic logic unit, including "ALU", "integer execution unit", and "E-box". Paul V. Bolotoff. "Functional Principles of Cache Memory" 2007.




Floating point numbers



IEEE 754

IEEE 754 format numbers are calculated as:


General floating point.svg

Floating Point Multiplication

Multiplying two floating point numbers is done as such:

Likewise, division can be performed by:


  1. Separate out the mantissa from the exponent
  2. Multiply (or divide) the mantissa parts together
  3. Add (or subtract) the exponents together
  4. Combine the two results into the new value
  5. Normalize the result value (optional).

Floating Point Addition


  1. Separate the mantissa from the exponent of each number
  5. Add the two mantissas together
  6. Normalize the result value (optional).

Floating Point Unit Design


For addition/Subtraction
  • An adder to add the mantissas together
For multiplication/division
  • A multiplier (or a divider) for the mantissa part
  • An adder for the exponent prts.

Both operation types require a complex control unit.



Further Reading

Control Unit


Simple Control Unit


Complex Control Unit

A more complex version of a control unit is implemented as a finite state machine (FSM). Multi-cycle, pipelined, and other advanced processor designs may require an FSM-based control unit.

Further reading

ALU Design

Add and Subtract Blocks

Addition and Subtraction



4-bit ripple carry adder-subtracter.svg


Bit Adders

Half Adder

A half adder is a circuit that performs binary addition on two bits. A half adder does not explicitly account for a carry input signal.



module half_adder(a, b, c, s)
   input a, b;
   output s, c;
   s = a ^ b;
   c = a & b;

Full Adder


Full-adder.svg1-bit full-adder.svg


Full-adder with gate delay.svg

We can use verilog to implement a full adder module:

   input a, b, cin;
   output cout, s;
   wire temp;
   temp = a ^ b;
   s = temp ^ cin;

Serial Adder




Parallel Adder


In many CPUs, the CPU latches the final carry-out of the parallel adder in an external "carry flag" in a "status register".

In a few CPUs, the latched value of the carry flag is always wired to the first carry-in of the parallel adder; this gives "Add with carry" with 2s' complement addition. (In a very few CPUs, an end-around carry -- the final carry-out of the parallel adder is directly connected to the first carry-in of the same parallel adder -- gives 1's complement addition).

Ripple Carry Adder

4-bit ripple carry adder.svg





wire [3:0] c;
wire [3:0] s;


This "ripple carry" arrangement makes "add" and "subtract" take much longer than the other operations of an ALU (AND, NAND, shift-left, divide-by-two, etc). A few CPUs use a ripple carry ALU, and require the programmer to insert NOPs to give the "add" time to settle.[1] A few other CPUs use a ripple carry adder, and simply set the clock rate slow enough that there is plenty of time for the carry bits to ripple through the adder. A few CPUs use a ripple carry adder, and make the "add" instruction take more clocks than the "XOR" instruction, in order to give the carry bits more time to ripple through the adder on an "add", but without unnecessarily slowing down the CPU during a "XOR". However, it makes pipelining much simpler if every instruction takes the same number of clocks to execute.

Carry Skip Adder

Carry Lookahead Adder

4-bit carry lookahead adder.svg



In the case of binary addition, generates if and only if both A and B are 1. If we write to represent the binary predicate that is true if and only if generates, we have:


In the case of binary addition, propagates if and only if at least one of A or B is 1. If we write to represent the binary predicate that is true if and only if propagates, we have:

Cascading Adders


the 64-bit carry lookahead unit is exactly the same as the 4-bit and 16-bit units. This means that once we have designed one carry lookahead module, we can cascade it to any large size.

Generalized Cascading



  1. "MuP21 Machine Forth": "Ripple Carry on + and +*"

Shift and Rotate Blocks

Shift and Rotate


Logical Shift

Rotate left logically.svg Rotate right logically.svg
A left logical shift A right logical shift


Arithmetic shift

Rotate right arithmetically.svg
A right arithmetic shift



Rotate left.svg Rotate right.svg
A left rotation A right rotation


Fast Shift Implementations



Further reading

32-Bit Barrel Shifter Implementation Using 74-Series Integrated Circuits

Multiply and Divide Blocks

Multiply and Divide Problems

Multiplication and Division operations are significantly more complicated than addition or subtraction operations. This additional complexity leads to more hardware, more complicated hardware, and longer processing time.



Multiplication Algorithms

Booth's Algorithm

Cascaded Multiplication

Wallace tree

The Wallace tree, a specialized structure for performing multiplication, has been called one of the most important advances in computing.[1]

A Wallace tree using many identical 3:2 compressors (aka full adders), such as the TI 74x275 chip, or the TI 74x183 chip, is one popular way to implement single-cycle multiplication. The datasheets for the TI 74x261 and 74x284 describe some practical details of implementing multiplication with a Wallace tree. The Dadda multiplier uses the same 3:2 compressors in a slightly more efficient arrangement.

Division Algorithm

Multiply and Accumulate



Would perform the operation:

A = A + (B × C)





Will perform the operation:

ACC = ACC + (B × C)

Fused Multiply-Add


ALU Flags





Zero Flag

Determining whether two values are equal requires the ALU to determine whether the result is zero. This can be accomplished by feeding each bit of the result into a NOR gate. The beauty of this is that a single multi-port NOR gate requires less hardware than an entire array of equivalent 2-port gates.

Overflow Flag


Carry/Borrow flag





Latch ALU flags or not?


 CMP R1,R2 // compare
 BEQ equal_routine // branch if equal





   JMP equal_routine


Design Paradigms

Single Cycle Processors



Cycle Times




Redundant Hardware


Single Cycle Designs


Multi Cycle Processors


Multi-Cycle Stages

Multi-cycle processors break up the instruction into its fundamental parts, and executes each part of the instruction in a different clock cycle. Since signals have less distance to travel in a single cycle, the cycle times can be sped up considerably.


Fetch the instruction from memory
Decode the instruction, and generate the necessary control signals
Feed the necessary control signals into the ALU and produce a result
Read from memory, if specified
Write the result back to the register file or to memory.

This is just a textbook example, and modern processes tend to use many more steps than this to execute an instruction.

Example: MicroChip PIC16 Microcontroller


Hardware Reuse



Pipelined Processors

Pipelining Introduction


  1. Instruction fetch (IF)
  2. Instruction Decode (ID)
  3. Execution (EX)
  4. Memory Read/Write (MEM)
  5. Result Writeback (WB)




Pipelining Philosophy

Pipelining is concerned with the following tasks:

  • Shorter computations per cycle allow for faster clock cycles.
  • Throughput is increased by having instructions complete more frequently.


Pipelining Hardware






Our resultant processor design will look similar to this:

Pipeline MIPS.png


Pipeline 3.png

Pipelined processors generate the same results as a one-instruction-at-a-time processor does when running the same software -- they just generate those results much more quickly. People who build pipelined processors sometimes add special hardware -- operand forwarding; pipeline interlocks; etc. -- in order to get the same results "as if" each instruction is fetched, evaluated, and its results committed before the next instruction is fetched (non-overlapped) -- even though pipelined processors actually overlap instructions.

The throughput of a processor is the number of instructions that complete in a span of time. Many processors are designed to have a typical throughput of one instruction per clock cycle, even though any one particular instruction requires many cycles -- one cycle per pipeline stage -- from the time it is fetched to the time it completes.






Commons:Pipeline (computer)

Superscalar Processors




VLIW Processors


VLIW Vs Superscalar






Vector Processors



Parallel Execution




Non-Parallel Execution




Multicore Processors


Symmetric Multi-core

A symmetric multi-core processor is one that has multiple cores on a single chip, and all of those cores are identical.

Example: Intel Core 2:

The Intel Core 2 is an example of a symmetric multi-core processor. The Core 2 can have either 2 cores on chip ("Core 2 Duo") or 4 cores on chip ("Core 2 Quad"). Each core in the Core 2 chip is symmetrical, and can function independently of one another. It requires a mixture of scheduling software and hardware to farm tasks out to each core.

Example: Parallax Propeller:

The Parallax Propeller is an example of a symmetric multi-core processor. The Parallax Propeller has 8 cores on chip, each one a 32-bit RISC processor. Each core in the Parallax Propeller chip is symmetrical, and can function independently of one another.

Asymmetric Multi-core


Example: Cell Processor


Example: Kilocore

Rapport's Kilocore processor, is an asymmetrical multi-core processor. The Kilocore has one general purpose processor, a PowerPC processing core, and either 256 or 1024 data processing cores on-chip. The cores are designed to run at extremely low power, so the overall chip is faster and yet uses less power than typical desktop CPUs[2].

Symmetric Multicore

The Intel Core 2 Duo

A symmetric multi-core processor is a processor which has multiple cores that are all exactly the same. Every single core has the same architecture and the same capabilities. An example of a symmetric multi-core system is the Intel Core 2 Duo processor.


Asymmetric Multi-core

In an asymmetric multi-core processor, the chip has multiple cores on-board, but the cores might be different designs. Each core will have different capabilities.

Example: IBM Cell Processor

An example of an asymmetric multi-core processor is the IBM Cell processor.

SPE (cell).png
PPE (Cell).png


IBM Cell Block Diagram.svg

Notice how the SPE cores only connect to the PPE, and not to each other. Notice also that the PPE core is much larger than the individual SPE cores.

further reading

Execution Problems






The image below shows conceptually how an interrupt happens:







Further Reading




Data Hazards


Read After Write (RAW)
Write After Read (WAR)
Write After Write (WAW)

Race Conditions


Control Hazards


Structural Hazards


Fixing Hazards

There are a number of ways to avoid or eliminate hazards.



Pipeline 5.png





Register renaming


add R1, R2, R1



Speculative execution



Branch delay


Branch Predication


Branch Prediction


    do this

Which roughly translates to this assembly pseudo code:

top of loop:
compare condition and 0.
branch to end of loop if equal
do this
branch to top of loop
bottom of loop:


Example: Loop Optimization


while(loop condition)
   if(branch condition)
      do this
      do that


1) compare loop condition and 0
2) branch to end of loop if equal
3) compare branch condition and 0
4) branch to branch true if not equal
5) do that
6) branch to end of if
7) branch true
8) do this
9) end of if
10)branch to top of loop


while(loop condition)
   if(not branch condition)
      do this
      do that



A 2-bit branch predictor with 4 stages.


  • q0:Strong Take
  • q1:Weak Take
  • q2:Weak Not Take
  • q3:Strong Not Take


Benchmarking and Optimization

Performance Metrics

Performance Metrics




Runtime is the time it takes to run a program.






Clock rate



Cycles per Instruction



instructions executed per program




Some examples where it did turn out to be worthwhile:




Processor Time





In hard real-time systems, low latency is critical.







Further reading




Common Benchmarks

  • block move
  • Eratosthenes sieve
  • matrix multiply


Benchmark Problems

Further reading






Parallel Processing

Multi-Core Systems


Symmetric Multi-core


Example: Intel Core 2:


Example: Parallax Propeller:


Asymmetric Multi-core


Example: Cell Processor


Example: Kilocore


Symmetric Multicore

The Intel Core 2 Duo



Asymmetric Multi-core


Example: IBM Cell Processor


SPE (cell).png
PPE (Cell).png


IBM Cell Block Diagram.svg


further reading

Memory-Level Parallelism

Memory-Level Parallelism



Out Of Order Execution


The Tomasulo scheduling algorithm is a OOOE algorithm that supports function units with variable latency, including data-dependent latency.[1]



Example: Intel Hyperthreading



Support Software









With an assembler written, it is typically a good idea (although not always) to write a high-level language compiler for your new processor. Typically the high-level language in these situations is C because of its small number of built in constructions, and the close relationship that C shares with the underlying assembly language.


Further reading

Microprocessor Production






Dozens of FPGA CPU designs are available for download and tinkering. An appendix to this book, Microprocessor Design/Resources, lists details on how to get them.





Basic Photolithography







further reading

Sockets and interfacing

Form Factors







Advanced Topics





Some CPUs, such as the ECOMIPS[7], the Intel Core 2 and the Intel Xeon,[8] use "writable microcode" -- rather than storing the microcode in ROM or hard-wired logic, the microcode is stored in a RAM called a Writable Control Store or WCS.

Further Reading



  1. Daniel Kröning. "Design and Evaluation of a RISC Processor with a Tomasulo Scheduler". Section "2.2 The Tomasulo Scheduling Algorithm". 1999.
  6. B. Govindarajalu. "Computer Architecture and Organization, 2E" 2010.
  8. Wikipedia: microcode#Writable_control_stores

Register Renaming


In a register machine, programs are composed of instructions which operate on values. The instructions must name these values in order to distinguish them from one another. A typical instruction might say, "add X and Y and put the result in Z." In this instruction, X, Y, and Z are the names of storage locations.

In order to have a compact instruction encoding, most processor instruction sets have a small set of special locations which can be directly named. For example, the x86 instruction set architecture has 8 integer registers, the x86-64 set architecture has 16, many RISC microprocessors have 32, and the IA-64 instruction set architecture has 128. In smaller processors, the names of these locations correspond directly to elements of a register file.

Different instructions may take different amounts of time; for example, a processor may be able to execute hundreds of instructions while a single load from the main memory is in progress. Shorter instructions executed while the load is outstanding will finish first, thus the instructions will be finishing out of the original program order. Out-of-order execution has been used in most recent high-performance CPU's to achieve some of their speed gains.

When possible, an assembly language compiler will try to assign distinct instructions to different registers. However, there is a finite number of register names that can be used in assembly code, as limited by the specific microprocessor architecture. Many high performance CPU's have more physical registers than may be named directly in the instruction set, so they rename registers in hardware to achieve additional parallelism.

Data hazards

When more than one instruction references a particular location for an operand, either reading it (as an input) or writing to it (as an output), executing those instructions in an order different from the original program order can lead to three kinds of data hazards:

Read-after-write (RAW) Error
A read from a register or memory location must return the value placed there by the last write in program order, not some other write. This is referred to as a true dependency or flow dependency, and requires the instructions to execute in program order.
Write-after-write (WAW) Error
Successive writes to a particular register or memory location must leave that location containing the result of the second write. This can be resolved by squashing (synonyms: cancelling, annulling, mooting) the first write if necessary. WAW dependencies are also known as output dependencies.
Write-after-read (WAR) Error
A read from a register or memory location must return the last prior value written to that location, and not one written programmatically after the read. This is a sort of false dependency that can be resolved by register renaming. WAR dependencies are also known as anti-dependencies.

Instead of delaying the write until all reads are completed, two copies of the location can be maintained: the old value and the new value. If reads precede in program order, the write of the new value can be provided with the old value, even while other reads that follow the write are provided with the new value. The false dependency is broken and additional opportunities for out-of-order execution are created. When all reads that need the old value have been satisfied, it can be discarded. This is the essential concept behind register renaming.

Anything that is read and written can be renamed. While the general-purpose and floating-point registers are discussed the most, flag and status registers or even individual status bits are commonly renamed as well. Memory locations can also be renamed, although it is not commonly done to the extent practiced in register renaming. An example is the Transmeta Crusoe processor's gated store buffer, which is a form of memory renaming.

If programs refrained from reusing registers immediately, there would be no need for register renaming. Some instruction sets (e.g., IA-64) specify very large numbers of registers for specifically this reason. However, there are limitations to this approach:

  • It is very difficult for the compiler to avoid reusing registers without large code size increases. In loops, for instance, successive iterations would have to use different registers, which requires replicating the code in a process called loop unrolling (but see register rotation).
  • Large numbers of registers require more bits for specifying a register as an operand in an instruction, resulting in increased code size.
  • Many instruction sets historically specified smaller numbers of registers and cannot be changed now.

Code size increases are important because, when the program code is larger, the instruction cache misses more often and the processor stalls waiting for new instructions.

Architectural vs physical registers

Machine language programs specify reads and writes to a limited set of registers specified by the instruction set architecture (ISA). For instance, the DEC Alpha ISA specifies 32 integer registers, each 64 bits wide, and 32 floating-point registers, each 64 bits wide. These are the architectural registers. Programs written for processors running the Alpha instruction set will specify operations reading and writing those 64 registers. If a programmer stops the program in a debugger, they can observe the contents of these 64 registers (and a few status registers) to determine the progress of the machine.

One particular processor which implements this ISA, the Alpha 21264, has 80 integer and 72 floating-point physical registers. There are, on an Alpha 21264 chip, 80 physically separate locations which can store the results of integer operations, and 72 locations which can store the results of floating point operations.[1]

The following text describes two styles of register renaming, which are distinguished by the circuit which holds the data ready for an execution unit.

In all renaming schemes, the machine converts the architectural registers referenced in the instruction stream into tags. Where the architectural registers might be specified by 3 to 5 bits, the tags are usually a 6 to 8 bit number. The rename file must have a read port for every input of every instruction renamed every cycle, and a write port for every output of every instruction renamed every cycle. Because the size of a register file generally grows as the square of the number of ports, the rename file is usually physically large and consumes significant power.

In the tag-indexed register file style, there is one large register file for data values, containing one register for every tag. For example, if the machine has 80 physical registers, then it would use 7 bit tags. 48 of the possible tag values in this case are unused.

In this style, when an instruction is issued to an execution unit, the tags of the source registers are sent to the physical register file, where the values corresponding to those tags are read and sent to the execution unit.

In the reservation station style, there are many small associative register files, usually one at the inputs to each execution unit. Each operand of each instruction in an issue queue has a place for a value in one of these register files.

In this style, when an instruction is issued to an execution unit, the register file entries corresponding to the issue queue entry are read and forwarded to the execution unit.

Architectural Register File or Retirement Register File (RRF)
The committed register state of the machine. RAM indexed by logical register number. Typically written into as results are retired or committed out of a reorder buffer.
Future File
The most speculative register state of the machine. RAM indexed by logical register number.
Active Register File
The Intel P6 group's term for Future File.
History Buffer
Typically used in combination with a future file. Contains the "old" values of registers that have been overwritten. If the producer is still in flight it may be RAM indexed by history buffer number. After a branch misprediction must use results from the history buffer—either they are copied, or the future file lookup is disabled and the history buffer is indexed by logical register number in "content-addressable memory" (CAM).
Reorder Buffer (ROB)
A structure that is sequentially (circularly) indexed on a per-operation basis, for instructions in flight. It differs from a history buffer because the reorder buffer typically comes after the future file (if it exists) and before the architectural register file.

Reorder buffers can be data-less or data-ful.

In Willamette's ROB, the ROB entries point to registers in the physical register file (PRF), and also contain other book keeping. This was also the first Out of Order design done by Andy Glew, at Illinois with HaRRM.

In the P6's ROB, the ROB entries contain data; there is no separate PRF. Data values from the ROB are copied from the ROB to the RRF at retirement.

There is, however, one small detail: if there is temporal locality in ROB entries (i.e., if instructions close together in the von Neumann instruction sequence write back close together in time, it may be possible to perform write combining on ROB entries and so have fewer ports than a separate ROB/PRF would). It is not clear if it makes a difference, since a PRF should be banked.

ROBs usually don't have associative logic, and certainly none of the ROBs designed by Andy Glew have CAM (see above). However, designer Keith Diefendorff has, for many years, insisted that ROBs have complex associative logic. The first ROB proposal, on the other hand, may have utilized CAM.

Tag-indexed register file scheme

In the renaming stage, every architectural register referenced (for read or write) is looked up in an architecturally-indexed remap file. This file returns a tag and a ready bit. The tag is non-ready if there is a queued instruction which will write to it that has not yet executed. For read operands, this tag takes the place of the architectural register in the instruction. For every register write, a new tag is pulled from a free tag FIFO, and a new mapping is written into the remap file, so that future instructions reading the architectural register will refer to this new tag. The tag is marked as unready, because the instruction has not yet executed. The previous physical register allocated for that architectural register is saved with the instruction in the reorder buffer, which is a FIFO that holds the instructions in program order between the decode and graduation stages.

The instructions are then placed in various issue queues. As instructions are executed, the tags for their results are broadcast, and the issue queues match these tags against the tags of their non-ready source operands. A match means that the operand is ready. The remap file also matches these tags, so that it can mark the corresponding physical registers as ready. When all the operands of an instruction in an issue queue are ready, that instruction is ready to issue. The issue queues pick ready instructions to send to the various functional units each cycle. Non-ready instructions stay in the issue queues. This unordered removal of instructions from the issue queues can make them large and power-consuming.

Issued instructions are read from a tag-indexed physical register file (bypassing just-broadcast operands) and then execute. Execution results are written to tag-indexed physical register file, as well as broadcast to the bypass network preceding each functional unit. Graduation puts the previous tag for the written architectural register into the free queue so that it can be reused for a newly decoded instruction.

An exception or branch misprediction causes the remap file to back up to the remap state at last valid instruction via combination of state snapshots and cycling through the previous tags in the in-order pre-graduation queue. Since this mechanism is required, and since it can recover any remap state (not just the state before the instruction currently being graduated), branch mispredictions can be handled before the branch reaches graduation, potentially hiding the branch misprediction latency. This is the renaming style used in the MIPS R10000, the Alpha 21264, and the FP section of the AMD Athlon.

Reservation stations scheme

In the renaming stage, every architectural register referenced for reads is looked up in both the architecturally-indexed future file and the rename file. The future file read gives the value of that register, if there is no outstanding instruction yet to write to it (i.e., it's ready). When the instruction is placed in an issue queue, the values read from the future file are written into the corresponding entries in the reservation stations. Register writes in the instruction cause a new, non-ready tag to be written into the rename file. The tag number is usually serially allocated in instruction order—no free tag FIFO is necessary.

Just as with the tag-indexed scheme, the issue queues wait for non-ready operands to see matching tag broadcasts. Unlike the tag-indexed scheme, matching tags cause the corresponding broadcast value to be written into the issue queue entry's reservation station.

Issued instructions read their arguments from the reservation station, bypass just-broadcast operands, and then execute. As mentioned earlier, the reservation station register files are usually small, with perhaps eight entries.

Execution results are written to the reorder buffer, to the reservation stations (if the issue queue entry has a matching tag), and to the future file if this is the last instruction to target that architectural register (in which case register is marked ready).

Graduation copies the value from the reorder buffer into the architectural register file. The sole use of the architectural register file is to recover from exceptions and branch mispredictions.

Exceptions and branch mispredictions, recognised at graduation, cause the architectural file to be copied to the future file, and all registers marked as ready in the rename file. There is usually no way to reconstruct the state of the future file for some instruction intermediate between decode and graduation, so there is usually no way to do early recovery from branch mispredictions. This is the style used in the integer section of the AMD K7 and K8 designs.

Comparison between the schemes

In both schemes, instructions are inserted in-order into the issue queues, but are removed out-of-order. If the queues do not collapse empty slots, then they will either have many unused entries, or require some sort of variable priority encoding for when multiple instructions are simultaneously ready to go. Queues that collapse holes have simpler priority encoding, but require simple but large circuitry to advance instructions through the queue.

Reservation stations have better latency from rename to execute, because the rename stage finds the register values directly, rather than finding the physical register number, and then using that to find the value. This latency shows up as a component of the branch misprediction latency.

Reservation stations also have better latency from instruction issue to execution, because each local register file is smaller than the large central file of the tag-indexed scheme. Tag generation and exception processing are also simpler in the reservation station scheme, as discussed below.

The physical register files used by reservation stations usually collapse unused entries in parallel with the issue queue they serve, which makes these register files larger in aggregate, and consume more power, and more complicated than the simpler register files used in a tag-indexed scheme. Worse yet, every entry in each reservation station can be written by every result bus, so that a reservation-station machine with, e.g., 8 issue queue entries per functional unit will typically have 9 times as many bypass networks as an equivalent tag-indexed machine. Result forwarding thus consumes much more power and area than in a tag-indexed design.

Furthermore, the reservation station scheme has four places (Future File, Reservation Station, Reorder Buffer and Architectural File) where a result value can be stored, whereas the tag-indexed scheme has just one (the physical register file). Because the results from the functional units, broadcast to all these storage locations, must reach a much larger number of locations in the machine than in the tag-indexed scheme, this function consumes more power, area, and time. Still, in machines equipped with very accurate branch prediction schemes and if execute latencies are a major concern, reservation stations can work remarkably well.


  1. In fact, there are even more locations than that, but those extra locations are not germane to the register renaming operation.)



A cache is a small amount of memory which operates more quickly than main memory. Data is moved from the main memory to the cache, so that it can be accessed faster. Modern chip designers put several caches on the same die as the processor; designers often allocate more die area to caches than the CPU itself. Increasing chip performance is typically achieved by increasing the speed and efficiency of chip cache.

The cache memory performance is the most significant factor in achieving high processor performance.[1]


Cache helps to speed up processors because it works on the principle of locality.

In this chapter, we will discuss several possible cache arrangements, in increasing order of complexity:

  • No cache, single-CPU, physical addressing
  • Single cache, single-CPU, physical addressing
  • Cache hierarchy: L1, L2, L3, etc.
  • cache replacement policies: associativity, random replacement, LRU, etc.
  • Split cache: I-cache and D-cache, on top of a unified cache hierarchy
  • caching with multiple CPUs
  • cache hardware that supports virtual memory addressing
  • the TLB as a kind of cache
  • how single-address-space virtual memory addressing interacts with cache hardware
  • how per-process virtual memory addressing interacts with cache hardware

No cache

Most processors today, such as the processors inside standard keyboards and mice, don't have any cache. Many historically important computers, such as Cray supercomputers, don't have any cache.[1] The vast majority of software neither knows nor cares about the specific details of the cache, or if there is even a cache at all.

Processors without a cache are usually limited in performance by the main memory access time. Without a cache, the processor fetches each instruction, one at a time, from main memory, and every LOAD or STORE goes to main memory before executing the next instruction.

One way to improve performance is to substitute faster main memory. Alas, that usually has a financial limit: hardly anyone is willing to pay a penny a bit for a gigabyte of really fast main memory.

Even if money is no object, eventually one reaches physical limits to main memory access time. Even with the fastest possible memory money can buy, the memory access time for a unified 1 gigabyte main memory is limited by the time it takes a signal to get from the CPU to the most distant part of the memory and back.

Single cache

Using exactly the same technology, it takes less time for a signal to traverse a small block of memory than a large block of memory.

The performance of a processor with a cache is no longer limited by the main memory access time. The performance of a processor with a cache is usually limited in performance by the (much faster) cache memory access time: if the cache access time of a processor could be decreased, the processor would have higher performance. [1] However, cache memory is generally much easier to speed up than main memory: really fast memory is much more affordable when we only buy small amounts of it. If it will improve the performance of a system significantly, lots of people are willing to pay a penny a bit for a kilobyte of really fast cache memory.

Principal of Locality


Spatial Locality
Temporal Locality
When data item is accessed, it is likely that the same data item will be accessed again. For instance, variables are typically read and written to in rapid succession. It is a good idea to keep recently used items in the cache, and not over-write data that has been recently used.

Hit or Miss


Measurements of "the hit ratio" are typically performed on benchmark applications. The actual hit ratio varies widely from one application to another. In particular, video and audio streaming applications often have a hit ratio close to zero, because each bit of data in the stream is read once for the first time (a compulsory miss), used, and then never read or written again. Even worse, many cache algorithms (in particular, LRU) allow this streaming data fill the cache, pushing out of the cache information that will be used again soon (cache pollution).[2]

Cache performance

A processor with a cache first looks in the cache for data (or instructions). On a miss, the processor then fetches the data (or instructions) from main memory. On a miss, this process takes *longer* than an equivalent processor without a cache.

There are three ways a cache gives better net performance than a processor without a cache:

  • A hit (read from the cache) is faster than the time it takes a processor without a cache to fetch from main memory. The trick is to design the cache so we get hits often enough that their increase in performance more than makes up for the loss in performance on the occasional miss. (This requires a cache that is faster than main memory).
  • Multiprocessor computers with a shared main memory often have a bottleneck accessing main memory. When a local cache succeeds in satisfying memory operations without going all the way to main memory, main memory bandwidth is freed up for the other processors, and the local processor doesn't need to wait for the other processors to finish their memory operations.[1]
  • Many systems are designed so the processor often read multiple items from cache simultaneously -- either 3 separate caches for instruction, data, and TLB; or a multiported cache; or both -- which takes less time than reading the same items from main memory one at a time.

The last two ways improve overall performance even if the cache is no faster than main memory.

A processor without a cache has a constant memory reference time T of

A processor with a cache has an average memory access time of[1]


  • m is the miss ratio
  • Tm is the time to make a main memory reference
  • Th is the time to make a cache reference on a hit
  • E accounts for various secondary factors (memory refresh time, multiprocessor contention, etc.)

Flushing the Cache


Cache Hierarchy


Inclusive, exclusive, and other cache hierarchy

When there are several levels of cache, and a copy of the data in some location in main memory has been cached in the L1 cache, is there another copy of that data in the L2 cache?

  • No. Some systems are designed to have strictly exclusive cache levels: any particular location in main memory is cached in at most one cache level.
  • Yes. Other systems are designed to have a strictly inclusive cache levels: whenever some location in main memory is cached in any one level, the same location is also cached in all higher levels. All the data in the L2 cache can also be found in L3 (and also in main memory).

All the data in a L1 cache can also be found in L2 and L3 (and also in main memory).

  • Maybe. In some systems, such as the Intel Pentium 4, some data in the L1 cache is also in the L2 cache, while other data in the L1 cache is not in the L2 cache. This kind of cache policy does not yet have a popular name.

Size of Cache



  1. Moore's law provides an increasing number of transistors per chip. After around 1989, more transistors are available per chip than a designer can use to make a CPU. These extra transistors are easily converted to large caches.


Cache Tagging


  2. The memory address of the data in the block
  3. The data from the specified memory address (a "block in the cache", also called a "line in the cache"[1])


The cache controller splits an effective memory address (MSB to LSB) into the tag, the index, and the block offset.[3][4] Some authors refer to the block offset as simply the "offset"[5] or the "displacement".[6][7]

A diagram of cache showing non-sequential data


Memory Stall Cycles

If the cache misses, the processor will need to stall the current instruction until the cache can fetch the correct data from a higher level. The amount of time lost by the stall is dependent on a number of factors. The number of memory accesses in a particular program is denoted as Am; some of those accesses will hit the cache, and the rest will miss the cache. The rate of misses, equal to the probability that any particular access will miss, is denoted rm. The average amount of time lost for each miss is known as the miss penalty, and is denoted as Pm. We can calculate the amount of time wasted because of cache miss stalls as:



Read Stall Times



Write Stall Times




To do:
Why would the cache ever attempt to synchronize with main memory? What causes such a synchronization to start?

Hierarchy Stall Times


Design Considerations



L3 cache further continues this trend, with larger block sizes, and minimized miss rate.

block size

A very small cache block size increases the miss ratio, since a miss will fetch less data at a time. A very large cache block size also increases the miss ratio, since it causes the system to fetch a bunch of extra information that is used less than the data it displaces in the cache. [1]






Cache Block Basic.svg


Most external caches (located on the motherboard, but external to the CPU) are direct-mapped or occasionally 2-way set associative, because it's complicated to build higher-associativity caches out of standard components.[8] If there is such a cache, typically there is only one external cache on the motherboard, shared between all CPUs.

The replacement policy for a direct-mapped cache is the simplest possible replacement policy: the new data must go in the one and only one place in the cache it corresponds to. (The old data at the location in the cache, if its dirty bit is set, must be written to main memory first).

2-Way Set Associative


The LRU replacement policy for a 2-way set associative cache is one of the simplest replacement policies: The new data must go in one of a set of 2 possible locations. Those 2 locations share a LRU bit that is updated whenever either one is read or written, indicating which one of the two entries in the set was the most-recently used. The new data goes in the *other* location (the least-recently used location). (The old data at that LRU location in the cache, if its dirty bit is set, must be written to main memory first).

2 way skewed associative

The 2-way skewed associative cache is "the best tradeoff for .... caches whose sizes are in the range 4K-8K bytes" -- André SeznecAndré Seznec. "A Case for Two-Way Skewed-Associative Caches". http://citeseer.ist.psu.edu/seznec93case.html. Retrieved 2007-12-13. [9]

Fully Associative


Cache Misses

There are three basic types of misses in a cache:

  1. Conflict Misses
  2. Compulsory Misses
  3. Capacity Misses

Conflict Misses

Cache Block Basic Conflict.svg


Compulsory Misses

Cache Block Conflict Compulsary.svg

The image above shows the difference between a conflict miss and a compulsory miss. A compulsory miss is an instance where the cache must miss because it does not contain any data. For instance, when a processor is first powered-on, there is no valid data in the cache and the first few reads will always miss.


Capacity Misses


Cache Write Policy




Write Through



Write Back



Write bypass

Some processors send writes directly to main memory, bypassing the cache. If that location is *not* already cached, then nothing more needs to be done. If that location *is* already cached, then the old data in the cache(s) needs to be marked "invalid" ("stale") so if the CPU ever reads that location, the CPU will read the latest value from main memory rather than some earlier value(s) in the cache(s).

Stale Data

It is possible for the data in main memory to be changed by a component besides the microcontroller. For instance, many computer systems have memory-mapped I/O, or a DMA controller that can alter the data. Some computer systems have several CPUs connected to a common main memory. It is important that the cache controller check that data in the cache is correct. Data in the cache that is old and may be incorrect is called "stale".

The three most popular[citation needed] approaches to dealing with stale data ("cache coherency protocols") are:

  • Use simple cache hardware that ignores what the other CPUs are doing.
  • Set all caches to write-through all STOREs (write-through policy). Use additional cache hardware to listen in ("snoop") whenever some other device writes to main memory, and invalidate local cache line whenever some other device writes to the corresponding cached location in main memory.
  • Design caches to use the MESI protocol.

To do:
Fill in more details on MESI and alternative cache coherency protocols

With simple cache hardware that ignores what the other CPUs are doing, cache coherency is maintained by the OS software. The OS sets up each page in memory as either (a) exclusive to one particular CPU (which is allowed to read, write, and cache it); all other CPUs are not allowed to read or write or cache that page; (b) shared read/write between CPUs, and set to "non-cacheable", in the same way that memory-mapped I/O devices are set to non-cacheable; or (c) shared read-only; all CPUs are allowed to cache but not write that page.

Split cache

High-performance processors invariably have 2 separate L1 caches, the instruction cache and the data cache (I-cache and D-cache). This "split cache" has several advantages over a unified cache:[8]

  • Wiring simplicity: the decoder and scheduler are only hooked to the I-cache; the registers and ALU and FPU are only hooked to the D-cache.
  • Speed: the CPU can be reading data from the D-cache, while simultaneously loading the next instruction(s) from the I-cache.

Multi-CPU systems typically have a separate L1 I-cache and L1 D-cache for each CPU, each one direct-mapped for speed.

Open question: To speed up running Java applications in a JVM (and similar interpreters and CPU emulators), would it help to have 3 separate caches -- a machine instruction cache indexed by the program counter PC, a byte code cache indexed by the VM's instruction pointer IP, and a data cache ?

On the other hand, in a high-performance processor, other levels of cache, if any -- L2, L3, etc. -- as well as main memory -- are typically unified, although there are several exceptions (such as the Itanium 2 Montecito). The advantages of a unified cache (and a unified main memory) are:[8]

  • Some programs spend most of their time in a small part of the program processing lots of data. Other programs run lots of different subroutines against a small amount of data. A unified cache automatically balances the proportion of the cache used for instructions and the proportion used for data -- to get the same performance on a split cache would require a larger cache.
  • when instructions are written to memory -- by an OS loading an executable file from storage, or from a just-in-time compiler translating bytecode to executable code -- a split cache requires the CPU to flush and reload the instruction cache; a unified cache doesn't require that.

Error detection

Each cache row entry may have error detection bits. Since the cache only holds a copy of information in the main memory (except for the write-back queue), when an error is detected, the desired data can be re-fetched from the main memory -- treated as a kind of miss-on-invalid -- and the system can continue as if no error occurred. A few computer systems use Hamming error correction to correct single-bit errors in the "data" field of the cache without going all the way back to main memory.[10]

Specialized cache features

Many CPUs use exactly the same hardware for the instruction cache and the data cache. (And, of course, the same hardware is used for instructions as for data in a unified cache. The revolutionary idea of a Von Neumann architecture is to use the same hardware for instructions and for data in the main memory itself). For example, the Fairchild CLIPPER used 2 identical CAMMU chips, one for the instruction cache and one for the data cache.[1]

Because the various caches are used slightly differently, some CPU designers customize each cache in different ways.

  • Some CPU designers put the "branch history bits" used for branch prediction in the instruction cache. There's no point to adding such information to a data-only cache.
  • Many instruction caches are designed in such a way that the only way to deal with stale instructions is to invalidate the entire cache and reload. Data caches are typically designed with more fine-grained response, with extra hardware that can invalidate and reload only the particular cache lines that have gone stale.
  • The virtual-to-physical address translation process often has a lot of specialized hardware associated with it to make it go faster -- the TLB cache, hardware page-walkers, etc. We will discuss this in more detail in the next chapter, Virtual Memory.


  1. a b c d e f g h Alan Jay Smith. "Design of CPU Cache Memories". Proc. IEEE TENCON, 1987. [1] [2]
  2. Paul V. Bolotoff. "Functional Principles of Cache Memory". 2007.
  3. John L. Hennessy, David A. Patterson. "Computer Architecture: A Quantitative Approach". 2011. ISBN 012383872X, ISBN 9780123838728. page B-9. [3]
  4. David A. Patterson, John L. Hennessy. "Computer organization and design: the hardware/software interface". 2009. ISBN 0123744938, ISBN 9780123744937 "Chapter 5: Large and Fast: Exploiting the Memory Hierarchy". p. 484. [4]
  5. Gene Cooperman. "Cache Basics". 2003. [5]
  6. Ben Dugan. "Concerning Caches". 2002. [6]
  7. Harvey G. Cragon. "Memory systems and pipelined processors". 1996. ISBN 0867204745, ISBN 9780867204742. "Chapter 4.1: Cache Addressing, Virtual or Real" p. 209 [7]
  8. a b c Paul V. Bolotoff. "Functional Principles of Cache Memory". 2007.
  10. Paul V. Bolotoff. Functional Principles of Cache Memory. 2007.

Further reading

  • Parallel Computing and Computer Clusters/Memory

Virtual Memory


If a simple virtual==physical address path is adequate for your CPU, you don't need virtual memory.



If your CPU needs to do this, then you need something to translate user-visible addresses to physical address -- either design the CPU to connect to some off-chip bank register or MMU (such as the 8722 MMU or the 68851 MMU) or design in an on-chip bank register or MMU.

You may want to do this in order to:

  • support various debug tools that trap on reads or writes to selected addresses.
  • allow access to more RAM (wider physical address) than the user-level address seems to support (banking)
  • support many different programs all in RAM at the same time at different physical RAM locations, even though they were all compiled to run at location 0x300.
  • allow a program to successfully read and write a large block of data using normal LOAD and STORE instructions as if it were all in RAM, even though the machine doesn't have that much RAM (paging with virtual memory)
  • support a "protected" supervisor-level system that can run buggy or malicious user-level code in an isolated sandbox at full speed without damaging other user-level programs or the supervisor system itself -- Popek and Goldberg virtualization, W xor X memory protection, etc.
  • or some combination of the above.



Paging systems are designed to be transparent, that is, the (user-mode) programs running on the microprocessor do not need to be explicitly aware of the paging mechanism to operate correctly.

Many processor systems give pages certain qualifiers to specify what kinds of data can be stored in the page. For instance, many new processors specify whether a page contains instructions or data, so that data pages cannot be executed as instructions, and instructions cannot be corrupted by data writes (see W^X).

The hardware part of virtual memory is called the memory management unit (MMU). Most MMUs have a granularity of one page.

A few CPU designs use a more fine-grained access control to detect and prevent buffer overflow bugs, a common security vulnerability.[1]

Memory Accessing

Memory addresses correspond to a particular page, and an offset within that page. If a page is 212 bytes in a 32-bit computer, then the first 20 bits of the memory address are the page address, and the lower 12 bits are the offset of the data inside that page. The top 20 bits in this case will be separated from the address, and they will be replaced with the current physical address of that page. If the page does not exist in main memory, the processor (or the paging software) will retrieve the page from secondary storage, which can cause a significant delay.


A page is a basic unit of memory, typically several kilobytes or larger. A page may be moved in memory to different locations, or if it is not being used, it can frequently be moved to secondary storage instead. The area in the secondary storage is typically known as the page file, the "scratchpad", or something similar.

Page Table


Page Faults


Translation Look-Aside Buffer


Notice that even though the TLB can be considered a kind of cache, caching part of the page table stored in main memory, it is a physically separate structure than the instruction cache or the data cache, and has several features not found in those caches.

TLB entry

The SRAM in the TLB can be seen as entirely composed of TLB entries. The format of the TLB entries in the TLB SRAM is fixed by the TLB hardware. The paging supervisor -- part of the operating system -- typically maintains a page table in main memory which stores the page table entries in exactly the same format as TLB entries. Each TLB entry contains:

  • the virtual address of a page (analogous to the "tag" in a cache)
  • the physical address of a page (analogous to the "data" in a cache)

While not essential, some TLB hardware has many other optional control and protection fields and flags in the TLB, including:

  • the no-execute bit (NX bit), used to implement W^X ("Write XOR Execute")
  • a "dirty bit" (also called the "modified bit"), set whenever there is a STORE written into that page, and typically cleared when the modified page is written to the backing store.
  • the writable bit, used to implement PaX, sometimes cleared and later set by the OS in order to implement copy-on-write (COW)
  • which virtual address space a physical page belongs to (unnecessary on a single address space operating system)
  • the supervisor bit
  • statistics on which TLB entries were most recently or most frequently used, used to decide which TLB entry to discard when loading a new TLB entry from main memory
  • statistics on which page was most recently or most frequently used, used to support LRU or more sophisticated page-replacement algorithms that decide which page currently in main memory to "page out" to the backing store when the OS needs to load some other page from the backing store into physical memory

The page table entries may include additional per-page fields that are not copied into the TLB entries, such as

  • the "pinned bit" (aka "fixed flag") that indicates that a page must stay in main memory -- the paging supervisor marks as pinned pages that must stay in main memory, including the paging supervisor executable code itself, the device drivers for the secondary storage devices on which pages are swapped out; interrupt handler executable code. Some data buffers are also pinned during I/O transactions during the time that devices outside the CPU read or write those buffers (direct memory access and I/O channel hardware).
  • a "present" bit (clear when that particular virtual page does not currently exist in physical main memory)

Further reading

Power Dissipation


The primary problem in server farms like the ones used by Google is power.[2]


Gene's Law


Two reasons to reduce power


The peak power problem




The average power problem


In some situations, there are other reasons to reduce power:









further reading




Further Reading

Related Wikibooks

Wikipedia Articles

Wikiversity Courses

Commons Image Categories

External Links


  • Nisan and Schocken. "The Elements of Computing Systems: Building a Modern Computer from First Principles". 2005. ISBN 978-0262640688. [20]
    • Shimon Schocken. "From NAND to Tetris in 12 steps: building a modern computer from first principles" [21] is an overview of the Nisan and Schocken book.
  • Hamacher, Vranesic, Zaky, Manjikian. "Computer Organization and Embedded Systems". ISBN 978-0073380650

David Winkel and Franklin Prosser. "The Art of Digital Design". ISBN 0-13-046607-7. Published by Prentice-Hall, 1987. "build a PDP-8 using registers and microcode."





GNU Free Documentation License





























  4. Preserve all the copyright notices of the Document.
  8. Include an unaltered copy of this License.
  15. Preserve any Warranty Disclaimers.
































How to use this License for your documents


Copyright (c) YEAR YOUR NAME.
under the terms of the GNU Free Documentation License, Version 1.3
or any later version published by the Free Software Foundation;
Free Documentation License".


with the Invariant Sections being LIST THEIR TITLES, with the

