title: OpenMP Dynamic vs Guided Scheduling
body: <p>I'm studying OpenMP's scheduling and specifically the different types.  I understand the general behavior of each type, but clarification would be helpful regarding when to choose between <code>dynamic</code> and <code>guided</code> scheduling.</p>
  
  <p><a href="https://software.intel.com/en-us/articles/openmp-loop-scheduling" rel="noreferrer">Intel's docs</a> describe <code>dynamic</code> scheduling:</p>
  
  <blockquote>
    <p>Use the internal work queue to give a chunk-sized block of loop
    iterations to each thread. When a thread is finished, it retrieves the
    next block of loop iterations from the top of the work queue. By
    default, the chunk size is 1. Be careful when using this scheduling
    type because of the extra overhead involved.</p>
  </blockquote>
  
  <p>It also describes <code>guided</code> scheduling:</p>
  
  <blockquote>
    <p>Similar to dynamic scheduling, but the chunk size starts off large and
    decreases to better handle load imbalance between iterations. The
    optional chunk parameter specifies them minimum size chunk to use. By
    default the chunk size is approximately loop_count/number_of_threads.</p>
  </blockquote>
  
  <p>Since <code>guided</code> scheduling dynamically decreases the chunk size at runtime, why would I ever use <code>dynamic</code> scheduling?</p>
  
  <p>I've researched this question and <a href="https://www.dartmouth.edu/~rc/classes/intro_openmp/schedule_loops.html" rel="noreferrer">found this table from Dartmouth</a>:</p>
  
  <p><a href="https://i.stack.imgur.com/Mr2ME.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Mr2ME.png" alt="enter image description here"></a></p>
  
  <p><code>guided</code> is listed as having <code>high</code> overhead, while <code>dynamic</code> has medium overhead.</p>
  
  <p>This initially made sense, but upon further investigation I <a href="https://software.intel.com/en-us/articles/performance-obstacles-for-threading-how-do-they-affect-openmp-code" rel="noreferrer">read an Intel article</a> on the topic.  From the previous table, I theorized <code>guided</code> scheduling would take longer because of the analysis and adjustments of the chunk size at runtime (even when used correctly).  However, in the Intel article it states:</p>
  
  <blockquote>
    <p>Guided schedules work best with small chunk sizes as their limit; this
    gives the most flexibility. It’s not clear why they get worse at
    bigger chunk sizes, but they can take too long when limited to large
    chunk sizes.</p>
  </blockquote>
  
  <p>Why would the chunk size relate to <code>guided</code> taking longer than <code>dynamic</code>?  It would make sense for the lack of "flexibility" to cause performance loss through locking the chunk size too high.  However, I would not describe this as "overhead", and the locking problem would discredit previous theory.</p>
  
  <p>Lastly, it's stated in the article:</p>
  
  <blockquote>
    <p>Dynamic schedules give the most flexibility, but take the biggest
    performance hit when scheduled wrong.</p>
  </blockquote>
  
  <p>It makes sense for <code>dynamic</code> scheduling to be more optimal than <code>static</code>, but why is it more optimal than <code>guided</code>?  Is it just the overhead I'm questioning?</p>
  
  <p>This <a href="https://stackoverflow.com/questions/10850155/openmp-for-schedule">somewhat related SO post</a> explains NUMA related to the scheduling types.  It's irrelevant to this question, since the required organization is lost by the "first come, first served" behavior of these scheduling types.</p>
  
  <p><code>dynamic</code> scheduling may be coalescent, causing performance improvement, but then the same hypothetical should apply to <code>guided</code>.</p>
  
  <p>Here's the timing of each scheduling type across different chunk sizes from the Intel article for reference.  It's only recordings from one program and some rules apply differently per program and machine (especially with scheduling), but it should provide the general trends.</p>
  
  <p><a href="https://i.stack.imgur.com/juUpZ.png" rel="noreferrer"><img src="https://i.stack.imgur.com/juUpZ.png" alt="enter image description here"></a></p>
  
  <p><strong>EDIT</strong> (core of my question):</p>
  
  <ul>
  <li>What affects the runtime of <code>guided</code> scheduling?  Specific examples?  Why is it slower than <code>dynamic</code> in some cases?</li>
  <li>When would I favor <code>guided</code> over <code>dynamic</code> or vice-versa?</li>
  <li>Once this has been explained, do the sources above support your explanation?  Do they contradict at all?</li>
  </ul>