MODULE 5

BASIC PROCESSING UNIT

Some Fundamental Concepts:

 To execute a program, the processor fetches one instruction at a time and
performs the operations specified.
 Instructions are fetched from successive memory locations until a branch
or a jump instruction is encountered.
 The processor keeps track of the address of the memory location containing
the next instruction to be fetched using the program counter, PC.
 After fetching an instruction, the contents of the PC are updated to point to
the next instruction in the sequence.
 A branch instruction may load a different value into the PC. Another key
register in the processor is the instruction register, IR.
 Suppose that each instruction comprises 4 bytes, and that it is stored in one
memory word. To execute an instruction, the processor has to perform the
following steps.
Step 1: Fetch the contents of the memory location pointed to by the PC. The
contents of this location are the instruction to be executed; hence they are loaded
into the IR. In register transfer notation, the required action is
IR← [[PC]]
Step 2: Increment the PC to point to the next instruction. Assuming that the
memory is byte addressable, the PC is incremented by 4; that is
PC← [PC] + 4
Step 3: Carry out the operation specified by the instruction in the IR.
Fetching an instruction and loading it into the IR is usually referred to as the
instruction fetch phase.
Performing the operation specified in the instruction constitutes the instruction
execution phase.

Single Bus organization of Processor:

 Figure shows the organization in which the arithmetic and logic unit (ALU)
and all the registers are interconnected via a single common bus.
 This bus is internal to the processor and should not be confused with the
external bus that connects the processor to the memory and I/O devices.
 The data and address lines of the external memory bus are connected to the
internal processor bus via the memory data register, MDR, and the memory
address register, MAR,
 Respectively. Register MDR has two inputs and two outputs. Data may be
loaded into MDR either from the memory bus or from the internal
processor bus.
 The data stored in MDR may be placed on either bus. The input of MAR
is connected to the internal bus, and its output is connected to the external
bus.
 The control lines of the memory bus are connected to the instruction
decoder and control logic block.
 Three registers Y, Z, and TEMP registers are used by the processor for
temporary storage during execution of some instructions.
 The multiplexer MUX selects either the output of register Y or a constant
value 4 to be provided as input A of the ALU.
 The constant 4 is used to increment the contents of the program counter.
 With few exceptions, an instruction can be executed by performing one or
more of the following operations in some specified sequence:
1. Transfer a word of data from one processor register to another or to
the ALU.
2. Perform an arithmetic or a logic operation and store the result in a
processor register.
3. Fetch the contents of a given memory location and load them into a
processor register.
4. Store a word of data from a processor register into a given memory
location.
Register Transfers:
 Instruction execution involves a sequence of steps in which data are
transferred from one register to another.
 For each register, two control signals are used to place the contents of that
register on the bus or to load the data on the bus into the register.
 The input and output of register Ri are connected to the bus via switches
controlled by the signals Riin and Riout, respectively.
 When Riin is set to 1, the data on the bus are loaded into Ri. Similarly,
when Riout, is set to 1, the contents of register Ri are placed on the bus.
 While Riout is equal to 0, the bus can be used for transferring data from
other registers.
Suppose that we wish to transfer the contents of register R1 to register R4. This
can be accomplished as follows:
1. Enable the output of register R1 by setting R1out to 1. This places the
contents of R1 on the processor bus.
2. Enable the input of register R4 by setting R4in, to 1. This loads data from
the processor bus into register R4.
3. All operations and data transfers within the processor take place within
time periods defined by the processor clock.

Performing an Arithmetic Or Logic Operation:

 The ALU is a combinational circuit that has no internal storage.
 It performs arithmetic and logic operations on the two operands applied
to its A and B inputs, one of the operands is the output of the multiplexer
MUX and the other operand is obtained directly from the bus.
 The result produced by the ALU is stored temporarily in register Z.
 Therefore, a sequence of operations to add the contents of register R1 to
those of register R2 and store the result in register R3 is
1. R1out, Yin
2. R2out, Select Y, Add, Zin
3. Zout R3in
  Step 1: The output of register R1 and the input of register Y are enabled,
causing the contents of R1 to be transferred over the bus to Y.
 Step 2: The multiplexer's Select signal is set to select, causing the
multiplexer to gate the contents of register Y to input A of the ALU. At the
same time, the contents of register R2 are gated onto the bus and, hence, to
input B. The function performed by the ALU depends on the signals
applied to its control lines. In this case, the Add line is set to 1, causing the
output of the ALU to be the sum of the two numbers at inputs A and B.
This sum is loaded into register Z because its input control signal is
activated.
 Step 3: The contents of register Z are transferred to the destination register,
R3. This last transfer cannot be carried out during step 2, because only one
register output can be connected to the bus during any clock cycle.

Fetching a word from memory

 To fetch a word of information from memory, the processor has to specify
the address of the memory location where this information is stored and
request a Read operation.
 The connections for register MDR are illustrated in Figure.
 It has four control signals:
MDRin and MDRout control the connection to the internal bus, and
MDRinE and MDR outE control the connection to the external bus.

As an example of a read operation, consider the instruction Move (R1), R2. The
actions needed to execute this instruction are:
1. MAR [RI]
2. Start a Read operation on the memory bus
3. Wait for the MFC (Memory Function Completed) response from the memory
4. Load MDR from the memory bus
5. R2 [MDR]
  These actions may be carried out as separate steps, but some can be
combined into a single step.
 Each action can be completed in one clock cycle, except action 3 which
requires one or more clock cycles, depending on the speed of the addressed
device.
 The memory read operation requires three steps, which can be described
by the signals being activated as follows:
1. Rlout, MARin, Read
2. MDRinE, WMFC
3. MDROUT, R2in
Where WMFC is the control signal that causes the processor's control circuitry to
wait for the arrival of the MFC signal.
Storing a word in Memory:
 Writing a word into a memory location follows a similar procedure.
 The desired address is loaded into MAR. Then, the data to be written are
loaded into MDR, and a Write command is issued.
 Hence, executing the instruction Move R2, (R1) requires the following
sequence:
1. R1out, MARin
2. R2out, MDRin, Write
3. MDRoutE, WMFC
 As in the case of the read operation, the Write control signal causes the
memory bus interface hardware to issue a Write command on the memory
bus.
 The processor remains in step 3 until the memory operation is completed
and an MFC response is received.

EXECUTION OF A COMPLETE INSTRUCTION:

 Consider the instruction Add (R3), R1 which adds the contents of a
memory location pointed to by R3 to register R1.
 Executing this instruction requires the following actions:
1. Fetch the instruction.
2. Fetch the first operand (the contents of the memory location pointed to by R3).
3. Perform the addition.
4. Load the result into RI.
Instruction execution proceeds as follows:

Step 1: The instruction fetch operation is initiated by loading the contents of the
PC into the MAR and sending a Read request to the memory. The Select signal
is set to Select4, which causes the multiplexer MUX to select the constant 4. This
value is added to the operand at input B, which is the contents of the PC, and the
result is stored in register Z.

Step 2: The updated value is moved from register Z back into the PC, while
waiting for the memory to respond.

Step 3: The word fetched from the memory is loaded into the IR. (Steps 1 through
3 constitute the instruction fetch phase, which is the same for all instructions.)

Step 4: The instruction decoding circuit interprets the contents of the IR. This
enables the control circuitry to activate the control signals for steps 4 through 7,
which constitute the execution phase. The contents of register R3 are transferred
to the MAR in step 4, and a memory read operation is initiated.

Step 5: the contents of R1 are transferred to register Y, to prepare for the addition
operation.

Step 6: When the Read operation is completed, the memory operand is available
in register MDR, and the addition operation is performed. The contents of MDR
are gated to the bus, and thus also to the B input of the ALU, and register Y is
selected as the second input to the ALU by choosing Select Y.

Step 7: The sum is stored in register Z, and then transferred to R1. The End signal
causes a new instruction fetch cycle to begin by returning to step 1.

To speed up the execution of Branch instructions, this value is copied into register
Y in step 2. Since step 2 is part of the fetch phase, the same action will be
performed for all instructions. This does not cause any harm because register Y
is not used for any other purpose at that time.
Pipelining:
Basic Concepts:
The speed of execution of programs is influenced by many factors.
 One way to improve performance is to use faster circuit technology to build
the processor and the main memory.
 Another possibility is to arrange the hardware so that more than one
operation can be performed at the same time.
In this way, the number of operations performed per second is increased even
though the elapsed time needed to perform any one operation is not changed.
 Pipelining is a particularly effective way of organizing concurrent activity
in a computer system.
 The technique of decomposing a sequential process into sub-operations,
with each sub-operation being executed in a dedicated segment.
 Pipelining is commonly known as an assembly-line operation.
Consider how the idea of pipelining can be used in a computer. The processor
executes a program by fetching and executing instructions, one after the other.
Let Fi and Ei refer to the fetch and execute steps for instruction Ii .
Execution of a program consists of a sequence of fetch and execute steps, as
shown in Figure.
  Now consider a computer that has two separate hardware units, one for
fetching instructions and another for executing them, as shown in Figure
b.
 The instruction fetched by the fetch unit is deposited in an intermediate
storage buffer, B1. This buffer is needed to enable the execution unit
to execute the instruction while the fetch unit is fetching the next
instruction.
 The results of execution are deposited in the destination location specified
by the instruction
 The computer is controlled by a clock.
 Any instruction fetch and execute steps completed in one clock cycle.
 Operation of the computer proceeds as in Figure 8.1
 In the first clock cycle, the fetch unit fetches an instruction I1 (step F1)
and stores it in buffer B1 at the end of the clock cycle.
 In the second clock cycle, the instruction fetch unit proceeds with the fetch
operation for instruction I2 (step F2).
 Meanwhile, the execution unit performs the operation specified by
instruction I1, which is available to it in buffer B1 (step E1). By the end of
the second clock cycle, the execution of instruction I1 is completed and
instruction I2 is available. Instruction I2 is stored in B1, replacing I1, which
is no longer needed.
 Step E2 is performed by the execution unit during the third clock cycle,
while instruction I3 is being fetched by the fetch unit. In this manner, both
the fetch and execute units are kept busy all the time.
 If the pattern in Figure 8.1c can be sustained for a long time, the completion
rate of instruction execution will be twice that achievable by the sequential
operation depicted in Figure a.

Idea of Pipelining in a computer

A pipelined processor may process each instruction in four steps, as follows:
F (Fetch): read the instruction from the memory.
D (Decode): decode the instruction and fetch the source operand(s).
E (Execute): perform the operation specified by the instruction.
W (Write): store the result in the destination location.

 The sequence of events for this case is shown in Figure a. Four instructions
are in progress at any given time.
 This means that four distinct hardware units are needed, as shown in Figure
b.
 These units must be capable of performing their tasks simultaneously and
without interfering with one another.
 Information is passed from one unit to the next through a storage buffer.
As an instruction progresses through the pipeline, all the information
needed by the stages
Downstream must be passed along. For example, during clock cycle 4, the
information in the buffers is as follows:
 Buffer B1 holds instruction I3, which was fetched in cycle 3 and is being
decoded by the instruction-decoding unit.
 Buffer B2 holds both the source operands for instruction I2 and the
specification of the operation to be performed. This is the information
produced by the decoding hardware in cycle 3. The buffer also holds the
information needed for the write step of instruction I2 (stepW2). Even
though it is not needed by stage E, this information must be passed on to
stage W in the following clock cycle to enable that stage to perform the
required Write operation.
 Buffer B3 holds the results produced by the execution unit and the
destination information for instruction I1.

Role of Cache Memory

 Each stage in a pipeline is expected to complete its operation in one clock
cycle. Hence, the clock period should be sufficiently long to complete
the task being performed in any stage.
 If different units require different amounts of time, the clock period must
allow the longest task to be completed.
 A unit that completes its task early is idle for the remainder of the clock
period. Hence, pipelining is most effective in improving performance if
the tasks being performed in different stages require about the same
amount of time.
 This consideration is particularly important for the instruction fetch step,
which is assigned one clock period in Figure a. The clock cycle has to be
equal to or greater than the time needed to complete a fetch operation.
 However, the access time of the main memory may be as much as ten
times greater than the time needed to perform basic pipeline stage
operations inside the processor, such as adding two numbers. Thus, if
each instruction fetch required access to the main memory,
pipelining would be of little value.
The use of cache memories solves the memory access problem.
 In particular, when a cache is included on the same chip as the processor,
access time to the cache is usually the same as the time needed to perform
other basic operations inside the processor.
 This makes it possible to divide instruction fetching and processing into
steps that are more or less equal in duration. Each of these steps is
performed by a different pipeline stage, and the clock period is chosen to
correspond to the longest one.
Pipeline Performance:
 The potential increase in performance resulting from pipelining is
proportional to the number of pipeline stages.
 However, this increase would be achieved only if pipelined operation as
depicted in Figure, could be sustained without interruption throughout
program execution.
 Unfortunately, this is not the True.
 Floating point may involve many clock cycle.
 For a variety of reasons, one of the pipeline stages may not be able to
complete its processing task for a given instruction in the time allotted.
 For example, stage E in the four stage pipeline of Figure b is responsible
for arithmetic and logic operations, and one clock cycle is assigned for this
task.
 Although this may be sufficient for most operations, some operations, such
as divide, may require more time to complete.
 Figure shows an example in which the operation specified in instruction I2
requires three cycles to complete, from cycle 4 through cycle 6.
 Thus, in cycles 5 and 6, the Write stage must be told to do nothing, because
it has no data to work with. Meanwhile, the information in buffer B2 must
remain intact until the Execute stage has completed its operation. This
means that stage 2 and, in turn, stage 1 are blocked from accepting new
instructions because the information in B1 cannot be overwritten. Thus,
steps D4 and F5 must be postponed as shown.
Pipelined operation in Figure 8.3 is said to have been stalled for two clock cycles.
Normal pipelined operation resumes in cycle 7. Any condition that causes the
pipeline to stall is called a hazard. We have just seen an example of a data hazard.
1) A data hazard is any condition in which either the source or the
destination operands of an instruction are not available at the time expected
in the pipeline. As a result some operation has to be delayed, and the pipeline
stalls.
2) control hazards or instruction hazards: The pipeline may also be stalled
because of a delay in the availability of an instruction.
For example, this may be a result of a miss in the cache .
3) A third type of hazard known as a structural hazard: This is the situation
when two instructions require the use of a given hardware resource at the
same time.

The effect of a cache miss on pipelined operation is illustrated in Figure.

Instruction I1 is fetched from the cache in cycle 1, and its execution proceeds
normally. However, the fetch operation for instruction I2, which is started in cycle
2, results in a cache miss. The instruction fetch unit must now suspend any further
fetch requests and wait for I2 to arrive. We assume that instruction I2 is received
and loaded into buffer B1 at the end of cycle 5. The pipeline resumes its normal
operation at that point.
 An alternative representation of the operation of a pipeline in the case of a
cache miss is shown in Figure b.
 This figure gives the function performed by each pipeline stage in each
clock cycle. Note that the Decode unit is idle in cycles 3 through 5, the
Execute unit is idle in cycles 4 through 6, and the
 Write unit is idle in cycles 5 through 7. Such idle periods are called
stalls. They are also often referred to as bubbles in the pipeline.
  If instructions and data reside in the same cache unit, only one instruction
can proceed and the other instruction is delayed.
 Many processors use separate instruction and data caches to avoid this
delay.
 An example of a structural hazard is shown in Figure. This figure shows
how the load instruction Load X(R1),R2
 The memory address, X + [R1], is computed in stepE2 in cycle 4, then
memory access takes place in cycle 5.
 The operand read from memory is written into register R2 in cycle 6. This
means that the execution step of this instruction takes two clock cycles
(cycles 4 and 5). It causes the pipeline to stall for one cycle, because both
instructions I2 and I3 require access to the register file in cycle 6.
Even though the instructions and their data are all available, the pipeline is
stalled because one hardware resource, the register file, cannot handle two
operations at once. If the register file had two input ports, that is, if it allowed two
simultaneous write operations, the pipeline would not be stalled. In general,
structural hazards are avoided by providing sufficient hardware resources
on the processor chip.
It is important to understand that pipelining does not result in individual
instructions being executed faster; rather, it is the throughput that increases,
where throughput is measured by the rate at which instruction execution is
completed.
The pipeline stalls, causes degradation in pipeline performance.
We need to identify all hazards that may cause the pipeline to stall and to
find ways to minimize their impact.