Rashtreeya Sikshana Samithi Trust
RV Institute of Technology and Management®
(Affiliated to VTU, Belagavi)
JP Nagar, Bengaluru – 560076
Department of Information Science and Engineering
Course Name: Computer Organization
Course Code: BCS302
Semester: III
Scheme :2022
Prepared By:
Prof. Krishnamurthy H
Assistant Professor,
Department of Information Science and Engineering
RVITM, Bengaluru - 560076
Email:[Link]@[Link]
1|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
Module 5
Basic processing Unit- 1. Fundamental Concepts, Computer Arithmetic, Floating Point
Arithmetic operations
Pipelining: Basic concepts of pipelining, throughput and speedup, pipeline hazards.
OBJECTIVES:
In this lesson, you will learn about Execution of instructions by a processor, the functional
units of a processor and how they are interconnected, hardware for generating control
signals and microprogrammed control and fixed point and floating-point arithmetic for
ALU operation such as adder and subtractor circuits, high-speed adders based on carry-
lookahead logic circuits, the Booth algorithm for multiplication of signed numbers, logic
circuits for divisionand arithmetic operations on floating-point numbers conforming to
the IEEE standard
CONTENTS:
1. Fundamental Concepts
Execution of a complete instruction, Multiple Bus Organization,
2. Computer Arithmetic
Addition and Subtraction, Multiplication Algorithm,Division Algorithm
3. Floating Point Arithmetic operations
Decimal Arithmetic Unit, Decimal Arithmetic Operations
2|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
Introduction
First, we focus on the processing unit, which executes machine-language instructionsand
coordinates the activities of other units in a computer. We examine its internal structure
and show how it performs the tasks of fetching, decoding, and executing such instructions.
The processing unit is often called the central processing unit (CPU). Addition and
subtraction oftwo numbers are basic operations at the machine-instruction level in all
computers. And arithmetic and logic operations, are implemented in ALU of the
processor.
1. FUNDAMENTAL CONCEPTS
A typical computing task consists of a series of operations specified by a sequence of
machine-language instructions that constitute a program. The processor fetches one
instruction at a time and performs the operation specified. Instructions are fetched from
successive memory locations until a branch or a jump instruction is encountered. The
processor uses theprogram counter, PC, to keep track of the address of the next
instruction to be fetched and executed. After fetching an instruction, the contents of the
PC are updated to point to the nextinstruction in sequence. A branch instruction may
cause a different value to be loaded into thePC.
When an instruction is fetched, it is placed in the instruction register, IR, from where itis
interpreted, or decoded, by the processor’s control circuitry. The IR holds the instruction
until its execution is completed. Consider a 32-bit computer in which each instruction is
contained in one word in the memory, as in RISC-style instruction set architecture. To
execute an instruction, the processor has to perform the following steps:
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]]
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
3|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
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
fetchphase. Performing the operation specified in the instruction constitutes the
instructionexecution phase. With few exceptions, the operation specified by an instruction
can be carried out by performing one or more of the following actions:
• Read the contents of a given memory location and load them into a processor register.
• Read data from one or more processor registers.
• Perform an arithmetic or logic operation and place the result into a processor register.
• Store data from a processor register into a given memory location.
The hardware components needed to perform these actions are shown in Figure. The
processor communicates with the memory through the processor-memory interface,
which transfers data from and to the memory during Read and Write operations. The
instruction
address generator updates the contents of the PC after every instruction is fetched. The
register file is a memory unit whose storage locations are organized to form the processor’s
general- purpose registers. During execution, the contents of the registers named in an
instruction that performs an arithmetic or logic operation are sent to the arithmetic and logic
unit (ALU), which performs the required computation. The results of the computation are
stored in a register inthe register file.
4|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
Fig 7:Functional units of Computer. R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
Atypical computation operates on data stored in registers. These data are processed by
combinational circuits, such as adders, and the results are placed into a register. A clock
signal is used to control the timing of data transfers. The registers comprise edge-triggered
flip-flops into which new data are loaded at the active edge of the clock. In this chapter, we
assume that the rising edge of the clock is the active edge. The clock period, which is the time
between two successive rising edges, must be long enough to allow the combinational circuit
to produce the correct result. Let us now examine the actions involved in fetching and
executing instructions. We illustrate these actions using a few representative RISC-style
instructions
SINGLE BUS ORGANIZATION
ALU and all the registers are interconnected via a Single Common Bus. Data & address lines
of the external memory-bus is connected to the internal processor-bus via MDR and
MAR respectively. (MDRà Memory Data Register, MAR à Memory Address
Register).MDR has 2 inputs and 2 outputs. Data may be loaded into MDR either from
memory-bus (external) or from processor-bus (internal).
5|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
6|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
MAR‟s input is connected to internal-bus; MAR‟s output is connected toexternal-bus.
Instruction Decoder & Control Unit is responsible for issuing the control-signals to
allthe units inside the processor. We implement the actions specified by the instruction
(loadedin the IR). Register R0 through R(n-1) are the Processor Registers. The programmer
can access these registers for general-purpose use. Only processor can access 3 registers Y,
Z & Temp for temporary storage during program-execution. The programmer cannot
access these 3 registers. In ALU,1) “A‟ input gets the operand from the output of the
multiplexer (MUX). 2) “B‟ input gets the operand directly from the processor-bus. There
are 2 options provided for“A‟ input of the ALU. MUX is used to select one of the 2
inputs. MUX selects either outputof Y or constant-value 4( which is used to increment
PC content). An instruction is executedby performing one or more of the following
operations:
1) Transfer a word of data from one register to another or to the ALU.
2) Perform arithmetic or a logic operation and store the result in a register.
3) Fetch the contents of a given memory-location and load them into a register.
4) Store a word of data from a register into a given memory-location.
Disadvantage: Only one data-word can be transferred over the bus in a clock cycle.
Solution: Provide multiple internal-paths. Multiple paths allow several data-transfers to take
place in parallel.
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: Riin & Riout.
Theseare called Gating Signals. Riin=1 = data on bus is loaded into Ri. Riout=1 as
content of Ri is placed on bus. Riout=0, makes bus can be used for transferring data
from other [Link], Move R1, R2; This transfers the contents of register
R1 to register R2. This can beaccomplished as follows:
1) Enable the output of registers R1 by setting R1out to 1 (Figure 7.2). This places
the contentsof R1 on processor-bus.
7|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
2) Enable the input of register R2 by setting R2out to 1. This loads data from
8|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
processor-businto register R4.
9|Page
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
All operations and data transfers within the processor take place within time-periods defined
by the processor-clock. The control-signals that govern a particular transfer are asserted
at the start of the clock cycle.
Input & Output Gating for one Register Bit
A 2-input multiplexer is used to select the data applied to the input of an edge- triggered
D flip-flop. Riin=1 makes mux selects data on bus. This data will be loaded into flip- flop at
rising-edge of clock. Riin=0 makes mux feeds back the value currently stored in flip-
flop (Figure). Q output of flip-flop is connected to bus via a tri-state gate. Riout=0
makes gate's output is in the high-impedance state. Riout=1 makesthe gate drives the
bus to 0 or 1, depending on the value of Q.
PERFORMING AN ARITHMETIC OR LOGIC OPERATION
The ALU performs arithmetic operations on the 2 operands applied to its A and Binputs.
One of the operands is output of MUX and, the other operand is obtained directly from
processor-bus. The result (produced by the ALU) is stored temporarily in register Z. The
sequence of operations for [R3] [R1]+[R2] is as follows:
1) R1out, Yin
2) R2out, SelectY, Add, Zin
3) Zout, R3in
Instruction execution proceeds as follows:
Step 1 --> Contents from register R1 are loaded into register Y.
Step2 --> Contents from Y and from register R2 are applied to the A and B inputs of ALU;
Addition is performed & Result is stored in the Z register.
Step 3 --> The contents of Z register is stored in the R3 register.
The signals are activated for the duration of the clock cycle corresponding to thatstep. All
other signals are inactive.
CONTROL-SIGNALS OF MDR
10 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
The MDR register has 4 control-signals (Figure). MDRin & MDRout control the
connection to the internal processor data bus & MDRinE & MDRoutE control the
connection to the memory Data bus. MAR register has 2 control-signals. MARin controls
the connection to the internal processor address bus & MARout controls the connection
to the memory address bus.
FETCHING A WORD FROM MEMORY
To fetch instruction/data from memory, processor transfers required address to MAR. At the
same time, processor issues Read signal on control-lines of memory-bus. When
requested-data are received from memory, they are stored in MDR. From MDR, they
are transferred to other registers. The response time of each memory access varies (based on
cache miss, memory-mapped I/O). To accommodate this, MFC is used. (MFC makes
Memory Function Completed). MFC is a signal sent from addressed-device to the
processor. MFC informs the processor that the requested operation has been completed
by addressed-device.
11 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
RRVVInstitute
InstituteofofTechnology
Technology&&Management®
Management®
COMPUTER
COMPUTERORGANIZATION
ORGANIZATION MODULE
MODULEVV
Consider the instruction Move (R1),R2. The sequence of steps is (Figure): R1out,
MARin, Read ;desired address is loaded into MAR & Read command is issued.
MDRinE, WMFC; load MDR from memory-bus & Wait for MFC response from
memory. MDRout,R2in; load R2 from MDR where WMFC=control-signal that
causes processor's control. circuitry to wait for arrival of MFC signal.
Storing a Word in Memory
Consider the instruction Move R2,(R1). This requires the following sequence: R1out,
MARin; desired address is loaded into MAR. R2out, MDRin, Write; data to be
written areloaded into MDR & Write command is issued. MDRoutE, WMFC ;load
data into memorylocation pointed by R1 from MDR.
EXECUTION OF A COMPLETE INSTRUCTION
Consider the instruction Add (R3),R1 which adds the contents of a memory-location
pointed by R3 to register R1. Executing this instruction requires the following actions:
1) Fetch the instruction.
2) Fetch the first operand.
3) Perform the addition &
12 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
4) Load the result into R1. R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
Instruction execution proceeds as follows:
Step1: The instruction-fetch operation is initiated by loading contents of PC into MAR
& sending a Read request to memory. The Select signal is set to Select4, which causes
the Muxto select constant 4. This value is added to operand at input B (PC‟s content),
and the result isstored in Z.
Step2: Updated value in Z is moved to PC. This completes the PC increment operation and
PCwill now point to next instruction.
Step3: Fetched instruction is moved into MDR and then to IR. The step 1 through 3
constitutes the Fetch Phase. At the beginning of step 4, the instruction decoder
interprets the contents ofthe IR. This enables the control circuitry to activate the
control-signals for steps 4 through [Link] step 4 through 7 constitutes the Execution
Phase.
Step4: Contents of R3 are loaded into MAR & a memory read signal is
issued.Step5: Contents of R1 are transferred to Y to prepare for addition.
Step6: When Read operation is completed, memory-operand is available in MDR, and
theaddition is performed.
Step7: Sum is stored in Z, then transferred to [Link] End signal causes a new instruction
fetchcycle to begin by returning to step1.
BRANCHING INSTRUCTIONS
Control sequence for an unconditional branch instruction is as follows: Instruction
execution proceeds as follows:
13 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
Step 1-3: The processing starts & the fetch phase ends in step3.
Step 4: The offset-value is extracted from IR by instruction-decoding circuit. Since
the updated value of PC is already available in register Y, the offset X is gated onto
the bus, andan addition operation is performed.
Step 5: The result, which is the branch-address, is loaded into the PC.
The branch instruction loads the branch target address in PC so that PC will fetch the next
instruction from the branch target address. The branch target address is usually
obtained by adding the offset in the contents of PC. The offset X is usually the
difference between thebranch target-address and the address immediately following
the branch instruction. In case of conditional branch, we have to check the status of
the condition-codes before loading a new value into the PC. e.g.: Offset-field-of-IRout,
Add, Zin, If N=0 then End If N=0, processor returns to step 1 immediately after step 4.
If N=1, step 5 is performed to load a new value into PC.
MULTIPLE BUS ORGANIZATION
The disadvantage of Single-bus organization is only one data-word can be transferred over
the bus in a clock cycle. This increases the steps required to complete the execution of
the instruction. The solution to reduce the number of steps, most processors provide
multipleinternal-paths. Multiple paths enable several transfers to take place in
parallel.
14 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
15 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
As shown in figure, three buses can be used to connect registers and the ALU of the
processor. All general-purpose registers are grouped into a single block called the
Register
File. Register-file has 3 ports:
1) Two output-ports allow the contents of 2 different registers to be simultaneously
placed onbuses A & B.
2) Third input-port allows data on bus C to be loaded into a third register during
the sameclock-cycle.
Buses A and B are used to transfer source-operands to A & B inputs of ALU.
Theresult is transferred to destination over bus C. Incrementer Unit is used to
increment PC by 4. Instruction execution proceeds as follows:
Step 1: Contents of PC are passed through ALU using R=B control-signal & loaded into
MARto start memory Read operation. At the same time, PC is incremented by 4.
Step2: Processor waits for MFC signal from memory.
Step3: Processor loads requested-data into MDR, and then transfers them to IR.
Step4: The instruction is decoded and add operation takes place in a single
step.
16 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
COMPLETE PROCESSOR
This has separate processing-units to deal with integer data and floating-point data.
Integer unit has to process integer data. (Figure). Floating unit has to process floating
point data. Data-Cache is inserted between these processing-units & main-memory.
The integer and floating unit gets data from data cache. Instruction-Unit fetches
instructions from an instruction-cache or from main-memory when desired instructions
are not already in cache. Processor is connected to system-bus & hence to the rest of the
computer by means ofa Bus Interface. Using separate caches for instructions & data is
common practice in many processors today. A processor may include several units of
each type to increase the potentialfor concurrent operations. The 80486 processor has
8-kbytes single cache for both instructionand data. Whereas the Pentium processor has
two separate 8 Kbytes caches for instruction anddata.
Note: To execute instructions, the processor must have some means of generating the
control- signals. There are two approaches for this purpose:
1) Hardwired control and Microprogrammed control.
17 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
Basic concepts of pipelining:
Performance of a computer can be increased by increasing the performance of the CPU.
This can be done by executing more than one task at a time. This procedure is referred
to as [Link] concept of pipelining is to allow the processing of a new task even
though the processing of previous task has not ended.
Pipelining is a technique of decomposing a sequential process into sub operations,
with each subprocessbeing executed in a special dedicated segment that operates
concurrently with all other segments. A pipeline can be visualized as a collection of
processing segments through which binary information flows. Each segment
performs partial processing dictated by the way the task is partitioned. The result
obtained from the computation in each segment is transferred to the next segment in
the pipeline. The final result is obtained after the data have passed through all
segments.
Consider the following operation: Result=(A+B)*[Link] the A and B values are
Fetched which is nothing but a “Fetch Operation”.The result of the Fetch operations
is given as input to the Addition operation, which is an [Link]
result of the Arithmetic operation is again given to the Data operand C which is
fetched from thememory and using another arithmetic operation which is
Multiplication in this scenario is executed. Finally the Result is again stored in the
“Result” [Link] this process we are using up-to 5 pipelines which are
Fetch Operation (A), Fetch Operation(B)Addition of (A & B), Fetch
Operation(C)Multiplication of ((A+B), C) Load ( (A+B)*C)
18 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
Now consider the case where a k-segment pipeline with a clock cycle time t, is used
to execute n tasks. The first task T1 requires a time equal to k t, to complete its
operation since there are k segments in the pipe. The remaining n - 1 tasks emerge
from the pipe at the rate of one task per clock cycle and they willbe completed after a
time equal to (n - 1)t, . Therefore, to complete n tasks using a k-segment pipeline
requires k + (n - 1) clock cycles. For example, the diagram of [Link] four
segments and six tasks. The time required to complete all the operations is 4 + (6 - 1)
= 9 clock cycles, as indicated in thediagram.
Throughput and Speedup
Parallel processing is a term used to denote a large class of techniques that are used
to provide simultaneous data-processing tasks for the purpose of inaeasing the
computational speed of a computersystem. The purpose of parallel processing is to
speed up the computer processing capability and increase its throughput.
Throughput: Is the amount of processing that can be accomplished during a given
interval of time. Theamount of hardware increases with parallel processing and with
it, the cost of the system increases. However, technological developments have
reduced hardware costs to the point where parallel processing techniques [Link]
19 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
economically feasible.
Speedup of a pipeline processing: The speedup of a pipeline processing over an
equivalent nonpipelineprocesSsi=nTgseisq d/eTfpinipeed =bny*tmhe/ r(amti+on -1)
the maximum speedup, also called ideal speedup, of a pipeline processor with m
stages over an equivalent nonpipelined processor is m. In other words, the ideal
speedup is equal to the number of pipeline stages. That is, when n is very large, a
pipelined processor can produce output approximately m times faster than a
nonpipelined processor. When n is small, the speedup decreases.
Pipeline Hazards
There are situations in pipelining when the next instruction
cannot execute in the following clock cycle. These events are
called hazards, and there are three differenttypes.
Hazards
The first hazard is called a structural hazard. It means that the hardware cannot
support the combination of instructions that we want to execute in the same clock
cycle. A structural hazard in the laundry room would occur if we used a washer
dryer combination instead of a separate washer and dryer, or if our roommate was
busy doing something else and wouldn‟t put clothes away. Our carefully scheduled
pipeline plans would then be foiled.
As we said above, the MIPS instruction set was designed to be pipelined,
making it fairly easy for designers to avoid structural hazards when designing a
pipeline. Suppose, however, that we had a single memory instead of two memories.
If the pipeline in Figure 4.27 had a fourth instruction, we would see that in the same
clock cycle the fi rst instruction is accessing data from memory while the fourth
instruction is fetching an instruction from that same memory. Without two memories,
our pipelinecould have a structural hazard.
20 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
Data Hazards
Data hazards occur when the pipeline must be stalled because one step must wait
for another to complete. Suppose you found a sock at the folding station for which
no match existed. One possible strategy is to run down to your room and search
through your clothes bureau to see if you can find thematch. Obviously, while you
are doing the search, loads must wait that have completed drying and areready to
fold as well as those that have finished washing and are ready to dry.
In a pipeline, data hazards arise from the dependence of one instruction on an
earlier one that is still inthe pipeline (a relationship that does not really exist when
doing laundry). For example, suppose we have an add instruction followed
immediately by a subtract instruction that uses the sum ($s0): add $s0, $t0, $t1sub
$t2, $s0, $t3
Without intervention, a data hazard could severely stall the pipeline. The add
instruction doesn’twrite its result until the fifth stage, meaning that we would have to
waste three clock cycles in the pipeline. Although we could try to rely on compilers
to remove all such hazards, the results would not besatisfactory. These dependences
happen just too often and the delay is just too long to expect the compiler to rescue
us from this dilemma.
The primary solution is based on the observation that we don’t need to wait
for the instruction tocomplete before trying to resolve the data hazard. For the code
sequence above, as soon as the ALU creates the sum for the add, we can supply it as
an input for the subtract. Adding extra hardware to retrieve the missing item early
from the internal resources is called forwarding or bypassing.
21 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
In this graphical representation of events, forwarding paths are valid only if the
22 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
destination stageis later in time than the source stage. For example, there cannot be a
valid forwarding path from the output of the memory access stage in the first
instruction to the input of the execution stage of the following, since that would
mean going backward in time.
It cannot prevent all pipeline stalls, however. For example, suppose the first
instruction was a load of $s0 instead of an add. As we can imagine from looking at
Figure 4.29, the desired data would be available only after the fourth stage of the first
instruction in the dependence, which is too late for the input of the third stage of sub.
Hence, even with forwarding, we would have to stall one stage for a load-use data
hazard, as Figure 4.30 shows. This figure shows an important pipeline concept,
officially called a pipeline stall, but oft en given the nickname bubble. We shall see
stalls elsewhere in the pipeline.
Control Hazards
The third type of hazard is called a control hazard, arising from the need to decide
based on the results of one instruction while others are executing. Suppose our
laundry crew was given the happytask of cleaning the uniforms of a football team.
Given how filthy the laundry is, we need to determine whether the detergent and
water temperature setting we select is strong enough to get the uniforms cleanbut not
so strong that the uniforms wear out sooner. In our laundry pipeline, we have to wait
until aft er the second stage to examine the dry uniform to see if we need to change
the washer setup or not. What to do? Here are the first of two solutions to control
23 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
hazards
24 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION
R V Institute of Technology & Management®
COMPUTER ORGANIZATION MODULE V
in the laundry room and its computer [Link]: Just operate sequentially until
the first batch is dry and then repeat until you have the right formula. This
conservative option certainly works, but it is slow.
25 | P a g e
III SEMESTER DIGITAL DESIGN & COMPUTER ORGANIZATION