IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.
M.C.A 2 All right are reserved with CU-IDOL PARALLEL AND DISTRIBUTED COMPUTING Course Code: MCA635 Semester: Third SLM Unit : 2 e-Lesson: 2 www.cuidol.in Unit-2 (MCA635)
Pipeline Processing 33 OBJECTIVES INTRODUCTION Student will be able to : In this unit we are going to learn about the Define Pipeline Performance Pipeline Processing . Explain Arithmetic Pipelines Under this unit you will also understand the Describe Pipelined instruction processing pipelined instruction processing. Explain Pipeline stage design This Unit will also make us to understand the Elaborate Dynamic instruction scheduling explanation and description of Pipeline stage Design. Describe Pipeline stage design Unit-2 (MCA635) INASllTITriUgThEt aOrFeDreISsTeArNveCdE AwNitDh OCNUL-IIDNOE LLEARNING www.cuidol.in
TOPICS TO BE COVERED 4 > Introduction to Pipeline Processing > Pipeline Performance > Arithmetic Pipelines > Pipelined Instruction Processing > Pipeline Stage Design > Hazards > Dynamic Instruction Scheduling www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
WHAT IS PIPELINING? 5 Pipelining is the process of accumulating instruction from the processor through a pipeline. It allows storing and executing instructions in an orderly process. It is also known as pipeline processing. Pipelining is a technique where multiple instructions are overlapped during execution. Pipeline is divided into stages and these stages are connected with one another to form a pipe like structure. Instructions enter from one end and exit from another end. Pipelining increases the overall instruction throughput. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
WHAT IS PIPELINING? 6 www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
WHAT IS 7 PIPELINING? • In pipeline system, each segment consists of an input register followed by a combinational circuit. The register is used to hold data and combinational circuit performs operations on it. The output of combinational circuit is applied to the input register of the next segment. • Pipeline system is like the modern day assembly line setup in factories. For example in a car manufacturing industry, huge assembly lines are setup and at each point, there are robotic arms to perform a certain task, and then the car moves on ahead to the next arm. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
WORKING OF PIPELINING? 8 • Pipelining organizes the execution of the multiple instructions simultaneously. Pipelining improves the throughput of the system. • In pipelining the instruction is divided into the subtasks. Each subtask performs the dedicated task. • The instruction is divided into 5 subtasks: 1. Instruction fetch 2. Instruction decode 3. Operand fetch 4. Instruction execution 5. Operand store www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
WORKING OF PIPELINING? 9 • In the first subtask, the instruction is fetched. • The fetched instruction is decoded in the second stage. • In the third stage, the operands of the instruction are fetched. • In the fourth, arithmetic and logical operation are performed on the operands to execute the instruction. • In the fifth stage, the result is stored in memory. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
WORKING OF PIPELINING? 10 www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
WORKING OF PIPELINING? 11 • The first instruction gets completed in 5 clock cycle. After the completion of first instruction, in every new clock cycle, a new instruction completes its execution. • Observe that when the Instruction fetch operation of the first instruction is completed in the next clock cycle the instruction fetch of second instruction gets started. • This way the hardware never sits idle it is always busy in performing some or other operation. • But, no two instructions can execute their same stage at the same clock cycle. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
TYPES OF PIPELINING? 12 1. Arithmetic Pipelining: It is designed to perform high-speed floating-point addition, multiplication and division. Here, the multiple arithmetic logic units are built in the system to perform the parallel arithmetic computation in various data format. 2. Instruction Pipelining: Here, the number of instruction are pipelined and the execution of current instruction is overlapped by the execution of the subsequent instruction. It is also called instruction lookahead. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
TYPES OF PIPELINING? 13 3. Processor Pipelining: Here, the processors are pipelined to process the same data stream. The data stream is processed by the first processor and the result is stored in the memory block. The result in the memory block is accessed by the second processor. The second processor reprocesses the result obtained by the first processor and the passes the refined result to the third processor and so on. 4. Unifunction Vs. Multifunction Pipelining: The pipeline performing the precise function every time is unifunctional pipeline. On the other hand, the pipeline performing multiple functions at a different time or multiple functions at the same time is multifunction pipeline. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
TYPES OF PIPELINING? 14 5. Static vs Dynamic Pipelining: • The static pipeline performs a fixed-function each time. The static pipeline is unifunctional. The static pipeline executes the same type of instructions continuously. Frequent change in the type of instruction may vary the performance of the pipelining. • Dynamic pipeline performs several functions simultaneously. It is a multifunction pipelining. 6. Scalar vs Vector Pipelining: Scalar pipelining processes the instructions with scalar operands. The vector pipeline processes the instruction with vector operands. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINING CONFLICTS 15 There are some factors that cause the pipeline to deviate its normal performance. Some of these factors are given below: 1. Timing Variations: All stages cannot take same amount of time. This problem generally occurs in instruction processing where different instructions have different operand requirements and thus different processing time. 2. Data Hazards: When several instructions are in partial execution, and if they reference same data then the problem arises. We must ensure that next instruction does not attempt to access data before the current instruction, because this will lead to incorrect results. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINING CONFLICTS 16 3. Branching: In order to fetch and execute the next instruction, we must know what that instruction is. If the present instruction is a conditional branch, and its result will lead us to the next instruction, then the next instruction may not be known until the current one is processed. 4. Interrupts: Interrupts set unwanted instruction into the instruction stream. Interrupts effect the execution of instruction. 5. Data Dependency: It arises when an instruction depends upon the result of a previous instruction but this result is not yet available. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
ADVANTAGES OF PIPELINING 17 • The cycle time of the processor is reduced. • It increases the throughput of the system • It makes the system reliable. • Instruction throughput increases. • Increase in the number of pipeline stages increases the number of instructions executed simultaneously. • Faster ALU can be designed when pipelining is used. • Pipelined CPU’s works at higher clock frequencies than the RAM. • Pipelining increases the overall performance of the CPU. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
DISADVANTAGES OF 18 PIPELINING • Designing of the pipelined processor is complex. • Instruction latency increases in pipelined processors. • The throughput of a pipelined processor is difficult to predict. • The longer the pipeline, worse the problem of hazard for branch instructions. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE PERFORMANCE 19 The following parameters serve as criterion to estimate the performance of pipelined execution: • Speed Up • Efficiency • Throughput www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE PERFORMANCE 20 Speed Up: It gives an idea of “how much faster” the pipelined execution is as compared to non- pipelined execution. • It is calculated as- www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE PERFORMANCE 21 Efficiency: The efficiency of pipelined execution is calculated as: www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE 22 PERFORMANCE Throughput: Throughput is defined as number of instructions executed per unit time. It is calculated as: www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
ARITHMETIC PIPELINE 23 Arithmetic Pipelines are mostly used in high-speed computers. They are used to implement floating-point operations, multiplication of fixed-point numbers, and similar computations encountered in scientific problems. let us consider an example of a pipeline unit for floating-point addition and subtraction. The inputs to the floating-point adder pipeline are two normalized floating-point binary numbers defined as: X = A * 2a = 0.9504 * 103 Y = B * 2b = 0.8200 * 102 www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
ARITHMETIC PIPELINE 24 Where A and B are two fractions that represent the mantissa and a and b are the exponents. The combined operation of floating-point addition and subtraction is divided into four segments. Each segment contains the corresponding sub-operation to be performed in the given pipeline. The sub- operations that are shown in the four segments are: • Compare the exponents by subtraction. • Align the mantissas. • Add or subtract the mantissas. • Normalize the result. Unit-2 (MCA635) All right are reserved with CU-IDOL www.cuidol.in
ARITHMETIC PIPELINE 25 www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
INSTRUCTION PIPELINE 26 • Pipeline processing can occur not only in the data stream but in the instruction stream as well. • Most of the digital computers with complex instructions require instruction pipeline to carry out operations like fetch, decode and execute instructions. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
INSTRUCTION PIPELINE 27 • In general, the computer needs to process each instruction with the following sequence of steps: • Fetch instruction from memory. • Decode the instruction. • Calculate the effective address. • Fetch the operands from memory. • Execute the instruction. • Store the result in the proper place. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
INSTRUCTION PIPELINE 28 • Segment 1:The instruction fetch segment can be implemented using first in, first out (FIFO) buffer. • Segment 2:The instruction fetched from memory is decoded in the second segment, and eventually, the effective address is calculated in a separate arithmetic circuit. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
INSTRUCTION PIPELINE 29 • Segment 3: An operand from memory is fetched in the third segment. • Segment 4: The instructions are finally executed in the last segment of the pipeline organization. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE STAGE DESIGN 30 In four stage pipelined architecture, the execution of each instruction is completed in following 4 stages: Instruction fetch (IF) Instruction decode (ID) Instruction Execute (IE) Write back (WB) www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE STAGE DESIGN 31 To implement four stage pipeline: • The hardware of the CPU is divided into four functional units. • Each functional unit performs a dedicated task. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE STAGE 32 DESIGN Stage-01: • First functional unit performs instruction fetch. • It fetches the instruction to be executed. Stage-02: • Second functional unit performs instruction decode. • It decodes the instruction to be executed. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE STAGE DESIGN 33 Stage-03: • Third functional unit performs instruction execution. • It executes the instruction. Stage-04: • Fourth functional unit performs write back. • It writes back the result so obtained after executing the instruction. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE STAGE 34 DESIGN Execution: • In pipelined architecture, • Instructions of the program execute parallely. • When one instruction goes from nth stage to (n+1)th stage, another instruction goes from (n- 1)th stage to nth stage. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINE STAGE 35 DESIGN Phase-Time Diagram: • Phase-time diagram shows the execution of instructions in the pipelined architecture. • The following diagram shows the execution of three instructions in four stage pipeline architecture. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINING HAZARDS 36 Whenever a pipeline has to stall due to some reason it is called pipeline hazards. we are having four pipelining hazards: 1. Data Dependency: Consider the following two instructions and their pipeline execution: www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINING HAZARDS 37 • In the figure above, you can see that result of the Add instruction is stored in the register R2 and we know that the final result is stored at the end of the execution of the instruction which will happen at the clock cycle t4. • But the Sub instruction need the value of the register R2 at the cycle t3. So the Sub instruction has to stall two clock cycles. If it doesn’t stall it will generate an incorrect result. Thus depending of one instruction on other instruction for data is data dependency. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINING HAZARDS 38 2. Memory Delay: When an instruction or data is required, it is first searched in the cache memory if not found then it is a cache miss. The data is further searched in the memory which may take ten or more cycles. So, for that number of cycle the pipeline has to stall and this is a memory delay hazard. The cache miss, also results in the delay of all the subsequent instructions. 3. Branch Delay: Suppose the four instructions are pipelined I1, I2, I3, I4 in a sequence. The instruction I1 is a branch instruction and its target instruction is Ik. Now, processing starts and instruction I1 is fetched, decoded and the target address is computed at the 4th stage in cycle t3. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINING HAZARDS 39 But till then the instructions I2, I3, I4 are fetched in cycle 1, 2 & 3 before the target branch address is computed. As I1 is found to be a branch instruction, the instructions I2, I3, I4 has to be discarded because the instruction Ik has to be processed next to I1. So, this delay of three cycles 1, 2, 3 is a branch delay. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
PIPELINING HAZARDS 40 Prefetching the target branch address will reduce the branch delay. Like if the target branch is identified at the decode stage then the branch delay will reduce to 1 clock cycle. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
DYNAMIC INSTRUCTION SCHEDULING 41 The order in which the instructions comprising a program are to be executed is normally assumed to be given by the order in which the instructions are held in program storage and by the sequencing control indicated by transfer and conditional transfer instructions. However a programmer, or compiler, can produce many different but equivalent versions of a program merely by making minor alterations to the sequence in which instructions are placed. Normally the actual choice among these alternative sequences will be somewhat arbitrary, though careful programming or compilation often involves an attempt to design a program whose detailed sequences are tailored to make best use of a computer's control and functional capabilities. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
DYNAMIC INSTRUCTION 42 SCHEDULING • Take, for example, a computer which initiates execution of instructions in strict sequence, without necessarily awaiting the completion of one instruction before execution of the next instruc-tion, provided that the operands of the second instruction are ready, and the necessary busses and functional units are available. In such a computer the sequence (written here for convenience in a 3- address format) www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
• R1 + R2 -> R3 DYNAMIC INSTRUCTION 43 SCHEDULING • R1 x R4 -> R5 • R6 + R2 -> R7 • R3 x R6 -> R8 • might well be preferable to • R1 + R2 -> R3 • R6 + R2 -> R7 • R1 x R4 -> R5 • R3 x R6 -> R8 • if the adder and multiplier were independent functional units. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
NON-SEQUENTIAL INSTRUCTION 44 EXECUTION • we restrict our attention to the sequencing of straight line coding comprised of instructions, the locations of whose operands and results can be determined directly from the instructions themselves, rather than needing any address computation to be performed. • The sequence in which a series of instructions have been written implies the total effect that these instructions are intended to have when executed. • Each separate instruction-contributes to this total effect by performing its operations on the contents of certain registers (accumulators, index registers, indicators, etc.) and setting its results into other registers. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
NON-SEQUENTIAL 45 INSTRUCTION EXECUTION • A dynamic scheduling technique has to insure that any instructions obeyed out of sequence do not change the contents of any registers which are to be used by any instructions whose execution has been delayed temporarily. • A simple set of rules for determining if a given-instruction can be obeyed out of sequence is as follows: (i) The required busses and functional units are available. (ii) The instruction must not use any registers which are used as result registers by instructions whose execution has been initiated but not yet completed. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
NON-SEQUENTIAL 46 INSTRUCTION EXECUTION (iii) The instruction must not use as result registers any registers which are used as operand registers by any preceding instructions which have not yet been initiated. (iv) The instruction must not use any registers (either as result or operand registers) which are used as result registers by any preceding instructions which have not yet been initiated. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
UNCONDITIONAL AND 47 CONDITIONAL BRANCHING There is one kind of branch instruction, namely the unconditional branch to an explicit instruction address, which can be handled very simply, without recourse to the sequencing matrices. The instruction is executed as soon as it has been decoded, causing the appropriate modification to the instruction counter which indicates the location from which the sequencing matrices are to replenished. The other types of branch instructions, where the branch address and/or the question of whether the branch is to be taken cannot be determined directly from the instruction, but rather depend on the contents of one or more registers, cause rows to be entered into the sequencing matrices in the usual way. Unit-2 (MCA635) All right are reserved with CU-IDOL www.cuidol.in
MULTIPLE CHOICE QUESTIONS 1. ______ have been developed specifically for pipelined systems. 48 a) Utility software c) Optimizing compilers b) Speed up utilities d) None of the mentioned 2. The pipelining process is also called as ______ a) Superscalar operation c) Von Neumann cycle b) Assembly line operation d) None of the mentioned 3. The fetch and execution cycles are interleaved with the help of ________ a) Modification in processor architecture c) Special unit b) Clock d) Control unit 4. Each stage in pipelining should be completed within ___________ cycle. a) 1 c) 3 b) 2 d) 4 Answers:1. c) 2.b) 3.b) 4.a) Unit-2 (MCA635) All right are reserved with CU-IDOL www.cuidol.in
MULTIPLE CHOICE QUESTIONS 5. If a unit completes its task before the allotted time period, then _______ 49 a) It’ll perform some other task in the remaining time b) Its time gets reallocated to a different task c) It’ll remain idle for the remaining time d) None of the mentioned 6. To increase the speed of memory access in pipelining, we make use of _______ a) Special memory locations b) Special purpose registers c) Cache d) Buffers 7. The periods of time when the unit is idle is called as _____ a) Stalls b) Bubbles c) Hazards d) Both Stalls and Bubbles Answers: 5.c) 6.c) 7.d) www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
SUMMARY 50 Pipelining is the process of accumulating instruction from the processor through a pipeline. It allows storing and executing instructions in an orderly process. It is also known as pipeline processing. Arithmetic Pipelining: It is designed to perform high-speed floating-point addition, multiplication and division. Here, the multiple arithmetic logic units are built in the system to perform the parallel arithmetic computation in various data format. Instruction Pipelining: Here, the number of instruction are pipelined and the execution of current instruction is overlapped by the execution of the subsequent instruction. It is also called instruction look ahead. PIPELINING CONFLICTS: There are some factors that cause the pipeline to deviate its normal performance: 1. Timing Variations 2. Data Hazards 3. Branching 4. Interrupts 5. Data Dependency DYNAMIC INSTRUCTION SCHEDULING: The order in which the instructions comprising a program are to be executed is normally assumed to be given by the order in which the instructions are held in program storage and by the sequencing control indicated by transfer and conditional transfer instructions. www.cuidol.in Unit-2 (MCA635) All right are reserved with CU-IDOL
Search
