|
111
|
1 /* scheduler.h -*-C++-*-
|
|
|
2 *
|
|
|
3 *************************************************************************
|
|
|
4 *
|
|
|
5 * Copyright (C) 2009-2016, Intel Corporation
|
|
|
6 * All rights reserved.
|
|
|
7 *
|
|
|
8 * Redistribution and use in source and binary forms, with or without
|
|
|
9 * modification, are permitted provided that the following conditions
|
|
|
10 * are met:
|
|
|
11 *
|
|
|
12 * * Redistributions of source code must retain the above copyright
|
|
|
13 * notice, this list of conditions and the following disclaimer.
|
|
|
14 * * Redistributions in binary form must reproduce the above copyright
|
|
|
15 * notice, this list of conditions and the following disclaimer in
|
|
|
16 * the documentation and/or other materials provided with the
|
|
|
17 * distribution.
|
|
|
18 * * Neither the name of Intel Corporation nor the names of its
|
|
|
19 * contributors may be used to endorse or promote products derived
|
|
|
20 * from this software without specific prior written permission.
|
|
|
21 *
|
|
|
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
|
|
23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
|
|
24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
|
|
|
25 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
|
|
|
26 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
|
|
|
27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
|
|
|
28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
|
|
|
29 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
|
|
|
30 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
|
|
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
|
|
|
32 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
|
|
|
33 * POSSIBILITY OF SUCH DAMAGE.
|
|
|
34 *
|
|
|
35 * *********************************************************************
|
|
|
36 *
|
|
|
37 * PLEASE NOTE: This file is a downstream copy of a file mainitained in
|
|
|
38 * a repository at cilkplus.org. Changes made to this file that are not
|
|
|
39 * submitted through the contribution process detailed at
|
|
|
40 * http://www.cilkplus.org/submit-cilk-contribution will be lost the next
|
|
|
41 * time that a new version is released. Changes only submitted to the
|
|
|
42 * GNU compiler collection or posted to the git repository at
|
|
|
43 * https://bitbucket.org/intelcilkruntime/intel-cilk-runtime.git are
|
|
|
44 * not tracked.
|
|
|
45 *
|
|
|
46 * We welcome your contributions to this open source project. Thank you
|
|
|
47 * for your assistance in helping us improve Cilk Plus.
|
|
|
48 **************************************************************************/
|
|
|
49
|
|
|
50 /**
|
|
|
51 * @file scheduler.h
|
|
|
52 *
|
|
|
53 * @brief scheduler.h declares routines for the Intel Cilk Plus scheduler,
|
|
|
54 * making it the heart of the Intel Cilk Plus implementation.
|
|
|
55 */
|
|
|
56
|
|
|
57 #ifndef INCLUDED_SCHEDULER_DOT_H
|
|
|
58 #define INCLUDED_SCHEDULER_DOT_H
|
|
|
59
|
|
|
60 #include <cilk/common.h>
|
|
|
61 #include <internal/abi.h>
|
|
|
62
|
|
|
63 #include "rts-common.h"
|
|
|
64 #include "full_frame.h"
|
|
|
65 #include "reducer_impl.h"
|
|
|
66 #include "global_state.h"
|
|
|
67
|
|
|
68 #ifdef CILK_RECORD_REPLAY
|
|
|
69 #include "record-replay.h"
|
|
|
70 #endif
|
|
|
71
|
|
|
72 __CILKRTS_BEGIN_EXTERN_C
|
|
|
73
|
|
|
74
|
|
|
75 /**
|
|
|
76 * @brief Flag to disable parallel reductions.
|
|
|
77 *
|
|
|
78 * Set to 0 to allow parallel reductions.
|
|
|
79 */
|
|
|
80 #define DISABLE_PARALLEL_REDUCERS 0
|
|
|
81
|
|
|
82 /**
|
|
|
83 * @brief Debugging level for parallel reductions.
|
|
|
84 *
|
|
|
85 * Print debugging messages and assertions for parallel reducers. 0 is
|
|
|
86 * no debugging. A higher value generates more output.
|
|
|
87 */
|
|
|
88
|
|
|
89 #ifndef REDPAR_DEBUG
|
|
|
90 #define REDPAR_DEBUG 0
|
|
|
91 #endif
|
|
|
92
|
|
|
93 /**
|
|
|
94 * @brief Lock the worker mutex to allow exclusive access to the
|
|
|
95 * values in the @c __cilkrts_worker and local_state structures.
|
|
|
96 *
|
|
|
97 * @pre @c w->l->do_not_steal must not be set. Essentially this
|
|
|
98 * condition asserts that the worker is not locked recursively.
|
|
|
99 *
|
|
|
100 * @param w The worker to lock.
|
|
|
101 */
|
|
|
102 COMMON_PORTABLE
|
|
|
103 void __cilkrts_worker_lock(__cilkrts_worker *w);
|
|
|
104
|
|
|
105 /**
|
|
|
106 * @brief Unlock the worker mutex.
|
|
|
107 *
|
|
|
108 * @pre @c w->l->do_not_steal must be set. Essentially this condition
|
|
|
109 * asserts that the worker has been previously locked.
|
|
|
110 *
|
|
|
111 * @param w The worker to unlock.
|
|
|
112 */
|
|
|
113 COMMON_PORTABLE
|
|
|
114 void __cilkrts_worker_unlock(__cilkrts_worker *w);
|
|
|
115
|
|
|
116 /**
|
|
|
117 * @brief Push the next full frame to be made active in this worker
|
|
|
118 * and increment its join counter.
|
|
|
119 *
|
|
|
120 * __cilkrts_push_next_frame and pop_next_frame work on a one-element queue.
|
|
|
121 * This queue is used to communicate across the runtime from the code that
|
|
|
122 * wants to activate a frame to the code that can actually begin execution
|
|
|
123 * on that frame. They are asymetrical in that push increments the join
|
|
|
124 * counter but pop does not decrement it. Rather, a single push/pop
|
|
|
125 * combination makes a frame active and increments its join counter once.
|
|
|
126 *
|
|
|
127 * @note A system worker may chose to push work onto a user worker if
|
|
|
128 * the work is the continuation from a sync which only the user worker
|
|
|
129 * may complete.
|
|
|
130 *
|
|
|
131 * @param w The worker which the frame is to be pushed onto.
|
|
|
132 * @param ff The full_frame which is to be continued by the worker.
|
|
|
133 */
|
|
|
134 COMMON_PORTABLE
|
|
|
135 void __cilkrts_push_next_frame(__cilkrts_worker *w,
|
|
|
136 full_frame *ff);
|
|
|
137
|
|
|
138 /**
|
|
|
139 * @brief Sync on this worker.
|
|
|
140 *
|
|
|
141 * If this worker is the last to reach the sync, execution may resume
|
|
|
142 * on this worker after the sync.
|
|
|
143 *
|
|
|
144 * If this worker is not the last spawned child to reach the sync,
|
|
|
145 * then execution is suspended and the worker will re-enter the
|
|
|
146 * scheduling loop, looking for work it can steal.
|
|
|
147 *
|
|
|
148 * This function will jump into the runtime to switch to the scheduling
|
|
|
149 * stack to implement most of its logic.
|
|
|
150 *
|
|
|
151 * @param w The worker which is executing the sync.
|
|
|
152 * @param sf The __cilkrts_stack_frame containing the sync.
|
|
|
153 */
|
|
|
154 COMMON_PORTABLE
|
|
|
155 NORETURN __cilkrts_c_sync(__cilkrts_worker *w,
|
|
|
156 __cilkrts_stack_frame *sf);
|
|
|
157
|
|
|
158 /**
|
|
|
159 * @brief Worker @c w completely promotes its own deque, simulating the case
|
|
|
160 * where the whole deque is stolen.
|
|
|
161 *
|
|
|
162 * We use this mechanism to force the allocation of new storage for
|
|
|
163 * reducers for race-detection purposes.
|
|
|
164 *
|
|
|
165 * This method is called from the reducer lookup logic when
|
|
|
166 * @c g->force_reduce is set.
|
|
|
167 *
|
|
|
168 * @warning Use of "force_reduce" is known to have bugs when run with
|
|
|
169 * more than 1 worker.
|
|
|
170 *
|
|
|
171 * @param w The worker which is to have all entries in its deque
|
|
|
172 * promoted to full frames.
|
|
|
173 */
|
|
|
174 COMMON_PORTABLE
|
|
|
175 void __cilkrts_promote_own_deque(__cilkrts_worker *w);
|
|
|
176
|
|
|
177 /**
|
|
|
178 * Called when a spawned function attempts to return and
|
|
|
179 * __cilkrts_undo_detach() fails. This can happen for two reasons:
|
|
|
180 *
|
|
|
181 * @li If another worker is considering stealing our parent, it bumps the
|
|
|
182 * exception pointer while it did so, which will cause __cilkrts_undo_detach()
|
|
|
183 * to fail. If the other worker didn't complete the steal of our parent, we
|
|
|
184 * still may be able to return to it, either because the steal attempt failed,
|
|
|
185 * or we won the race for the tail pointer.
|
|
|
186 *
|
|
|
187 * @li If the function's parent has been stolen then we cannot return. Instead
|
|
|
188 * we'll longjmp into the runtime to switch onto the scheduling stack to
|
|
|
189 * execute do_return_from_spawn() and determine what to do. Either this
|
|
|
190 * worker is the last one to the sync, in which case we need to jump to the
|
|
|
191 * sync, or this worker is not the last one to the sync, in which case we'll
|
|
|
192 * abandon this work and jump to the scheduling loop to search for more work
|
|
|
193 * we can steal.
|
|
|
194 *
|
|
|
195 * @param w The worker which attempting to return from a spawn to
|
|
|
196 * a stolen parent.
|
|
|
197 * @param returning_sf The stack frame which is returning.
|
|
|
198 */
|
|
|
199 COMMON_PORTABLE
|
|
|
200 void __cilkrts_c_THE_exception_check(__cilkrts_worker *w,
|
|
|
201 __cilkrts_stack_frame *returning_sf);
|
|
|
202
|
|
|
203 /**
|
|
|
204 * @brief Return an exception to an stolen parent.
|
|
|
205 *
|
|
|
206 * Used by the gcc implementation of exceptions to return an exception
|
|
|
207 * to a stolen parent
|
|
|
208 *
|
|
|
209 * @param w The worker which attempting to return from a spawn with an
|
|
|
210 * exception to a stolen parent.
|
|
|
211 * @param returning_sf The stack frame which is returning.
|
|
|
212 */
|
|
|
213 COMMON_PORTABLE
|
|
|
214 NORETURN __cilkrts_exception_from_spawn(__cilkrts_worker *w,
|
|
|
215 __cilkrts_stack_frame *returning_sf);
|
|
|
216
|
|
|
217 /**
|
|
|
218 * @brief Used by the Windows implementations of exceptions to migrate an exception
|
|
|
219 * across fibers.
|
|
|
220 *
|
|
|
221 * Call this function when an exception has been thrown and has to
|
|
|
222 * traverse across a steal. The exception has already been wrapped
|
|
|
223 * up, so all that remains is to longjmp() into the continuation,
|
|
|
224 * sync, and re-raise it.
|
|
|
225 *
|
|
|
226 * @param sf The __cilkrts_stack_frame for the frame that is attempting to
|
|
|
227 * return an exception to a stolen parent.
|
|
|
228 */
|
|
|
229 void __cilkrts_migrate_exception (__cilkrts_stack_frame *sf);
|
|
|
230
|
|
|
231 /**
|
|
|
232 * @brief Return from a call, not a spawn, where this frame has ever
|
|
|
233 * been stolen.
|
|
|
234 *
|
|
|
235 * @param w The worker that is returning from a frame which was ever stolen.
|
|
|
236 */
|
|
|
237 COMMON_PORTABLE
|
|
|
238 void __cilkrts_return(__cilkrts_worker *w);
|
|
|
239
|
|
|
240 /**
|
|
|
241 * @brief Special return from the initial frame.
|
|
|
242 *
|
|
|
243 * This method will be called from @c __cilkrts_leave_frame if
|
|
|
244 * @c CILK_FRAME_LAST is set.
|
|
|
245 *
|
|
|
246 * This function will do the things necessary to cleanup, and unbind the
|
|
|
247 * thread from the Intel Cilk Plus runtime. If this is the last user
|
|
|
248 * worker unbinding from the runtime, all system worker threads will be
|
|
|
249 * suspended.
|
|
|
250 *
|
|
|
251 * @pre @c w must be the currently executing worker, and must be a user
|
|
|
252 * worker.
|
|
|
253 *
|
|
|
254 * @param w The worker that's returning from the initial frame.
|
|
|
255 */
|
|
|
256 COMMON_PORTABLE
|
|
|
257 void __cilkrts_c_return_from_initial(__cilkrts_worker *w);
|
|
|
258
|
|
|
259 /**
|
|
|
260 * @brief Used by exception handling code to pop an entry from the
|
|
|
261 * worker's deque.
|
|
|
262 *
|
|
|
263 * @param w Worker to pop the entry from
|
|
|
264 *
|
|
|
265 * @return __cilkrts_stack_frame of parent call
|
|
|
266 * @return NULL if the deque is empty
|
|
|
267 */
|
|
|
268 COMMON_PORTABLE
|
|
|
269 __cilkrts_stack_frame *__cilkrts_pop_tail(__cilkrts_worker *w);
|
|
|
270
|
|
|
271 /**
|
|
|
272 * @brief Modifies the worker's protected_tail to prevent frames from
|
|
|
273 * being stolen.
|
|
|
274 *
|
|
|
275 * The Dekker protocol has been extended to only steal if head+1 is also
|
|
|
276 * less than protected_tail.
|
|
|
277 *
|
|
|
278 * @param w The worker to be modified.
|
|
|
279 * @param new_protected_tail The new setting for protected_tail, or NULL if the
|
|
|
280 * entire deque is to be protected
|
|
|
281 *
|
|
|
282 * @return Previous value of protected tail.
|
|
|
283 */
|
|
|
284 COMMON_PORTABLE
|
|
|
285 __cilkrts_stack_frame *volatile *__cilkrts_disallow_stealing(
|
|
|
286 __cilkrts_worker *w,
|
|
|
287 __cilkrts_stack_frame *volatile *new_protected_tail);
|
|
|
288
|
|
|
289 /**
|
|
|
290 * @brief Restores the protected tail to a previous state, possibly
|
|
|
291 * allowing frames to be stolen.
|
|
|
292 *
|
|
|
293 * @param w The worker to be modified.
|
|
|
294 * @param saved_protected_tail A previous setting for protected_tail that is
|
|
|
295 * to be restored
|
|
|
296 */
|
|
|
297 COMMON_PORTABLE
|
|
|
298 void __cilkrts_restore_stealing(
|
|
|
299 __cilkrts_worker *w,
|
|
|
300 __cilkrts_stack_frame *volatile *saved_protected_tail);
|
|
|
301
|
|
|
302 /**
|
|
|
303 * @brief Initialize a @c __cilkrts_worker.
|
|
|
304 *
|
|
|
305 * @note The memory for the worker must have been allocated outside
|
|
|
306 * this call.
|
|
|
307 *
|
|
|
308 * @param g The global_state_t.
|
|
|
309 * @param self The index into the global_state's array of workers for this
|
|
|
310 * worker, or -1 if this worker was allocated from the heap and cannot be
|
|
|
311 * stolen from.
|
|
|
312 * @param w The worker to be initialized.
|
|
|
313 *
|
|
|
314 * @return The initialized __cilkrts_worker.
|
|
|
315 */
|
|
|
316 COMMON_PORTABLE
|
|
|
317 __cilkrts_worker *make_worker(global_state_t *g,
|
|
|
318 int self,
|
|
|
319 __cilkrts_worker *w);
|
|
|
320
|
|
|
321 /**
|
|
|
322 * @brief Free up any resources allocated for a worker.
|
|
|
323 *
|
|
|
324 * @note The memory for the @c __cilkrts_worker itself must be
|
|
|
325 * deallocated outside this call.
|
|
|
326 *
|
|
|
327 * @param w The worker to be destroyed.
|
|
|
328 */
|
|
|
329 COMMON_PORTABLE
|
|
|
330 void destroy_worker (__cilkrts_worker *w);
|
|
|
331
|
|
|
332 /**
|
|
|
333 * @brief Initialize the runtime.
|
|
|
334 *
|
|
|
335 * If necessary, allocates and initializes the global state. If
|
|
|
336 * necessary, unsuspends the system workers.
|
|
|
337 *
|
|
|
338 * @param start Specifies whether the workers are to be unsuspended if
|
|
|
339 * they are suspended. Allows __cilkrts_init() to start up the runtime without
|
|
|
340 * releasing the system threads.
|
|
|
341 */
|
|
|
342 COMMON_PORTABLE
|
|
|
343 void __cilkrts_init_internal(int start);
|
|
|
344
|
|
|
345 /**
|
|
|
346 * @brief Part of the sequence to shutdown the runtime.
|
|
|
347 *
|
|
|
348 * Specifically, this call frees the @c global_state_t for the runtime.
|
|
|
349 *
|
|
|
350 * @param g The global_state_t.
|
|
|
351 */
|
|
|
352 COMMON_PORTABLE
|
|
|
353 void __cilkrts_deinit_internal(global_state_t *g);
|
|
|
354
|
|
|
355 /**
|
|
|
356 * Obsolete. We no longer need to import or export reducer maps.
|
|
|
357 */
|
|
|
358 COMMON_PORTABLE
|
|
|
359 cilkred_map *__cilkrts_xchg_reducer(
|
|
|
360 __cilkrts_worker *w, cilkred_map *newmap) cilk_nothrow;
|
|
|
361
|
|
|
362 /**
|
|
|
363 * @brief Called when a user thread is bound to the runtime.
|
|
|
364 *
|
|
|
365 * If this action increments the count of bound user threads from 0 to
|
|
|
366 * 1, the system worker threads are unsuspended.
|
|
|
367 *
|
|
|
368 * If this action increments the count of bound user threads from 0 to
|
|
|
369 * 1, the system worker threads are unsuspended.
|
|
|
370 *
|
|
|
371 * @pre Global lock must be held.
|
|
|
372 * @param g The runtime global state.
|
|
|
373 */
|
|
|
374 COMMON_PORTABLE
|
|
|
375 void __cilkrts_enter_cilk(global_state_t *g);
|
|
|
376
|
|
|
377 /**
|
|
|
378 * @brief Called when a user thread is unbound from the runtime.
|
|
|
379 *
|
|
|
380 * If this action decrements the count of bound user threads to 0, the
|
|
|
381 * system worker threads are suspended.
|
|
|
382 *
|
|
|
383 *
|
|
|
384 * @pre Global lock must be held.
|
|
|
385 *
|
|
|
386 * @param g The runtime global state.
|
|
|
387 */
|
|
|
388 COMMON_PORTABLE
|
|
|
389 void __cilkrts_leave_cilk(global_state_t *g);
|
|
|
390
|
|
|
391
|
|
|
392 /**
|
|
|
393 * @brief cilk_fiber_proc that runs the main scheduler loop on a
|
|
|
394 * user worker.
|
|
|
395 *
|
|
|
396 * @pre fiber's owner field should be set to the correct __cilkrts_worker
|
|
|
397 * @pre fiber must be a user worker.
|
|
|
398 *
|
|
|
399 * @param fiber The scheduling fiber object.
|
|
|
400 */
|
|
|
401 void scheduler_fiber_proc_for_user_worker(cilk_fiber *fiber);
|
|
|
402
|
|
|
403
|
|
|
404 /**
|
|
|
405 * @brief Prints out Cilk runtime statistics.
|
|
|
406 *
|
|
|
407 * @param g The runtime global state.
|
|
|
408 *
|
|
|
409 * This method is useful only for debugging purposes. No guarantees
|
|
|
410 * are made as to the validity of this data. :)
|
|
|
411 */
|
|
|
412 COMMON_PORTABLE
|
|
|
413 void __cilkrts_dump_stats_to_stderr(global_state_t *g);
|
|
|
414
|
|
|
415 #ifdef CILK_RECORD_REPLAY
|
|
|
416 COMMON_PORTABLE
|
|
|
417 char * walk_pedigree_nodes(char *p, const __cilkrts_pedigree *pnode);
|
|
|
418
|
|
|
419 /**
|
|
|
420 * @brief Used by exception handling code to simulate the popping of
|
|
|
421 * an entry from the worker's deque.
|
|
|
422 *
|
|
|
423 * @param w Worker whose deque we want to check
|
|
|
424 *
|
|
|
425 * @return @c __cilkrts_stack_frame of parent call
|
|
|
426 * @return NULL if the deque is empty
|
|
|
427 */
|
|
|
428 COMMON_PORTABLE
|
|
|
429 __cilkrts_stack_frame *simulate_pop_tail(__cilkrts_worker *w);
|
|
|
430
|
|
|
431 #endif
|
|
|
432
|
|
|
433 __CILKRTS_END_EXTERN_C
|
|
|
434
|
|
|
435 #endif // ! defined(INCLUDED_SCHEDULER_DOT_H)
|
