Pipelining: Two Marks Important Questions and Answers

Digital Principles and Computer Organization:

Chapter 9: Pipelining

Two Marks Questions with Answers

 

1. Define pipelining.

 Answer:  Pipelining is a technique of decomposing a sequential process into sub operations with each sub process being executed in a special dedicated segment that operates concurrently with all other segments.

2. What is stage delay ?

 Answer: The processing time in each pipeline stage is called stage delay.

3. What is interstage delay ?

 Answer: The delays are also introduced due to interstage transfer data. These time delays are known as interstage delay and it is denoted as d.

4. What is clock skewing?

 Answer: Ideally, we expect the clock pulse to arrive at all stage registers at the same time. In practice, the same clock pulse may arrive at different stages with a time offset of s. This problem is known as clock skewing.

5. What is speed–up factor ?

 Answer: The speedup factor of a k–stage pipeline over an equivalent non–pipelined processor is defined as

Sk  =   nT_n  / [k+ (n–1)]T_p

6. What is instruction pipelining?

 Answer: Performing fetch, decode and execute cycles for several simultaneously to reduce overall processing time is referred to referred to as instruction pipelining.

7. List the four stages in the instruction pipelining.

 Answer: The four stages in the instruction pipelining are :

S₁ – Fetch (F) : Read instruction from the memory.

S₂ – Decode (D) : Decode the opcode and fetch source operand (s) if necessary.

S₃ – Execute (E) : Perform the operation specified by the instruction.

S₄ – Store (S) : Store the result in the destination.

8. What is the ideal speed–up expected in a pipelined architecture with 'n' stages? Justify your answer.

 Answer: The pipelined processor ideally completes the processing of one instruction in each clock cycle, which means that the rate of instruction processing with n stage pipeline is n times that of sequential operation. Therefore, ideal speed–up factor is n. However, such ideal performance of the pipeline is achieved only when pipeline stages must complete their processing tasks for a given instruction in the time allotted. Unfortunately, this is not the case; pipeline operations could not sustained without interruption throughout the program execution.

9. What is meant by hazard in pipelining ?

 Answer: Any reason that causes the pipeline to stall is called a hazard.

10. List the different types of hazards.

 Answer:  The different types of instruction hazards are :

1. Structural hazards.

2. Data or Data dependent hazards.

3. Instruction or Control hazards.

11. What is structural hazard ?

 Answer: The hazard that exist because of conflicts due to insufficient resources when even with all possible combination, it may not be possible to overlap the operation is called structural hazard.

12. What is instruction or control hazard ?

 Answer: The hazard due to pipelining branch and other instructions that change the contents of program counter is called instruction or control hazard.

13. What is pipeline scheduling ?

 Answer: Rather than allowing the pipeline to stall, the compiler can rearrange instructions to avoid data hazard. It is called pipeline scheduling.

14. What is delayed load and delayed slot ?

 Answer: A load which requires that the following instruction do not use its result is said : to be delayed load and the pipeline slot after load instruction is called delayed slot.

15. How addressing modes affect the instruction pipelining ?

 Answer: Degradation of performance is an instruction pipeline may be due to address dependency where operand address cannot be calculated without available information needed by addressing mode for e.g. an instructions with register indirect mode cannot proceed to fetch the operand if the previous instructions is loading the address into the register. Hence operand access is delayed degrading the performance of pipeline.

16. How compiler is used in pipelining ?

 Answer: A compiler translates a high level language program into a sequence of machine instructions. The number of cycles required to execute program is dependent not only on the choice of instruction, but also on the order in which they appear in the program. The compiler may rearrange program instruction to achieve better performance of course, such changes must not affect of the result of the computation.

17. What is loop buffer?

 Answer: A loop buffer is a small very high speed memory. It is used to store recently prefetched instructions in sequence. If conditional branch is valid, the hardware first checks whether the branch target is within the loop buffer. If so, the next instructions are fetched from the buffer, instead of memory avoiding memory access.

18. Draw the structure of two stage instruction pipe line.

 Answer:  

Fig. 9.4.1 shows the structure of two stage instruction pipe line.

19. What would be the effect, if we increase the number of pipelining stages?

 Answer: As the number of pipeline stages increases, the probability of the pipeline being stalled also increases because more instructions are being executed concurrently. Thus, dependancies between instructions that are far apart may still cause the pipeline to stall. As the number of pipeline stages increase, the branch penalties may become more significant.

20. What is data hazard in pipelining? What are the solutions ?

 Answer: When either the source or the destination operands of an instruction are not available at the time expected in the pipeline and as a result pipeline is stalled, we say such a situation is a data hazard.

1. The easiest way to handle data hazards is to stall the pipeline.

2. The second simple hardware technique which can handle data hazard is called forwarding or register by passing.

21. What are the classification of data hazards ?

 Answer: The data hazard can be classified as,

1. RAW (read after write) hazard

2. WAW (write after write) hazard

3. WAR (write after read) hazard

22. What is the use of condition code register ?

 Answer: The conditional branch instruction checks the condition code flags to decide the flow of program execution.

23. What do you mean by out–of order execution ?

Answer: The dispatch unit dispatches the instructions in the order in which they appear in the program. But their execution may be completed in the different order because of data dependency among the instructions. Such situation is called out–of order execution.

24. What is instruction throughput ?

 Answer: The instruction throughput is the number of instructions executed per second. For sequential execution, it is given by,

P_s = R / S.

where R is a clock rate measured in clocks per second and S is the average number of steps needed to execute one machine instruction.

25. Why is branch prediction algorithm needed ?

 Answer: Branch prediction algorithm is needed to reduce the branch penalty.

26. List commonly used branch prediction techniques.

 Answer: The commonly used branch prediction techniques are :

• Predict Never Taken

• Predict Always Taken

• Predict By Opcode

• Taken/Not Taken Switch

• Branch History Table.

27. Name the two types of branch prediction strategies.

 Answer: The two types of branch prediction strategies are :

• Static branch strategy

• Dynamic branch strategy.

28. What is branch target / prediction buffer?

 Answer: The buffer in which the recent branch information is stored is called branch target buffer.

29. What is branch folding ?

 Answer: The instruction fetch unit has executed the branch instruction concurrently with the execution of other instructions. This technique is referred to as branch folding.

30. What is delayed branching ?

 Answer: A technique called delayed branching can minimize the penalty incurred as a result of conditional branch instructions. The idea is simple. The instructions in the delay slots are always fetched. Therefore, we would like to arrange for them to be fully executed whether or not the branch is taken. The objective is to be able to place useful instructions in these slots. If no useful instructions can be placed in the delay slots, these slots must be filled with NOP instructions.

31. What is meant by speculative execution?

 Answer: Speculative execution means that instructions are executed before the processor is certain that they are in the correct execution sequence. Hence, care must be taken that no processor registers or memory locations are updated until it is confirmed that these instructions should indeed be executed. If the branch decision indicates otherwise, the instructions and all their associated data in the execution units must be purged, and the correct instructions fetched and executed.

32. What is called static and dynamic branch prediction ?

OR

Differentiate between the static and dynamic techniques.

 Answer: The branch prediction decision is always the same every time a given instruction is executed. Any approach that has this characteristic is called static branch prediction. Another approach in which the prediction decision may change depending on execution history is called dynamic branch prediction.

33. What is the role of cache in pipelining?

 Answer: Each pipeline stage is expected to complete in one clock cycle. The clock period should be long enough to let the slowest pipeline stage to complete. Faster stages have to wait for the slowest one to complete. Since main memory is very slow compared to the execution, if each instruction needs to be fetched from main memory, pipeline is almost useless. The cache memory reduces the memory access time and makes pipelining useful.