scheduler.c 60.9 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);
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

Peter W. Draper's avatar
Peter W. Draper committed
131
  /* Number of possible 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 = fopen(filename, "w");
Peter W. Draper's avatar
Peter W. Draper committed
149
  if (f == NULL) error("Error opening dependency 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\";\n", 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

Peter W. Draper's avatar
Peter W. Draper committed
162
    /* and their 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);
220

Matthieu Schaller's avatar
Matthieu Schaller committed
221
222
        /* Change colour of implicit tasks */
        if (ta->implicit)
223
          fprintf(f, "\t %s [style = filled];\n\t %s [color = lightgrey];\n",
Matthieu Schaller's avatar
Matthieu Schaller committed
224
225
                  ta_name, ta_name);
        if (tb->implicit)
226
          fprintf(f, "\t %s [style = filled];\n\t %s [color = lightgrey];\n",
Matthieu Schaller's avatar
Matthieu Schaller committed
227
                  tb_name, tb_name);
lhausamm's avatar
lhausamm committed
228
      }
229
    }
lhausamm's avatar
lhausamm committed
230
  }
lhausamm's avatar
lhausamm committed
231

232
  int density_cluster[4] = {0};
233
  int gradient_cluster[4] = {0};
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
  int force_cluster[4] = {0};
  int gravity_cluster[4] = {0};

  /* Modify the style of some tasks on the plot */
  for (int type = 0; type < task_type_count; ++type) {

    for (int subtype = 0; subtype < task_subtype_count; ++subtype) {

      const int ind = 2 * (type * task_subtype_count + subtype) * max_nber_dep;

      /* Does this task/sub-task exist? */
      if (table[ind] != -1) {

        /* Make MPI tasks a different shape */
        if (type == task_type_send || type == task_type_recv)
          fprintf(f, "\t \"%s %s\" [shape = diamond];\n", taskID_names[type],
                  subtaskID_names[subtype]);

        for (int k = 0; k < 4; ++k) {
          if (type == task_type_self + k && subtype == task_subtype_density)
            density_cluster[k] = 1;
255
256
          if (type == task_type_self + k && subtype == task_subtype_gradient)
            gradient_cluster[k] = 1;
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
          if (type == task_type_self + k && subtype == task_subtype_force)
            force_cluster[k] = 1;
          if (type == task_type_self + k && subtype == task_subtype_grav)
            gravity_cluster[k] = 1;
        }
        if (type == task_type_grav_top_level) gravity_cluster[2] = 1;
        if (type == task_type_grav_long_range) gravity_cluster[3] = 1;
      }
    }
  }

  /* Make a cluster for the density tasks */
  fprintf(f, "\t subgraph cluster0{\n");
  fprintf(f, "\t\t label=\"\";\n");
  for (int k = 0; k < 4; ++k)
    if (density_cluster[k])
      fprintf(f, "\t\t \"%s %s\";\n", taskID_names[task_type_self + k],
              subtaskID_names[task_subtype_density]);
  fprintf(f, "\t};\n");

  /* Make a cluster for the force tasks */
  fprintf(f, "\t subgraph cluster1{\n");
  fprintf(f, "\t\t label=\"\";\n");
  for (int k = 0; k < 4; ++k)
    if (force_cluster[k])
      fprintf(f, "\t\t \"%s %s\";\n", taskID_names[task_type_self + k],
              subtaskID_names[task_subtype_force]);
  fprintf(f, "\t};\n");

286
  /* Make a cluster for the gradient tasks */
287
288
  fprintf(f, "\t subgraph cluster2{\n");
  fprintf(f, "\t\t label=\"\";\n");
289
290
291
292
293
294
295
296
297
  for (int k = 0; k < 4; ++k)
    if (gradient_cluster[k])
      fprintf(f, "\t\t \"%s %s\";\n", taskID_names[task_type_self + k],
              subtaskID_names[task_subtype_gradient]);
  fprintf(f, "\t};\n");

  /* Make a cluster for the gravity tasks */
  fprintf(f, "\t subgraph cluster3{\n");
  fprintf(f, "\t\t label=\"\";\n");
298
299
300
301
302
303
304
305
306
307
  for (int k = 0; k < 2; ++k)
    if (gravity_cluster[k])
      fprintf(f, "\t\t \"%s %s\";\n", taskID_names[task_type_self + k],
              subtaskID_names[task_subtype_grav]);
  if (gravity_cluster[2])
    fprintf(f, "\t\t %s;\n", taskID_names[task_type_grav_top_level]);
  if (gravity_cluster[3])
    fprintf(f, "\t\t %s;\n", taskID_names[task_type_grav_long_range]);
  fprintf(f, "\t};\n");

Matthieu Schaller's avatar
Matthieu Schaller committed
308
  /* Be clean */
309
310
  fprintf(f, "}");
  fclose(f);
311
  free(table);
Matthieu Schaller's avatar
Matthieu Schaller committed
312

Matthieu Schaller's avatar
Matthieu Schaller committed
313
  if (verbose)
Matthieu Schaller's avatar
Matthieu Schaller committed
314
    message("Printing task graph took %.3f %s.",
Matthieu Schaller's avatar
Matthieu Schaller committed
315
            clocks_from_ticks(getticks() - tic), clocks_getunit());
316
317
}

318
/**
319
 * @brief Split a hydrodynamic task if too large.
320
 *
321
322
 * @param t The #task
 * @param s The #scheduler we are working in.
323
 */
324
static void scheduler_splittask_hydro(struct task *t, struct scheduler *s) {
325

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

330
331
    /* Reset the redo flag. */
    redo = 0;
332

333
    /* Non-splittable task? */
334
335
    if ((t->ci == NULL) || (t->type == task_type_pair && t->cj == NULL) ||
        t->ci->count == 0 || (t->cj != NULL && t->cj->count == 0)) {
336
      t->type = task_type_none;
337
338
      t->subtype = task_subtype_none;
      t->cj = NULL;
339
340
341
      t->skip = 1;
      break;
    }
342

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

346
347
348
349
350
      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;

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

355
      /* Is this cell even split and the task does not violate h ? */
356
      if (cell_can_split_self_task(ci)) {
357

358
        /* Make a sub? */
359
        if (scheduler_dosub && ci->count < space_subsize_self) {
360

361
362
363
364
365
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

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

367
368
369
370
371
372
373
374
          /* 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++)
375
            if (ci->progeny[k] != NULL && ci->progeny[k]->count)
376
              scheduler_splittask_hydro(
377
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
378
                                    ci->progeny[k], NULL),
379
380
                  s);

381
382
          /* Make a task for each pair of progeny */
          for (int j = 0; j < 8; j++)
383
            if (ci->progeny[j] != NULL && ci->progeny[j]->count)
384
              for (int k = j + 1; k < 8; k++)
385
                if (ci->progeny[k] != NULL && ci->progeny[k]->count)
386
387
                  scheduler_splittask_hydro(
                      scheduler_addtask(s, task_type_pair, t->subtype,
388
                                        sub_sid_flag[j][k], 0, ci->progeny[j],
389
390
                                        ci->progeny[k]),
                      s);
391
        }
392
      } /* Cell is split */
393

394
    } /* Self interaction */
395

396
397
    /* Pair interaction? */
    else if (t->type == task_type_pair) {
398

399
400
401
      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
402

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

409
410
411
      /* 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
412
      const int sid = space_getsid(s->space, &ci, &cj, shift);
413

414
      /* Should this task be split-up? */
415
      if (cell_can_split_pair_task(ci) && cell_can_split_pair_task(cj)) {
416
417

        /* Replace by a single sub-task? */
418
419
        if (scheduler_dosub && /* Use division to avoid integer overflow. */
            ci->count * sid_scale[sid] < space_subsize_pair / cj->count &&
420
            !sort_is_corner(sid)) {
421
422
423
424
425

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

          /* Otherwise, split it. */
426
427
        } else {

428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
          /* 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;
444
              scheduler_splittask_hydro(
445
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
446
                                    ci->progeny[7], cj->progeny[1]),
447
                  s);
448
              scheduler_splittask_hydro(
449
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
450
                                    ci->progeny[6], cj->progeny[1]),
451
                  s);
452
              scheduler_splittask_hydro(
453
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
454
                                    ci->progeny[7], cj->progeny[0]),
455
456
457
458
459
460
461
462
463
464
465
466
467
                  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;
468
              scheduler_splittask_hydro(
469
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
470
                                    ci->progeny[7], cj->progeny[2]),
471
                  s);
472
              scheduler_splittask_hydro(
473
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
474
                                    ci->progeny[5], cj->progeny[2]),
475
                  s);
476
              scheduler_splittask_hydro(
477
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
478
                                    ci->progeny[7], cj->progeny[0]),
479
480
481
482
483
484
485
                  s);
              break;

            case 4: /* (  1 ,  0 ,  0 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[0];
              t->flags = 4;
486
              scheduler_splittask_hydro(
487
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
488
                                    ci->progeny[5], cj->progeny[0]),
489
                  s);
490
              scheduler_splittask_hydro(
491
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
492
                                    ci->progeny[6], cj->progeny[0]),
493
                  s);
494
              scheduler_splittask_hydro(
495
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
496
                                    ci->progeny[7], cj->progeny[0]),
497
                  s);
498
              scheduler_splittask_hydro(
499
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
500
                                    ci->progeny[4], cj->progeny[1]),
501
                  s);
502
              scheduler_splittask_hydro(
503
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
504
                                    ci->progeny[5], cj->progeny[1]),
505
                  s);
506
              scheduler_splittask_hydro(
507
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
508
                                    ci->progeny[6], cj->progeny[1]),
509
                  s);
510
              scheduler_splittask_hydro(
511
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
512
                                    ci->progeny[7], cj->progeny[1]),
513
                  s);
514
              scheduler_splittask_hydro(
515
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
516
                                    ci->progeny[4], cj->progeny[2]),
517
                  s);
518
              scheduler_splittask_hydro(
519
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
520
                                    ci->progeny[5], cj->progeny[2]),
521
                  s);
522
              scheduler_splittask_hydro(
523
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
524
                                    ci->progeny[6], cj->progeny[2]),
525
                  s);
526
              scheduler_splittask_hydro(
527
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
528
                                    ci->progeny[7], cj->progeny[2]),
529
                  s);
530
              scheduler_splittask_hydro(
531
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
532
                                    ci->progeny[4], cj->progeny[3]),
533
                  s);
534
              scheduler_splittask_hydro(
535
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
536
                                    ci->progeny[5], cj->progeny[3]),
537
                  s);
538
              scheduler_splittask_hydro(
539
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
540
                                    ci->progeny[6], cj->progeny[3]),
541
                  s);
542
              scheduler_splittask_hydro(
543
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
544
                                    ci->progeny[7], cj->progeny[3]),
545
546
547
548
549
550
551
                  s);
              break;

            case 5: /* (  1 ,  0 , -1 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[1];
              t->flags = 5;
552
              scheduler_splittask_hydro(
553
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
554
                                    ci->progeny[6], cj->progeny[3]),
555
                  s);
556
              scheduler_splittask_hydro(
557
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
558
                                    ci->progeny[4], cj->progeny[3]),
559
                  s);
560
              scheduler_splittask_hydro(
561
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
562
                                    ci->progeny[6], cj->progeny[1]),
563
564
565
566
567
568
569
570
571
572
573
574
575
                  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;
576
              scheduler_splittask_hydro(
577
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
578
                                    ci->progeny[5], cj->progeny[2]),
579
                  s);
580
              scheduler_splittask_hydro(
581
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
582
                                    ci->progeny[4], cj->progeny[2]),
583
                  s);
584
              scheduler_splittask_hydro(
585
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
586
                                    ci->progeny[5], cj->progeny[3]),
587
588
589
590
591
592
593
594
595
596
597
598
599
                  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;
600
              scheduler_splittask_hydro(
601
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
602
                                    ci->progeny[7], cj->progeny[4]),
603
                  s);
604
              scheduler_splittask_hydro(
605
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
606
                                    ci->progeny[3], cj->progeny[4]),
607
                  s);
608
              scheduler_splittask_hydro(
609
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
610
                                    ci->progeny[7], cj->progeny[0]),
611
612
613
614
615
616
617
                  s);
              break;

            case 10: /* (  0 ,  1 ,  0 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[0];
              t->flags = 10;
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, 7, 0,
624
                                    ci->progeny[6], cj->progeny[0]),
625
                  s);
626
              scheduler_splittask_hydro(
627
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 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[2], cj->progeny[1]),
633
                  s);
634
              scheduler_splittask_hydro(
635
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
636
                                    ci->progeny[3], cj->progeny[1]),
637
                  s);
638
              scheduler_splittask_hydro(
639
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
640
                                    ci->progeny[6], cj->progeny[1]),
641
                  s);
642
              scheduler_splittask_hydro(
643
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
644
                                    ci->progeny[7], cj->progeny[1]),
645
                  s);
646
              scheduler_splittask_hydro(
647
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
648
                                    ci->progeny[2], cj->progeny[4]),
649
                  s);
650
              scheduler_splittask_hydro(
651
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
652
                                    ci->progeny[3], cj->progeny[4]),
653
                  s);
654
              scheduler_splittask_hydro(
655
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
656
                                    ci->progeny[6], 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[2], cj->progeny[5]),
665
                  s);
666
              scheduler_splittask_hydro(
667
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
668
                                    ci->progeny[3], cj->progeny[5]),
669
                  s);
670
              scheduler_splittask_hydro(
671
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
672
                                    ci->progeny[6], cj->progeny[5]),
673
                  s);
674
              scheduler_splittask_hydro(
675
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
676
                                    ci->progeny[7], cj->progeny[5]),
677
678
679
680
681
682
683
                  s);
              break;

            case 11: /* (  0 ,  1 , -1 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[1];
              t->flags = 11;
684
              scheduler_splittask_hydro(
685
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
686
                                    ci->progeny[6], cj->progeny[5]),
687
                  s);
688
              scheduler_splittask_hydro(
689
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
690
                                    ci->progeny[2], cj->progeny[5]),
691
                  s);
692
              scheduler_splittask_hydro(
693
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
694
                                    ci->progeny[6], cj->progeny[1]),
695
696
697
698
699
700
701
                  s);
              break;

            case 12: /* (  0 ,  0 ,  1 ) */
              t->ci = ci->progeny[1];
              t->cj = cj->progeny[0];
              t->flags = 12;
702
              scheduler_splittask_hydro(
703
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
704
                                    ci->progeny[3], cj->progeny[0]),
705
                  s);
706
              scheduler_splittask_hydro(
707
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
708
                                    ci->progeny[5], cj->progeny[0]),
709
                  s);
710
              scheduler_splittask_hydro(
711
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
712
                                    ci->progeny[7], cj->progeny[0]),
713
                  s);
714
              scheduler_splittask_hydro(
715
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
716
                                    ci->progeny[1], cj->progeny[2]),
717
                  s);
718
              scheduler_splittask_hydro(
719
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
720
                                    ci->progeny[3], cj->progeny[2]),
721
                  s);
722
              scheduler_splittask_hydro(
723
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
724
                                    ci->progeny[5], cj->progeny[2]),
725
                  s);
726
              scheduler_splittask_hydro(
727
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
728
                                    ci->progeny[7], cj->progeny[2]),
729
                  s);
730
              scheduler_splittask_hydro(
731
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
732
                                    ci->progeny[1], cj->progeny[4]),
733
                  s);
734
              scheduler_splittask_hydro(
735
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
736
                                    ci->progeny[3], cj->progeny[4]),
737
                  s);
738
              scheduler_splittask_hydro(
739
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
740
                                    ci->progeny[5], cj->progeny[4]),
741
                  s);
742
              scheduler_splittask_hydro(
743
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
744
                                    ci->progeny[7], cj->progeny[4]),
745
                  s);
746
              scheduler_splittask_hydro(
747
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
748
                                    ci->progeny[1], cj->progeny[6]),
749
                  s);
750
              scheduler_splittask_hydro(
751
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
752
                                    ci->progeny[3], cj->progeny[6]),
753
                  s);
754
              scheduler_splittask_hydro(
755
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
756
                                    ci->progeny[5], cj->progeny[6]),
757
                  s);
758
              scheduler_splittask_hydro(
759
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
760
                                    ci->progeny[7], cj->progeny[6]),
761
762
763
                  s);
              break;
          } /* switch(sid) */
764
765
        }

766
767
768
769
770
771
772
773
774
775
776
        /* 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++)
777
          if (ci->progeny[j] != NULL && ci->progeny[j]->count)
778
            for (int k = 0; k < 8; k++)
779
              if (cj->progeny[k] != NULL && cj->progeny[k]->count) {
780
781
                struct task *tl =
                    scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
782
                                      ci->progeny[j], cj->progeny[k]);
783
                scheduler_splittask_hydro(tl, s);
784
785
786
787
788
789
790
                tl->flags = space_getsid(s->space, &t->ci, &t->cj, shift);
              }
      }
    } /* pair interaction? */
  }   /* iterate over the current task. */
}

791
792
793
794
795
796
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
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;
      }

827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
      /* 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 (