title: Understanding stalls and branch delay slots
body: <p>I am taking a course on Computer Architecture.  I found this website from another University which has notes and videos which are helping me thus far: <a href="http://www.eng.utah.edu/~cs6810/" rel="nofollow">CS6810, Univ of Utah</a>. I am working through some old homework assignments posted on that site, in particular <a href="http://www.eng.utah.edu/~cs6810/hw/hw13-3.html" rel="nofollow">this one</a>. I am trying to understand pipelining and related concepts, specifically stalls and branch delay slots.</p>
  
  <p>I am looking now at the first question from that old homework assignment and am unsure of how to do these problems. </p>
  
  <p>The question is as follows:</p>
  
  <blockquote>
    <p>Consider the following code segment, where the branch is taken 30% of the time and not 
    taken 70% of the time.</p>
    
    <p>R1 = R2 + R3</p>
    
    <p>R4 = R5 + R6</p>
    
    <p>R7 = R8 + R9 </p>
    
    <p>if R10 = 0, branch to linex </p>
    
    <p>R11 = R12 + R13 </p>
    
    <p>R14 = R11 + R15 </p>
    
    <p>R16 = R14 + R17 </p>
    
    <p>... </p>
    
    <p>linex: R18 = R19 + R20 </p>
    
    <p>R21 = R18 + R22 </p>
    
    <p>R23 = R18 + R21 </p>
    
    <p>... </p>
    
    <p>Consider a 10-stage in-order processor, where the instruction is fetched in the first 
    stage, and the branch outcome is known after three stages. Estimate the CPI of the 
    processor under the following scenarios (assume that all stalls in the processor are 
    branch-related and branches account for 15% of all executed instructions):</p>
    
    <ol>
    <li><p>On every branch, fetch is stalled until the branch outcome is known.</p></li>
    <li><p>Every branch is predicted not-taken and the mis-fetched instructions are squashed if the branch is taken.</p></li>
    <li><p>The processor has two delay slots and the two instructions following the branch are always fetched and executed, and</p>
    
    <p>3.1. You are unable to find any instructions to fill the delay slot.</p>
    
    <p>3.2. You are able to move two instructions before the branch into the delay slot.</p>
    
    <p>3.3. You are able to move two instructions after label "linex" into the delay slot.</p>
    
    <p>3.4. You are able to move one (note: one, not two!) instruction immediately after the branch (in the original code) into the delay slot.</p></li>
    </ol>
  </blockquote>
  
  <p>I am unsure of how to even begin to look at this question. I have read all the notes and watched the videos on that site and have read sections from the H&amp;P book but am still confused on this problem.  If anyone has the time, I would appreciate someone helping me step through this question. I just need to know how to begin to conceptualize the answers.</p>