{"id":160,"date":"2018-07-18T11:17:29","date_gmt":"2018-07-18T11:17:29","guid":{"rendered":"http:\/\/csp2.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=160"},"modified":"2018-08-03T09:11:05","modified_gmt":"2018-08-03T09:11:05","slug":"pipeline-hazards","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/chapter\/pipeline-hazards\/","title":{"rendered":"Pipeline Hazards"},"content":{"raw":"<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The objectives of this module are to discuss the various hazards associated with pipelining.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">We discussed the basics of pipelining and the MIPS pipeline implementation in the previous module. We made the following observations about pipelining:<\/p>\r\n\r\n<ul>\r\n \t<li>Pipelining doesn\u2019t help latency of single task, it helps throughput of entire workload<\/li>\r\n \t<li>Pipeline rate limited by slowest pipeline stage o Multiple tasks operating simultaneously<\/li>\r\n \t<li>Potential speedup = Number of pipe stages<\/li>\r\n \t<li>Unbalanced lengths of pipe stages reduces speedup<\/li>\r\n \t<li>Time to \u201cfill\u201d pipeline and time to \u201cdrain\u201d it reduces speedup o Unbalanced lengths of pipe stages reduces speedup<\/li>\r\n \t<li>Execute billions of instructions, so throughput is what matters o Data path design \u2013 Ideally we expect a CPI value of 1<\/li>\r\n \t<li>What is desirable in instruction sets for pipelining?<\/li>\r\n \t<li>Variable length instructions vs. all instructions same length?<\/li>\r\n \t<li>Memory operands part of any operation vs. memory operands only in loads or stores?<\/li>\r\n \t<li>Register operand many places in instruction format vs. registers located in same place?<\/li>\r\n<\/ul>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Ideally we expect a CPI value of 1 and a speedup equal to the number of stages in the pipeline. But, there are a number of factors that limit this. The problems that occur in the pipeline are called hazards. Hazards that arise in the pipeline prevent the next instruction from executing during its designated clock cycle. There are three types of hazards:<\/p>\r\n\r\n<ul>\r\n \t<li>Structural hazards: Hardware cannot support certain combinations of instructions (two instructions in the pipeline require the same resource).<\/li>\r\n \t<li>Data hazards: Instruction depends on result of prior instruction still in the pipeline<\/li>\r\n \t<li>Control hazards: Caused by delay between the fetching of instructions and decisions about changes in control flow (branches and jumps).<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nStructural hazards arise because there is not enough duplication of resources.\r\n\r\n&nbsp;\r\n\r\nResolving structural hazards:\r\n<ul>\r\n \t<li>Solution 1: Wait<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\no\u00a0\u00a0 Must detect the hazard\r\n\r\no\u00a0\u00a0 Must have mechanism to stall\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">o\u00a0\u00a0 Low cost and simple<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">o\u00a0\u00a0 Increases CPI<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">o\u00a0\u00a0 Used for rare cases<\/span>\r\n\r\n<\/div>\r\n<div>\r\n<ul>\r\n \t<li>Solution 2: Throw more hardware at the problem<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\no Pipeline hardware resource\r\n\r\n&nbsp;\r\n\r\n\u00a7\u00a0\u00a0\u00a0 useful for multi-cycle resources\r\n\r\n\u00a7\u00a0\u00a0\u00a0\u00a0 good performance\r\n\r\n\u00a7\u00a0\u00a0\u00a0\u00a0 sometimes complex e.g., RAM\r\n\r\n&nbsp;\r\n\r\no\u00a0\u00a0 Replicate resource\r\n\r\n&nbsp;\r\n\r\n\u00a7\u00a0\u00a0\u00a0\u00a0 good performance\r\n\r\n\u00a7\u00a0\u00a0\u00a0\u00a0 increases cost (+ maybe interconnect delay)\r\n\r\n\u00a7\u00a0\u00a0\u00a0\u00a0 useful for cheap or divisible resource\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Figure 11.1 shows one possibility of a structural hazard in the MIPS pipeline. Instruction 3 is accessing memory for an instruction fetch and instruction 1 is accessing memory for a data access (load\/store). These two are conflicting requirements and gives rise to a hazard. We should either stall one of the operations as shown in Figure 11.2, or have two separate memories for code and data. Structural hazards will have to handled at the design time itself.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Next, we shall discuss about data dependences and the associated hazards. There are two types of data dependence - true data dependences and name dependences.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2022\u00a0 An instruction <em>j<\/em> is <em>data dependent<\/em> on instruction <em>i<\/em> if either of the following holds:<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 Instruction <em>i<\/em> produces a result that may be used by instruction <em>j,<\/em> or<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 Instruction <em>j<\/em> is data dependent on instruction <em>k,<\/em> and instruction <em>k<\/em> is data dependent on instruction <em>i<\/em><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2022 A <em>name dependence o<\/em>ccurs when two instructions use the same register or memory location, called a <em>name<\/em>, but there is no flow of data between the instructions associated with that name<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 Two types of name dependences between an instruction <em>i<\/em> that <em>precedes<\/em> instruction <em>j<\/em> in program order:<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 An <em>antidependence<\/em> between instruction i and instruction j occurs when instruction <em>j<\/em> writes a register or memory location that instruction <em>i<\/em> reads. The original ordering must be preserved.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 An <em>output dependence<\/em> occurs when instruction <em>i<\/em> and instruction <em>j<\/em> write the same register or memory location. The ordering between the instructions must be preserved.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 Since this is not a true dependence, renaming can be more easily done for register operands, where it is called <em>register renaming<\/em><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 Register renaming can be done either <em>statically<\/em> by a compiler or <em>dynamically <\/em>by the hardware<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Last of all, we discuss control dependences. Control dependences determine the ordering of an instruction with respect to a branch instruction so that an instruction <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\"> is executed in correct program order. There are two general constraints imposed by control dependences:<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 An instruction that is control dependent on its branch cannot be moved <em>before <\/em>the branch so that its execution is<em> no longer controlled <\/em>by the branch.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 An instruction that is not control dependent on its branch cannot be moved <em>after <\/em>the branch so that its execution<em> is controlled <\/em>by the branch.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Having introduced the various types of data dependences and control dependence, let us discuss how these dependences cause problems in the pipeline. Dependences are properties of programs and whether the dependences turn out to be hazards and cause stalls in the pipeline are properties of the pipeline organization.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Data hazards may be classified as one of three types, depending on the order of read and write accesses in the instructions:<\/p>\r\n&nbsp;\r\n<ul>\r\n \t<li>RAW (R<em>ead After Write)<\/em><\/li>\r\n \t<li>Corresponds to a true data dependence<\/li>\r\n \t<li>Program order must be preserved<\/li>\r\n \t<li>This hazard results from an actual need for communication<\/li>\r\n \t<li>Considering two instructions i and j, instruction j reads the data before i writes it<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\ni:\u00a0 ADD R1, R2, R3\r\n\r\nj:\u00a0 SUB R4, R1, R3\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Add modifies R1 and then Sub should read it. If this order is changed, there is a RAW hazard<\/p>\r\n\r\n<ul>\r\n \t<li>WAW (W<em>rite After Write)<\/em><\/li>\r\n \t<li>Corresponds to an output dependence<\/li>\r\n \t<li>Occurs when there are multiple writes or a short integer pipeline and a longer floating-point pipeline or when an instruction proceeds when a previous instruction is stalled WAW (<em style=\"text-align: justify;font-size: 1em\">write after write)<\/em><\/li>\r\n \t<li>This is caused by a name dependence. There is no actual data transfer. It is the same name that causes the problem<\/li>\r\n \t<li>Considering two instructions i and j, instruction j should write after instruction i has written the data<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\ni:\u00a0 SUB R1, R4, R3\r\n\r\nj:\u00a0 ADD R1, R2, R3\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Instruction i has to modify register r1 first, and then j has to modify it. Otherwise, there is a WAW hazard. There is a problem because of R1. If some other register had been used, there will not be a problem<\/p>\r\n&nbsp;\r\n<ul>\r\n \t<li style=\"text-align: justify\">Solution is register renaming, that is, use some other register. The hardware can do the renaming or the compiler can do the renaming<\/li>\r\n \t<li style=\"text-align: justify\">WAR (<em style=\"font-size: 1em\">Write After Read)<\/em><\/li>\r\n \t<li style=\"text-align: justify\">Arises from an anti dependence<\/li>\r\n \t<li style=\"text-align: justify\">Cannot occur in most static issue pipelines<\/li>\r\n \t<li style=\"text-align: justify\">Occurs either when there are early writes <em style=\"text-align: initial;font-size: 1em\">and<\/em><span style=\"text-align: initial;font-size: 1em\"> late reads, or when instructions are re-ordered<\/span><\/li>\r\n \t<li style=\"text-align: justify\">There is no actual data transfer. It is the same name that causes the problem<\/li>\r\n \t<li style=\"text-align: justify\">Considering two instructions i and j, instruction j should write after instruction i has read the data.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\ni:\u00a0 SUB R4, R1, R3\r\n\r\nj:\u00a0 ADD R1, R2, R3\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Instruction i has to read register r1 first, and then j has to modify it. Otherwise, there is a WAR hazard. There is a problem because of R1. If some other register had been used, there will not be a problem<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2022 Solution is register renaming, that is, use some other register. The hardware can do the renaming or the compiler can do the renaming<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Figure 11.3 gives a situation of having true data dependences. The use of the result of the ADD instruction in the next three instructions causes a hazard, since the register is not written until after those instructions read it. The write back for the ADD instruction happens only in the fifth clock cycle, whereas the next three instructions read the register values before that, and hence will read the wrong data. This gives rise to RAW hazards.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">A control hazard is when we need to find the destination of a branch, and can\u2019t fetch any new instructions until we know that destination. Figure 11.4 illustrates a control hazard. The first instruction is a branch and it gets resolved only in the fourth clock cycle. So, the next three instructions fetched may be correct, or wrong, depending on the outcome of the branch. This is an example of a control hazard.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Now, having discussed the various dependences and the hazards that they might lead to, we shall see what are the hazards that can happen in our simple MIPS pipeline.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li>Structural hazard<\/li>\r\n \t<li>Conflict for use of a resource<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n\u2022 In MIPS pipeline with a single memory\r\n\r\n&nbsp;\r\n\r\n\u2013\u00a0\u00a0 Load\/store requires data access\r\n\r\n&nbsp;\r\n\r\n\u2013\u00a0\u00a0 Instruction fetch would have to <em>stall<\/em> for that cycle\r\n\r\n&nbsp;\r\n\r\n\u2022 Would cause a pipeline \u201cbubble\u201d\r\n\r\n&nbsp;\r\n\r\n\u2022 Hence, pipelined datapaths require separate instruction\/data memories or separate instruction\/data caches\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li>RAW hazards - can happen in any architecture<\/li>\r\n \t<li>WAR hazards - Can\u2019t happen in MIPS 5 stage pipeline because all instructions take 5 stages, and reads are always in stage 2, and writes are always in stage 5<\/li>\r\n \t<li>WAW hazards - Can\u2019t happen in MIPS 5 stage pipeline because all instructions take 5 stages, and writes are always in stage 5<\/li>\r\n \t<li>Control hazards<\/li>\r\n \t<li>Can happen<\/li>\r\n \t<li>The penalty depends on when the branch is resolved \u2013 in the second clock cycle or the third clock cycle<\/li>\r\n \t<li>\u00a0More aggressive implementations resolve the branch in the second clock cycle itself, leading to one clock cycle penalty<\/li>\r\n<\/ul>\r\n<\/div>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us look at the speedup equation with stalls and look at an example problem.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">CPIpipelined = Ideal CPI + Average Stall cycles per Inst<\/p>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-163 aligncenter\" src=\"http:\/\/csp2.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/46\/2018\/07\/2-96.png\" alt=\"\" width=\"636\" height=\"223\" \/>\r\n\r\n&nbsp;\r\n\r\nLet us assume we want to compare the performance of two machines. Which machine is faster?\r\n<ul>\r\n \t<li>Machine A: Dual ported memory - so there are no memory stalls<\/li>\r\n \t<li>Machine B: Single ported memory, but its pipelined implementation has a 1.05 times faster clock rate<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nAssume:\r\n<ul>\r\n \t<li>Ideal CPI = 1 for both<\/li>\r\n \t<li>Loads are 40% of instructions executed<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nSpeedupA = Pipeline Depth\/(1+0) x(clockunpipe\/clockpipe)\r\n\r\n= Pipeline Depth\r\n\r\nSpeedupB = Pipeline Depth\/(1 + 0.4 x 1)\u00a0 x (clockunpipe\/(clockunpipe \/ 1.05)\r\n\r\n= (Pipeline Depth\/1.4) x 1.05\r\n\r\n= 75 x Pipeline Depth\r\n\r\n&nbsp;\r\n\r\nSpeedupA \/ SpeedupB = Pipeline Depth \/ (0.75 x Pipeline Depth) = 1.33 Machine A is 1.33 times faster.\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">To summarize, we have discussed the various hazards that might occur in a pipeline. Structural hazards happen because there are not enough duplication of resources and they have to be handled at design time itself. Data hazards happen because of true data dependences and name dependences. Control hazards are caused by branches. The solutions for all these hazards will be discussed in the subsequent modules.<\/p>\r\n&nbsp;\r\n\r\n<strong>Web Links \/ Supporting Materials<\/strong>\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li>Computer Organization and Design \u2013 The Hardware \/ Software Interface, David A. Patterson and John L. Hennessy, 4th.Edition, Morgan Kaufmann, Elsevier, 2009.<\/li>\r\n \t<li>Computer Organization, Carl Hamacher, Zvonko Vranesic and Safwat Zaky, 5th.Edition, McGraw- Hill Higher Education, 2011.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n&nbsp;","rendered":"<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The objectives of this module are to discuss the various hazards associated with pipelining.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We discussed the basics of pipelining and the MIPS pipeline implementation in the previous module. We made the following observations about pipelining:<\/p>\n<ul>\n<li>Pipelining doesn\u2019t help latency of single task, it helps throughput of entire workload<\/li>\n<li>Pipeline rate limited by slowest pipeline stage o Multiple tasks operating simultaneously<\/li>\n<li>Potential speedup = Number of pipe stages<\/li>\n<li>Unbalanced lengths of pipe stages reduces speedup<\/li>\n<li>Time to \u201cfill\u201d pipeline and time to \u201cdrain\u201d it reduces speedup o Unbalanced lengths of pipe stages reduces speedup<\/li>\n<li>Execute billions of instructions, so throughput is what matters o Data path design \u2013 Ideally we expect a CPI value of 1<\/li>\n<li>What is desirable in instruction sets for pipelining?<\/li>\n<li>Variable length instructions vs. all instructions same length?<\/li>\n<li>Memory operands part of any operation vs. memory operands only in loads or stores?<\/li>\n<li>Register operand many places in instruction format vs. registers located in same place?<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Ideally we expect a CPI value of 1 and a speedup equal to the number of stages in the pipeline. But, there are a number of factors that limit this. The problems that occur in the pipeline are called hazards. Hazards that arise in the pipeline prevent the next instruction from executing during its designated clock cycle. There are three types of hazards:<\/p>\n<ul>\n<li>Structural hazards: Hardware cannot support certain combinations of instructions (two instructions in the pipeline require the same resource).<\/li>\n<li>Data hazards: Instruction depends on result of prior instruction still in the pipeline<\/li>\n<li>Control hazards: Caused by delay between the fetching of instructions and decisions about changes in control flow (branches and jumps).<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>Structural hazards arise because there is not enough duplication of resources.<\/p>\n<p>&nbsp;<\/p>\n<p>Resolving structural hazards:<\/p>\n<ul>\n<li>Solution 1: Wait<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>o\u00a0\u00a0 Must detect the hazard<\/p>\n<p>o\u00a0\u00a0 Must have mechanism to stall<\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">o\u00a0\u00a0 Low cost and simple<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">o\u00a0\u00a0 Increases CPI<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">o\u00a0\u00a0 Used for rare cases<\/span><\/p>\n<\/div>\n<div>\n<ul>\n<li>Solution 2: Throw more hardware at the problem<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>o Pipeline hardware resource<\/p>\n<p>&nbsp;<\/p>\n<p>\u00a7\u00a0\u00a0\u00a0 useful for multi-cycle resources<\/p>\n<p>\u00a7\u00a0\u00a0\u00a0\u00a0 good performance<\/p>\n<p>\u00a7\u00a0\u00a0\u00a0\u00a0 sometimes complex e.g., RAM<\/p>\n<p>&nbsp;<\/p>\n<p>o\u00a0\u00a0 Replicate resource<\/p>\n<p>&nbsp;<\/p>\n<p>\u00a7\u00a0\u00a0\u00a0\u00a0 good performance<\/p>\n<p>\u00a7\u00a0\u00a0\u00a0\u00a0 increases cost (+ maybe interconnect delay)<\/p>\n<p>\u00a7\u00a0\u00a0\u00a0\u00a0 useful for cheap or divisible resource<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Figure 11.1 shows one possibility of a structural hazard in the MIPS pipeline. Instruction 3 is accessing memory for an instruction fetch and instruction 1 is accessing memory for a data access (load\/store). These two are conflicting requirements and gives rise to a hazard. We should either stall one of the operations as shown in Figure 11.2, or have two separate memories for code and data. Structural hazards will have to handled at the design time itself.<\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Next, we shall discuss about data dependences and the associated hazards. There are two types of data dependence &#8211; true data dependences and name dependences.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2022\u00a0 An instruction <em>j<\/em> is <em>data dependent<\/em> on instruction <em>i<\/em> if either of the following holds:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 Instruction <em>i<\/em> produces a result that may be used by instruction <em>j,<\/em> or<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 Instruction <em>j<\/em> is data dependent on instruction <em>k,<\/em> and instruction <em>k<\/em> is data dependent on instruction <em>i<\/em><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2022 A <em>name dependence o<\/em>ccurs when two instructions use the same register or memory location, called a <em>name<\/em>, but there is no flow of data between the instructions associated with that name<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 Two types of name dependences between an instruction <em>i<\/em> that <em>precedes<\/em> instruction <em>j<\/em> in program order:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 An <em>antidependence<\/em> between instruction i and instruction j occurs when instruction <em>j<\/em> writes a register or memory location that instruction <em>i<\/em> reads. The original ordering must be preserved.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 An <em>output dependence<\/em> occurs when instruction <em>i<\/em> and instruction <em>j<\/em> write the same register or memory location. The ordering between the instructions must be preserved.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 Since this is not a true dependence, renaming can be more easily done for register operands, where it is called <em>register renaming<\/em><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 Register renaming can be done either <em>statically<\/em> by a compiler or <em>dynamically <\/em>by the hardware<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Last of all, we discuss control dependences. Control dependences determine the ordering of an instruction with respect to a branch instruction so that an instruction <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\"> is executed in correct program order. There are two general constraints imposed by control dependences:<\/span><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 An instruction that is control dependent on its branch cannot be moved <em>before <\/em>the branch so that its execution is<em> no longer controlled <\/em>by the branch.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 An instruction that is not control dependent on its branch cannot be moved <em>after <\/em>the branch so that its execution<em> is controlled <\/em>by the branch.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Having introduced the various types of data dependences and control dependence, let us discuss how these dependences cause problems in the pipeline. Dependences are properties of programs and whether the dependences turn out to be hazards and cause stalls in the pipeline are properties of the pipeline organization.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Data hazards may be classified as one of three types, depending on the order of read and write accesses in the instructions:<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>RAW (R<em>ead After Write)<\/em><\/li>\n<li>Corresponds to a true data dependence<\/li>\n<li>Program order must be preserved<\/li>\n<li>This hazard results from an actual need for communication<\/li>\n<li>Considering two instructions i and j, instruction j reads the data before i writes it<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>i:\u00a0 ADD R1, R2, R3<\/p>\n<p>j:\u00a0 SUB R4, R1, R3<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Add modifies R1 and then Sub should read it. If this order is changed, there is a RAW hazard<\/p>\n<ul>\n<li>WAW (W<em>rite After Write)<\/em><\/li>\n<li>Corresponds to an output dependence<\/li>\n<li>Occurs when there are multiple writes or a short integer pipeline and a longer floating-point pipeline or when an instruction proceeds when a previous instruction is stalled WAW (<em style=\"text-align: justify;font-size: 1em\">write after write)<\/em><\/li>\n<li>This is caused by a name dependence. There is no actual data transfer. It is the same name that causes the problem<\/li>\n<li>Considering two instructions i and j, instruction j should write after instruction i has written the data<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>i:\u00a0 SUB R1, R4, R3<\/p>\n<p>j:\u00a0 ADD R1, R2, R3<\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Instruction i has to modify register r1 first, and then j has to modify it. Otherwise, there is a WAW hazard. There is a problem because of R1. If some other register had been used, there will not be a problem<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li style=\"text-align: justify\">Solution is register renaming, that is, use some other register. The hardware can do the renaming or the compiler can do the renaming<\/li>\n<li style=\"text-align: justify\">WAR (<em style=\"font-size: 1em\">Write After Read)<\/em><\/li>\n<li style=\"text-align: justify\">Arises from an anti dependence<\/li>\n<li style=\"text-align: justify\">Cannot occur in most static issue pipelines<\/li>\n<li style=\"text-align: justify\">Occurs either when there are early writes <em style=\"text-align: initial;font-size: 1em\">and<\/em><span style=\"text-align: initial;font-size: 1em\"> late reads, or when instructions are re-ordered<\/span><\/li>\n<li style=\"text-align: justify\">There is no actual data transfer. It is the same name that causes the problem<\/li>\n<li style=\"text-align: justify\">Considering two instructions i and j, instruction j should write after instruction i has read the data.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>i:\u00a0 SUB R4, R1, R3<\/p>\n<p>j:\u00a0 ADD R1, R2, R3<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Instruction i has to read register r1 first, and then j has to modify it. Otherwise, there is a WAR hazard. There is a problem because of R1. If some other register had been used, there will not be a problem<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2022 Solution is register renaming, that is, use some other register. The hardware can do the renaming or the compiler can do the renaming<\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Figure 11.3 gives a situation of having true data dependences. The use of the result of the ADD instruction in the next three instructions causes a hazard, since the register is not written until after those instructions read it. The write back for the ADD instruction happens only in the fifth clock cycle, whereas the next three instructions read the register values before that, and hence will read the wrong data. This gives rise to RAW hazards.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A control hazard is when we need to find the destination of a branch, and can\u2019t fetch any new instructions until we know that destination. Figure 11.4 illustrates a control hazard. The first instruction is a branch and it gets resolved only in the fourth clock cycle. So, the next three instructions fetched may be correct, or wrong, depending on the outcome of the branch. This is an example of a control hazard.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">Now, having discussed the various dependences and the hazards that they might lead to, we shall see what are the hazards that can happen in our simple MIPS pipeline.<\/span><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<ul>\n<li>Structural hazard<\/li>\n<li>Conflict for use of a resource<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>\u2022 In MIPS pipeline with a single memory<\/p>\n<p>&nbsp;<\/p>\n<p>\u2013\u00a0\u00a0 Load\/store requires data access<\/p>\n<p>&nbsp;<\/p>\n<p>\u2013\u00a0\u00a0 Instruction fetch would have to <em>stall<\/em> for that cycle<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022 Would cause a pipeline \u201cbubble\u201d<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022 Hence, pipelined datapaths require separate instruction\/data memories or separate instruction\/data caches<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>RAW hazards &#8211; can happen in any architecture<\/li>\n<li>WAR hazards &#8211; Can\u2019t happen in MIPS 5 stage pipeline because all instructions take 5 stages, and reads are always in stage 2, and writes are always in stage 5<\/li>\n<li>WAW hazards &#8211; Can\u2019t happen in MIPS 5 stage pipeline because all instructions take 5 stages, and writes are always in stage 5<\/li>\n<li>Control hazards<\/li>\n<li>Can happen<\/li>\n<li>The penalty depends on when the branch is resolved \u2013 in the second clock cycle or the third clock cycle<\/li>\n<li>\u00a0More aggressive implementations resolve the branch in the second clock cycle itself, leading to one clock cycle penalty<\/li>\n<\/ul>\n<\/div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us look at the speedup equation with stalls and look at an example problem.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">CPIpipelined = Ideal CPI + Average Stall cycles per Inst<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-163 aligncenter\" src=\"http:\/\/csp2.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/46\/2018\/07\/2-96.png\" alt=\"\" width=\"636\" height=\"223\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-content\/uploads\/sites\/46\/2018\/07\/2-96.png 636w, https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-content\/uploads\/sites\/46\/2018\/07\/2-96-300x105.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-content\/uploads\/sites\/46\/2018\/07\/2-96-65x23.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-content\/uploads\/sites\/46\/2018\/07\/2-96-225x79.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-content\/uploads\/sites\/46\/2018\/07\/2-96-350x123.png 350w\" sizes=\"auto, (max-width: 636px) 100vw, 636px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Let us assume we want to compare the performance of two machines. Which machine is faster?<\/p>\n<ul>\n<li>Machine A: Dual ported memory &#8211; so there are no memory stalls<\/li>\n<li>Machine B: Single ported memory, but its pipelined implementation has a 1.05 times faster clock rate<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>Assume:<\/p>\n<ul>\n<li>Ideal CPI = 1 for both<\/li>\n<li>Loads are 40% of instructions executed<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>SpeedupA = Pipeline Depth\/(1+0) x(clockunpipe\/clockpipe)<\/p>\n<p>= Pipeline Depth<\/p>\n<p>SpeedupB = Pipeline Depth\/(1 + 0.4 x 1)\u00a0 x (clockunpipe\/(clockunpipe \/ 1.05)<\/p>\n<p>= (Pipeline Depth\/1.4) x 1.05<\/p>\n<p>= 75 x Pipeline Depth<\/p>\n<p>&nbsp;<\/p>\n<p>SpeedupA \/ SpeedupB = Pipeline Depth \/ (0.75 x Pipeline Depth) = 1.33 Machine A is 1.33 times faster.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">To summarize, we have discussed the various hazards that might occur in a pipeline. Structural hazards happen because there are not enough duplication of resources and they have to be handled at design time itself. Data hazards happen because of true data dependences and name dependences. Control hazards are caused by branches. The solutions for all these hazards will be discussed in the subsequent modules.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Web Links \/ Supporting Materials<\/strong><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>Computer Organization and Design \u2013 The Hardware \/ Software Interface, David A. Patterson and John L. Hennessy, 4th.Edition, Morgan Kaufmann, Elsevier, 2009.<\/li>\n<li>Computer Organization, Carl Hamacher, Zvonko Vranesic and Safwat Zaky, 5th.Edition, McGraw- Hill Higher Education, 2011.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"author":2,"menu_order":11,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-a-p-shanthi"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-160","chapter","type-chapter","status-publish","hentry","contributor-dr-a-p-shanthi"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/160","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/users\/2"}],"version-history":[{"count":4,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/160\/revisions"}],"predecessor-version":[{"id":448,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/160\/revisions\/448"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/160\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/media?parent=160"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapter-type?post=160"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/contributor?post=160"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/license?post=160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}