Instruction pipelining - wikipedia Instruction pipelining This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. ( May 2016 ) Basic five - stage pipeline ( IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back ). In the fourth clock cycle ( the green column ), the earliest instruction is in MEM stage, and the latest instruction has not yet entered the pipeline. Instruction pipelining is a technique for implementing instruction - level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing incoming instructions into a series of sequential steps ( the eponymous `` pipeline '' ), each performed by a different processor units, and occupying different units with parts of different instructions that are then processed in parallel. It allows faster CPU throughput than would otherwise be possible at a given clock rate, but may increase latency due to the added overhead of the pipelining process itself. Contents 1 Introduction 1.1 Number of steps 1.2 Hazards 1.2. 1 Workarounds 1.2. 2 Solutions 1.3 Branches 1.4 Special situations 2 Design considerations 3 Illustrated example 3.1 Pipeline bubble 4 History 5 See also 6 Notes 7 References 8 External links Introduction Central processing units ( CPUs ) are driven by a clock. Each clock pulse need not do the same thing ; rather, logic in the CPU directs successive pulses to different places to perform a useful sequence. There are many reasons that the entire execution of a machine instruction can not happen at once ; in pipelining, effects that can not happen at the same time are made into dependent steps of the instruction. For example, if one clock pulse latches a value into a register or begins a calculation, it will take some time for the value to be stable at the outputs of the register or for the calculation to complete. As another example, reading an instruction out of a memory unit can not be done at the same time that an instruction writes a result to the same memory unit. Number of steps The number of dependent steps varies with the machine architecture. For example : The 1956 - 1961 IBM Stretch project proposed the terms Fetch, Decode, and Execute that have become common. The classic RISC pipeline comprises : Instruction fetch Instruction decode and register fetch Execute Memory access Register write back The Atmel AVR and the PIC microcontroller each have a two - stage pipeline. Many designs include pipelines as long as 7, 10 and even 20 stages ( as in the Intel Pentium 4 ). The later `` Prescott '' and `` Cedar Mill '' Netburst cores from Intel, used in the last Pentium 4 models and their Pentium D and Xeon derivatives, have a long 31 - stage pipeline. The Xelerated X10q Network Processor has a pipeline more than a thousand stages long, although in this case 200 of these stages represent independent CPUs with individually programmed instructions. The remaining stages are used to coordinate accesses to memory and on - chip function units. As the pipeline is made `` deeper '' ( with a greater number of dependent steps ), a given step can be implemented with simpler circuitry, which may let the processor clock run faster. Such pipelines may be called superpipelines. A processor is said to be fully pipelined if it can fetch an instruction on every cycle. Thus, if some instructions or conditions require delays that inhibit fetching new instructions, the processor is not fully pipelined. Hazards Main article : Hazard ( computer architecture ) The model of sequential execution assumes that each instruction completes before the next one begins ; this assumption is not true on a pipelined processor. A situation where the expected result is problematic is known as a hazard. Imagine the following two register instructions to a hypothetical processor : 1 : add 1 to R5 2 : copy R5 to R6 If the processor has the 5 steps listed in the initial illustration, instruction 1 would be fetched at time t and its execution would be complete at t. Instruction 2 would be fetched at t and would be complete at t. The first instruction might deposit the incremented number into R5 as its fifth step ( register write back ) at t. But the second instruction might get the number from R5 ( to copy to R6 ) in its second step ( instruction decode and register fetch ) at time t. It seems that the first instruction would not have incremented the value by then. The above code invokes a hazard. Writing computer programs in a compiled language might not raise these concerns, as the compiler could be designed to generate machine code that avoids hazards. Workarounds In some early DSP and RISC processors, the documentation advises programmers to avoid such dependencies in adjacent and nearly adjacent instructions ( called delay slots ), or declares that the second instruction uses an old value rather than the desired value ( in the example above, the processor might counter-intuitively copy the unincremented value ), or declares that the value it uses is undefined. The programmer may have unrelated work that the processor can do in the meantime ; or, to ensure correct results, the programmer may insert NOPs into the code, partly negating the advantages of pipelining. Solutions Pipelined processors commonly use three techniques to work as expected when the programmer assumes that each instruction completes before the next one begins : Processors that can compute the presence of a hazard may stall, delaying processing of the second instruction ( and subsequent instructions ) until the values it requires as input are ready. This creates a bubble in the pipeline ( see below ), also partly negating the advantages of pipelining. Some processors can not only compute the presence of a hazard but can compensate by having additional data paths that provide needed inputs to a computation step before a subsequent instruction would otherwise compute them, an attribute called operand forwarding. Some processors can determine that instructions other than the next sequential one are not dependent on the current ones and can be executed without hazards. Such processors may perform out - of - order execution. Branches A branch out of the normal instruction sequence often involves a hazard. Unless the processor can give effect to the branch in a single time cycle, the pipeline will continue fetching instructions sequentially. Such instructions can not be allowed to take effect because the programmer has diverted control to another part of the program. A conditional branch is even more problematic. The processor may or may not branch, depending on a calculation that has not yet occurred. Various processors may stall, may attempt branch prediction, and may be able to begin to execute two different program sequences ( eager execution ), both assuming the branch is and is not taken, discarding all work that pertains to the incorrect guess. A processor with an implementation of branch prediction that usually makes correct predictions can minimize the performance penalty from branching. However, if branches are predicted poorly, it may create more work for the processor, such as flushing from the pipeline the incorrect code path that has begun execution before resuming execution at the correct location. Programs written for a pipelined processor deliberately avoid branching to minimize possible loss of speed. For example, the programmer can handle the usual case with sequential execution and branch only on detecting unusual cases. Using programs such as gcov to analyze code coverage lets the programmer measure how often particular branches are actually executed and gain insight with which to optimize the code. Special situations Self - modifying programs The technique of self - modifying code can be problematic on a pipelined processor. In this technique, one of the effects of a program is to modify its own upcoming instructions. If the processor has an instruction cache, the original instruction may already have been copied into a prefetch input queue and the modification will not take effect. Uninterruptible instructions An instruction may be uninterruptible to ensure its atomicity, such as when it swaps two items. A sequential processor permits interrupts between instructions, but a pipelining processor overlaps instructions, so executing an uninterruptible instruction renders portions of ordinary instructions uninterruptible too. The Cyrix coma bug would hang a single - core system using an infinite loop in which an uninterruptible instruction was always in the pipeline. Design considerations Speed Pipelining keeps all portions of the processor occupied and increases the amount of useful work the processor can do in a given time. Pipelining typically reduces the processor 's cycle time and increases the throughput of instructions. The speed advantage is diminished to the extent that execution encounters hazards that require execution to slow below its ideal rate. A non-pipelined processor executes only a single instruction at a time. The start of the next instruction is delayed not based on hazards but unconditionally. A pipelined processor 's need to organize all its work into modular steps may require the duplication of registers that increases the latency of some instructions. Economy By making each dependent step simpler, pipelining can enable complex operations more economically than adding complex circuitry, such as for numerical calculations. However, a processor that declines to pursue increased speed with pipelining may be simpler and cheaper to manufacture. Predictability Compared to environments where the programmer needs to avoid or work around hazards, use of a non-pipelined processor may make it easier to program and to train programmers. The non-pipelined processor also makes it easier to predict the exact timing of a given sequence of instructions. Illustrated example Generic 4 - stage pipeline ; the colored boxes represent instructions independent of each other To the right is a generic pipeline with four stages : fetch, decode, execute and write - back. The top gray box is the list of instructions waiting to be executed, the bottom gray box is the list of instructions that have had their execution completed, and the middle white box is the pipeline. The execution is as follows : Time Execution 0 Four instructions are waiting to be executed The green instruction is fetched from memory The green instruction is decoded The purple instruction is fetched from memory The green instruction is executed ( actual operation is performed ) The purple instruction is decoded The blue instruction is fetched The green instruction 's results are written back to the register file or memory The purple instruction is executed The blue instruction is decoded The red instruction is fetched 5 The execution of green instruction is completed The purple instruction is written back The blue instruction is executed The red instruction is decoded 6 The execution of purple instruction is completed The blue instruction is written back The red instruction is executed 7 The execution of blue instruction is completed The red instruction is written back 8 The execution of red instruction is completed 9 The execution of all four instructions is completed Pipeline bubble Main article : Bubble ( computing ) A bubble in cycle 3 delays execution. A pipelined processor may deal with hazards by stalling and creating a bubble in the pipeline, resulting in one or more cycles in which nothing useful happens. In the illustration at right, in cycle 3, the processor can not decode the purple instruction, perhaps because the processor determines that decoding depends on results produced by the execution of the green instruction. The green instruction can proceed to the Execute stage and then to the Write - back stage as scheduled, but the purple instruction is stalled for one cycle at the Fetch stage. The blue instruction, which was due to be fetched during cycle 3, is stalled for one cycle, as is the red instruction after it. Because of the bubble ( the blue ovals in the illustration ), the processor 's Decode circuitry is idle during cycle 3. Its Execute circuitry is idle during cycle 4 and its Write - back circuitry is idle during cycle 5. When the bubble moves out of the pipeline ( at cycle 6 ), normal execution resumes. But everything now is one cycle late. It will take 8 cycles ( cycle 1 through 8 ) rather than 7 to completely execute the four instructions shown in colors. History Seminal uses of pipelining were in the ILLIAC II project and the IBM Stretch project, though a simple version was used earlier in the Z1 in 1939 and the Z3 in 1941. Pipelining began in earnest in the late 1970s in supercomputers such as vector processors and array processors. One of the early supercomputers was the Cyber series built by Control Data Corporation. Its main architect, Seymour Cray, later headed Cray Research. Cray developed the XMP line of supercomputers, using pipelining for both multiply and add / subtract functions. Later, Star Technologies added parallelism ( several pipelined functions working in parallel ), developed by Roger Chen. In 1984, Star Technologies added the pipelined divide circuit developed by James Bradley. By the mid 1980s, supercomputing was used by many different companies around the world. Today, pipelining and most of the above innovations are implemented by the instruction unit of most microprocessors. See also Wait state Classic RISC pipeline Notes Jump up ^ Early pipelined processors without any of these heuristics, such as the PA - RISC processor of Hewlett - Packard, dealt with hazards by simply warning the programmer ; in this case, that one or more instructions following the branch would be executed whether or not the branch was taken. This could be useful ; for instance, after computing a number in a register, a conditional branch could be followed by loading into the register a value more useful to subsequent computations in both the branch and the non-branch case. References Jump up ^ Glaskowsky, Peter ( Aug 18, 2003 ). `` Xelerated 's Xtraordinary NPU -- World 's First 40Gb / s Packet Processor Has 200 CPUs ''. Microprocessor Report. 18 ( 8 ) : 12 -- 14. Retrieved 20 March 2017. Jump up ^ John Paul Shen, Mikko H. Lipasti ( 2004 ). Modern Processor Design. McGraw - Hill Professional. Jump up ^ Sunggu Lee ( 2000 ). Design of Computers and Other Complex Digital Devices. Prentice Hall. Jump up ^ `` CMSC 411 Lecture 19, Pipelining Data Forwarding ''. Csee.umbc.edu. Retrieved 2014 - 02 - 08. Jump up ^ `` High performance computing, Notes of class 11 ''. hpc.serc.iisc.ernet.in. September 2000. Retrieved 2014 - 02 - 08. Jump up ^ Raul Rojas ( 1997 ). `` Konrad Zuse 's Legacy : The Architecture of the Z1 and Z3 ''. IEEE Annals of the History of Computing. 19 ( 2 ). External links Wikimedia Commons has media related to Pipeline ( computer hardware ). Wikibooks has a book on the topic of : Microprocessor Design / Pipelined Processors Branch Prediction in the Pentium Family ( Archive.org copy ) ArsTechnica article on pipelining Counterflow Pipeline Processor Architecture CPU technologies Architecture Turing machine Post -- Turing machine Universal Turing machine Quantum Turing machine Belt machine Stack machine Register machine Counter machine Pointer machine Random access machine Random access stored program machine Finite - state machine Queue automaton Von Neumann Harvard ( modified ) Dataflow TTA Cellular Artificial neural network Machine learning Deep learning Neural processing unit ( NPU ) Convolutional neural network Load / store architecture Register memory architecture Register register architecture Endianness FIFO Zero - copy NUMA HUMA HSA Heterogeneous computing Parallel computing Amorphous computing Reconfigurable computing Cognitive computing DNA computing Peptide computing Chemical computing Organic computing Wetware computer Quantum computing Neuromorphic computing Optical computing Reversible computing Unconventional computing Hypercomputation Ternary computer Symmetric multiprocessing ( SMP ) Asymmetric multiprocessing ( AMP ) Cache hierarchy Memory hierarchy ISA types ASIP CISC RISC EDGE ( TRIPS ) VLIW ( EPIC ) MISC OISC NISC ZISC Comparison ISAs x86 z / Architecture ARM MIPS Power Architecture ( PowerPC ) SPARC VISC Mill Itanium ( IA - 64 ) Alpha Prism SuperH Clipper VAX Unicore PA - RISC MicroBlaze Word size 1 - bit 2 - bit 4 - bit 8 - bit 9 - bit 10 - bit 12 - bit 15 - bit 16 - bit 18 - bit 22 - bit 24 - bit 25 - bit 26 - bit 27 - bit 31 - bit 32 - bit 33 - bit 34 - bit 36 - bit 39 - bit 40 - bit 48 - bit 50 - bit 60 - bit 64 - bit 128 - bit 256 - bit 512 - bit Variable Execution Instruction pipelining Bubble Operand forwarding Out - of - order execution Register renaming Speculative execution Branch predictor Memory dependence prediction Hazards Parallel level Bit Bit - serial Word Instruction Pipelining Scalar Superscalar Task Thread Process Data Vector Memory Multithreading Temporal Simultaneous ( SMT ) ( Hyper - threading ) Speculative ( SpMT ) Preemptive Cooperative Clustered Multi-Thread ( CMT ) Hardware scout Flynn 's taxonomy SISD SIMD ( SWAR ) SIMT MISD MIMD SPMD Addressing mode CPU performance Instructions per second ( IPS ) Instructions per clock ( IPC ) Cycles per instruction ( CPI ) Floating - point operations per second ( FLOPS ) Transactions per second ( TPS ) SUPS Performance per watt Orders of magnitude ( computing ) Cache performance measurement and metric Core count Single - core processor Multi-core processor Manycore processor Types Central processing unit ( CPU ) GPGPU AI accelerator Vision processing unit ( VPU ) Vector processor Barrel processor Stream processor Digital signal processor ( DSP ) I / O processor / DMA controller Network processor Baseband processor Physics processing unit ( PPU ) Coprocessor Secure cryptoprocessor ASIC FPGA FPOA CPLD Microcontroller Microprocessor Mobile processor Notebook processor Ultra-low - voltage processor Multi-core processor Manycore processor Tile processor Multi-chip module ( MCM ) Chip stack multi-chip modules System on a chip ( SoC ) Network on a chip ( NoC ) Multiprocessor system - on - chip ( MPSoC ) Programmable System - on - Chip ( PSoC ) Components Execution unit ( EU ) Arithmetic logic unit ( ALU ) Address generation unit ( AGU ) Floating - point unit ( FPU ) Load - store unit ( LSU ) Fixed - point unit ( FXU ) Vector unit ( VU ) Branch predictor Branch execution unit ( BEU ) Instruction Decoder Instruction Scheduler Instruction Fetch Unit Instruction Dispatch Unit Instruction Sequencing Unit Unified Reservation Station Barrel shifter Uncore Sum addressed decoder ( SAD ) Front - side bus Back - side bus Northbridge ( computing ) Southbridge ( computing ) Adder ( electronics ) Binary multiplier Binary decoder Address decoder Multiplexer Demultiplexer Registers Cache Memory management unit ( MMU ) Input -- output memory management unit ( IOMMU ) Integrated Memory Controller ( IMC ) Power Management Unit ( PMU ) Translation lookaside buffer ( TLB ) Stack engine Register file Processor register Hardware register Memory buffer register ( MBR ) Program counter Microcode ROM Datapath Control unit Instruction unit Re-order buffer Data buffer Write buffer Coprocessor Electronic switch Electronic circuit Integrated circuit Three - dimensional integrated circuit Boolean circuit Digital circuit Analog circuit Mixed - signal integrated circuit Power management integrated circuit Quantum circuit Logic gate Combinational logic Sequential logic Emitter - coupled logic ( ECL ) Transistor -- transistor logic ( TTL ) Glue logic Quantum gate Gate array Counter ( digital ) Bus ( computing ) Semiconductor device Clock rate CPU multiplier Vision chip Memristor Power management APM ACPI Dynamic frequency scaling Dynamic voltage scaling Clock gating Hardware security Non-executable memory ( NX bit ) Bounds checking ( Intel MPX ) Intel Secure Key Hardware restriction ( firmware ) Software Guard Extensions ( Intel SGX ) Trusted Execution Technology OmniShield Trusted Platform Module ( TPM ) Secure cryptoprocessor Hardware security module Hengzhi chip Related History of general - purpose CPUs Retrieved from `` https://en.wikipedia.org/w/index.php?title=Instruction_pipelining&oldid=799939666 '' Categories : Instruction processing Hidden categories : Articles needing additional references from May 2016 All articles needing additional references Talk Contents About Wikipedia Čeština Deutsch Ελληνικά Español فارسی Français 한국어 Hrvatski Italiano Монгол Nederlands 日本 語 Norsk Polski Português Русский Simple English Svenska Türkçe Українська 中文 Edit links This page was last edited on 10 September 2017, at 18 : 36. Text is available under the Creative Commons Attribution - ShareAlike License ; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia ® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. About Wikipedia

Question: in what way do instruction pipeline aid in parallel processing
Answer: attempts to keep every part of the processor busy with some instruction by dividing incoming instructions into a series of sequential steps (the eponymous "pipeline"), each performed by a different processor units