Inside the Machine: An Illustrated Introduction to Microprocessors and Computer Architecture (10 page)

like #12, or an address stored in a register, like #D.

Unconditional branches are fairly easy to execute, since all that the com-

puter needs to do upon decoding such a branch in the instruction register is

to have the control unit replace the address currently in the program counter

with branch’s target address. Then the next time the processor goes to fetch

the instruction at the address given by the program counter, it’ll fetch the

address at the branch target instead.

Conditional Branch

Though it has the same basic instruction format as the unconditional

branch (instruction #target), the
conditional branch
instruction is a

30

Chapter 2

little more complicated, because it involves jumping to the target

address only if a certain condition is met.

For example, say we want to jump to a new line of the program only if

the previous arithmetic instruction’s result is zero; if the result is nonzero,

we want to continue executing normally. We would use a conditional

branch instruction that first checks to see if the previously executed

arithmetic instruction yielded a zero result, and then writes the branch

target into the program counter if it did.

Because of such conditional jumps, we need a special register or set

of registers in which to store information about the results of arithmetic

instructions—information such as whether the previous result was zero or

nonzero, positive or negative, and so on.

Different architectures handle this in different ways, but in our DLW-1,

this is the function of the
processor status word (PSW)
register. On the DLW-1, every arithmetic operation stores different types of data about its outcome in

the PSW upon completion. To execute a conditional branch, the DLW-1

must first
evaluate
the condition on which the branch depends (e.g., “is the previous arithmetic instruction’s result zero?” in the preceding example) by

checking the appropriate bit in the PSW to see if that condition is true or

false. If the branch condition evaluates to true, then the control unit replaces the address in the program counter with the branch target address. If the

branch condition evaluates to false, then the program counter is left as-is,

and the next instruction in the normal program sequence is fetched on the

next cycle.

For example, suppose we had just subtracted the number in A from the

number in B, and if the result was zero (that is, if the two numbers were equal), we want to jump to the instruction at memory address #106. Program 2-2

shows what assembler code for such a conditional branch might look like.

Line

Code

Comments

16

sub A, B, C

Subtract the number in register A from the number in register B and

store the result in C.

17

jumpz #106

Check the PSW, and if the result of the previous instruction was zero,

jump to the instruction at address #106. If the result was nonzero,

continue on to line 18.

18

add A, B, C

Add the numbers in registers A and B and store the result in C.

Program 2-2: Assembler code for a conditional branch

The jumpz instruction causes the processor to check the PSW to determine

whether a certain bit is 1 (true) or 0 (false). If the bit is 1, the result of the subtraction instruction was 0 and the program counter must be loaded with

the branch target address. If the bit is 0, the program counter is incremented

to point to the next instruction in sequence (which is the add instruction in

line 18).

There are other bits in the PSW that specify other types of information

about the result of the previous operation (whether it is positive or negative,

is too large for the registers to hold, and so on). As such, there are also other The Mechanics of Program Execution

31

types of conditional branch instructions that check these bits. For instance,

the jumpn instruction jumps to the target address if the result of the preceding arithmetic operation was negative; the jumpo instruction jumps to the target

address if the result of the previous operation was too large and overflowed

the register. If the machine language instruction format of the DLW-1 could

accommodate more than eight possible instructions, we could add more

types of conditional jumps.

Branch Instructions and the Fetch-Execute Loop

Now that we have looked at the basics of branching, we can modify our three-

step summary of program execution to include the possibility of a branch

instruction:

1.

Fetch
the next instruction from the address stored in the program

counter, and load that instruction into the instruction register.

Increment the program counter.

2.

Decode
the instruction in the instruction register.

3.

Execute
the instruction in the instruction register, using the following rules:

a.

If the instruction is an arithmetic instruction, then execute it using

the ALU and register file.

b.

If the instruction is a memory-access instruction, then execute it

using the memory hardware.

c.

If the instruction is a branch instruction, then execute it using the

control unit and the program counter. (For a taken branch, write

the branch target address into the program counter.)

In short, you might say that branch instructions allow the programmer to

redirect the processor as it travels through the instruction stream. Branches

point the processor to different sections of the code stream by manipulating

its control unit, which, because it contains the instruction register and pro-

gram counter, is the rudder of the CPU.

The Branch Instruction as a Special Type of Load

Recall that an instruction fetch is a special type of load that happens auto-

matically for every instruction and that always takes the address in the program counter as its source and the instruction register as its destination. With that in mind, you might think of a branch instruction as a similar kind of load,

but under the control of the programmer instead of the CPU. The branch

instruction is a load that takes the address specified by #target as its source

and the instruction register as its destination.

Like a regular load, a branch instruction can take as its target an address

stored in a register. In other words, branch instructions can use register-

relative addressing just like regular load instructions. This capability is useful because it allows the computer to store blocks of code at arbitrary places in

memory. The programmer doesn’t need to know the address where the

32

Chapter 2

block of code will wind up before writing a branch instruction that jumps to

that particular block; all he or she needs is a way to get to the memory

location where the operating system, which is responsible for managing

memory, has stored the starting address of the desired block of code.

Consider Program 2-3, in which the programmer knows that the

operating system has placed the address of the branch target in line 17 in

register C. Upon reaching line 17, the computer jumps to the address stored

in C by copying the contents of C into the instruction register.

Line

Code

Comments

16

sub A, B, A

Subtract the number in register A from the number in register B and

store the result in A.

17

jumpz #C

Check the PSW, and if the result of the previous instruction was

zero, jump to the instruction at the address stored in C. If the result

was nonzero, continue on to line 18.

18

add A, 15, A

Add 15 to the number in A and store the result in A.

Program 2-3: A conditional branch that uses an address stored in a register

When a programmer uses register-relative addressing with a branch

instruction, the operating system must load a certain register with the base

address of the
code segment
in which the program resides. Like the data

segment, the code segment is a contiguous block of memory cells, but its

cells store instructions instead of data. So to jump to line 15 in the currently running program, assuming that the operating system has placed the base

address of the code segment in C, the programmer could use the following

instruction:

Code

Comments

jump #(C + 30)

Jump to the instruction located 30 bytes away from the start of the code

segment. (Each instruction is 2 bytes in length, so this puts us at the 15

instruction.)

Branch Instructions and Labels

In programs written for real-world architectures, branch targets don’t usually

take the form of either immediate values or register-relative values. Rather,

the programmer places a
label
on the line of code to which he or she wants to jump, and then puts that label in the branch’s target field. Program 2-4

shows a portion of assembly language code that uses labels.

sub A, B, A

jumpz LBL1

add A, 15, A

store A, #(D + 16)

LBL1: add A, B, B

store B, #(D + 16)

Program 2-4: Assembly language code that uses labels

The Mechanics of Program Execution

33

In this example, if the contents of A and B are equal, the computer will

jump to the instruction with the label LBL1 and begin executing there,

skipping the instructions between the jump and the labeled add. Just as the

absolute memory addresses used in load and store instructions are modified

at load time to fit the location in memory of the program’s data segment,

labels like LBL1 are changed at load time into memory addresses that reflect

the location in memory of the program’s code segment.

Excursus: Booting Up

If you’ve been around computers for any length of time, you’ve heard the

terms
reboot
or
boot up
used in connection with either resetting the computer to its initial state or powering it on initially. The term boot is a shortened

version of the term bootstrap, which is itself a reference to the seemingly

impossible task a computer must perform on start-up, namely, “pulling itself

up by its own bootstraps.”

I say “seemingly impossible,” because when a computer is first powered

on there is no program in memory, but programs contain the instructions

that make the computer run. If the processor has no program running when

it’s first powered on, then how does it know where to fetch the first instruc-

tion from?

The solution to this dilemma is that the microprocessor, in its power-on

default state, is hard-wired to fetch that first instruction from a predetermined address in memory. This first instruction, which is loaded into the processor’s

instruction register, is the first line of a program called the BIOS that lives in a special set of storage locations—a small read-only memory (ROM) module

attached to the computer’s motherboard. It’s the job of the BIOS to perform

basic tests of the RAM and peripherals in order to verify that everything is

working properly. Then the boot process can continue.

At the end of the BIOS program lies a jump instruction, the target of

which is the location of a
bootloader
program. By using a jump, the BIOS

hands off control of the system to this second program, whose job it is to

search for and load the computer’s operating system from the hard disk.

The operating system (OS) loads and unloads all of the other programs

that run on the computer, so once the OS is up and running the computer

is ready to interact with the user.

34

Chapter 2

P I P E L I N E D E X E C U T I O N

All of the processor architectures that you’ve looked at

so far are relatively simple, and they reflect the earliest

stages of computer evolution. This chapter will bring

you closer to the modern computing era by introducing

one of the key innovations that underlies the rapid

performance increases that have characterized the past

few decades of microprocessor development:
pipelined

execution
.

Pipelined execution is a technique that enables microprocessor designers

to increase the speed at which a processor operates, thereby decreasing the

amount of time that the processor takes to execute a program. This chapter

will first introduce the concept of pipelining by means of a factory analogy,

and it will then apply the analogy to microprocessors. You’ll then learn how

to evaluate the benefits of pipelining, before I conclude with a discussion of

the technique’s limitations and costs.

NOTE

This chapter’s discussion of pipelined execution focuses solely on the execution of
arithmetic instructions. Memory instructions and branch instructions are pipelined
using the same fundamental principles as arithmetic instructions, and later chapters
will cover the peculiarities of the actual execution process of each of these two types of
instruction.

The Lifecycle of an Instruction