Test: Instruction Pipelining - Computer Science Engineering (CSE) MCQ

A flow dependence, also known as a data dependency, true dependency, or read-after-write (RAW) happens when one instruction is dependent on the outcome of another. A hazard occurs if the read takes place before the write operation is complete.
Hence the correct answer is True dependency.

Concept:
Data forwarding also known as bypassing is an efficient way to solve data hazards in pipelined instruction execution. In the data forwarding or bypassing technique, the normal processor is updated with special hardware.

In this technique, the result of one stage is forward before the complete execution of particular instruction. Where the result is required it is directly passed to that pipeline stage. In the forwarding, there is no restriction from which stage data is transferred to next every next stage.

Option 1: Write after Write (WAW) hazard can be mitigated by data forwarding.
False, Write after Write (WAW)  is a situation that occurs when an instruction tries to write an operand before the first instruction writes it. This kind of hazard can also occur due to the concurrent execution of instructions. It may not calculate the inconsistent results. 

Option 2: Both WAW and WAR hazards can be mitigated by data forwarding.
False, Write after write, and write after reading can not reduce the problem of data forwarding where the result of one stage is forward before the complete execution of particular instruction is not possible because these are concurrent execution of instructions.

Option 3: Write after reading (WAR) hazard can be mitigated by data forwarding.
False, Write after the read is a situation that occurs when instruction II tries to write a destination before instruction I read it. It occurs due to the concurrent execution of instructions. It is also called Name dependence. Data forwarding the results are required it is directly passed to that pipeline stage but it is not possible where values are updated consequently. 
Hence the correct answer is None of the above.

Concept:
The segments are separated by registers Ri that holds the intermediate results between the stages.

Data:
Stage delay and corresponding register delay given
S₁ = 5 ,
S₂ = 6 ,
S₃ = 11,
S₄ = 8,
And corresponding register delay is 1 for each stage
Number of stage = 4
Time is taken to execute N instructions in non-pipelined implementation will be = (5 + 6 + 11 + 8)N = 30 × N
Clock period for pipelined implementation = max(5, 6, 11, 8) + 1 = 12 ns
Time is taken to execute N instructions in pipelined implementation will be = (4 + N-1)12 ≈ 12×N (N is very large)
Speedup = 30 N/12N = 2.5

Concept:
Speed up factor is defined as the ratio of time required for non-pipelined execution to that of time received for pipelined execution.

Data:
Time for non-pipelined execution per task = t_n = 50 ns
Time for pipelined execution per task =  t_p = 10 ns
Number of stages in the pipeline = k = 6
Number of tasks = 500

Formula
S = T_n/T_p
S = speed up facto

Calculation:
Time for non-pipelined = T_n = t_n × Number of tasks
Time for non-pipelined = T_n =  50 × 500
Time for pipelined = T_p​ = 1st task × k × t_p + (All Remaining Tasks (k - 1)) × t_p
Time for pipelined = T_p​ =  1 × 6 × 10 + (500 - 1) × 10
S = T_n/T_p = 4.95

Data:
number of instructions/tasks = m
number of stage (segment) = n

Non-pipeline
Assume each stage take 1 unit of time
Time taken (T_wp)  = number of stage × number of instructions
T_wp  = n.m

For pipeline 
Only 1st instruction takes n unit time then every (m - 1) instruction takes 1 unit time
Time taken(T_p) = (n + m - 1) 

Therefore option 2 is correct

Data:
Number of Instructions = n = 100
Number of stages = 5;
Stage delay = 5 ns

Calculation:
Time taken by five stage pipeline processor of singel instruction = T = Max (150, 120, 150, 160,140)  + stages delay
= 160 + 5 = 165 ns
The time required to execute n instructions with pipeline = [k + (n – 1)]T
= (5 + (100 - 1))×165 = 17160 ns

Concept:
Instruction pipelining partitions the execution process into multiple independent steps capable of occurring in parallel. Instructions traverse these partitions one stage at a time. Once an instruction progresses to the next step, the next instruction can take its place in the pipeline, and so on.

RISC processor has 5 stage instruction pipeline to execute all the instructions in the RISC instruction set.

• Instruction Fetch: In this stage, the CPU reads instructions from the address in the memory whose value is present in the program counter.
• Instruction Decode: In this stage, instruction is decoded and the register file is accessed to get the values from the registers used in the instruction.
• Instruction Execute: In this stage, ALU operations are performed.
• Memory Access: In this stage, memory operands are read and written from/to the memory that is present in the instruction.
• Write Back: In this stage, the computed/fetched value is written back to the register present in the instructions.

A processor that supports paging (which typically includes a mechanism for excluding execute permission even if not separately from reading permission) will access a TLB as part of instruction fetch. A translation lookaside data (TLB) is a memory cache that is used to reduce the time taken to access a user's memory location. The earliest that the instruction TLB and data TLB can be accessed is the fetch stage and memory stage respectively.

Hence the correct answer is the Fetch stage and memory stage respectively.

It is given that there is operand forwarding. In the case of operand forwarding, the updated value from the previous instruction's PO stage is forwarded to the present instruction's PO stage. Here there's a RAW dependency between I₁-I₂ for R5 and between I₂-I₃ for R₂. These dependencies are resolved by using operand forwarding as shown in the below table. The total number of clock cycles needed is 15.

clock cycles = 15.
Hence the correct answer is 15.

Concept:
Pipelining is an implementation technique whereby multiple instructions are overlapped in execution. It is like an assembly line. 
In pipelining, each step operates parallel with other steps. It stores and executes instructions in an orderly manner.
The main advantages of using pipeline are :

• It increases the overall instruction throughput. 
• Pipeline is divided into stages and stages are connected to form a pipe-like structure.
• We can execute multiple instructions simultaneously.
• It makes the system reliable. 
• It increases the program speed.
• It reduces the overall execution time but does not reduce the individual instruction time.

Concept:
Pipelining is an implementation technique whereby multiple instructions are overlapped in execution. It is like an assembly line. 
In pipelining, each step operates parallel with other steps. It stores and executes instructions in an orderly manner.
The main advantages of using pipeline are :

• It increases the overall instruction throughput. 
• Pipeline is divided into stages and stages are connected to form a pipe-like structure.
• We can execute multiple instructions simultaneously.
• It makes the system reliable. 
• It increases the program speed.
• It reduces the overall execution time but does not reduce the individual instruction time.

​Therefore option 2 is the false statement about Pipelining