libgomp/iter_ull.c

   1 /* Copyright (C) 2005, 2008, 2009, 2011 Free Software Foundation, Inc.
   2    Contributed by Richard Henderson <rth@redhat.com>.
   3
   4    This file is part of the GNU OpenMP Library (libgomp).
   5
   6    Libgomp is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
  12    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14    more details.
  15
  16    Under Section 7 of GPL version 3, you are granted additional
  17    permissions described in the GCC Runtime Library Exception, version
  18    3.1, as published by the Free Software Foundation.
  19
  20    You should have received a copy of the GNU General Public License and
  21    a copy of the GCC Runtime Library Exception along with this program;
  22    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23    <http://www.gnu.org/licenses/>.  */
  24
  25 /* This file contains routines for managing work-share iteration, both
  26    for loops and sections.  */
  27
  28 #include "libgomp.h"
  29 #include <stdlib.h>
  30
  31 typedef unsigned long long gomp_ull;
  32
  33 /* This function implements the STATIC scheduling method.  The caller should
  34    iterate *pstart <= x < *pend.  Return zero if there are more iterations
  35    to perform; nonzero if not.  Return less than 0 if this thread had
  36    received the absolutely last iteration.  */
  37
  38 int
  39 gomp_iter_ull_static_next (gomp_ull *pstart, gomp_ull *pend)
  40 {
  41   struct gomp_thread *thr = gomp_thread ();
  42   struct gomp_team *team = thr->ts.team;
  43   struct gomp_work_share *ws = thr->ts.work_share;
  44   unsigned long nthreads = team ? team->nthreads : 1;
  45
  46   if (thr->ts.static_trip == -1)
  47     return -1;
  48
  49   /* Quick test for degenerate teams and orphaned constructs.  */
  50   if (nthreads == 1)
  51     {
  52       *pstart = ws->next_ull;
  53       *pend = ws->end_ull;
  54       thr->ts.static_trip = -1;
  55       return ws->next_ull == ws->end_ull;
  56     }
  57
  58   /* We interpret chunk_size zero as "unspecified", which means that we
  59      should break up the iterations such that each thread makes only one
  60      trip through the outer loop.  */
  61   if (ws->chunk_size_ull == 0)
  62     {
  63       gomp_ull n, q, i, t, s0, e0, s, e;
  64
  65       if (thr->ts.static_trip > 0)
  66         return 1;
  67
  68       /* Compute the total number of iterations.  */
  69       if (__builtin_expect (ws->mode, 0) == 0)
  70         n = (ws->end_ull - ws->next_ull + ws->incr_ull - 1) / ws->incr_ull;
  71       else
  72         n = (ws->next_ull - ws->end_ull - ws->incr_ull - 1) / -ws->incr_ull;
  73       i = thr->ts.team_id;
  74
  75       /* Compute the "zero-based" start and end points.  That is, as
  76          if the loop began at zero and incremented by one.  */
  77       q = n / nthreads;
  78       t = n % nthreads;
  79       if (i < t)
  80         {
  81           t = 0;
  82           q++;
  83         }
  84       s0 = q * i + t;
  85       e0 = s0 + q;
  86
  87       /* Notice when no iterations allocated for this thread.  */
  88       if (s0 >= e0)
  89         {
  90           thr->ts.static_trip = 1;
  91           return 1;
  92         }
  93
  94       /* Transform these to the actual start and end numbers.  */
  95       s = s0 * ws->incr_ull + ws->next_ull;
  96       e = e0 * ws->incr_ull + ws->next_ull;
  97
  98       *pstart = s;
  99       *pend = e;
 100       thr->ts.static_trip = (e0 == n ? -1 : 1);
 101       return 0;
 102     }
 103   else
 104     {
 105       gomp_ull n, s0, e0, i, c, s, e;
 106
 107       /* Otherwise, each thread gets exactly chunk_size iterations
 108          (if available) each time through the loop.  */
 109
 110       if (__builtin_expect (ws->mode, 0) == 0)
 111         n = (ws->end_ull - ws->next_ull + ws->incr_ull - 1) / ws->incr_ull;
 112       else
 113         n = (ws->next_ull - ws->end_ull - ws->incr_ull - 1) / -ws->incr_ull;
 114       i = thr->ts.team_id;
 115       c = ws->chunk_size_ull;
 116
 117       /* Initial guess is a C sized chunk positioned nthreads iterations
 118          in, offset by our thread number.  */
 119       s0 = (thr->ts.static_trip * (gomp_ull) nthreads + i) * c;
 120       e0 = s0 + c;
 121
 122       /* Detect overflow.  */
 123       if (s0 >= n)
 124         return 1;
 125       if (e0 > n)
 126         e0 = n;
 127
 128       /* Transform these to the actual start and end numbers.  */
 129       s = s0 * ws->incr_ull + ws->next_ull;
 130       e = e0 * ws->incr_ull + ws->next_ull;
 131
 132       *pstart = s;
 133       *pend = e;
 134
 135       if (e0 == n)
 136         thr->ts.static_trip = -1;
 137       else
 138         thr->ts.static_trip++;
 139       return 0;
 140     }
 141 }
 142
 143
 144 /* This function implements the DYNAMIC scheduling method.  Arguments are
 145    as for gomp_iter_ull_static_next.  This function must be called with
 146    ws->lock held.  */
 147
 148 bool
 149 gomp_iter_ull_dynamic_next_locked (gomp_ull *pstart, gomp_ull *pend)
 150 {
 151   struct gomp_thread *thr = gomp_thread ();
 152   struct gomp_work_share *ws = thr->ts.work_share;
 153   gomp_ull start, end, chunk, left;
 154
 155   start = ws->next_ull;
 156   if (start == ws->end_ull)
 157     return false;
 158
 159   chunk = ws->chunk_size_ull;
 160   left = ws->end_ull - start;
 161   if (__builtin_expect (ws->mode & 2, 0))
 162     {
 163       if (chunk < left)
 164         chunk = left;
 165     }
 166   else
 167     {
 168       if (chunk > left)
 169         chunk = left;
 170     }
 171   end = start + chunk;
 172
 173   ws->next_ull = end;
 174   *pstart = start;
 175   *pend = end;
 176   return true;
 177 }
 178
 179
 180 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
 181 /* Similar, but doesn't require the lock held, and uses compare-and-swap
 182    instead.  Note that the only memory value that changes is ws->next_ull.  */
 183
 184 bool
 185 gomp_iter_ull_dynamic_next (gomp_ull *pstart, gomp_ull *pend)
 186 {
 187   struct gomp_thread *thr = gomp_thread ();
 188   struct gomp_work_share *ws = thr->ts.work_share;
 189   gomp_ull start, end, nend, chunk;
 190
 191   end = ws->end_ull;
 192   chunk = ws->chunk_size_ull;
 193
 194   if (__builtin_expect (ws->mode & 1, 1))
 195     {
 196       gomp_ull tmp = __sync_fetch_and_add (&ws->next_ull, chunk);
 197       if (__builtin_expect (ws->mode & 2, 0) == 0)
 198         {
 199           if (tmp >= end)
 200             return false;
 201           nend = tmp + chunk;
 202           if (nend > end)
 203             nend = end;
 204           *pstart = tmp;
 205           *pend = nend;
 206           return true;
 207         }
 208       else
 209         {
 210           if (tmp <= end)
 211             return false;
 212           nend = tmp + chunk;
 213           if (nend < end)
 214             nend = end;
 215           *pstart = tmp;
 216           *pend = nend;
 217           return true;
 218         }
 219     }
 220
 221   start = ws->next_ull;
 222   while (1)
 223     {
 224       gomp_ull left = end - start;
 225       gomp_ull tmp;
 226
 227       if (start == end)
 228         return false;
 229
 230       if (__builtin_expect (ws->mode & 2, 0))
 231         {
 232           if (chunk < left)
 233             chunk = left;
 234         }
 235       else
 236         {
 237           if (chunk > left)
 238             chunk = left;
 239         }
 240       nend = start + chunk;
 241
 242       tmp = __sync_val_compare_and_swap (&ws->next_ull, start, nend);
 243       if (__builtin_expect (tmp == start, 1))
 244         break;
 245
 246       start = tmp;
 247     }
 248
 249   *pstart = start;
 250   *pend = nend;
 251   return true;
 252 }
 253 #endif /* HAVE_SYNC_BUILTINS */
 254
 255
 256 /* This function implements the GUIDED scheduling method.  Arguments are
 257    as for gomp_iter_ull_static_next.  This function must be called with the
 258    work share lock held.  */
 259
 260 bool
 261 gomp_iter_ull_guided_next_locked (gomp_ull *pstart, gomp_ull *pend)
 262 {
 263   struct gomp_thread *thr = gomp_thread ();
 264   struct gomp_work_share *ws = thr->ts.work_share;
 265   struct gomp_team *team = thr->ts.team;
 266   gomp_ull nthreads = team ? team->nthreads : 1;
 267   gomp_ull n, q;
 268   gomp_ull start, end;
 269
 270   if (ws->next_ull == ws->end_ull)
 271     return false;
 272
 273   start = ws->next_ull;
 274   if (__builtin_expect (ws->mode, 0) == 0)
 275     n = (ws->end_ull - start) / ws->incr_ull;
 276   else
 277     n = (start - ws->end_ull) / -ws->incr_ull;
 278   q = (n + nthreads - 1) / nthreads;
 279
 280   if (q < ws->chunk_size_ull)
 281     q = ws->chunk_size_ull;
 282   if (q <= n)
 283     end = start + q * ws->incr_ull;
 284   else
 285     end = ws->end_ull;
 286
 287   ws->next_ull = end;
 288   *pstart = start;
 289   *pend = end;
 290   return true;
 291 }
 292
 293 #if defined HAVE_SYNC_BUILTINS && defined __LP64__
 294 /* Similar, but doesn't require the lock held, and uses compare-and-swap
 295    instead.  Note that the only memory value that changes is ws->next_ull.  */
 296
 297 bool
 298 gomp_iter_ull_guided_next (gomp_ull *pstart, gomp_ull *pend)
 299 {
 300   struct gomp_thread *thr = gomp_thread ();
 301   struct gomp_work_share *ws = thr->ts.work_share;
 302   struct gomp_team *team = thr->ts.team;
 303   gomp_ull nthreads = team ? team->nthreads : 1;
 304   gomp_ull start, end, nend, incr;
 305   gomp_ull chunk_size;
 306
 307   start = ws->next_ull;
 308   end = ws->end_ull;
 309   incr = ws->incr_ull;
 310   chunk_size = ws->chunk_size_ull;
 311
 312   while (1)
 313     {
 314       gomp_ull n, q;
 315       gomp_ull tmp;
 316
 317       if (start == end)
 318         return false;
 319
 320       if (__builtin_expect (ws->mode, 0) == 0)
 321         n = (end - start) / incr;
 322       else
 323         n = (start - end) / -incr;
 324       q = (n + nthreads - 1) / nthreads;
 325
 326       if (q < chunk_size)
 327         q = chunk_size;
 328       if (__builtin_expect (q <= n, 1))
 329         nend = start + q * incr;
 330       else
 331         nend = end;
 332
 333       tmp = __sync_val_compare_and_swap (&ws->next_ull, start, nend);
 334       if (__builtin_expect (tmp == start, 1))
 335         break;
 336
 337       start = tmp;
 338     }
 339
 340   *pstart = start;
 341   *pend = nend;
 342   return true;
 343 }
 344 #endif /* HAVE_SYNC_BUILTINS */