|
0
|
1 /* Copyright (C) 2005, 2008, 2009 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
|
|
|
32 /* This function implements the STATIC scheduling method. The caller should
|
|
|
33 iterate *pstart <= x < *pend. Return zero if there are more iterations
|
|
|
34 to perform; nonzero if not. Return less than 0 if this thread had
|
|
|
35 received the absolutely last iteration. */
|
|
|
36
|
|
|
37 int
|
|
|
38 gomp_iter_static_next (long *pstart, long *pend)
|
|
|
39 {
|
|
|
40 struct gomp_thread *thr = gomp_thread ();
|
|
|
41 struct gomp_team *team = thr->ts.team;
|
|
|
42 struct gomp_work_share *ws = thr->ts.work_share;
|
|
|
43 unsigned long nthreads = team ? team->nthreads : 1;
|
|
|
44
|
|
|
45 if (thr->ts.static_trip == -1)
|
|
|
46 return -1;
|
|
|
47
|
|
|
48 /* Quick test for degenerate teams and orphaned constructs. */
|
|
|
49 if (nthreads == 1)
|
|
|
50 {
|
|
|
51 *pstart = ws->next;
|
|
|
52 *pend = ws->end;
|
|
|
53 thr->ts.static_trip = -1;
|
|
|
54 return ws->next == ws->end;
|
|
|
55 }
|
|
|
56
|
|
|
57 /* We interpret chunk_size zero as "unspecified", which means that we
|
|
|
58 should break up the iterations such that each thread makes only one
|
|
|
59 trip through the outer loop. */
|
|
|
60 if (ws->chunk_size == 0)
|
|
|
61 {
|
|
|
62 unsigned long n, q, i;
|
|
|
63 unsigned long s0, e0;
|
|
|
64 long s, e;
|
|
|
65
|
|
|
66 if (thr->ts.static_trip > 0)
|
|
|
67 return 1;
|
|
|
68
|
|
|
69 /* Compute the total number of iterations. */
|
|
|
70 s = ws->incr + (ws->incr > 0 ? -1 : 1);
|
|
|
71 n = (ws->end - ws->next + s) / ws->incr;
|
|
|
72 i = thr->ts.team_id;
|
|
|
73
|
|
|
74 /* Compute the "zero-based" start and end points. That is, as
|
|
|
75 if the loop began at zero and incremented by one. */
|
|
|
76 q = n / nthreads;
|
|
|
77 q += (q * nthreads != n);
|
|
|
78 s0 = q * i;
|
|
|
79 e0 = s0 + q;
|
|
|
80 if (e0 > n)
|
|
|
81 e0 = n;
|
|
|
82
|
|
|
83 /* Notice when no iterations allocated for this thread. */
|
|
|
84 if (s0 >= e0)
|
|
|
85 {
|
|
|
86 thr->ts.static_trip = 1;
|
|
|
87 return 1;
|
|
|
88 }
|
|
|
89
|
|
|
90 /* Transform these to the actual start and end numbers. */
|
|
|
91 s = (long)s0 * ws->incr + ws->next;
|
|
|
92 e = (long)e0 * ws->incr + ws->next;
|
|
|
93
|
|
|
94 *pstart = s;
|
|
|
95 *pend = e;
|
|
|
96 thr->ts.static_trip = (e0 == n ? -1 : 1);
|
|
|
97 return 0;
|
|
|
98 }
|
|
|
99 else
|
|
|
100 {
|
|
|
101 unsigned long n, s0, e0, i, c;
|
|
|
102 long s, e;
|
|
|
103
|
|
|
104 /* Otherwise, each thread gets exactly chunk_size iterations
|
|
|
105 (if available) each time through the loop. */
|
|
|
106
|
|
|
107 s = ws->incr + (ws->incr > 0 ? -1 : 1);
|
|
|
108 n = (ws->end - ws->next + s) / ws->incr;
|
|
|
109 i = thr->ts.team_id;
|
|
|
110 c = ws->chunk_size;
|
|
|
111
|
|
|
112 /* Initial guess is a C sized chunk positioned nthreads iterations
|
|
|
113 in, offset by our thread number. */
|
|
|
114 s0 = (thr->ts.static_trip * nthreads + i) * c;
|
|
|
115 e0 = s0 + c;
|
|
|
116
|
|
|
117 /* Detect overflow. */
|
|
|
118 if (s0 >= n)
|
|
|
119 return 1;
|
|
|
120 if (e0 > n)
|
|
|
121 e0 = n;
|
|
|
122
|
|
|
123 /* Transform these to the actual start and end numbers. */
|
|
|
124 s = (long)s0 * ws->incr + ws->next;
|
|
|
125 e = (long)e0 * ws->incr + ws->next;
|
|
|
126
|
|
|
127 *pstart = s;
|
|
|
128 *pend = e;
|
|
|
129
|
|
|
130 if (e0 == n)
|
|
|
131 thr->ts.static_trip = -1;
|
|
|
132 else
|
|
|
133 thr->ts.static_trip++;
|
|
|
134 return 0;
|
|
|
135 }
|
|
|
136 }
|
|
|
137
|
|
|
138
|
|
|
139 /* This function implements the DYNAMIC scheduling method. Arguments are
|
|
|
140 as for gomp_iter_static_next. This function must be called with ws->lock
|
|
|
141 held. */
|
|
|
142
|
|
|
143 bool
|
|
|
144 gomp_iter_dynamic_next_locked (long *pstart, long *pend)
|
|
|
145 {
|
|
|
146 struct gomp_thread *thr = gomp_thread ();
|
|
|
147 struct gomp_work_share *ws = thr->ts.work_share;
|
|
|
148 long start, end, chunk, left;
|
|
|
149
|
|
|
150 start = ws->next;
|
|
|
151 if (start == ws->end)
|
|
|
152 return false;
|
|
|
153
|
|
|
154 chunk = ws->chunk_size;
|
|
|
155 left = ws->end - start;
|
|
|
156 if (ws->incr < 0)
|
|
|
157 {
|
|
|
158 if (chunk < left)
|
|
|
159 chunk = left;
|
|
|
160 }
|
|
|
161 else
|
|
|
162 {
|
|
|
163 if (chunk > left)
|
|
|
164 chunk = left;
|
|
|
165 }
|
|
|
166 end = start + chunk;
|
|
|
167
|
|
|
168 ws->next = end;
|
|
|
169 *pstart = start;
|
|
|
170 *pend = end;
|
|
|
171 return true;
|
|
|
172 }
|
|
|
173
|
|
|
174
|
|
|
175 #ifdef HAVE_SYNC_BUILTINS
|
|
|
176 /* Similar, but doesn't require the lock held, and uses compare-and-swap
|
|
|
177 instead. Note that the only memory value that changes is ws->next. */
|
|
|
178
|
|
|
179 bool
|
|
|
180 gomp_iter_dynamic_next (long *pstart, long *pend)
|
|
|
181 {
|
|
|
182 struct gomp_thread *thr = gomp_thread ();
|
|
|
183 struct gomp_work_share *ws = thr->ts.work_share;
|
|
|
184 long start, end, nend, chunk, incr;
|
|
|
185
|
|
|
186 end = ws->end;
|
|
|
187 incr = ws->incr;
|
|
|
188 chunk = ws->chunk_size;
|
|
|
189
|
|
|
190 if (__builtin_expect (ws->mode, 1))
|
|
|
191 {
|
|
|
192 long tmp = __sync_fetch_and_add (&ws->next, chunk);
|
|
|
193 if (incr > 0)
|
|
|
194 {
|
|
|
195 if (tmp >= end)
|
|
|
196 return false;
|
|
|
197 nend = tmp + chunk;
|
|
|
198 if (nend > end)
|
|
|
199 nend = end;
|
|
|
200 *pstart = tmp;
|
|
|
201 *pend = nend;
|
|
|
202 return true;
|
|
|
203 }
|
|
|
204 else
|
|
|
205 {
|
|
|
206 if (tmp <= end)
|
|
|
207 return false;
|
|
|
208 nend = tmp + chunk;
|
|
|
209 if (nend < end)
|
|
|
210 nend = end;
|
|
|
211 *pstart = tmp;
|
|
|
212 *pend = nend;
|
|
|
213 return true;
|
|
|
214 }
|
|
|
215 }
|
|
|
216
|
|
|
217 start = ws->next;
|
|
|
218 while (1)
|
|
|
219 {
|
|
|
220 long left = end - start;
|
|
|
221 long tmp;
|
|
|
222
|
|
|
223 if (start == end)
|
|
|
224 return false;
|
|
|
225
|
|
|
226 if (incr < 0)
|
|
|
227 {
|
|
|
228 if (chunk < left)
|
|
|
229 chunk = left;
|
|
|
230 }
|
|
|
231 else
|
|
|
232 {
|
|
|
233 if (chunk > left)
|
|
|
234 chunk = left;
|
|
|
235 }
|
|
|
236 nend = start + chunk;
|
|
|
237
|
|
|
238 tmp = __sync_val_compare_and_swap (&ws->next, start, nend);
|
|
|
239 if (__builtin_expect (tmp == start, 1))
|
|
|
240 break;
|
|
|
241
|
|
|
242 start = tmp;
|
|
|
243 }
|
|
|
244
|
|
|
245 *pstart = start;
|
|
|
246 *pend = nend;
|
|
|
247 return true;
|
|
|
248 }
|
|
|
249 #endif /* HAVE_SYNC_BUILTINS */
|
|
|
250
|
|
|
251
|
|
|
252 /* This function implements the GUIDED scheduling method. Arguments are
|
|
|
253 as for gomp_iter_static_next. This function must be called with the
|
|
|
254 work share lock held. */
|
|
|
255
|
|
|
256 bool
|
|
|
257 gomp_iter_guided_next_locked (long *pstart, long *pend)
|
|
|
258 {
|
|
|
259 struct gomp_thread *thr = gomp_thread ();
|
|
|
260 struct gomp_work_share *ws = thr->ts.work_share;
|
|
|
261 struct gomp_team *team = thr->ts.team;
|
|
|
262 unsigned long nthreads = team ? team->nthreads : 1;
|
|
|
263 unsigned long n, q;
|
|
|
264 long start, end;
|
|
|
265
|
|
|
266 if (ws->next == ws->end)
|
|
|
267 return false;
|
|
|
268
|
|
|
269 start = ws->next;
|
|
|
270 n = (ws->end - start) / ws->incr;
|
|
|
271 q = (n + nthreads - 1) / nthreads;
|
|
|
272
|
|
|
273 if (q < ws->chunk_size)
|
|
|
274 q = ws->chunk_size;
|
|
|
275 if (q <= n)
|
|
|
276 end = start + q * ws->incr;
|
|
|
277 else
|
|
|
278 end = ws->end;
|
|
|
279
|
|
|
280 ws->next = end;
|
|
|
281 *pstart = start;
|
|
|
282 *pend = end;
|
|
|
283 return true;
|
|
|
284 }
|
|
|
285
|
|
|
286 #ifdef HAVE_SYNC_BUILTINS
|
|
|
287 /* Similar, but doesn't require the lock held, and uses compare-and-swap
|
|
|
288 instead. Note that the only memory value that changes is ws->next. */
|
|
|
289
|
|
|
290 bool
|
|
|
291 gomp_iter_guided_next (long *pstart, long *pend)
|
|
|
292 {
|
|
|
293 struct gomp_thread *thr = gomp_thread ();
|
|
|
294 struct gomp_work_share *ws = thr->ts.work_share;
|
|
|
295 struct gomp_team *team = thr->ts.team;
|
|
|
296 unsigned long nthreads = team ? team->nthreads : 1;
|
|
|
297 long start, end, nend, incr;
|
|
|
298 unsigned long chunk_size;
|
|
|
299
|
|
|
300 start = ws->next;
|
|
|
301 end = ws->end;
|
|
|
302 incr = ws->incr;
|
|
|
303 chunk_size = ws->chunk_size;
|
|
|
304
|
|
|
305 while (1)
|
|
|
306 {
|
|
|
307 unsigned long n, q;
|
|
|
308 long tmp;
|
|
|
309
|
|
|
310 if (start == end)
|
|
|
311 return false;
|
|
|
312
|
|
|
313 n = (end - start) / incr;
|
|
|
314 q = (n + nthreads - 1) / nthreads;
|
|
|
315
|
|
|
316 if (q < chunk_size)
|
|
|
317 q = chunk_size;
|
|
|
318 if (__builtin_expect (q <= n, 1))
|
|
|
319 nend = start + q * incr;
|
|
|
320 else
|
|
|
321 nend = end;
|
|
|
322
|
|
|
323 tmp = __sync_val_compare_and_swap (&ws->next, start, nend);
|
|
|
324 if (__builtin_expect (tmp == start, 1))
|
|
|
325 break;
|
|
|
326
|
|
|
327 start = tmp;
|
|
|
328 }
|
|
|
329
|
|
|
330 *pstart = start;
|
|
|
331 *pend = nend;
|
|
|
332 return true;
|
|
|
333 }
|
|
|
334 #endif /* HAVE_SYNC_BUILTINS */
|
