GATE 2026 and ESE 2026
Subject : Computer Organization
by
Dr Y Chakrapani
Q. The microinstructions in the control memory of the processor have a
width of 26 bits: a microoperation field of 13 bits, a next address
field X and a Mux select field Y. There are 8 status bits at the input of
the Mux.
How many bits are there in X and Y fields and what is the size of the
control memory in number of words.
(a) 10,3,1024
(b) 8,5,256
(c) 5, 8, 2048
(d) 10,3,512
Micro Program Sequencer
*Control Memory size is 128 words(27 words), that is it
require 7 Address Lines
Control
Memory Micro Instruction
Micro Instruction
Micro Instruction
Micro Instruction
Microoperations
Microinstruction Format
Types of Microprogrammed Control Unit
1. Horizontal microprogrammed
2. Vertical microprogrammed
3. Hybrid Microprogramed
4. Nano programmed
Horizontal
Microprogramming
Vertical
Microprogramming
Hybrid
Microprogramming
P) Consider a hypothetical control unit that supports 5 groups
of mutually exclusive control signals. Also assume that group-1
and group-2 are using horizontal microprogramming where as
group-3, 4 and 5 are using vertical micro-programming. The
total number of bits used for control words are
Nano programming
Q. A Vertical Microinstruction is characterized by
(a) Limited Encoding
(b) High Degree of Encoding
(c) Limited Parallelism
(d) High Degree of Parallelism
Q. Which of the following is correct in Horizontal Microprogramming
(a) Decoders are not required
(b) Results in smaller sized microinstructions than Vertical
microprogramming
(c) Has High level of Concurrency
(d) Efficient use of Control memory
P) Consider a CPU where all the instructions require 7 clock cycles
to complete execution. There are 140 instructions in the instruction
set. It is found that 125 control signals are needed to be generated
by the control unit. While designing the horizontal
microprogrammed control unit, single address field format is used
for branch control logic. What is the minimum size of the control
word and control address register?
a) 125 , 7 b) 125,10 c) 135 , 9 d) 135 , 10
Pipelining
Pipelining
It is a Process where a Sequential Process is divided into
number of Subprocess of equal complexity such that each
subprocess is executed in a separate segment and all the
segments are active simultaneously
1. Arithmetic Pipelining
2. Instruction Pipelining
Arithmetic Pipelining
Arithmetic pipelining is a technique in computer
architecture where complex arithmetic operations (like
addition, multiplication, division) are split into smaller
stages, and multiple operations are processed
simultaneously, one in each stage , to increase throughput.
Stage 1 Stage 2 Stage 3 Stage 4
R1 R2 R3 R4 R5
1
2
3
6
7
Instruction Pipelining
Definition:
Instruction pipelining is a CPU technique where multiple instruction
stages, such as fetch, decode, execute, and write-back, are
overlapped so that different parts of multiple instructions are
processed simultaneously, improving overall throughput.
Instruction Cycle Consists of Fetch Cycle and Execution Cycle
Eg. Consider Inst Cycle of the Instruction ‘ADD R1, (450)’
L IF L ID L OF L EX L WB L
clk
Space Time Diagram
1 2 3 4 5 6 7 8
IF
ID
OF
EX
WB
Clock Cycles
1 2 3 4 5 6 7 8 9 Space-
Time
IF T1 T2 T3 T4
Diagram
ID T1 T2 T3 T4
OF T1 T2 T3 T4
EX T1 T2 T3 T4
WB T1 T2 T3 T4
Clock Cycles
1 2 3 4 5 6 7 8 9
I1 IF1 ID1 OF1 EX1 WB1
I2 - IF2 ID2 OF2 EX2 WB2
I3 - - IF3 ID3 OF3 EX3 WB3
I4 - - - IF4 ID4 OF4 EX4 WB4
Clock Cycles
1 2 3 4 5 6 7 8 9
I1 IF1 ID1 OF1 EX1 WB1
I2 - IF2 ID2 OF2 EX2 WB2
I3 - - IF3 ID3 OF3 EX3 WB3
I4 - - - IF4 ID4 OF4 EX4 WB4
Clock Cycles
1 2 3 4 5 6 7 8 9
Space-Time
IF T1 T2 T3 T4 Diagram
ID T1 T2 T3 T4
OF T1 T2 T3 T4
EX T1 T2 T3 T4
WB T1 T2 T3 T4
Maximum Frequency of Operation
of Instruction Pipelining
L IF L ID L OF L EX L WB L
clk
Case 1) When all the Latches have the same Delay
L IF L ID L OF L EX L WB L
clk
Case 2) When Latches have different Delays
L IF L ID L OF L EX L WB L
clk
Note:
Choose the Clock Cycle 𝜏 , such that
Clock Cycle 𝜏 ≥ 𝑚𝑎𝑥 𝜏𝑖 + 𝜏𝑑
where i = 1 to k and 𝜏𝑑 = Latch delay
𝑁𝑜𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 𝐸𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛 𝑇𝑖𝑚𝑒
1. Speedup Ratio =
𝑃𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 𝐸𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛 𝑇𝑖𝑚𝑒
𝑛. 𝑡𝑛
𝑆𝐾 =
𝑘 +𝑛 −1 .𝜏
𝑇𝑜𝑡𝑎𝑙 𝑛𝑜 𝑜𝑓 𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛𝑠
2. Throughput =
𝑃𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 𝐸𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛 𝑇𝑖𝑚𝑒
𝒏
𝑯𝑲 =
𝒌 + 𝒏 − 𝟏 .𝝉
𝑆𝑘
3. Pipeline Efficiency, Ek =
𝐾
𝒏
𝑬𝑲 =
𝒌+𝒏−𝟏
• Pipelining increases the Throughput
• but
the Time taken to execute
an Instruction remains 𝐬𝐚𝐦𝐞
Q. Comparing the time T1 taken for a single instruction on a pipelined CPU
with time T2 taken on a non-pipelined but identical CPU, we can say that
__________ ?
(a) T1 = T2
(b) T1 > T2
(c) T1 < T2
(d) T1 is T2 plus time taken for one instruction fetch cycle.
Q. The given pipeline has 4 phases with duration 60, 50, 90, 80 ns.
Latch delay is 10ns.
L S1 L S2 L S3 L S4 L
clk
Find a) Pipeline Cycle time
b) Non Pipeline execution Time
c) Speed up Factor
d) Pipeline time for 1000 tasks
e) Sequential Time for 1000 tasks
f) Throughout
Q. The given pipeline has 4 phases with duration 60, 50, 90, 80, ns.
Latch delay is 10ns.
L S1 L S2 L S3 L S4 L
clk
Find a) Pipeline Cycle time
b) Non Pipeline execution Time
c) Speed up Factor
d) Pipeline time for 1000 tasks
e) Sequential Time for 1000 tasks
f) Throughout
Q. The given pipeline has 4 phases with duration 60, 50, 90, 80, ns.
Latch delay is 10ns.
L S1 L S2 L S3 L S4 L
clk
Find a) Pipeline Cycle time
b) Non Pipeline execution Time
c) Speed up Factor
d) Pipeline time for 1000 tasks
e) Sequential Time for 1000 tasks
f) Throughout
Q. The given pipeline has 4 phases with duration 60, 50, 90, 80, ns.
Latch delay is 10ns.
L S1 L S2 L S3 L S4 L
clk
Find a) Pipeline Cycle time
b) Non Pipeline execution Time
c) Speed up Factor
d) Pipeline time for 1000 tasks
e) Sequential Time for 1000 tasks
f) Throughout
Q. The given pipeline has 4 phases with duration 60, 50, 90, 80, ns.
Latch delay is 10ns.
L S1 L S2 L S3 L S4 L
clk
Find a) Pipeline Cycle time
b) Non Pipeline execution Time
c) Speed up Factor
d) Pipeline time for 1000 tasks
e) Sequential Time for 1000 tasks
f) Throughout
Q. The given pipeline has 4 phases with duration 60, 50, 90, 80, ns.
Latch delay is 10ns.
L S1 L S2 L S3 L S4 L
clk
Find a) Pipeline Cycle time
b) Non Pipeline execution Time
c) Speed up Factor
d) Pipeline time for 1000 tasks
e) Sequential Time for 1000 tasks
f) Throughout
Dependencies in Pipelining
Data Dependency
a) RAW Dependency (True Dependency)
b) WAR Dependency (Anti Dependency)
c) WAW Dependency (Output Dependency)
a) RAW Dependency (True Dependency)
1 2 3 4 5 6 7 8
IF
ID
OF
EX
WB
1 2 3 4 5 6 7 8
IF
ID
OF
EX
WB
Introduce Stall Cycles
1 2 3 4 5 6 7 8
IF Stall Cycles
ID
OF
EX
WB
Operand Forwarding
1 2 3 4 5 6 7 8
IF
ID
OF
EX
WB
Control Dependency
Structural Dependency
P) Consider 5 stage pipeline which allows overlapping of all the
instructions except memory based instructions. Penality of the memory
based instruction is 3 cycles. In the program 40% memory instructions
are present, among them 60% are optimized. What is the average
instruction execution time? (Assume the pipeline cycle time as 8 ns)
(a) 9.76 ns. (b) 11.84 ns (c) 14.84 ns (d) 13.76 ns
i) 60% Instructions take Non-Memory Instructions need 1 CPI and
ii) 40% Instructions take Memory Instructions of which 60% are optimized and
40% are Not optimized
CPI Avg= 0.6x1 + 0•4(0.6x1+0.4x4)]
= 0.6 + 0•4 (0.6+1.6)
= 0.6 + 0.4×2.2
= 1.48
Avg time for Instruction = (CPI Avg )(𝜏)= 1.48 * 8ns = 11.84ns
Q. An instruction pipeline was designed with five stages without any
branch prediction: Fetch Instruction(FI), Decode Instruction(DI), Fetch
Operand (FO), Execute Instruction (EI) and Write Operand(WO).
Individually each of stage will take 5 ns, 7 ns, 10 ns and 8 ns, 6 ns
respectively. There are intermediate storage buffers after each stage and
delay of each buffer is 1 ns. A Program consisting of 12 instruction I1,
I2,…..I11, I12 is executed in this pipelined processor. Instruction I4 is the
only branch instruction and its branch target is I10. If the branch is taken
during the execution of the program, the time (in ns) need to execute the
program is _______.