scheduler.c 55.3 KB
Newer Older
1
2
/*******************************************************************************
 * This file is part of SWIFT.
3
 * Copyright (c) 2012 Pedro Gonnet (pedro.gonnet@durham.ac.uk)
4
 *                    Matthieu Schaller (matthieu.schaller@durham.ac.uk)
5
 *               2016 Peter W. Draper (p.w.draper@durham.ac.uk)
6
 *
7
8
9
10
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published
 * by the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
11
 *
12
13
14
15
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
16
 *
17
18
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
19
 *
20
21
22
23
24
25
 ******************************************************************************/

/* Config parameters. */
#include "../config.h"

/* Some standard headers. */
26
27
28
#include <limits.h>
#include <math.h>
#include <pthread.h>
29
30
31
32
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

33
34
/* MPI headers. */
#ifdef WITH_MPI
35
#include <mpi.h>
36
37
#endif

38
39
40
/* This object's header. */
#include "scheduler.h"

41
42
/* Local headers. */
#include "atomic.h"
43
#include "cycle.h"
44
#include "engine.h"
45
#include "error.h"
46
#include "intrinsics.h"
47
#include "kernel_hydro.h"
48
#include "queue.h"
49
#include "sort_part.h"
50
51
#include "space.h"
#include "task.h"
52
#include "timers.h"
53

54
55
56
57
58
/**
 * @brief Re-set the list of active tasks.
 */
void scheduler_clear_active(struct scheduler *s) { s->active_count = 0; }

59
60
61
62
63
64
65
/**
 * @brief Add an unlock_task to the given task.
 *
 * @param s The #scheduler.
 * @param ta The unlocking #task.
 * @param tb The #task that will be unlocked.
 */
66
67
void scheduler_addunlock(struct scheduler *s, struct task *ta,
                         struct task *tb) {
68
69
70
71
72
#ifdef SWIFT_DEBUG_CHECKS
  if (ta == NULL) error("Unlocking task is NULL.");
  if (tb == NULL) error("Unlocked task is NULL.");
#endif

73
74
75
76
77
  /* Get an index at which to store this unlock. */
  const int ind = atomic_inc(&s->nr_unlocks);

  /* Does the buffer need to be grown? */
  if (ind == s->size_unlocks) {
78
    /* Allocate the new buffer. */
79
80
81
    struct task **unlocks_new;
    int *unlock_ind_new;
    const int size_unlocks_new = s->size_unlocks * 2;
82
83
    if ((unlocks_new = (struct task **)malloc(sizeof(struct task *) *
                                              size_unlocks_new)) == NULL ||
84
85
        (unlock_ind_new = (int *)malloc(sizeof(int) * size_unlocks_new)) ==
            NULL)
86
      error("Failed to re-allocate unlocks.");
87

88
    /* Wait for all writes to the old buffer to complete. */
89
90
91
    while (s->completed_unlock_writes < ind)
      ;

92
    /* Copy the buffers. */
93
94
95
96
97
98
    memcpy(unlocks_new, s->unlocks, sizeof(struct task *) * ind);
    memcpy(unlock_ind_new, s->unlock_ind, sizeof(int) * ind);
    free(s->unlocks);
    free(s->unlock_ind);
    s->unlocks = unlocks_new;
    s->unlock_ind = unlock_ind_new;
99

100
    /* Publish the new buffer size. */
101
102
    s->size_unlocks = size_unlocks_new;
  }
103

104
  /* Wait for there to actually be space at my index. */
105
106
  while (ind > s->size_unlocks)
    ;
107
108
109
110

  /* Write the unlock to the scheduler. */
  s->unlocks[ind] = tb;
  s->unlock_ind[ind] = ta - s->tasks;
111
  atomic_inc(&s->completed_unlock_writes);
112
113
}

114
/**
115
 * @brief Split a hydrodynamic task if too large.
116
 *
117
118
 * @param t The #task
 * @param s The #scheduler we are working in.
119
 */
120
static void scheduler_splittask_hydro(struct task *t, struct scheduler *s) {
121

122
123
124
  /* Iterate on this task until we're done with it. */
  int redo = 1;
  while (redo) {
125

126
127
    /* Reset the redo flag. */
    redo = 0;
128

129
    /* Non-splittable task? */
130
    if ((t->ci == NULL) || (t->type == task_type_pair && t->cj == NULL)) {
131
      t->type = task_type_none;
132
133
      t->subtype = task_subtype_none;
      t->cj = NULL;
134
135
136
      t->skip = 1;
      break;
    }
137

138
139
    /* Self-interaction? */
    if (t->type == task_type_self) {
140

141
142
143
144
145
      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;

      /* Foreign task? */
      if (ci->nodeID != s->nodeID) {
146
        t->skip = 1;
147
        break;
148
149
      }

150
      /* Is this cell even split and the task does not violate h ? */
151
      if (cell_can_split_self_task(ci)) {
152

153
        /* Make a sub? */
154
        if (scheduler_dosub && ci->count < space_subsize_self) {
155

156
157
158
159
160
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

          /* Otherwise, make tasks explicitly. */
        } else {
161

162
163
164
165
166
167
168
169
170
          /* Take a step back (we're going to recycle the current task)... */
          redo = 1;

          /* Add the self tasks. */
          int first_child = 0;
          while (ci->progeny[first_child] == NULL) first_child++;
          t->ci = ci->progeny[first_child];
          for (int k = first_child + 1; k < 8; k++)
            if (ci->progeny[k] != NULL)
171
              scheduler_splittask_hydro(
172
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
173
                                    ci->progeny[k], NULL),
174
175
                  s);

176
177
178
179
180
181
182
          /* Make a task for each pair of progeny */
          for (int j = 0; j < 8; j++)
            if (ci->progeny[j] != NULL)
              for (int k = j + 1; k < 8; k++)
                if (ci->progeny[k] != NULL)
                  scheduler_splittask_hydro(
                      scheduler_addtask(s, task_type_pair, t->subtype,
183
                                        sub_sid_flag[j][k], 0, ci->progeny[j],
184
185
                                        ci->progeny[k]),
                      s);
186
        }
187
      } /* Cell is split */
188

189
    } /* Self interaction */
190

191
192
    /* Pair interaction? */
    else if (t->type == task_type_pair) {
193

194
195
196
      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
197

198
199
200
201
202
      /* Foreign task? */
      if (ci->nodeID != s->nodeID && cj->nodeID != s->nodeID) {
        t->skip = 1;
        break;
      }
203

204
205
206
      /* Get the sort ID, use space_getsid and not t->flags
         to make sure we get ci and cj swapped if needed. */
      double shift[3];
Matthieu Schaller's avatar
Matthieu Schaller committed
207
      const int sid = space_getsid(s->space, &ci, &cj, shift);
208

209
      /* Should this task be split-up? */
210
      if (cell_can_split_pair_task(ci) && cell_can_split_pair_task(cj)) {
211
212

        /* Replace by a single sub-task? */
213
214
        if (scheduler_dosub && /* Use division to avoid integer overflow. */
            ci->count * sid_scale[sid] < space_subsize_pair / cj->count &&
215
            !sort_is_corner(sid)) {
216
217
218
219
220

          /* Make this task a sub task. */
          t->type = task_type_sub_pair;

          /* Otherwise, split it. */
221
222
        } else {

223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
          /* Take a step back (we're going to recycle the current task)... */
          redo = 1;

          /* For each different sorting type... */
          switch (sid) {

            case 0: /* (  1 ,  1 ,  1 ) */
              t->ci = ci->progeny[7];
              t->cj = cj->progeny[0];
              t->flags = 0;
              break;

            case 1: /* (  1 ,  1 ,  0 ) */
              t->ci = ci->progeny[6];
              t->cj = cj->progeny[0];
              t->flags = 1;
239
              scheduler_splittask_hydro(
240
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
241
                                    ci->progeny[7], cj->progeny[1]),
242
                  s);
243
              scheduler_splittask_hydro(
244
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
245
                                    ci->progeny[6], cj->progeny[1]),
246
                  s);
247
              scheduler_splittask_hydro(
248
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
249
                                    ci->progeny[7], cj->progeny[0]),
250
251
252
253
254
255
256
257
258
259
260
261
262
                  s);
              break;

            case 2: /* (  1 ,  1 , -1 ) */
              t->ci = ci->progeny[6];
              t->cj = cj->progeny[1];
              t->flags = 2;
              break;

            case 3: /* (  1 ,  0 ,  1 ) */
              t->ci = ci->progeny[5];
              t->cj = cj->progeny[0];
              t->flags = 3;
263
              scheduler_splittask_hydro(
264
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
265
                                    ci->progeny[7], cj->progeny[2]),
266
                  s);
267
              scheduler_splittask_hydro(
268
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
269
                                    ci->progeny[5], cj->progeny[2]),
270
                  s);
271
              scheduler_splittask_hydro(
272
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
273
                                    ci->progeny[7], cj->progeny[0]),
274
275
276
277
278
279
280
                  s);
              break;

            case 4: /* (  1 ,  0 ,  0 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[0];
              t->flags = 4;
281
              scheduler_splittask_hydro(
282
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
283
                                    ci->progeny[5], cj->progeny[0]),
284
                  s);
285
              scheduler_splittask_hydro(
286
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
287
                                    ci->progeny[6], cj->progeny[0]),
288
                  s);
289
              scheduler_splittask_hydro(
290
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
291
                                    ci->progeny[7], cj->progeny[0]),
292
                  s);
293
              scheduler_splittask_hydro(
294
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
295
                                    ci->progeny[4], cj->progeny[1]),
296
                  s);
297
              scheduler_splittask_hydro(
298
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
299
                                    ci->progeny[5], cj->progeny[1]),
300
                  s);
301
              scheduler_splittask_hydro(
302
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
303
                                    ci->progeny[6], cj->progeny[1]),
304
                  s);
305
              scheduler_splittask_hydro(
306
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
307
                                    ci->progeny[7], cj->progeny[1]),
308
                  s);
309
              scheduler_splittask_hydro(
310
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
311
                                    ci->progeny[4], cj->progeny[2]),
312
                  s);
313
              scheduler_splittask_hydro(
314
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
315
                                    ci->progeny[5], cj->progeny[2]),
316
                  s);
317
              scheduler_splittask_hydro(
318
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
319
                                    ci->progeny[6], cj->progeny[2]),
320
                  s);
321
              scheduler_splittask_hydro(
322
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
323
                                    ci->progeny[7], cj->progeny[2]),
324
                  s);
325
              scheduler_splittask_hydro(
326
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
327
                                    ci->progeny[4], cj->progeny[3]),
328
                  s);
329
              scheduler_splittask_hydro(
330
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
331
                                    ci->progeny[5], cj->progeny[3]),
332
                  s);
333
              scheduler_splittask_hydro(
334
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
335
                                    ci->progeny[6], cj->progeny[3]),
336
                  s);
337
              scheduler_splittask_hydro(
338
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
339
                                    ci->progeny[7], cj->progeny[3]),
340
341
342
343
344
345
346
                  s);
              break;

            case 5: /* (  1 ,  0 , -1 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[1];
              t->flags = 5;
347
              scheduler_splittask_hydro(
348
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
349
                                    ci->progeny[6], cj->progeny[3]),
350
                  s);
351
              scheduler_splittask_hydro(
352
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
353
                                    ci->progeny[4], cj->progeny[3]),
354
                  s);
355
              scheduler_splittask_hydro(
356
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
357
                                    ci->progeny[6], cj->progeny[1]),
358
359
360
361
362
363
364
365
366
367
368
369
370
                  s);
              break;

            case 6: /* (  1 , -1 ,  1 ) */
              t->ci = ci->progeny[5];
              t->cj = cj->progeny[2];
              t->flags = 6;
              break;

            case 7: /* (  1 , -1 ,  0 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[3];
              t->flags = 6;
371
              scheduler_splittask_hydro(
372
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
373
                                    ci->progeny[5], cj->progeny[2]),
374
                  s);
375
              scheduler_splittask_hydro(
376
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
377
                                    ci->progeny[4], cj->progeny[2]),
378
                  s);
379
              scheduler_splittask_hydro(
380
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
381
                                    ci->progeny[5], cj->progeny[3]),
382
383
384
385
386
387
388
389
390
391
392
393
394
                  s);
              break;

            case 8: /* (  1 , -1 , -1 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[3];
              t->flags = 8;
              break;

            case 9: /* (  0 ,  1 ,  1 ) */
              t->ci = ci->progeny[3];
              t->cj = cj->progeny[0];
              t->flags = 9;
395
              scheduler_splittask_hydro(
396
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
397
                                    ci->progeny[7], cj->progeny[4]),
398
                  s);
399
              scheduler_splittask_hydro(
400
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
401
                                    ci->progeny[3], cj->progeny[4]),
402
                  s);
403
              scheduler_splittask_hydro(
404
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
405
                                    ci->progeny[7], cj->progeny[0]),
406
407
408
409
410
411
412
                  s);
              break;

            case 10: /* (  0 ,  1 ,  0 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[0];
              t->flags = 10;
413
              scheduler_splittask_hydro(
414
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
415
                                    ci->progeny[3], cj->progeny[0]),
416
                  s);
417
              scheduler_splittask_hydro(
418
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
419
                                    ci->progeny[6], cj->progeny[0]),
420
                  s);
421
              scheduler_splittask_hydro(
422
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
423
                                    ci->progeny[7], cj->progeny[0]),
424
                  s);
425
              scheduler_splittask_hydro(
426
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
427
                                    ci->progeny[2], cj->progeny[1]),
428
                  s);
429
              scheduler_splittask_hydro(
430
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
431
                                    ci->progeny[3], cj->progeny[1]),
432
                  s);
433
              scheduler_splittask_hydro(
434
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
435
                                    ci->progeny[6], cj->progeny[1]),
436
                  s);
437
              scheduler_splittask_hydro(
438
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
439
                                    ci->progeny[7], cj->progeny[1]),
440
                  s);
441
              scheduler_splittask_hydro(
442
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
443
                                    ci->progeny[2], cj->progeny[4]),
444
                  s);
445
              scheduler_splittask_hydro(
446
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
447
                                    ci->progeny[3], cj->progeny[4]),
448
                  s);
449
              scheduler_splittask_hydro(
450
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
451
                                    ci->progeny[6], cj->progeny[4]),
452
                  s);
453
              scheduler_splittask_hydro(
454
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
455
                                    ci->progeny[7], cj->progeny[4]),
456
                  s);
457
              scheduler_splittask_hydro(
458
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
459
                                    ci->progeny[2], cj->progeny[5]),
460
                  s);
461
              scheduler_splittask_hydro(
462
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
463
                                    ci->progeny[3], cj->progeny[5]),
464
                  s);
465
              scheduler_splittask_hydro(
466
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
467
                                    ci->progeny[6], cj->progeny[5]),
468
                  s);
469
              scheduler_splittask_hydro(
470
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
471
                                    ci->progeny[7], cj->progeny[5]),
472
473
474
475
476
477
478
                  s);
              break;

            case 11: /* (  0 ,  1 , -1 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[1];
              t->flags = 11;
479
              scheduler_splittask_hydro(
480
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
481
                                    ci->progeny[6], cj->progeny[5]),
482
                  s);
483
              scheduler_splittask_hydro(
484
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
485
                                    ci->progeny[2], cj->progeny[5]),
486
                  s);
487
              scheduler_splittask_hydro(
488
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
489
                                    ci->progeny[6], cj->progeny[1]),
490
491
492
493
494
495
496
                  s);
              break;

            case 12: /* (  0 ,  0 ,  1 ) */
              t->ci = ci->progeny[1];
              t->cj = cj->progeny[0];
              t->flags = 12;
497
              scheduler_splittask_hydro(
498
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
499
                                    ci->progeny[3], cj->progeny[0]),
500
                  s);
501
              scheduler_splittask_hydro(
502
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
503
                                    ci->progeny[5], cj->progeny[0]),
504
                  s);
505
              scheduler_splittask_hydro(
506
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
507
                                    ci->progeny[7], cj->progeny[0]),
508
                  s);
509
              scheduler_splittask_hydro(
510
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
511
                                    ci->progeny[1], cj->progeny[2]),
512
                  s);
513
              scheduler_splittask_hydro(
514
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
515
                                    ci->progeny[3], cj->progeny[2]),
516
                  s);
517
              scheduler_splittask_hydro(
518
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
519
                                    ci->progeny[5], cj->progeny[2]),
520
                  s);
521
              scheduler_splittask_hydro(
522
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
523
                                    ci->progeny[7], cj->progeny[2]),
524
                  s);
525
              scheduler_splittask_hydro(
526
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
527
                                    ci->progeny[1], cj->progeny[4]),
528
                  s);
529
              scheduler_splittask_hydro(
530
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
531
                                    ci->progeny[3], cj->progeny[4]),
532
                  s);
533
              scheduler_splittask_hydro(
534
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
535
                                    ci->progeny[5], cj->progeny[4]),
536
                  s);
537
              scheduler_splittask_hydro(
538
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
539
                                    ci->progeny[7], cj->progeny[4]),
540
                  s);
541
              scheduler_splittask_hydro(
542
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
543
                                    ci->progeny[1], cj->progeny[6]),
544
                  s);
545
              scheduler_splittask_hydro(
546
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
547
                                    ci->progeny[3], cj->progeny[6]),
548
                  s);
549
              scheduler_splittask_hydro(
550
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
551
                                    ci->progeny[5], cj->progeny[6]),
552
                  s);
553
              scheduler_splittask_hydro(
554
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
555
                                    ci->progeny[7], cj->progeny[6]),
556
557
558
                  s);
              break;
          } /* switch(sid) */
559
560
        }

561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
        /* Otherwise, break it up if it is too large? */
      } else if (scheduler_doforcesplit && ci->split && cj->split &&
                 (ci->count > space_maxsize / cj->count)) {

        // message( "force splitting pair with %i and %i parts." , ci->count ,
        // cj->count );

        /* Replace the current task. */
        t->type = task_type_none;

        for (int j = 0; j < 8; j++)
          if (ci->progeny[j] != NULL)
            for (int k = 0; k < 8; k++)
              if (cj->progeny[k] != NULL) {
                struct task *tl =
                    scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
577
                                      ci->progeny[j], cj->progeny[k]);
578
                scheduler_splittask_hydro(tl, s);
579
580
581
582
583
584
585
                tl->flags = space_getsid(s->space, &t->ci, &t->cj, shift);
              }
      }
    } /* pair interaction? */
  }   /* iterate over the current task. */
}

586
587
588
589
590
591
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
static void scheduler_splittask_gravity(struct task *t, struct scheduler *s) {

  /* Iterate on this task until we're done with it. */
  int redo = 1;
  while (redo) {

    /* Reset the redo flag. */
    redo = 0;

    /* Non-splittable task? */
    if ((t->ci == NULL) || (t->type == task_type_pair && t->cj == NULL)) {
      t->type = task_type_none;
      t->subtype = task_subtype_none;
      t->cj = NULL;
      t->skip = 1;
      break;
    }

    /* Self-interaction? */
    if (t->type == task_type_self) {

      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;

      /* Foreign task? */
      if (ci->nodeID != s->nodeID) {
        t->skip = 1;
        break;
      }

      /* Is this cell even split? */
      if (ci->split) {

        /* Make a sub? */
626
        if (scheduler_dosub && ci->gcount < space_subsize_self) {
627
628
629
630
631
632
633
634
635
636

          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

          /* Make sure we have a drift task (MATTHIEU temp. fix) */
          lock_lock(&ci->lock);
          if (ci->drift_gpart == NULL)
            ci->drift_gpart = scheduler_addtask(
                s, task_type_drift_gpart, task_subtype_none, 0, 0, ci, NULL);
          lock_unlock_blind(&ci->lock);
637

638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
          /* Otherwise, make tasks explicitly. */
        } else {

          /* Take a step back (we're going to recycle the current task)... */
          redo = 1;

          /* Add the self tasks. */
          int first_child = 0;
          while (ci->progeny[first_child] == NULL) first_child++;
          t->ci = ci->progeny[first_child];
          for (int k = first_child + 1; k < 8; k++)
            if (ci->progeny[k] != NULL)
              scheduler_splittask_gravity(
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
                                    ci->progeny[k], NULL),
                  s);

          /* Make a task for each pair of progeny */
          if (t->subtype != task_subtype_external_grav) {
            for (int j = 0; j < 8; j++)
              if (ci->progeny[j] != NULL)
                for (int k = j + 1; k < 8; k++)
                  if (ci->progeny[k] != NULL)
                    scheduler_splittask_gravity(
                        scheduler_addtask(s, task_type_pair, t->subtype,
                                          sub_sid_flag[j][k], 0, ci->progeny[j],
                                          ci->progeny[k]),
                        s);
          }
        }
      } /* Cell is split */

      /* Otherwise, make sure the self task has a drift task */
      else {

        lock_lock(&ci->lock);

        if (ci->drift_gpart == NULL)
          ci->drift_gpart = scheduler_addtask(
              s, task_type_drift_gpart, task_subtype_none, 0, 0, ci, NULL);
        lock_unlock_blind(&ci->lock);
      }
    } /* Self interaction */

    /* Pair interaction? */
    else if (t->type == task_type_pair) {
684
685
686

      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
687
688
689
690
691
692
693
694
695
696
697
698
699
700
      struct cell *cj = t->cj;

      /* Foreign task? */
      if (ci->nodeID != s->nodeID && cj->nodeID != s->nodeID) {
        t->skip = 1;
        break;
      }

      /* Should this task be split-up? */
      if (ci->split && cj->split) {

        // MATTHIEU: nothing here for now

      } else {
701

702
703
704
705
706
707
        /* Create the drift for ci. */
        lock_lock(&ci->lock);
        if (ci->drift_gpart == NULL && ci->nodeID == engine_rank)
          ci->drift_gpart = scheduler_addtask(
              s, task_type_drift_gpart, task_subtype_none, 0, 0, ci, NULL);
        lock_unlock_blind(&ci->lock);
708

709
710
711
712
713
714
715
716
        /* Create the drift for cj. */
        lock_lock(&cj->lock);
        if (cj->drift_gpart == NULL && cj->nodeID == engine_rank)
          cj->drift_gpart = scheduler_addtask(
              s, task_type_drift_gpart, task_subtype_none, 0, 0, cj, NULL);
        lock_unlock_blind(&cj->lock);
      }
    } /* pair interaction? */
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
  }   /* iterate over the current task. */
}

/**
 * @brief Mapper function to split tasks that may be too large.
 *
 * @param map_data the tasks to process
 * @param num_elements the number of tasks.
 * @param extra_data The #scheduler we are working in.
 */
void scheduler_splittasks_mapper(void *map_data, int num_elements,
                                 void *extra_data) {

  /* Extract the parameters. */
  struct scheduler *s = (struct scheduler *)extra_data;
  struct task *tasks = (struct task *)map_data;
733

734
735
  for (int ind = 0; ind < num_elements; ind++) {
    struct task *t = &tasks[ind];
736
737
738
739
740
741
742
743
744
745
746
747
748
749

    /* Invoke the correct splitting strategy */
    if (t->subtype == task_subtype_density) {
      scheduler_splittask_hydro(t, s);
    } else if (t->subtype == task_subtype_external_grav) {
      scheduler_splittask_gravity(t, s);
    } else if (t->subtype == task_subtype_grav) {
      scheduler_splittask_gravity(t, s);
    } else if (t->type == task_type_grav_top_level ||
               t->type == task_type_grav_ghost) {
      // MATTHIEU: for the future
    } else {
      error("Unexpected task sub-type");
    }
750
  }
751
}
752

Matthieu Schaller's avatar
Matthieu Schaller committed
753
754
755
756
757
/**
 * @brief Splits all the tasks in the scheduler that are too large.
 *
 * @param s The #scheduler.
 */
758
void scheduler_splittasks(struct scheduler *s) {
759

760
761
  /* Call the mapper on each current task. */
  threadpool_map(s->threadpool, scheduler_splittasks_mapper, s->tasks,
762
                 s->nr_tasks, sizeof(struct task), 1000, s);
763
764
}

765
766
767
768
769
770
771
/**
 * @brief Add a #task to the #scheduler.
 *
 * @param s The #scheduler we are working in.
 * @param type The type of the task.
 * @param subtype The sub-type of the task.
 * @param flags The flags of the task.
772
773
 * @param implicit If true, only use this task to unlock dependencies, i.e.
 *        this task is never enqueued.
774
775
776
 * @param ci The first cell to interact.
 * @param cj The second cell to interact.
 */
777
struct task *scheduler_addtask(struct scheduler *s, enum task_types type,
778
779
                               enum task_subtypes subtype, int flags,
                               int implicit, struct cell *ci, struct cell *cj) {
780

781
782
783
784
785
786
#ifdef SWIFT_DEBUG_CHECKS
  if (ci == NULL && cj != NULL)
    error("Added a task with ci==NULL and cj!=NULL type=%s/%s",
          taskID_names[type], subtaskID_names[subtype]);
#endif

787
  /* Get the next free task. */
Pedro Gonnet's avatar
Pedro Gonnet committed
788
  const int ind = atomic_inc(&s->tasks_next);
Matthieu Schaller's avatar
Matthieu Schaller committed
789

790
791
792
793
  /* Overflow? */
  if (ind >= s->size) error("Task list overflow.");

  /* Get a pointer to the new task. */
Pedro Gonnet's avatar
Pedro Gonnet committed
794
  struct task *t = &s->tasks[ind];
795
796
797
798
799

  /* Copy the data. */
  t->type = type;
  t->subtype = subtype;
  t->flags = flags;
800
  t->wait = 0;
801
802
  t->ci = ci;
  t->cj = cj;
803
  t->skip = 1; /* Mark tasks as skip by default. */
804
  t->implicit = implicit;
805
806
807
  t->weight = 0;
  t->rank = 0;
  t->nr_unlock_tasks = 0;
808
#ifdef SWIFT_DEBUG_TASKS
809
  t->rid = -1;
810
811
  t->tic = 0;
  t->toc = 0;
812
#endif
813
814
815
816
817
818
819
820
821

  /* Add an index for it. */
  // lock_lock( &s->lock );
  s->tasks_ind[atomic_inc(&s->nr_tasks)] = ind;
  // lock_unlock_blind( &s->lock );

  /* Return a pointer to the new task. */
  return t;
}
822

823
824
825
826
827
828
829
830
/**
 * @brief Set the unlock pointers in each task.
 *
 * @param s The #scheduler.
 */
void scheduler_set_unlocks(struct scheduler *s) {

  /* Store the counts for each task. */
831
832
  short int *counts;
  if ((counts = (short int *)malloc(sizeof(short int) * s->nr_tasks)) == NULL)
833
    error("Failed to allocate temporary counts array.");
834
835
836
837
838
839
840
841
  bzero(counts, sizeof(short int) * s->nr_tasks);
  for (int k = 0; k < s->nr_unlocks; k++) {
    counts[s->unlock_ind[k]] += 1;

#ifdef SWIFT_DEBUG_CHECKS
    /* Check that we are not overflowing */
    if (counts[s->unlock_ind[k]] < 0)
      error("Task unlocking more than %d other tasks!",
842
843
            (1 << (8 * sizeof(short int) - 1)) - 1);

844
845
#endif
  }
846
847
848
849
850
851

  /* Compute the offset for each unlock block. */
  int *offsets;
  if ((offsets = (int *)malloc(sizeof(int) * (s->nr_tasks + 1))) == NULL)
    error("Failed to allocate temporary offsets array.");
  offsets[0] = 0;
852
853
854
855
856
857
858
859
  for (int k = 0; k < s->nr_tasks; k++) {
    offsets[k + 1] = offsets[k] + counts[k];

#ifdef SWIFT_DEBUG_CHECKS
    /* Check that we are not overflowing */
    if (offsets[k + 1] < 0) error("Task unlock offset array overflowing");
#endif
  }
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886

  /* Create and fill a temporary array with the sorted unlocks. */
  struct task **unlocks;
  if ((unlocks = (struct task **)malloc(sizeof(struct task *) *
                                        s->size_unlocks)) == NULL)
    error("Failed to allocate temporary unlocks array.");
  for (int k = 0; k < s->nr_unlocks; k++) {
    const int ind = s->unlock_ind[k];
    unlocks[offsets[ind]] = s->unlocks[k];
    offsets[ind] += 1;
  }

  /* Swap the unlocks. */
  free(s->unlocks);
  s->unlocks = unlocks;

  /* Re-set the offsets. */
  offsets[0] = 0;
  for (int k = 1; k < s->nr_tasks; k++)
    offsets[k] = offsets[k - 1] + counts[