scheduler.c 57.5 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 "version.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
149
  FILE *f = fopen(filename, "w");
  if (f == NULL) error("Error opening depenency graph file.");
150

Matthieu Schaller's avatar
Matthieu Schaller committed
151
  /* Write header */
152
  fprintf(f, "digraph task_dep {\n");
153
  fprintf(f, "label=\"Task dependencies for SWIFT %s\"", git_revision());
154
155
156
157
158
  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
159
160
  for (int i = 0; i < s->nr_tasks; i++) {
    const struct task *ta = &s->tasks[i];
lhausamm's avatar
lhausamm committed
161
162

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

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

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

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

lhausamm's avatar
lhausamm committed
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
        /* 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];
      }
193
194
195

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

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

        /* 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
220
      }
221
    }
lhausamm's avatar
lhausamm committed
222
  }
lhausamm's avatar
lhausamm committed
223

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

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

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

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

246
247
    /* Reset the redo flag. */
    redo = 0;
248

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

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

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

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

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

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

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

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

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

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

310
    } /* Self interaction */
311

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

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

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

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

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

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

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

          /* Otherwise, split it. */
342
343
        } else {

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

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

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

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

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

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

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

707
708
709
710
711
712
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
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
741
742
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;
      }

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

    } /* Self interaction */

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

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

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