CST 202 : Computer
Organization and
Architecture Module: 3
P R E PA RED BY
AS HA ROS E T HOMAS
A P CS E ( A I), ASIET,K A LA DY
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
SYLLABUS
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
MULTIPLICATION ALGORITHMS
❖The product of two, unsigned, n-digit numbers can give a product of 2n digits.
❖Basic components are an AND gate and an adder.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Multiplication of Unsigned Numbers
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Array implementation
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Array multiplication of unsigned binary
numbers(4 bit)
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Reference
Reference Text1
◦ Hamacher C., Z. Vranesic and S. Zaky, Computer Organization ,5/e, McGraw Hill, 2011
Chapter 6:
◦ Section 6.3 -Multiplication of positive numbers page No: 376
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
MULTIPLICATION OF UNSIGNED NUMBERS
(Add-Shift Method)-RESTORING METHOD
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
PROBLEM MULTIPLY 13*11-(RESTORING
METHOD)
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Sequential Circuit for binary
Multiplier(Add -Shift Method)
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Reference
Reference Text1
◦ Hamacher C., Z. Vranesic and S. Zaky, Computer Organization ,5/e, McGraw Hill, 2011
Chapter 6:
◦ Section 6.3 -Multiplication of positive numbers page No: 378
◦ Home work-
◦ 1110(Multiplicand) & 1010(Multiplier) Ans:C=0 A=1000,Q=1100
◦ 10111(M)&10011(Q) ANS C=0,A=01101 Q=10101
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Integer Division
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
RESTORING DIVISION
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Algorithm
I. Initial Steps
Divisor = n-bit positive divisor M
Dividend = n-bit positive dividend Q .
Register A is set to 0.
After the division is complete, the n-bit quotient is in register Q and the remainder is in register A.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
II.STEPS
Do the following three steps n times:
1. Shift A and Q left one bit position.
2. Subtract M from A, and place the answer back in A.
3. If the sign of A is 1, set q0 to 0 and add M back to A (that is, restore A); otherwise, set
q0 to 1.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
FLOWCHART
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
CIRCUIT ARRANGEMENT FOR BINARY
DIVISION
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Restoring Division
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
PROBLEM
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Example 1: (Divide 1000(Q)/0011(M))
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Example 2: (Divide 1001(Q)/0011(M))
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Reference
Reference Text1
◦ Hamacher C., Z. Vranesic and S. Zaky, Computer Organization ,5/e, McGraw Hill, 2011
Chapter 6:
◦ Section 6.6 –Integer Division No: 390
◦ Home work-
◦ 10010(Dividend) & 0010(Divisor)
◦ ANSWER remainder=000000 Quotient =01001
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Multiplication of Signed
Numbers
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
The Booth Algorithm
1. Multiplicand is placed in BR and Multiplier in QR
2. Accumulator register AC, Qn+1 are initialized to 0
3. Sequence counter SC is initialized to n (number of bits).
4. Compare Qn and Qn+1 and perform the following
◦ 01 –> AC=AC+BR
◦ 10 –> AC=AC+BR’+1
◦ 00 –> No arithmetic operation
◦ 11-> No arithmetic operation
5. ASHR- Arithmetic Shift right AC,QR
6. Decrement SC by 1
The final product will be store in AC, QR
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Booth Algorithm-Flowchart
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
HARDWARE FOR BOOTH ALGORITHM
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
ARITHMETIC SHIFT RIGHT OPERATION
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
EXAMPLE-PROBLEM
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
PROBLEM Cont…
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
PROBLEM Cont…
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Reference
Reference Text1
William Stallings, Computer Organization and Architecture: Designing for Performance,
Pearson, 9/e, 2013.
Chapter 11:
◦ Section 11.3 –Integer Arithmetic
◦ HW—9*-13
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
EXAMPLE 2: Multiply 13 x -6 using Booth
Algorithm
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Multiply -11 x 8 using Booth Algorithm
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
PIPELINING-Introduction
The laundry analogy for pipelining
1)Washing
2)Drying
3)Ironing
4)Folding
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
PIPELINING
Pipelining is a technique of decomposing a sequential process into sub operations.
◦ Each sub process being executed in a special dedicated segment.
◦ operates concurrently with all other segments.
A pipeline processor may process each instruction in 4 steps
F Fetch: Read the instruction from the memory
D Decode: Decode the instruction and fetch the source operands
E Execute: Perform the operation specified by the instruction
W Write: Store the result in the destination location.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
CLASSIFICATION OF PIPELINE
PROCESSORS
Arithmetic Pipelining:
The arithmetic logic units of a computer can be segmented for various pipeline operations.
Instruction Pipelining:
The execution of instructions can be pipelined by overlapping the execution of concurrent
instructions.
Processor Pipelining:
Pipeline processing of the same data stream by a cascade of processors, each of which
processes a specific task.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Instruction Pipelining
Here a pipeline processor may process each instruction in 4 steps
F Fetch: Read the instruction from the memory
D Decode: Decode the instruction and fetch the source operands
E Execute: Perform the operation specified by the instruction
W Write: Store the result in the destination location.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Instruction Pipelining-BASIC CONCEPT
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Space Time Diagram
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
INSTRUCTION PIPELINE-EXAMPLE 2
Four Segment Instruction Pipeline
PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
3/23/2024
INSTRUCTION PIPELINE-Flow Diagram
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Space Time Diagram
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
PIPELINE CONFLICTS
Resource Conflicts:They are caused by access to same memory or same resource by two
segments at the same time.
Data Dependency:Conflicts arise when an instruction depends on the result of a previous
instruction.
Branch Difference(Control dependency):they arise from branch and other instructions that
change the value of PC.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Reference
Reference Text1
◦ Hamacher C., Z. Vranesic and S. Zaky, Computer Organization ,5/e, McGraw Hill, 2011
Chapter 8:
◦ Section 8.1 –Introduction page No: 454
Reference Text2
oKaiHwang, Faye Alye Briggs, Computer architecture and parallel processing McGraw-
Hill, 1984
Chapter 3:
◦ Section 3.1 –Introduction page No: 145
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
MODULE 3 ASSIGNMENT-ARRAY
MULTIPLIER
Q)
SUBMISSION DATE 2/4/24
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
ARITHMETIC PIPELINES
Arithmetic Pipelining:
❑The arithmetic logic units of a computer can be segmented for pipeline operations in various
data formats.
❑An arithmetic pipeline divides an arithmetic operation into sub operations for execution in the
pipeline segments.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Pipeline Unit For Floating Point Addition And Subtraction
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Space Time Diagram
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Reference
Reference Text1
oKaiHwang, Faye Alye Briggs, Computer architecture and parallel processing McGraw-
Hill, 1984
Chapter 3:
◦ Section 3.2
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
HAZARDS
❑When one of the pipeline stage is not able to complete its processing task for a given
instruction in the time allotted, the pipelined operation is said to have stalled(bubble).
❑ Any condition that cause pipeline to stall is called a hazard.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
PIPELINE HAZARDS DETECTION AND
RESOLUTION
There are three classes of data dependent hazards,
1. Write After Read hazards (WAR)
2. Read After Write hazards (RAW)
3. Write After Write hazards (WAW)
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
DATA HAZARDS-INTRODUCTION
• Domain – Input Set (Operands in Registers or in Memory)
of an instruction.
• Range – Output set of an instruction.
• Instruction i comes before instruction j in the program
order
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Data Hazard Classification - RAW
Instruction i comes before instruction j
◦ RAW : Read After Write ➔ R(I)∩ D(J) ≠ ɸ
(flow dependence)
◦ j tries to read a source before i writes it, so j incorrectly gets the old
value.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
WAR- Write After Read
WAR : Write After Read ➔ D(I) ∩ R(J) ≠ ɸ
(anti dependence)
◦ j tries to write a destination before it is read by i, so i incorrectly gets the new
value.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Data Hazard Classification - WAW
WAW : Write After Write ➔ R(I)∩ R(J) ≠ ɸ
(output dependence)
◦ j tries to write an operand before it is written by i, so we end up writing values
in the wrong order.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
CONCLUSION
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
HAZARD-RESOLUTION-operand
Forwarding-RAW-important
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Reference
Reference Text1
oKaiHwang, Faye Alye Briggs, Computer architecture and parallel processing McGraw-
Hill, 1984
Chapter 3:
◦ Section 3
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
TUTORIALS-PIPELINING
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
Q1:Identify the data dependency in the code
below.
3/23/2024 PREPARED BY ASHA ROSE THOMAS,AP,CSE(AI),ASIET,KALADY
