Debian Codegraph @

rts/c/scheduler.h

raw
1 // start of scheduler.h
2
3 // First, the API that the generated code will access. In principle,
4 // we could then compile the scheduler separately and link an object
5 // file with the generated code. In practice, we will embed all of
6 // this in the generated code.
7
8 // Scheduler handle.
9 struct scheduler;
10
11 // Initialise a scheduler (and start worker threads).
12 static int scheduler_init(struct scheduler *scheduler,
13 int num_workers,
14 double kappa);
15
16 // Shut down a scheduler (and destroy worker threads).
17 static int scheduler_destroy(struct scheduler *scheduler);
18
19 // Figure out the smallest amount of work that amortises task
20 // creation.
21 static int determine_kappa(double *kappa);
22
23 // How a segop should be scheduled.
24 enum scheduling {
25 DYNAMIC,
26 STATIC
27 };
28
29 // How a given task should be executed. Filled out by the scheduler
30 // and passed to the segop function
31 struct scheduler_info {
32 int64_t iter_pr_subtask;
33 int64_t remainder;
34 int nsubtasks;
35 enum scheduling sched;
36 int wake_up_threads;
37
38 int64_t *task_time;
39 int64_t *task_iter;
40 };
41
42 // A segop function. This is what you hand the scheduler for
43 // execution.
44 typedef int (*segop_fn)(void* args,
45 int64_t iterations,
46 int tid,
47 struct scheduler_info info);
48
49 // A task for the scheduler to execute.
50 struct scheduler_segop {
51 void *args;
52 segop_fn top_level_fn;
53 segop_fn nested_fn;
54 int64_t iterations;
55 enum scheduling sched;
56
57 // Pointers to timer and iter associated with the task
58 int64_t *task_time;
59 int64_t *task_iter;
60
61 // For debugging
62 const char* name;
63 };
64
65 static inline int scheduler_prepare_task(struct scheduler *scheduler,
66 struct scheduler_segop *task);
67
68 typedef int (*parloop_fn)(void* args,
69 int64_t start,
70 int64_t end,
71 int subtask_id,
72 int tid);
73
74 // A parallel parloop task.
75 struct scheduler_parloop {
76 void* args;
77 parloop_fn fn;
78 int64_t iterations;
79 struct scheduler_info info;
80
81 // For debugging
82 const char* name;
83 };
84
85 static inline int scheduler_execute_task(struct scheduler *scheduler,
86 struct scheduler_parloop *task);
87
88 // Then the API implementation.
89
90 #include <signal.h>
91
92 #if defined(_WIN32)
93 #include <windows.h>
94 #elif defined(__APPLE__)
95 #include <sys/sysctl.h>
96 // For getting cpu usage of threads
97 #include <mach/mach.h>
98 #include <sys/resource.h>
99 #elif defined(__linux__)
100 #include <sys/sysinfo.h>
101 #include <sys/resource.h>
102 #include <signal.h>
103 #elif defined(__EMSCRIPTEN__)
104 #include <emscripten/threading.h>
105 #include <sys/sysinfo.h>
106 #include <sys/resource.h>
107 #include <signal.h>
108 #endif
109
110 /* Multicore Utility functions */
111
112 /* A wrapper for getting rusage on Linux and MacOS */
113 /* TODO maybe figure out this for windows */
114 static inline int getrusage_thread(struct rusage *rusage)
115 {
116 int err = -1;
117 #if defined(__APPLE__)
118 thread_basic_info_data_t info = { 0 };
119 mach_msg_type_number_t info_count = THREAD_BASIC_INFO_COUNT;
120 kern_return_t kern_err;
121
122 kern_err = thread_info(mach_thread_self(),
123 THREAD_BASIC_INFO,
124 (thread_info_t)&info,
125 &info_count);
126 if (kern_err == KERN_SUCCESS) {
127 memset(rusage, 0, sizeof(struct rusage));
128 rusage->ru_utime.tv_sec = info.user_time.seconds;
129 rusage->ru_utime.tv_usec = info.user_time.microseconds;
130 rusage->ru_stime.tv_sec = info.system_time.seconds;
131 rusage->ru_stime.tv_usec = info.system_time.microseconds;
132 err = 0;
133 } else {
134 errno = EINVAL;
135 }
136 #elif defined(__linux__) || __EMSCRIPTEN__
137 err = getrusage(RUSAGE_THREAD, rusage);
138 #endif
139 return err;
140 }
141
142 /* returns the number of logical cores */
143 static int num_processors(void) {
144 #if defined(_WIN32)
145 /* https://docs.microsoft.com/en-us/windows/win32/api/sysinfoapi/ns-sysinfoapi-system_info */
146 SYSTEM_INFO sysinfo;
147 GetSystemInfo(&sysinfo);
148 int ncores = sysinfo.dwNumberOfProcessors;
149 fprintf(stderr, "Found %d cores on your Windows machine\n Is that correct?\n", ncores);
150 return ncores;
151 #elif defined(__APPLE__)
152 int ncores;
153 size_t ncores_size = sizeof(ncores);
154 CHECK_ERRNO(sysctlbyname("hw.logicalcpu", &ncores, &ncores_size, NULL, 0),
155 "sysctlbyname (hw.logicalcpu)");
156 return ncores;
157 #elif defined(__linux__)
158 return get_nprocs();
159 #elif __EMSCRIPTEN__
160 return emscripten_num_logical_cores();
161 #else
162 fprintf(stderr, "operating system not recognised\n");
163 return -1;
164 #endif
165 }
166
167 static unsigned int g_seed;
168
169 // Used to seed the generator.
170 static inline void fast_srand(unsigned int seed) {
171 g_seed = seed;
172 }
173
174 // Compute a pseudorandom integer.
175 // Output value in range [0, 32767]
176 static inline unsigned int fast_rand(void) {
177 g_seed = (214013*g_seed+2531011);
178 return (g_seed>>16)&0x7FFF;
179 }
180
181 struct subtask_queue {
182 int capacity; // Size of the buffer.
183 int first; // Index of the start of the ring buffer.
184 int num_used; // Number of used elements in the buffer.
185 struct subtask **buffer;
186
187 pthread_mutex_t mutex; // Mutex used for synchronisation.
188 pthread_cond_t cond; // Condition variable used for synchronisation.
189 int dead;
190
191 #if defined(MCPROFILE)
192 /* Profiling fields */
193 uint64_t time_enqueue;
194 uint64_t time_dequeue;
195 uint64_t n_dequeues;
196 uint64_t n_enqueues;
197 #endif
198 };
199
200 /* A subtask that can be executed by a worker */
201 struct subtask {
202 /* The parloop function */
203 parloop_fn fn;
204 /* Execution parameters */
205 void* args;
206 int64_t start, end;
207 int id;
208
209 /* Dynamic scheduling parameters */
210 int chunkable;
211 int64_t chunk_size;
212
213 /* Shared variables across subtasks */
214 volatile int *counter; // Counter for ongoing subtasks
215 // Shared task timers and iterators
216 int64_t *task_time;
217 int64_t *task_iter;
218
219 /* For debugging */
220 const char *name;
221 };
222
223
224 struct worker {
225 pthread_t thread;
226 struct scheduler *scheduler; /* Reference to the scheduler struct the worker belongs to*/
227 struct subtask_queue q;
228 int dead;
229 int tid; /* Just a thread id */
230
231 /* "thread local" time fields used for online algorithm */
232 uint64_t timer;
233 uint64_t total;
234 int nested; /* How nested the current computation is */
235
236 // Profiling fields
237 int output_usage; /* Whether to dump thread usage */
238 uint64_t time_spent_working; /* Time spent in parloop functions */
239 };
240
241 static inline void output_worker_usage(struct worker *worker)
242 {
243 struct rusage usage;
244 CHECK_ERRNO(getrusage_thread(&usage), "getrusage_thread");
245 struct timeval user_cpu_time = usage.ru_utime;
246 struct timeval sys_cpu_time = usage.ru_stime;
247 fprintf(stderr, "tid: %2d - work time %10llu us - user time: %10llu us - sys: %10llu us\n",
248 worker->tid,
249 (long long unsigned)worker->time_spent_working / 1000,
250 (long long unsigned)(user_cpu_time.tv_sec * 1000000 + user_cpu_time.tv_usec),
251 (long long unsigned)(sys_cpu_time.tv_sec * 1000000 + sys_cpu_time.tv_usec));
252 }
253
254 /* Doubles the size of the queue */
255 static inline int subtask_queue_grow_queue(struct subtask_queue *subtask_queue) {
256
257 int new_capacity = 2 * subtask_queue->capacity;
258 #ifdef MCDEBUG
259 fprintf(stderr, "Growing queue to %d\n", subtask_queue->capacity * 2);
260 #endif
261
262 struct subtask **new_buffer = calloc(new_capacity, sizeof(struct subtask*));
263 for (int i = 0; i < subtask_queue->num_used; i++) {
264 new_buffer[i] = subtask_queue->buffer[(subtask_queue->first + i) % subtask_queue->capacity];
265 }
266
267 free(subtask_queue->buffer);
268 subtask_queue->buffer = new_buffer;
269 subtask_queue->capacity = new_capacity;
270 subtask_queue->first = 0;
271
272 return 0;
273 }
274
275 // Initialise a job queue with the given capacity. The queue starts out
276 // empty. Returns non-zero on error.
277 static inline int subtask_queue_init(struct subtask_queue *subtask_queue, int capacity)
278 {
279 assert(subtask_queue != NULL);
280 memset(subtask_queue, 0, sizeof(struct subtask_queue));
281
282 subtask_queue->capacity = capacity;
283 subtask_queue->buffer = calloc(capacity, sizeof(struct subtask*));
284 if (subtask_queue->buffer == NULL) {
285 return -1;
286 }
287
288 CHECK_ERRNO(pthread_mutex_init(&subtask_queue->mutex, NULL), "pthread_mutex_init");
289 CHECK_ERRNO(pthread_cond_init(&subtask_queue->cond, NULL), "pthread_cond_init");
290
291 return 0;
292 }
293
294 // Destroy the job queue. Blocks until the queue is empty before it
295 // is destroyed.
296 static inline int subtask_queue_destroy(struct subtask_queue *subtask_queue)
297 {
298 assert(subtask_queue != NULL);
299
300 CHECK_ERR(pthread_mutex_lock(&subtask_queue->mutex), "pthread_mutex_lock");
301
302 while (subtask_queue->num_used != 0) {
303 CHECK_ERR(pthread_cond_wait(&subtask_queue->cond, &subtask_queue->mutex), "pthread_cond_wait");
304 }
305
306 // Queue is now empty. Let's kill it!
307 subtask_queue->dead = 1;
308 free(subtask_queue->buffer);
309 CHECK_ERR(pthread_cond_broadcast(&subtask_queue->cond), "pthread_cond_broadcast");
310 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
311
312 return 0;
313 }
314
315 static inline void dump_queue(struct worker *worker)
316 {
317 struct subtask_queue *subtask_queue = &worker->q;
318 CHECK_ERR(pthread_mutex_lock(&subtask_queue->mutex), "pthread_mutex_lock");
319 for (int i = 0; i < subtask_queue->num_used; i++) {
320 struct subtask * subtask = subtask_queue->buffer[(subtask_queue->first + i) % subtask_queue->capacity];
321 printf("queue tid %d with %d task %s\n", worker->tid, i, subtask->name);
322 }
323 CHECK_ERR(pthread_cond_broadcast(&subtask_queue->cond), "pthread_cond_broadcast");
324 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
325 }
326
327 // Push an element onto the end of the job queue. Blocks if the
328 // subtask_queue is full (its size is equal to its capacity). Returns
329 // non-zero on error. It is an error to push a job onto a queue that
330 // has been destroyed.
331 static inline int subtask_queue_enqueue(struct worker *worker, struct subtask *subtask )
332 {
333 assert(worker != NULL);
334 struct subtask_queue *subtask_queue = &worker->q;
335
336 #ifdef MCPROFILE
337 uint64_t start = get_wall_time();
338 #endif
339
340 CHECK_ERR(pthread_mutex_lock(&subtask_queue->mutex), "pthread_mutex_lock");
341 // Wait until there is room in the subtask_queue.
342 while (subtask_queue->num_used == subtask_queue->capacity && !subtask_queue->dead) {
343 if (subtask_queue->num_used == subtask_queue->capacity) {
344 CHECK_ERR(subtask_queue_grow_queue(subtask_queue), "subtask_queue_grow_queue");
345 continue;
346 }
347 CHECK_ERR(pthread_cond_wait(&subtask_queue->cond, &subtask_queue->mutex), "pthread_cond_wait");
348 }
349
350 if (subtask_queue->dead) {
351 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
352 return -1;
353 }
354
355 // If we made it past the loop, there is room in the subtask_queue.
356 subtask_queue->buffer[(subtask_queue->first + subtask_queue->num_used) % subtask_queue->capacity] = subtask;
357 subtask_queue->num_used++;
358
359 #ifdef MCPROFILE
360 uint64_t end = get_wall_time();
361 subtask_queue->time_enqueue += (end - start);
362 subtask_queue->n_enqueues++;
363 #endif
364 // Broadcast a reader (if any) that there is now an element.
365 CHECK_ERR(pthread_cond_broadcast(&subtask_queue->cond), "pthread_cond_broadcast");
366 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
367
368 return 0;
369 }
370
371
372 /* Like subtask_queue_dequeue, but with two differences:
373 1) the subtask is stolen from the __front__ of the queue
374 2) returns immediately if there is no subtasks queued,
375 as we dont' want to block on another workers queue and
376 */
377 static inline int subtask_queue_steal(struct worker *worker,
378 struct subtask **subtask)
379 {
380 struct subtask_queue *subtask_queue = &worker->q;
381 assert(subtask_queue != NULL);
382
383 #ifdef MCPROFILE
384 uint64_t start = get_wall_time();
385 #endif
386 CHECK_ERR(pthread_mutex_lock(&subtask_queue->mutex), "pthread_mutex_lock");
387
388 if (subtask_queue->num_used == 0) {
389 CHECK_ERR(pthread_cond_broadcast(&subtask_queue->cond), "pthread_cond_broadcast");
390 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
391 return 1;
392 }
393
394 if (subtask_queue->dead) {
395 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
396 return -1;
397 }
398
399 // Tasks gets stolen from the "front"
400 struct subtask *cur_back = subtask_queue->buffer[subtask_queue->first];
401 struct subtask *new_subtask = NULL;
402 int remaining_iter = cur_back->end - cur_back->start;
403 // If subtask is chunkable, we steal half of the iterations
404 if (cur_back->chunkable && remaining_iter > 1) {
405 int64_t half = remaining_iter / 2;
406 new_subtask = malloc(sizeof(struct subtask));
407 *new_subtask = *cur_back;
408 new_subtask->start = cur_back->end - half;
409 cur_back->end = new_subtask->start;
410 __atomic_fetch_add(cur_back->counter, 1, __ATOMIC_RELAXED);
411 } else {
412 new_subtask = cur_back;
413 subtask_queue->num_used--;
414 subtask_queue->first = (subtask_queue->first + 1) % subtask_queue->capacity;
415 }
416 *subtask = new_subtask;
417
418 if (*subtask == NULL) {
419 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthred_mutex_unlock");
420 return 1;
421 }
422
423 #ifdef MCPROFILE
424 uint64_t end = get_wall_time();
425 subtask_queue->time_dequeue += (end - start);
426 subtask_queue->n_dequeues++;
427 #endif
428
429 // Broadcast a writer (if any) that there is now room for more.
430 CHECK_ERR(pthread_cond_broadcast(&subtask_queue->cond), "pthread_cond_broadcast");
431 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
432
433 return 0;
434 }
435
436
437 // Pop an element from the back of the job queue.
438 // Optional argument can be provided to block or not
439 static inline int subtask_queue_dequeue(struct worker *worker,
440 struct subtask **subtask, int blocking)
441 {
442 assert(worker != NULL);
443 struct subtask_queue *subtask_queue = &worker->q;
444
445 #ifdef MCPROFILE
446 uint64_t start = get_wall_time();
447 #endif
448
449 CHECK_ERR(pthread_mutex_lock(&subtask_queue->mutex), "pthread_mutex_lock");
450 if (subtask_queue->num_used == 0 && !blocking) {
451 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
452 return 1;
453 }
454 // Try to steal some work while the subtask_queue is empty
455 while (subtask_queue->num_used == 0 && !subtask_queue->dead) {
456 pthread_cond_wait(&subtask_queue->cond, &subtask_queue->mutex);
457 }
458
459 if (subtask_queue->dead) {
460 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
461 return -1;
462 }
463
464 // dequeue pops from the back
465 *subtask = subtask_queue->buffer[(subtask_queue->first + subtask_queue->num_used - 1) % subtask_queue->capacity];
466 subtask_queue->num_used--;
467
468 if (*subtask == NULL) {
469 assert(!"got NULL ptr");
470 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthred_mutex_unlock");
471 return -1;
472 }
473
474 #ifdef MCPROFILE
475 uint64_t end = get_wall_time();
476 subtask_queue->time_dequeue += (end - start);
477 subtask_queue->n_dequeues++;
478 #endif
479
480 // Broadcast a writer (if any) that there is now room for more.
481 CHECK_ERR(pthread_cond_broadcast(&subtask_queue->cond), "pthread_cond_broadcast");
482 CHECK_ERR(pthread_mutex_unlock(&subtask_queue->mutex), "pthread_mutex_unlock");
483
484 return 0;
485 }
486
487 static inline int subtask_queue_is_empty(struct subtask_queue *subtask_queue)
488 {
489 return subtask_queue->num_used == 0;
490 }
491
492 /* Scheduler definitions */
493
494 struct scheduler {
495 struct worker *workers;
496 int num_threads;
497 int minimum_chunk_size;
498
499
500 // If there is work to steal => active_work > 0
501 volatile int active_work;
502
503 // Only one error can be returned at the time now. Maybe we can
504 // provide a stack like structure for pushing errors onto if we wish
505 // to backpropagte multiple errors
506 volatile int error;
507
508 // kappa time unit in nanoseconds
509 double kappa;
510 };
511
512
513 // Thread local variable worker struct
514 // Note that, accesses to tls variables are expensive
515 // Minimize direct references to this variable
516 __thread struct worker* worker_local = NULL;
517
518 static int64_t total_now(int64_t total, int64_t time) {
519 return total + (get_wall_time_ns() - time);
520 }
521
522 static int random_other_worker(struct scheduler *scheduler, int my_id) {
523 int my_num_workers = scheduler->num_threads;
524 assert(my_num_workers != 1);
525 int i = fast_rand() % (my_num_workers - 1);
526 if (i >= my_id) {
527 i++;
528 }
529 #ifdef MCDEBUG
530 assert(i >= 0);
531 assert(i < my_num_workers);
532 assert(i != my_id);
533 #endif
534
535 return i;
536 }
537
538 static inline int64_t compute_chunk_size(int64_t minimum_chunk_size, double kappa, struct subtask* subtask)
539 {
540 double C = (double)*subtask->task_time / (double)*subtask->task_iter;
541 if (C == 0.0F) C += DBL_EPSILON;
542 return smax64((int64_t)(kappa / C), minimum_chunk_size);
543 }
544
545 /* Takes a chunk from subtask and enqueues the remaining iterations onto the worker's queue */
546 /* A no-op if the subtask is not chunkable */
547 static inline struct subtask* chunk_subtask(struct worker* worker, struct subtask *subtask)
548 {
549 if (subtask->chunkable) {
550 // Do we have information from previous runs avaliable
551 if (*subtask->task_iter > 0) {
552 subtask->chunk_size = compute_chunk_size(worker->scheduler->minimum_chunk_size,
553 worker->scheduler->kappa,
554 subtask);
555 assert(subtask->chunk_size > 0);
556 }
557 int64_t remaining_iter = subtask->end - subtask->start;
558 assert(remaining_iter > 0);
559 if (remaining_iter > subtask->chunk_size) {
560 struct subtask *new_subtask = malloc(sizeof(struct subtask));
561 *new_subtask = *subtask;
562 // increment the subtask join counter to account for new subtask
563 __atomic_fetch_add(subtask->counter, 1, __ATOMIC_RELAXED);
564 // Update range parameters
565 subtask->end = subtask->start + subtask->chunk_size;
566 new_subtask->start = subtask->end;
567 subtask_queue_enqueue(worker, new_subtask);
568 }
569 }
570 return subtask;
571 }
572
573 static inline int run_subtask(struct worker* worker, struct subtask* subtask)
574 {
575 assert(subtask != NULL);
576 assert(worker != NULL);
577
578 subtask = chunk_subtask(worker, subtask);
579 worker->total = 0;
580 worker->timer = get_wall_time_ns();
581 #if defined(MCPROFILE)
582 int64_t start = worker->timer;
583 #endif
584 worker->nested++;
585 int err = subtask->fn(subtask->args, subtask->start, subtask->end,
586 subtask->id,
587 worker->tid);
588 worker->nested--;
589 // Some error occured during some other subtask
590 // so we just clean-up and return
591 if (worker->scheduler->error != 0) {
592 // Even a failed task counts as finished.
593 __atomic_fetch_sub(subtask->counter, 1, __ATOMIC_RELAXED);
594 free(subtask);
595 return 0;
596 }
597 if (err != 0) {
598 __atomic_store_n(&worker->scheduler->error, err, __ATOMIC_RELAXED);
599 }
600 // Total sequential time spent
601 int64_t time_elapsed = total_now(worker->total, worker->timer);
602 #if defined(MCPROFILE)
603 worker->time_spent_working += get_wall_time_ns() - start;
604 #endif
605 int64_t iter = subtask->end - subtask->start;
606 // report measurements
607 // These updates should really be done using a single atomic CAS operation
608 __atomic_fetch_add(subtask->task_time, time_elapsed, __ATOMIC_RELAXED);
609 __atomic_fetch_add(subtask->task_iter, iter, __ATOMIC_RELAXED);
610 // We need a fence here, since if the counter is decremented before either
611 // of the two above are updated bad things can happen, e.g. if they are stack-allocated
612 __atomic_thread_fence(__ATOMIC_SEQ_CST);
613 __atomic_fetch_sub(subtask->counter, 1, __ATOMIC_RELAXED);
614 free(subtask);
615 return 0;
616 }
617
618
619 static inline int is_small(struct scheduler_segop *task, struct scheduler *scheduler, int *nsubtasks)
620 {
621 int64_t time = *task->task_time;
622 int64_t iter = *task->task_iter;
623
624 if (task->sched == DYNAMIC || iter == 0) {
625 *nsubtasks = scheduler->num_threads;
626 return 0;
627 }
628
629 // Estimate the constant C
630 double C = (double)time / (double)iter;
631 double cur_task_iter = (double) task->iterations;
632
633 // Returns true if the task is small i.e.
634 // if the number of iterations times C is smaller
635 // than the overhead of subtask creation
636 if (C == 0.0F || C * cur_task_iter < scheduler->kappa) {
637 *nsubtasks = 1;
638 return 1;
639 }
640
641 // Else compute how many subtasks this tasks should create
642 int64_t min_iter_pr_subtask = smax64(scheduler->kappa / C, 1);
643 *nsubtasks = smin64(smax64(task->iterations / min_iter_pr_subtask, 1), scheduler->num_threads);
644
645 return 0;
646 }
647
648 // TODO make this prettier
649 static inline struct subtask* create_subtask(parloop_fn fn,
650 void* args,
651 const char* name,
652 volatile int* counter,
653 int64_t *timer,
654 int64_t *iter,
655 int64_t start, int64_t end,
656 int chunkable,
657 int64_t chunk_size,
658 int id)
659 {
660 struct subtask* subtask = malloc(sizeof(struct subtask));
661 if (subtask == NULL) {
662 assert(!"malloc failed in create_subtask");
663 return NULL;
664 }
665 subtask->fn = fn;
666 subtask->args = args;
667
668 subtask->counter = counter;
669 subtask->task_time = timer;
670 subtask->task_iter = iter;
671
672 subtask->start = start;
673 subtask->end = end;
674 subtask->id = id;
675 subtask->chunkable = chunkable;
676 subtask->chunk_size = chunk_size;
677
678 subtask->name = name;
679 return subtask;
680 }
681
682 static int dummy_counter = 0;
683 static int64_t dummy_timer = 0;
684 static int64_t dummy_iter = 0;
685
686 static int dummy_fn(void *args, int64_t start, int64_t end, int subtask_id, int tid) {
687 (void)args;
688 (void)start;
689 (void)end;
690 (void)subtask_id;
691 (void)tid;
692 return 0;
693 }
694
695 // Wake up threads, who are blocking by pushing a dummy task
696 // onto their queue
697 static inline void wake_up_threads(struct scheduler *scheduler, int start_tid, int end_tid) {
698
699 #if defined(MCDEBUG)
700 assert(start_tid >= 1);
701 assert(end_tid <= scheduler->num_threads);
702 #endif
703 for (int i = start_tid; i < end_tid; i++) {
704 struct subtask *subtask = create_subtask(dummy_fn, NULL, "dummy_fn",
705 &dummy_counter,
706 &dummy_timer, &dummy_iter,
707 0, 0,
708 0, 0,
709 0);
710 CHECK_ERR(subtask_queue_enqueue(&scheduler->workers[i], subtask), "subtask_queue_enqueue");
711 }
712 }
713
714 static inline int is_finished(struct worker *worker) {
715 return worker->dead && subtask_queue_is_empty(&worker->q);
716 }
717
718 // Try to steal from a random queue
719 static inline int steal_from_random_worker(struct worker* worker)
720 {
721 int my_id = worker->tid;
722 struct scheduler* scheduler = worker->scheduler;
723 int k = random_other_worker(scheduler, my_id);
724 struct worker *worker_k = &scheduler->workers[k];
725 struct subtask* subtask = NULL;
726 int retval = subtask_queue_steal(worker_k, &subtask);
727 if (retval == 0) {
728 subtask_queue_enqueue(worker, subtask);
729 return 1;
730 }
731 return 0;
732 }
733
734
735 static inline void *scheduler_worker(void* args)
736 {
737 struct worker *worker = (struct worker*) args;
738 struct scheduler *scheduler = worker->scheduler;
739 worker_local = worker;
740 struct subtask *subtask = NULL;
741
742 while(!is_finished(worker)) {
743 if (!subtask_queue_is_empty(&worker->q)) {
744 int retval = subtask_queue_dequeue(worker, &subtask, 0);
745 if (retval == 0) {
746 assert(subtask != NULL);
747 CHECK_ERR(run_subtask(worker, subtask), "run_subtask");
748 } // else someone stole our work
749
750 } else if (scheduler->active_work) { /* steal */
751 while (!is_finished(worker) && scheduler->active_work) {
752 if (steal_from_random_worker(worker)) {
753 break;
754 }
755 }
756 } else { /* go back to sleep and wait for work */
757 int retval = subtask_queue_dequeue(worker, &subtask, 1);
758 if (retval == 0) {
759 assert(subtask != NULL);
760 CHECK_ERR(run_subtask(worker, subtask), "run_subtask");
761 }
762 }
763 }
764
765 assert(subtask_queue_is_empty(&worker->q));
766 #if defined(MCPROFILE)
767 if (worker->output_usage)
768 output_worker_usage(worker);
769 #endif
770 return NULL;
771 }
772
773
774 static inline int scheduler_execute_parloop(struct scheduler *scheduler,
775 struct scheduler_parloop *task,
776 int64_t *timer)
777 {
778
779 struct worker *worker = worker_local;
780
781 struct scheduler_info info = task->info;
782 int64_t iter_pr_subtask = info.iter_pr_subtask;
783 int64_t remainder = info.remainder;
784 int nsubtasks = info.nsubtasks;
785 volatile int join_counter = nsubtasks;
786
787 // Shared timer used to sum up all
788 // sequential work from each subtask
789 int64_t task_timer = 0;
790 int64_t task_iter = 0;
791
792 enum scheduling sched = info.sched;
793 /* If each subtasks should be processed in chunks */
794 int chunkable = sched == STATIC ? 0 : 1;
795 int64_t chunk_size = scheduler->minimum_chunk_size; // The initial chunk size when no info is avaliable
796
797
798 if (info.wake_up_threads || sched == DYNAMIC)
799 __atomic_add_fetch(&scheduler->active_work, nsubtasks, __ATOMIC_RELAXED);
800
801 int64_t start = 0;
802 int64_t end = iter_pr_subtask + (int64_t)(remainder != 0);
803 for (int subtask_id = 0; subtask_id < nsubtasks; subtask_id++) {
804 struct subtask *subtask = create_subtask(task->fn, task->args, task->name,
805 &join_counter,
806 &task_timer, &task_iter,
807 start, end,
808 chunkable, chunk_size,
809 subtask_id);
810 assert(subtask != NULL);
811 // In most cases we will never have more subtasks than workers,
812 // but there can be exceptions (e.g. the kappa tuning function).
813 struct worker *subtask_worker =
814 worker->nested
815 ? &scheduler->workers[worker->tid]
816 : &scheduler->workers[subtask_id % scheduler->num_threads];
817 CHECK_ERR(subtask_queue_enqueue(subtask_worker, subtask),
818 "subtask_queue_enqueue");
819 // Update range params
820 start = end;
821 end += iter_pr_subtask + ((subtask_id + 1) < remainder);
822 }
823
824 if (info.wake_up_threads) {
825 wake_up_threads(scheduler, nsubtasks, scheduler->num_threads);
826 }
827
828 // Join (wait for subtasks to finish)
829 while(join_counter != 0) {
830 if (!subtask_queue_is_empty(&worker->q)) {
831 struct subtask *subtask = NULL;
832 int err = subtask_queue_dequeue(worker, &subtask, 0);
833 if (err == 0 ) {
834 CHECK_ERR(run_subtask(worker, subtask), "run_subtask");
835 }
836 } else {
837 if (steal_from_random_worker(worker)) {
838 struct subtask *subtask = NULL;
839 int err = subtask_queue_dequeue(worker, &subtask, 0);
840 if (err == 0) {
841 CHECK_ERR(run_subtask(worker, subtask), "run_subtask");
842 }
843 }
844 }
845 }
846
847
848 if (info.wake_up_threads || sched == DYNAMIC) {
849 __atomic_sub_fetch(&scheduler->active_work, nsubtasks, __ATOMIC_RELAXED);
850 }
851
852 // Write back timing results of all sequential work
853 (*timer) += task_timer;
854 return scheduler->error;
855 }
856
857
858 static inline int scheduler_execute_task(struct scheduler *scheduler,
859 struct scheduler_parloop *task)
860 {
861
862 struct worker *worker = worker_local;
863
864 int err = 0;
865
866 // How much sequential work was performed by the task
867 int64_t task_timer = 0;
868
869 /* Execute task sequential or parallel based on decision made earlier */
870 if (task->info.nsubtasks == 1) {
871 int64_t start = get_wall_time_ns();
872 err = task->fn(task->args, 0, task->iterations, 0, worker->tid);
873 int64_t end = get_wall_time_ns();
874 task_timer = end - start;
875 worker->time_spent_working += task_timer;
876 // Report time measurements
877 // TODO the update of both of these should really be a single atomic!!
878 __atomic_fetch_add(task->info.task_time, task_timer, __ATOMIC_RELAXED);
879 __atomic_fetch_add(task->info.task_iter, task->iterations, __ATOMIC_RELAXED);
880 } else {
881 // Add "before" time if we already are inside a task
882 int64_t time_before = 0;
883 if (worker->nested > 0) {
884 time_before = total_now(worker->total, worker->timer);
885 }
886
887 err = scheduler_execute_parloop(scheduler, task, &task_timer);
888
889 // Report time measurements
890 // TODO the update of both of these should really be a single atomic!!
891 __atomic_fetch_add(task->info.task_time, task_timer, __ATOMIC_RELAXED);
892 __atomic_fetch_add(task->info.task_iter, task->iterations, __ATOMIC_RELAXED);
893
894 // Update timers to account for new timings
895 worker->total = time_before + task_timer;
896 worker->timer = get_wall_time_ns();
897 }
898
899
900 return err;
901 }
902
903 /* Decide on how schedule the incoming task i.e. how many subtasks and
904 to run sequential or (potentially nested) parallel code body */
905 static inline int scheduler_prepare_task(struct scheduler* scheduler,
906 struct scheduler_segop *task)
907 {
908 assert(task != NULL);
909
910 struct worker *worker = worker_local;
911 struct scheduler_info info;
912 info.task_time = task->task_time;
913 info.task_iter = task->task_iter;
914
915 int nsubtasks;
916 // Decide if task should be scheduled sequentially
917 if (is_small(task, scheduler, &nsubtasks)) {
918 info.iter_pr_subtask = task->iterations;
919 info.remainder = 0;
920 info.nsubtasks = nsubtasks;
921 return task->top_level_fn(task->args, task->iterations, worker->tid, info);
922 } else {
923 info.iter_pr_subtask = task->iterations / nsubtasks;
924 info.remainder = task->iterations % nsubtasks;
925 info.sched = task->sched;
926 switch (task->sched) {
927 case STATIC:
928 info.nsubtasks = info.iter_pr_subtask == 0 ? info.remainder : ((task->iterations - info.remainder) / info.iter_pr_subtask);
929 break;
930 case DYNAMIC:
931 // As any thread can take any subtasks, we are being safe with using
932 // an upper bound on the number of tasks such that the task allocate enough memory
933 info.nsubtasks = info.iter_pr_subtask == 0 ? info.remainder : nsubtasks;
934 break;
935 default:
936 assert(!"Got unknown scheduling");
937 }
938 }
939
940 info.wake_up_threads = 0;
941 // We only use the nested parallel segop function if we can't exchaust all cores
942 // using the outer most level
943 if (task->nested_fn != NULL && info.nsubtasks < scheduler->num_threads && info.nsubtasks == task->iterations) {
944 if (worker->nested == 0)
945 info.wake_up_threads = 1;
946 return task->nested_fn(task->args, task->iterations, worker->tid, info);
947 }
948
949 return task->top_level_fn(task->args, task->iterations, worker->tid, info);
950 }
951
952 // Now some code for finding the proper value of kappa on a given
953 // machine (the smallest amount of work that amortises the cost of
954 // task creation).
955
956 struct tuning_struct {
957 int32_t *free_tuning_res;
958 int32_t *array;
959 };
960
961 // Reduction function over an integer array
962 static int tuning_loop(void *args, int64_t start, int64_t end,
963 int flat_tid, int tid) {
964 (void)flat_tid;
965 (void)tid;
966
967 int err = 0;
968 struct tuning_struct *tuning_struct = (struct tuning_struct *) args;
969 int32_t *array = tuning_struct->array;
970 int32_t *tuning_res = tuning_struct->free_tuning_res;
971
972 int32_t sum = 0;
973 for (int i = start; i < end; i++) {
974 int32_t y = array[i];
975 sum = add32(sum, y);
976 }
977 *tuning_res = sum;
978 return err;
979 }
980
981 // The main entry point for the tuning process. Sets the provided
982 // variable ``kappa``.
983 static int determine_kappa(double *kappa) {
984 int err = 0;
985
986 int64_t iterations = 100000000;
987 int64_t tuning_time = 0;
988 int64_t tuning_iter = 0;
989
990 int32_t *array = malloc(sizeof(int32_t) * iterations);
991 for (int64_t i = 0; i < iterations; i++) {
992 array[i] = fast_rand();
993 }
994
995 int64_t start_tuning = get_wall_time_ns();
996 /* **************************** */
997 /* Run sequential reduce first' */
998 /* **************************** */
999 int64_t tuning_sequentiual_start = get_wall_time_ns();
1000 struct tuning_struct tuning_struct;
1001 int32_t tuning_res;
1002 tuning_struct.free_tuning_res = &tuning_res;
1003 tuning_struct.array = array;
1004
1005 err = tuning_loop(&tuning_struct, 0, iterations, 0, 0);
1006 int64_t tuning_sequentiual_end = get_wall_time_ns();
1007 int64_t sequential_elapsed = tuning_sequentiual_end - tuning_sequentiual_start;
1008
1009 double C = (double)sequential_elapsed / (double)iterations;
1010 fprintf(stderr, " Time for sequential run is %lld - Found C %f\n", (long long)sequential_elapsed, C);
1011
1012 /* ********************** */
1013 /* Now run tuning process */
1014 /* ********************** */
1015 // Setup a scheduler with a single worker
1016 struct scheduler scheduler;
1017 scheduler.num_threads = 1;
1018 scheduler.workers = malloc(sizeof(struct worker));
1019 worker_local = &scheduler.workers[0];
1020 worker_local->tid = 0;
1021 CHECK_ERR(subtask_queue_init(&scheduler.workers[0].q, 1024),
1022 "failed to init queue for worker %d\n", 0);
1023
1024 // Start tuning for kappa
1025 double kappa_tune = 1000; // Initial kappa is 1 us
1026 double ratio;
1027 int64_t time_elapsed;
1028 while(1) {
1029 int64_t min_iter_pr_subtask = (int64_t) (kappa_tune / C) == 0 ? 1 : (kappa_tune / C);
1030 int nsubtasks = iterations / min_iter_pr_subtask;
1031 struct scheduler_info info;
1032 info.iter_pr_subtask = min_iter_pr_subtask;
1033
1034 info.nsubtasks = iterations / min_iter_pr_subtask;
1035 info.remainder = iterations % min_iter_pr_subtask;
1036 info.task_time = &tuning_time;
1037 info.task_iter = &tuning_iter;
1038 info.sched = STATIC;
1039
1040 struct scheduler_parloop parloop;
1041 parloop.name = "tuning_loop";
1042 parloop.fn = tuning_loop;
1043 parloop.args = &tuning_struct;
1044 parloop.iterations = iterations;
1045 parloop.info = info;
1046
1047 int64_t tuning_chunked_start = get_wall_time_ns();
1048 int determine_kappa_err =
1049 scheduler_execute_task(&scheduler,
1050 &parloop);
1051 assert(determine_kappa_err == 0);
1052 int64_t tuning_chunked_end = get_wall_time_ns();
1053 time_elapsed = tuning_chunked_end - tuning_chunked_start;
1054
1055 ratio = (double)time_elapsed / (double)sequential_elapsed;
1056 if (ratio < 1.055) {
1057 break;
1058 }
1059 kappa_tune += 100; // Increase by 100 ns at the time
1060 fprintf(stderr, "nsubtask %d - kappa %f - ratio %f\n", nsubtasks, kappa_tune, ratio);
1061 }
1062
1063 int64_t end_tuning = get_wall_time_ns();
1064 fprintf(stderr, "tuning took %lld ns and found kappa %f - time %lld - ratio %f\n",
1065 (long long)end_tuning - start_tuning,
1066 kappa_tune,
1067 (long long)time_elapsed,
1068 ratio);
1069 *kappa = kappa_tune;
1070
1071 // Clean-up
1072 CHECK_ERR(subtask_queue_destroy(&scheduler.workers[0].q), "failed to destroy queue");
1073 free(array);
1074 free(scheduler.workers);
1075 return err;
1076 }
1077
1078 static int scheduler_init(struct scheduler *scheduler,
1079 int num_workers,
1080 double kappa) {
1081 #ifdef FUTHARK_BACKEND_ispc
1082 int64_t get_gang_size();
1083 scheduler->minimum_chunk_size = get_gang_size();
1084 #else
1085 scheduler->minimum_chunk_size = 1;
1086 #endif
1087
1088 assert(num_workers > 0);
1089
1090 scheduler->kappa = kappa;
1091 scheduler->num_threads = num_workers;
1092 scheduler->active_work = 0;
1093 scheduler->error = 0;
1094
1095 scheduler->workers = calloc(num_workers, sizeof(struct worker));
1096
1097 const int queue_capacity = 1024;
1098
1099 worker_local = &scheduler->workers[0];
1100 worker_local->tid = 0;
1101 worker_local->scheduler = scheduler;
1102 CHECK_ERR(subtask_queue_init(&worker_local->q, queue_capacity),
1103 "failed to init queue for worker %d\n", 0);
1104
1105 for (int i = 1; i < num_workers; i++) {
1106 struct worker *cur_worker = &scheduler->workers[i];
1107 memset(cur_worker, 0, sizeof(struct worker));
1108 cur_worker->tid = i;
1109 cur_worker->output_usage = 0;
1110 cur_worker->scheduler = scheduler;
1111 CHECK_ERR(subtask_queue_init(&cur_worker->q, queue_capacity),
1112 "failed to init queue for worker %d\n", i);
1113
1114 CHECK_ERR(pthread_create(&cur_worker->thread,
1115 NULL,
1116 &scheduler_worker,
1117 cur_worker),
1118 "Failed to create worker %d\n", i);
1119 }
1120
1121 return 0;
1122 }
1123
1124 static int scheduler_destroy(struct scheduler *scheduler) {
1125 // We assume that this function is called by the thread controlling
1126 // the first worker, which is why we treat scheduler->workers[0]
1127 // specially here.
1128
1129 // First mark them all as dead.
1130 for (int i = 1; i < scheduler->num_threads; i++) {
1131 struct worker *cur_worker = &scheduler->workers[i];
1132 cur_worker->dead = 1;
1133 }
1134
1135 // Then destroy their task queues (this will wake up the threads and
1136 // make them do their shutdown).
1137 for (int i = 1; i < scheduler->num_threads; i++) {
1138 struct worker *cur_worker = &scheduler->workers[i];
1139 subtask_queue_destroy(&cur_worker->q);
1140 }
1141
1142 // Then actually wait for them to stop.
1143 for (int i = 1; i < scheduler->num_threads; i++) {
1144 struct worker *cur_worker = &scheduler->workers[i];
1145 CHECK_ERR(pthread_join(scheduler->workers[i].thread, NULL), "pthread_join");
1146 }
1147
1148 // And then destroy our own queue.
1149 subtask_queue_destroy(&scheduler->workers[0].q);
1150
1151 free(scheduler->workers);
1152
1153 return 0;
1154 }
1155
1156 // End of scheduler.h