title: Deoptimizing a program for the pipeline in Intel Sandybridge-family CPUs
body: <p>I've been racking my brain for a week trying to complete this assignment and I'm hoping someone here can lead me toward the right path. Let me start with the instructor's instructions:</p>
  <blockquote>
  <p>Your assignment is the opposite of our first lab assignment, which was to optimize a prime number program. Your purpose in this assignment is to pessimize the program, i.e. make it run slower. Both of these are CPU-intensive programs. They take a few seconds to run on our lab PCs. You may not change the algorithm.</p>
  <p>To deoptimize the program, use your knowledge of how the Intel i7 pipeline operates. Imagine ways to re-order instruction paths to introduce WAR, RAW, and other hazards. Think of ways to minimize the effectiveness of the cache. Be diabolically incompetent.</p>
  </blockquote>
  <p>The assignment gave a choice of Whetstone or Monte-Carlo programs.  The cache-effectiveness comments are mostly only applicable to Whetstone, but I chose the Monte-Carlo simulation program:</p>
  <pre><code>// Un-modified baseline for pessimization, as given in the assignment
  #include &lt;algorithm&gt;    // Needed for the &quot;max&quot; function
  #include &lt;cmath&gt;
  #include &lt;iostream&gt;
  
  // A simple implementation of the Box-Muller algorithm, used to generate
  // gaussian random numbers - necessary for the Monte Carlo method below
  // Note that C++11 actually provides std::normal_distribution&lt;&gt; in 
  // the &lt;random&gt; library, which can be used instead of this function
  double gaussian_box_muller() {
    double x = 0.0;
    double y = 0.0;
    double euclid_sq = 0.0;
  
    // Continue generating two uniform random variables
    // until the square of their &quot;euclidean distance&quot; 
    // is less than unity
    do {
      x = 2.0 * rand() / static_cast&lt;double&gt;(RAND_MAX)-1;
      y = 2.0 * rand() / static_cast&lt;double&gt;(RAND_MAX)-1;
      euclid_sq = x*x + y*y;
    } while (euclid_sq &gt;= 1.0);
  
    return x*sqrt(-2*log(euclid_sq)/euclid_sq);
  }
  
  // Pricing a European vanilla call option with a Monte Carlo method
  double monte_carlo_call_price(const int&amp; num_sims, const double&amp; S, const double&amp; K, const double&amp; r, const double&amp; v, const double&amp; T) {
    double S_adjust = S * exp(T*(r-0.5*v*v));
    double S_cur = 0.0;
    double payoff_sum = 0.0;
  
    for (int i=0; i&lt;num_sims; i++) {
      double gauss_bm = gaussian_box_muller();
      S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
      payoff_sum += std::max(S_cur - K, 0.0);
    }
  
    return (payoff_sum / static_cast&lt;double&gt;(num_sims)) * exp(-r*T);
  }
  
  // Pricing a European vanilla put option with a Monte Carlo method
  double monte_carlo_put_price(const int&amp; num_sims, const double&amp; S, const double&amp; K, const double&amp; r, const double&amp; v, const double&amp; T) {
    double S_adjust = S * exp(T*(r-0.5*v*v));
    double S_cur = 0.0;
    double payoff_sum = 0.0;
  
    for (int i=0; i&lt;num_sims; i++) {
      double gauss_bm = gaussian_box_muller();
      S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
      payoff_sum += std::max(K - S_cur, 0.0);
    }
  
    return (payoff_sum / static_cast&lt;double&gt;(num_sims)) * exp(-r*T);
  }
  
  int main(int argc, char **argv) {
    // First we create the parameter list                                                                               
    int num_sims = 10000000;   // Number of simulated asset paths                                                       
    double S = 100.0;  // Option price                                                                                  
    double K = 100.0;  // Strike price                                                                                  
    double r = 0.05;   // Risk-free rate (5%)                                                                           
    double v = 0.2;    // Volatility of the underlying (20%)                                                            
    double T = 1.0;    // One year until expiry                                                                         
  
    // Then we calculate the call/put values via Monte Carlo                                                                          
    double call = monte_carlo_call_price(num_sims, S, K, r, v, T);
    double put = monte_carlo_put_price(num_sims, S, K, r, v, T);
  
    // Finally we output the parameters and prices                                                                      
    std::cout &lt;&lt; &quot;Number of Paths: &quot; &lt;&lt; num_sims &lt;&lt; std::endl;
    std::cout &lt;&lt; &quot;Underlying:      &quot; &lt;&lt; S &lt;&lt; std::endl;
    std::cout &lt;&lt; &quot;Strike:          &quot; &lt;&lt; K &lt;&lt; std::endl;
    std::cout &lt;&lt; &quot;Risk-Free Rate:  &quot; &lt;&lt; r &lt;&lt; std::endl;
    std::cout &lt;&lt; &quot;Volatility:      &quot; &lt;&lt; v &lt;&lt; std::endl;
    std::cout &lt;&lt; &quot;Maturity:        &quot; &lt;&lt; T &lt;&lt; std::endl;
  
    std::cout &lt;&lt; &quot;Call Price:      &quot; &lt;&lt; call &lt;&lt; std::endl;
    std::cout &lt;&lt; &quot;Put Price:       &quot; &lt;&lt; put &lt;&lt; std::endl;
  
    return 0;
  }
  </code></pre>
  <p>The changes I have made seemed to increase the code running time by a second but I'm not entirely sure what I can change to stall the pipeline without adding code. A point to the right direction would be awesome, I appreciate any responses.</p>
  <hr />
  <h2>Update: <a href="https://meta.stackoverflow.com/a/323690/224132">the professor who gave this assignment posted some details</a></h2>
  <p>The highlights are:</p>
  <ul>
  <li>It's a second semester architecture class at a community college (using the Hennessy and Patterson textbook).</li>
  <li>the lab computers have Haswell CPUs</li>
  <li>The students have been exposed to the <code>CPUID</code> instruction and how to determine cache size, as well as intrinsics and the <code>CLFLUSH</code> instruction.</li>
  <li>any compiler options are allowed, and so is inline asm.</li>
  <li>Writing your own square root algorithm was announced as being outside the pale</li>
  </ul>
  <p>Cowmoogun's comments on the meta thread indicate that <a href="https://meta.stackoverflow.com/questions/323603/is-it-possible-for-some-too-broad-questions-to-be-exceptions-to-the-rule/323690#comment347466_323612">it wasn't clear compiler optimizations could be part of this, and assumed <code>-O0</code></a>, and that a 17% increase in run-time was reasonable.</p>
  <p>So it sounds like the goal of the assignment was to get students to re-order the existing work to reduce instruction-level parallelism or things like that, but it's not a bad thing that people have delved deeper and learned more.</p>
  <hr />
  <p>Keep in mind that this is a computer-architecture question, not a question about how to make C++ slow in general.</p>