HAZARDS, that prevent the next instruction in the instruction stream from being executing during its designated clock cycle. Hazards reduce the performance from the ideal speedup gained by pipelining.
There are three classes of hazards:
Structural Hazards:
They arise from resource conflicts when the hardware cannot support all possible combinations of instructions in simultaneous overlapped execution.
Data Hazards:
They arise when an instruction depends on the result of a previous instruction in a way that is exposed by the overlapping of instructions in the pipeline.
Control Hazards:
They arise from the pipelining of branches and other instructions that change the PC
Monday, July 30, 2007
Clarify my doubt friends..................
Can anyone explain me Control Hazards with a simple example???????????I could not understand it
Advantages and Disadvantages of Pipelining
Advantages and Disadvantages
Pipelining does not help in all cases. There are several disadvantages associated. An instruction pipeline is said to be fully pipelined if it can accept a new instruction every clock cycles. A pipeline that is not fully pipelined has wait cycles that delay the progress of the pipeline.
Advantages of pipelining:
The cycle time of the processor is reduced, thus increasing instruction bandwidth in most cases.
Advantages of not pipelining:
The processor executes only a single instruction at a time. This prevents branch delays (in effect, every branch is delayed) and problems with serial instructions being executed concurrently. Consequently the design is simpler and cheaper to manufacture.
The instruction latency in a non-pipelined processor is slightly lower than in a pipelined equivalent. This is due to the fact that extra flip flops must be added to the data path of a pipelined processor.
A non-pipelined processor will have a stable instruction bandwidth. The performance of a pipelined processor is much harder to predict and may vary more widely between different programs.
Pipelining does not help in all cases. There are several disadvantages associated. An instruction pipeline is said to be fully pipelined if it can accept a new instruction every clock cycles. A pipeline that is not fully pipelined has wait cycles that delay the progress of the pipeline.
Advantages of pipelining:
The cycle time of the processor is reduced, thus increasing instruction bandwidth in most cases.
Advantages of not pipelining:
The processor executes only a single instruction at a time. This prevents branch delays (in effect, every branch is delayed) and problems with serial instructions being executed concurrently. Consequently the design is simpler and cheaper to manufacture.
The instruction latency in a non-pipelined processor is slightly lower than in a pipelined equivalent. This is due to the fact that extra flip flops must be added to the data path of a pipelined processor.
A non-pipelined processor will have a stable instruction bandwidth. The performance of a pipelined processor is much harder to predict and may vary more widely between different programs.
Structural Hazards
A "hazard'' is a circumstance that arises because of pipelining, that either will make implementing an instruction difficult or will cause errors in execution.
There are three classes of hazards:
1.Structural Hazards:
When a machine is pipelined, the overlapped execution of instructions requires pipelining of functional units and duplication of resources to allow all posible combinations of instructions in the pipeline. If some combination of instructions cannot be accommodated because of a resource conflict, the machine is said to have a structural hazard.
There are three classes of hazards:
1.Structural Hazards:
When a machine is pipelined, the overlapped execution of instructions requires pipelining of functional units and duplication of resources to allow all posible combinations of instructions in the pipeline. If some combination of instructions cannot be accommodated because of a resource conflict, the machine is said to have a structural hazard.
Common instances of structural hazards arise when :
- Some functional unit is not fully pipelined
- Some resource has not been duplicated enough to allow all combinations of instructions in the pipeline to execute.
Example: A machine may have only one register-file write port, but in some cases the pipeline might want to perform two writes in a clock cycle.
2.Data Hazards:
Data hazards occur when the pipeline changes the order of read/write accesses to operands so that the order differs from the order seen by sequentially executing instructions on the unpipelined machine.
Example:
ADD R1, R2, R3:Take for an instance the result of addition is placed in R1 at the end of fourth clock cycle,
SUB R4, R5, R1:Here R1's value is needed in the first clock cycle itself,This is the data hazard,as an instruction depends on the result of a previous instruction.
3.Control Hazards:
They arise from the pipelining of branches and other instructions that change the PC.
hazards in pipeline
Pipeline Hazards
There are situations, called hazards, that prevent the next instruction in the instruction stream from being executing during its designated clock cycle. Hazards reduce the performance from the ideal speedup gained by pipelining.
There are three classes of hazards:
Structural Hazards. They arise from resource conflicts when the hardware cannot support all possible combinations of instructions in simultaneous overlapped execution.
When a machine is pipelined, the overlapped execution of instructions requires pipelining of functional units and duplication of resources to allow all posible combinations of instructions in the pipeline. If some combination of instructions cannot be accommodated because of a resource conflict, the machine is said to have a structural hazard.
Common instances of structural hazards arise when
Some functional unit is not fully pipelined. Then a sequence of instructions using that unpipelined unit cannot proceed at the rate of one per clock cycle
Some resource has not been duplicated enough to allow all combinations of instructions in the pipeline to execute.
Example1: a machine may have only one register-file write port, but in some cases the pipeline might want to perform two writes in a clock cycle
Data Hazards. They arise when an instruction depends on the result of a previous instruction in a way that is exposed by the overlapping of instructions in the pipeline.
A major effect of pipelining is to change the relative timing of instructions by overlapping their execution. This introduces data and control hazards. Data hazards occur when the pipeline changes the order of read/write accesses to operands so that the order differs from the order seen by sequentially executing instructions on the unpipelined machine.
Control Hazards.They arise from the pipelining of branches and other instructions that change the PC.
There are situations, called hazards, that prevent the next instruction in the instruction stream from being executing during its designated clock cycle. Hazards reduce the performance from the ideal speedup gained by pipelining.
There are three classes of hazards:
Structural Hazards. They arise from resource conflicts when the hardware cannot support all possible combinations of instructions in simultaneous overlapped execution.
When a machine is pipelined, the overlapped execution of instructions requires pipelining of functional units and duplication of resources to allow all posible combinations of instructions in the pipeline. If some combination of instructions cannot be accommodated because of a resource conflict, the machine is said to have a structural hazard.
Common instances of structural hazards arise when
Some functional unit is not fully pipelined. Then a sequence of instructions using that unpipelined unit cannot proceed at the rate of one per clock cycle
Some resource has not been duplicated enough to allow all combinations of instructions in the pipeline to execute.
Example1: a machine may have only one register-file write port, but in some cases the pipeline might want to perform two writes in a clock cycle
Data Hazards. They arise when an instruction depends on the result of a previous instruction in a way that is exposed by the overlapping of instructions in the pipeline.
A major effect of pipelining is to change the relative timing of instructions by overlapping their execution. This introduces data and control hazards. Data hazards occur when the pipeline changes the order of read/write accesses to operands so that the order differs from the order seen by sequentially executing instructions on the unpipelined machine.
Control Hazards.They arise from the pipelining of branches and other instructions that change the PC.
Eliminating Hazards
In computer architecture, a hazard is a potential problem that can happen in a pipelined processor. There are typically three types of hazards: data hazards, branching hazards (control hazards), and structural hazards.
Instructions in a pipelined processor are performed in several stages, so that at any given time several instructions are being executed, and instructions may not be completed in the desired order.
A hazard occurs when two or more of these simultaneous (possibly out of order) instructions conflict.
Contents[hide]
1 Data hazards
2 Structural hazards
3 Branch (control) hazards
4 Eliminating hazards
4.1 Eliminating data hazards
4.2 Eliminating branch hazards
5 See also
//
Data hazards
Main article: Data dependency
Data hazards occur when data is modified. Ignoring potential data hazards can result in race conditions (sometimes known as race hazards). There are three situations a data hazard can occur in:
Read after Write (RAW) or True dependency: An operand is modified and read soon after. Because the first instruction may not have finished writing to the operand, the second instruction may use incorrect data.
Write after Read (WAR) or Anti dependency: Read an operand and write soon after to that same operand. Because the write may have finished before the read, the read instruction may incorrectly get the new written value.
Write after Write (WAW) or Output dependency: Two instructions that write to the same operand are performed. The first one issued may finish second, and therefore leave the operand with an incorrect data value.
The operands involved in data hazards can reside in memory or in a register.
Structural hazards
A structural hazard occurs when a part of the processor's hardware is needed by two or more instructions at the same time. A structural hazard might occur, for instance, if a program were to execute a branch instruction followed by a computation instruction. Because they are executed in parallel, and because branching is typically slow (requiring a comparison, program counter-related computation, and writing to registers), it is quite possible (depending on architecture) that the computation instruction and the branch instruction will both require the ALU (arithmetic logic unit) at the same time.
Branch (control) hazards
Branching hazards (also known as control hazards) occur when the processor is told to branch - i.e., if a certain condition is true, then jump from one part of the instruction stream to another - not necessarily to the next instruction sequentially. In such a case, the processor cannot tell in advance whether it should process the next instruction (when it may instead have to move to a distant instruction).
This can result in the processor doing unwanted actions.
Eliminating hazards
There are several established techniques for either preventing hazards from occurring, or working around them if they do.
Bubbling the Pipeline
Bubbling the pipeline (a technique also known as a pipeline break or pipeline stall) is a method for preventing data, structural, and branch hazards from occurring. As instructions are fetched, control logic determines whether a hazard could/will occur. If this is true, then the control logic inserts NOPs into the pipeline. Thus, before the next instruction (which would cause the hazard) is executed, the previous one will have had sufficient time to complete and prevent the hazard. If the number of NOPs is equal to the number of stages in the pipeline, the processor has been cleared of all instructions and can proceed free from hazards. This is called flushing the pipeline. All forms of stalling introduce a delay before the processor can resume execution.
Eliminating data hazards
Forwarding
NOTE: In the following examples, computed values are in bold, while Register numbers are not.
Forwarding involves feeding output data into a previous stage of the pipeline. For instance, let's say we want to write the value 3 to register 1, (which already contains a 6), and then add 7 to register 1 and store the result in register 2, i.e.:
Instruction 0: Register 1 = 6
Instruction 1: Register 1 = 3
Instruction 2: Register 2 = Register 1 + 7 = 10
Following execution, register 2 should contain the value 10. However, if Instruction 1 (write 3 to register 1) does not completely exit the pipeline before the second instruction starts execution, it means that Register 1 does not contain the value 3 when Instruction 2 performs its addition. In such an event, Instruction 2 adds 7 to the old value of register 1 (6), and so register 2 would contain 13 instead, i.e:
Instruction 0: Register 1 = 6
Instruction 1: Register 1 = 3
Instruction 2: Register 2 = Register 1 + 7 = 13
This error occurs because Instruction 2 reads Register 1 before Instruction 1 has committed/stored the result of its write operation to Register 1. So when Instruction 2 is reading the contents of Register 1, register 1 still contains 6, not 3.
Forwarding (described below) helps correct such errors by depending on the fact that the output of Instruction 1 (which is 3) can be used by subsequent instructions before the value 3 is committed to/stored in Register 1.
Forwarding is implemented by feeding back the output of an instruction into the previous stage(s) of the pipeline as soon as the output of that instruction is available. Forwarding applied to our example means that we do not wait to commit/store the output of Instruction 1 in Register 1 (in this example, the output is 3) before making that output available to the subsequent instruction (in this case, Instruction 2). The effect is that Instruction 2 uses the correct (the more recent) value of Register 1: the commit/store was made immediately and not pipelined.
With forwarding enabled, the ID/EX stage of the pipeline now has two inputs - the value read from the register specified (in this example, the value 6 from Register 1), and the new value of Register 1 (in this example, this value is 3) which is sent from the next stage (EX/MEM). Additional control logic is used to determine which input to use.
See feed-forward.
Register renaming
Instructions in a pipelined processor are performed in several stages, so that at any given time several instructions are being executed, and instructions may not be completed in the desired order.
A hazard occurs when two or more of these simultaneous (possibly out of order) instructions conflict.
Contents[hide]
1 Data hazards
2 Structural hazards
3 Branch (control) hazards
4 Eliminating hazards
4.1 Eliminating data hazards
4.2 Eliminating branch hazards
5 See also
//
Data hazards
Main article: Data dependency
Data hazards occur when data is modified. Ignoring potential data hazards can result in race conditions (sometimes known as race hazards). There are three situations a data hazard can occur in:
Read after Write (RAW) or True dependency: An operand is modified and read soon after. Because the first instruction may not have finished writing to the operand, the second instruction may use incorrect data.
Write after Read (WAR) or Anti dependency: Read an operand and write soon after to that same operand. Because the write may have finished before the read, the read instruction may incorrectly get the new written value.
Write after Write (WAW) or Output dependency: Two instructions that write to the same operand are performed. The first one issued may finish second, and therefore leave the operand with an incorrect data value.
The operands involved in data hazards can reside in memory or in a register.
Structural hazards
A structural hazard occurs when a part of the processor's hardware is needed by two or more instructions at the same time. A structural hazard might occur, for instance, if a program were to execute a branch instruction followed by a computation instruction. Because they are executed in parallel, and because branching is typically slow (requiring a comparison, program counter-related computation, and writing to registers), it is quite possible (depending on architecture) that the computation instruction and the branch instruction will both require the ALU (arithmetic logic unit) at the same time.
Branch (control) hazards
Branching hazards (also known as control hazards) occur when the processor is told to branch - i.e., if a certain condition is true, then jump from one part of the instruction stream to another - not necessarily to the next instruction sequentially. In such a case, the processor cannot tell in advance whether it should process the next instruction (when it may instead have to move to a distant instruction).
This can result in the processor doing unwanted actions.
Eliminating hazards
There are several established techniques for either preventing hazards from occurring, or working around them if they do.
Bubbling the Pipeline
Bubbling the pipeline (a technique also known as a pipeline break or pipeline stall) is a method for preventing data, structural, and branch hazards from occurring. As instructions are fetched, control logic determines whether a hazard could/will occur. If this is true, then the control logic inserts NOPs into the pipeline. Thus, before the next instruction (which would cause the hazard) is executed, the previous one will have had sufficient time to complete and prevent the hazard. If the number of NOPs is equal to the number of stages in the pipeline, the processor has been cleared of all instructions and can proceed free from hazards. This is called flushing the pipeline. All forms of stalling introduce a delay before the processor can resume execution.
Eliminating data hazards
Forwarding
NOTE: In the following examples, computed values are in bold, while Register numbers are not.
Forwarding involves feeding output data into a previous stage of the pipeline. For instance, let's say we want to write the value 3 to register 1, (which already contains a 6), and then add 7 to register 1 and store the result in register 2, i.e.:
Instruction 0: Register 1 = 6
Instruction 1: Register 1 = 3
Instruction 2: Register 2 = Register 1 + 7 = 10
Following execution, register 2 should contain the value 10. However, if Instruction 1 (write 3 to register 1) does not completely exit the pipeline before the second instruction starts execution, it means that Register 1 does not contain the value 3 when Instruction 2 performs its addition. In such an event, Instruction 2 adds 7 to the old value of register 1 (6), and so register 2 would contain 13 instead, i.e:
Instruction 0: Register 1 = 6
Instruction 1: Register 1 = 3
Instruction 2: Register 2 = Register 1 + 7 = 13
This error occurs because Instruction 2 reads Register 1 before Instruction 1 has committed/stored the result of its write operation to Register 1. So when Instruction 2 is reading the contents of Register 1, register 1 still contains 6, not 3.
Forwarding (described below) helps correct such errors by depending on the fact that the output of Instruction 1 (which is 3) can be used by subsequent instructions before the value 3 is committed to/stored in Register 1.
Forwarding is implemented by feeding back the output of an instruction into the previous stage(s) of the pipeline as soon as the output of that instruction is available. Forwarding applied to our example means that we do not wait to commit/store the output of Instruction 1 in Register 1 (in this example, the output is 3) before making that output available to the subsequent instruction (in this case, Instruction 2). The effect is that Instruction 2 uses the correct (the more recent) value of Register 1: the commit/store was made immediately and not pipelined.
With forwarding enabled, the ID/EX stage of the pipeline now has two inputs - the value read from the register specified (in this example, the value 6 from Register 1), and the new value of Register 1 (in this example, this value is 3) which is sent from the next stage (EX/MEM). Additional control logic is used to determine which input to use.
See feed-forward.
Register renaming
RAW WAR WAW
A ``hazard'' is a circumstance that arises because of pipelining, that either will make implementing an instruction difficult or will cause errors in execution (i.e. the pipelining changes the semantics of instruction execution).
There are three basic types of hazard, with subdivisions possible.
Structural Hazards
You can't use a single piece of hardware for two things at once. A Princeton architecture runs into a structural hazard on ld or st instructions, since there is only one path to memory and the pipeline is attempting to fetch an instruction on every cycle.
Data Hazards
An instruction may depend on data that is not available yet. There are three types of data hazards:
Read After Write (RAW)
The code calls for a read to occur after a write, but the pipeline causes the read to occur first. This is the most common (and is the only one that can occur in the simple example pipeline).
Write After Read (WAR)
The code calls for a write to occur after a read, but the pipeline causes the write to occur first. This can occur in a longer pipeline in which some instructions read registers in a late stage while others write registers in an early stage.
Write After Write (WAW)
The code calls for two writes to occur; the pipeline reorders them. This can occur in a pipeline in which register writes can occur in more than one pipeline stage.
Control Hazards
A decision needs to be made as to whether to take a branch, before the information to make the decision is available.
There are also three ways to fix a hazard.
Document
Simply document the instruction set as supporting the semantics as defined by the pipeline (in other words, punt). This is the origin of delayed branch and delayed load instructions. It results in non-intuitive instruction semantics, and is tied to a particular pipeline implementation. If the implementation changes then the hazards change, and you find yourself making a screwy semantics work. You can't just document the new semantics like you did the old, since you have legacy code to support.
Stall
Delay the execution of the second instruction until the hazard is resolved. This preserves reasonable semantics, but slows things down.
An improvement on simply stalling which can be used to resolve structural hazards is to use branch prediction: take a guess as to whether the branch is likely to be taken or not, and continue executing with whatever guess you've taken. If you guessed wrong you cancel any instructions that you started to execute, with a penalty no greater than what you would have had if you'd just stalled.
Forward
The data you need may actually exist somewhere in the system, just not where you want it to be. This can be resolved by adding extra data paths, which ``forward'' the data to where it is needed. This is the ideal solution, since it neither messes up the semantics nor slows down the system. But, if the data is simply not there yet, then it can't be done.
There are three basic types of hazard, with subdivisions possible.
Structural Hazards
You can't use a single piece of hardware for two things at once. A Princeton architecture runs into a structural hazard on ld or st instructions, since there is only one path to memory and the pipeline is attempting to fetch an instruction on every cycle.
Data Hazards
An instruction may depend on data that is not available yet. There are three types of data hazards:
Read After Write (RAW)
The code calls for a read to occur after a write, but the pipeline causes the read to occur first. This is the most common (and is the only one that can occur in the simple example pipeline).
Write After Read (WAR)
The code calls for a write to occur after a read, but the pipeline causes the write to occur first. This can occur in a longer pipeline in which some instructions read registers in a late stage while others write registers in an early stage.
Write After Write (WAW)
The code calls for two writes to occur; the pipeline reorders them. This can occur in a pipeline in which register writes can occur in more than one pipeline stage.
Control Hazards
A decision needs to be made as to whether to take a branch, before the information to make the decision is available.
There are also three ways to fix a hazard.
Document
Simply document the instruction set as supporting the semantics as defined by the pipeline (in other words, punt). This is the origin of delayed branch and delayed load instructions. It results in non-intuitive instruction semantics, and is tied to a particular pipeline implementation. If the implementation changes then the hazards change, and you find yourself making a screwy semantics work. You can't just document the new semantics like you did the old, since you have legacy code to support.
Stall
Delay the execution of the second instruction until the hazard is resolved. This preserves reasonable semantics, but slows things down.
An improvement on simply stalling which can be used to resolve structural hazards is to use branch prediction: take a guess as to whether the branch is likely to be taken or not, and continue executing with whatever guess you've taken. If you guessed wrong you cancel any instructions that you started to execute, with a penalty no greater than what you would have had if you'd just stalled.
Forward
The data you need may actually exist somewhere in the system, just not where you want it to be. This can be resolved by adding extra data paths, which ``forward'' the data to where it is needed. This is the ideal solution, since it neither messes up the semantics nor slows down the system. But, if the data is simply not there yet, then it can't be done.
Subscribe to:
Posts (Atom)