scheduler.c 57.4 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
#include "tools.h"
54

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

60
61
62
63
64
65
66
/**
 * @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.
 */
67
68
void scheduler_addunlock(struct scheduler *s, struct task *ta,
                         struct task *tb) {
69
70
71
72
73
#ifdef SWIFT_DEBUG_CHECKS
  if (ta == NULL) error("Unlocking task is NULL.");
  if (tb == NULL) error("Unlocked task is NULL.");
#endif

74
75
76
77
78
  /* 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) {
79
    /* Allocate the new buffer. */
80
81
82
    struct task **unlocks_new;
    int *unlock_ind_new;
    const int size_unlocks_new = s->size_unlocks * 2;
83
84
    if ((unlocks_new = (struct task **)malloc(sizeof(struct task *) *
                                              size_unlocks_new)) == NULL ||
85
86
        (unlock_ind_new = (int *)malloc(sizeof(int) * size_unlocks_new)) ==
            NULL)
87
      error("Failed to re-allocate unlocks.");
88

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

93
    /* Copy the buffers. */
94
95
96
97
98
99
    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;
100

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

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

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

115
116
117
/**
 * @brief Write a dot file with the task dependencies.
 *
Matthieu Schaller's avatar
Matthieu Schaller committed
118
119
120
 * Run plot_task_dependencies.sh for an example of how to use it
 * to generate the figure.
 *
121
 * @param s The #scheduler we are working in.
Matthieu Schaller's avatar
Matthieu Schaller committed
122
 * @param verbose Are we verbose about this?
123
 */
Matthieu Schaller's avatar
Matthieu Schaller committed
124
void scheduler_write_dependencies(struct scheduler *s, int verbose) {
Matthieu Schaller's avatar
Matthieu Schaller committed
125

Matthieu Schaller's avatar
Matthieu Schaller committed
126
  const ticks tic = getticks();
127

Matthieu Schaller's avatar
Matthieu Schaller committed
128
129
  /* Conservative number of dependencies per task type */
  const int max_nber_dep = 128;
lhausamm's avatar
lhausamm committed
130

Matthieu Schaller's avatar
Matthieu Schaller committed
131
  /* Number of possibble relations between tasks */
Matthieu Schaller's avatar
Matthieu Schaller committed
132
133
  const int nber_relation =
      2 * task_type_count * task_subtype_count * max_nber_dep;
134

Matthieu Schaller's avatar
Matthieu Schaller committed
135
136
137
138
  /* To get the table of max_nber_dep for a task:
   * ind = (ta * task_subtype_count + sa) * max_nber_dep * 2
   * where ta is the value of task_type and sa is the value of
   * task_subtype  */
139
  int *table = malloc(nber_relation * sizeof(int));
Matthieu Schaller's avatar
Matthieu Schaller committed
140
141
  if (table == NULL)
    error("Error allocating memory for task-dependency graph.");
lhausamm's avatar
lhausamm committed
142

Matthieu Schaller's avatar
Matthieu Schaller committed
143
144
  /* Reset everything */
  for (int i = 0; i < nber_relation; i++) table[i] = -1;
lhausamm's avatar
lhausamm committed
145

Matthieu Schaller's avatar
Matthieu Schaller committed
146
  /* Create file */
147
  char filename[200] = "dependency_graph.dot";
Matthieu Schaller's avatar
Matthieu Schaller committed
148
  FILE *f = open_and_check_file(filename, "w");
149

Matthieu Schaller's avatar
Matthieu Schaller committed
150
  /* Write header */
151
152
153
154
155
156
  fprintf(f, "digraph task_dep {\n");
  fprintf(f, "\t compound=true;\n");
  fprintf(f, "\t ratio=0.66;\n");
  fprintf(f, "\t node[nodesep=0.15];\n");

  /* loop over all tasks */
Matthieu Schaller's avatar
Matthieu Schaller committed
157
158
  for (int i = 0; i < s->nr_tasks; i++) {
    const struct task *ta = &s->tasks[i];
lhausamm's avatar
lhausamm committed
159
160

    /* and theirs dependencies */
Matthieu Schaller's avatar
Matthieu Schaller committed
161
162
    for (int j = 0; j < ta->nr_unlock_tasks; j++) {
      const struct task *tb = ta->unlock_tasks[j];
lhausamm's avatar
lhausamm committed
163
164

      /* check if dependency already written */
165
      int written = 0;
lhausamm's avatar
lhausamm committed
166

167
      /* Current index */
168
169
      int ind = ta->type * task_subtype_count + ta->subtype;
      ind *= 2 * max_nber_dep;
lhausamm's avatar
lhausamm committed
170

171
172
      int k = 0;
      int *cur = &table[ind];
lhausamm's avatar
lhausamm committed
173
      while (k < max_nber_dep) {
Matthieu Schaller's avatar
Matthieu Schaller committed
174

lhausamm's avatar
lhausamm committed
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
        /* not written yet */
        if (cur[0] == -1) {
          cur[0] = tb->type;
          cur[1] = tb->subtype;
          break;
        }

        /* already written */
        if (cur[0] == tb->type && cur[1] == tb->subtype) {
          written = 1;
          break;
        }

        k += 1;
        cur = &cur[3];
      }
191
192
193

      /* max_nber_dep is too small */
      if (k == max_nber_dep)
lhausamm's avatar
lhausamm committed
194
195
        error("Not enough memory, please increase max_nber_dep");

lhausamm's avatar
lhausamm committed
196
      /* Not written yet => write it */
197
      if (!written) {
Matthieu Schaller's avatar
Matthieu Schaller committed
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217

        /* text to write */
        char ta_name[200];
        char tb_name[200];

        /* construct line */
        if (ta->subtype == task_subtype_none)
          sprintf(ta_name, "%s", taskID_names[ta->type]);
        else
          sprintf(ta_name, "\"%s %s\"", taskID_names[ta->type],
                  subtaskID_names[ta->subtype]);

        if (tb->subtype == task_subtype_none)
          sprintf(tb_name, "%s", taskID_names[tb->type]);
        else
          sprintf(tb_name, "\"%s %s\"", taskID_names[tb->type],
                  subtaskID_names[tb->subtype]);

        /* Write to the ffile */
        fprintf(f, "\t %s->%s;\n", ta_name, tb_name);
lhausamm's avatar
lhausamm committed
218
      }
219
    }
lhausamm's avatar
lhausamm committed
220
  }
lhausamm's avatar
lhausamm committed
221

Matthieu Schaller's avatar
Matthieu Schaller committed
222
  /* Be clean */
223
224
  fprintf(f, "}");
  fclose(f);
225
  free(table);
Matthieu Schaller's avatar
Matthieu Schaller committed
226

Matthieu Schaller's avatar
Matthieu Schaller committed
227
  if (verbose)
Matthieu Schaller's avatar
Matthieu Schaller committed
228
    message("Printing task graph took %.3f %s.",
Matthieu Schaller's avatar
Matthieu Schaller committed
229
            clocks_from_ticks(getticks() - tic), clocks_getunit());
230
231
}

232
/**
233
 * @brief Split a hydrodynamic task if too large.
234
 *
235
236
 * @param t The #task
 * @param s The #scheduler we are working in.
237
 */
238
static void scheduler_splittask_hydro(struct task *t, struct scheduler *s) {
239

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

244
245
    /* Reset the redo flag. */
    redo = 0;
246

247
    /* Non-splittable task? */
248
249
    if ((t->ci == NULL) || (t->type == task_type_pair && t->cj == NULL) ||
        t->ci->count == 0 || (t->cj != NULL && t->cj->count == 0)) {
250
      t->type = task_type_none;
251
252
      t->subtype = task_subtype_none;
      t->cj = NULL;
253
254
255
      t->skip = 1;
      break;
    }
256

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

260
261
262
263
264
      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;

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

269
      /* Is this cell even split and the task does not violate h ? */
270
      if (cell_can_split_self_task(ci)) {
271

272
        /* Make a sub? */
273
        if (scheduler_dosub && ci->count < space_subsize_self) {
274

275
276
277
278
279
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

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

281
282
283
284
285
286
287
288
          /* 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++)
289
            if (ci->progeny[k] != NULL && ci->progeny[k]->count)
290
              scheduler_splittask_hydro(
291
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
292
                                    ci->progeny[k], NULL),
293
294
                  s);

295
296
          /* Make a task for each pair of progeny */
          for (int j = 0; j < 8; j++)
297
            if (ci->progeny[j] != NULL && ci->progeny[j]->count)
298
              for (int k = j + 1; k < 8; k++)
299
                if (ci->progeny[k] != NULL && ci->progeny[k]->count)
300
301
                  scheduler_splittask_hydro(
                      scheduler_addtask(s, task_type_pair, t->subtype,
302
                                        sub_sid_flag[j][k], 0, ci->progeny[j],
303
304
                                        ci->progeny[k]),
                      s);
305
        }
306
      } /* Cell is split */
307

308
    } /* Self interaction */
309

310
311
    /* Pair interaction? */
    else if (t->type == task_type_pair) {
312

313
314
315
      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
316

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

323
324
325
      /* 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
326
      const int sid = space_getsid(s->space, &ci, &cj, shift);
327

328
      /* Should this task be split-up? */
329
      if (cell_can_split_pair_task(ci) && cell_can_split_pair_task(cj)) {
330
331

        /* Replace by a single sub-task? */
332
333
        if (scheduler_dosub && /* Use division to avoid integer overflow. */
            ci->count * sid_scale[sid] < space_subsize_pair / cj->count &&
334
            !sort_is_corner(sid)) {
335
336
337
338
339

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

          /* Otherwise, split it. */
340
341
        } else {

342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
          /* 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;
358
              scheduler_splittask_hydro(
359
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
360
                                    ci->progeny[7], cj->progeny[1]),
361
                  s);
362
              scheduler_splittask_hydro(
363
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
364
                                    ci->progeny[6], cj->progeny[1]),
365
                  s);
366
              scheduler_splittask_hydro(
367
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
368
                                    ci->progeny[7], cj->progeny[0]),
369
370
371
372
373
374
375
376
377
378
379
380
381
                  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;
382
              scheduler_splittask_hydro(
383
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
384
                                    ci->progeny[7], cj->progeny[2]),
385
                  s);
386
              scheduler_splittask_hydro(
387
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
388
                                    ci->progeny[5], cj->progeny[2]),
389
                  s);
390
              scheduler_splittask_hydro(
391
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
392
                                    ci->progeny[7], cj->progeny[0]),
393
394
395
396
397
398
399
                  s);
              break;

            case 4: /* (  1 ,  0 ,  0 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[0];
              t->flags = 4;
400
              scheduler_splittask_hydro(
401
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
402
                                    ci->progeny[5], cj->progeny[0]),
403
                  s);
404
              scheduler_splittask_hydro(
405
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
406
                                    ci->progeny[6], cj->progeny[0]),
407
                  s);
408
              scheduler_splittask_hydro(
409
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
410
                                    ci->progeny[7], cj->progeny[0]),
411
                  s);
412
              scheduler_splittask_hydro(
413
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
414
                                    ci->progeny[4], cj->progeny[1]),
415
                  s);
416
              scheduler_splittask_hydro(
417
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
418
                                    ci->progeny[5], cj->progeny[1]),
419
                  s);
420
              scheduler_splittask_hydro(
421
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
422
                                    ci->progeny[6], cj->progeny[1]),
423
                  s);
424
              scheduler_splittask_hydro(
425
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
426
                                    ci->progeny[7], cj->progeny[1]),
427
                  s);
428
              scheduler_splittask_hydro(
429
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
430
                                    ci->progeny[4], cj->progeny[2]),
431
                  s);
432
              scheduler_splittask_hydro(
433
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
434
                                    ci->progeny[5], cj->progeny[2]),
435
                  s);
436
              scheduler_splittask_hydro(
437
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
438
                                    ci->progeny[6], cj->progeny[2]),
439
                  s);
440
              scheduler_splittask_hydro(
441
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
442
                                    ci->progeny[7], cj->progeny[2]),
443
                  s);
444
              scheduler_splittask_hydro(
445
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
446
                                    ci->progeny[4], cj->progeny[3]),
447
                  s);
448
              scheduler_splittask_hydro(
449
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
450
                                    ci->progeny[5], cj->progeny[3]),
451
                  s);
452
              scheduler_splittask_hydro(
453
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
454
                                    ci->progeny[6], cj->progeny[3]),
455
                  s);
456
              scheduler_splittask_hydro(
457
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
458
                                    ci->progeny[7], cj->progeny[3]),
459
460
461
462
463
464
465
                  s);
              break;

            case 5: /* (  1 ,  0 , -1 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[1];
              t->flags = 5;
466
              scheduler_splittask_hydro(
467
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
468
                                    ci->progeny[6], cj->progeny[3]),
469
                  s);
470
              scheduler_splittask_hydro(
471
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
472
                                    ci->progeny[4], cj->progeny[3]),
473
                  s);
474
              scheduler_splittask_hydro(
475
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
476
                                    ci->progeny[6], cj->progeny[1]),
477
478
479
480
481
482
483
484
485
486
487
488
489
                  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;
490
              scheduler_splittask_hydro(
491
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
492
                                    ci->progeny[5], cj->progeny[2]),
493
                  s);
494
              scheduler_splittask_hydro(
495
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
496
                                    ci->progeny[4], cj->progeny[2]),
497
                  s);
498
              scheduler_splittask_hydro(
499
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
500
                                    ci->progeny[5], cj->progeny[3]),
501
502
503
504
505
506
507
508
509
510
511
512
513
                  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;
514
              scheduler_splittask_hydro(
515
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
516
                                    ci->progeny[7], cj->progeny[4]),
517
                  s);
518
              scheduler_splittask_hydro(
519
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
520
                                    ci->progeny[3], cj->progeny[4]),
521
                  s);
522
              scheduler_splittask_hydro(
523
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
524
                                    ci->progeny[7], cj->progeny[0]),
525
526
527
528
529
530
531
                  s);
              break;

            case 10: /* (  0 ,  1 ,  0 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[0];
              t->flags = 10;
532
              scheduler_splittask_hydro(
533
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
534
                                    ci->progeny[3], cj->progeny[0]),
535
                  s);
536
              scheduler_splittask_hydro(
537
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
538
                                    ci->progeny[6], cj->progeny[0]),
539
                  s);
540
              scheduler_splittask_hydro(
541
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
542
                                    ci->progeny[7], cj->progeny[0]),
543
                  s);
544
              scheduler_splittask_hydro(
545
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
546
                                    ci->progeny[2], cj->progeny[1]),
547
                  s);
548
              scheduler_splittask_hydro(
549
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
550
                                    ci->progeny[3], cj->progeny[1]),
551
                  s);
552
              scheduler_splittask_hydro(
553
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
554
                                    ci->progeny[6], cj->progeny[1]),
555
                  s);
556
              scheduler_splittask_hydro(
557
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
558
                                    ci->progeny[7], cj->progeny[1]),
559
                  s);
560
              scheduler_splittask_hydro(
561
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
562
                                    ci->progeny[2], cj->progeny[4]),
563
                  s);
564
              scheduler_splittask_hydro(
565
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
566
                                    ci->progeny[3], cj->progeny[4]),
567
                  s);
568
              scheduler_splittask_hydro(
569
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
570
                                    ci->progeny[6], cj->progeny[4]),
571
                  s);
572
              scheduler_splittask_hydro(
573
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
574
                                    ci->progeny[7], cj->progeny[4]),
575
                  s);
576
              scheduler_splittask_hydro(
577
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
578
                                    ci->progeny[2], cj->progeny[5]),
579
                  s);
580
              scheduler_splittask_hydro(
581
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
582
                                    ci->progeny[3], cj->progeny[5]),
583
                  s);
584
              scheduler_splittask_hydro(
585
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
586
                                    ci->progeny[6], cj->progeny[5]),
587
                  s);
588
              scheduler_splittask_hydro(
589
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
590
                                    ci->progeny[7], cj->progeny[5]),
591
592
593
594
595
596
597
                  s);
              break;

            case 11: /* (  0 ,  1 , -1 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[1];
              t->flags = 11;
598
              scheduler_splittask_hydro(
599
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
600
                                    ci->progeny[6], cj->progeny[5]),
601
                  s);
602
              scheduler_splittask_hydro(
603
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
604
                                    ci->progeny[2], cj->progeny[5]),
605
                  s);
606
              scheduler_splittask_hydro(
607
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
608
                                    ci->progeny[6], cj->progeny[1]),
609
610
611
612
613
614
615
                  s);
              break;

            case 12: /* (  0 ,  0 ,  1 ) */
              t->ci = ci->progeny[1];
              t->cj = cj->progeny[0];
              t->flags = 12;
616
              scheduler_splittask_hydro(
617
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
618
                                    ci->progeny[3], cj->progeny[0]),
619
                  s);
620
              scheduler_splittask_hydro(
621
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
622
                                    ci->progeny[5], cj->progeny[0]),
623
                  s);
624
              scheduler_splittask_hydro(
625
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
626
                                    ci->progeny[7], cj->progeny[0]),
627
                  s);
628
              scheduler_splittask_hydro(
629
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
630
                                    ci->progeny[1], cj->progeny[2]),
631
                  s);
632
              scheduler_splittask_hydro(
633
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
634
                                    ci->progeny[3], cj->progeny[2]),
635
                  s);
636
              scheduler_splittask_hydro(
637
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
638
                                    ci->progeny[5], cj->progeny[2]),
639
                  s);
640
              scheduler_splittask_hydro(
641
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
642
                                    ci->progeny[7], cj->progeny[2]),
643
                  s);
644
              scheduler_splittask_hydro(
645
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
646
                                    ci->progeny[1], cj->progeny[4]),
647
                  s);
648
              scheduler_splittask_hydro(
649
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
650
                                    ci->progeny[3], cj->progeny[4]),
651
                  s);
652
              scheduler_splittask_hydro(
653
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
654
                                    ci->progeny[5], cj->progeny[4]),
655
                  s);
656
              scheduler_splittask_hydro(
657
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
658
                                    ci->progeny[7], cj->progeny[4]),
659
                  s);
660
              scheduler_splittask_hydro(
661
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
662
                                    ci->progeny[1], cj->progeny[6]),
663
                  s);
664
              scheduler_splittask_hydro(
665
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
666
                                    ci->progeny[3], cj->progeny[6]),
667
                  s);
668
              scheduler_splittask_hydro(
669
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
670
                                    ci->progeny[5], cj->progeny[6]),
671
                  s);
672
              scheduler_splittask_hydro(
673
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
674
                                    ci->progeny[7], cj->progeny[6]),
675
676
677
                  s);
              break;
          } /* switch(sid) */
678
679
        }

680
681
682
683
684
685
686
687
688
689
690
        /* 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++)
691
          if (ci->progeny[j] != NULL && ci->progeny[j]->count)
692
            for (int k = 0; k < 8; k++)
693
              if (cj->progeny[k] != NULL && cj->progeny[k]->count) {
694
695
                struct task *tl =
                    scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
696
                                      ci->progeny[j], cj->progeny[k]);
697
                scheduler_splittask_hydro(tl, s);
698
699
700
701
702
703
704
                tl->flags = space_getsid(s->space, &t->ci, &t->cj, shift);
              }
      }
    } /* pair interaction? */
  }   /* iterate over the current task. */
}

705
706
707
708
709
710
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
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;
      }

741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
      /* Should we split this task? */
      if (ci->split && ci->gcount > space_subsize_self_grav) {

        /* 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);
769
        }
770
      } /* Cell is split */
771
772
773
774
775

    } /* Self interaction */

    /* Pair interaction? */
    else if (t->type == task_type_pair) {
776
777
778

      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
779
780
781
782
783
784
785
786
      struct cell *cj = t->cj;

      /* Foreign task? */
      if (ci->nodeID != s->nodeID && cj->nodeID != s->nodeID) {
        t->skip = 1;
        break;
      }
    } /* pair interaction? */
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
  }   /* 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;
803

804
805
  for (int ind = 0; ind < num_elements; ind++) {
    struct task *t = &tasks[ind];