scheduler.c 60.8 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\"", 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 style for MPI communications */
        if (ta->type == task_type_send || ta->type == task_type_recv)
223
          fprintf(f, "\t %s [shape = diamond];\n", ta_name);
Matthieu Schaller's avatar
Matthieu Schaller committed
224
        if (tb->type == task_type_send || tb->type == task_type_recv)
225
          fprintf(f, "\t %s [shape = diamond];\n", tb_name);
Matthieu Schaller's avatar
Matthieu Schaller committed
226
227
228

        /* Change colour of implicit tasks */
        if (ta->implicit)
229
          fprintf(f, "\t %s [style = filled];\n\t %s [color = lightgrey];\n",
Matthieu Schaller's avatar
Matthieu Schaller committed
230
231
                  ta_name, ta_name);
        if (tb->implicit)
232
          fprintf(f, "\t %s [style = filled];\n\t %s [color = lightgrey];\n",
Matthieu Schaller's avatar
Matthieu Schaller committed
233
                  tb_name, tb_name);
lhausamm's avatar
lhausamm committed
234
      }
235
    }
lhausamm's avatar
lhausamm committed
236
  }
lhausamm's avatar
lhausamm committed
237

Matthieu Schaller's avatar
Matthieu Schaller committed
238
  /* Be clean */
239
240
  fprintf(f, "}");
  fclose(f);
241
  free(table);
Matthieu Schaller's avatar
Matthieu Schaller committed
242

Matthieu Schaller's avatar
Matthieu Schaller committed
243
  if (verbose)
Matthieu Schaller's avatar
Matthieu Schaller committed
244
    message("Printing task graph took %.3f %s.",
Matthieu Schaller's avatar
Matthieu Schaller committed
245
            clocks_from_ticks(getticks() - tic), clocks_getunit());
246
247
}

248
/**
249
 * @brief Split a hydrodynamic task if too large.
250
 *
251
252
 * @param t The #task
 * @param s The #scheduler we are working in.
253
 */
254
static void scheduler_splittask_hydro(struct task *t, struct scheduler *s) {
255

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

260
261
    /* Reset the redo flag. */
    redo = 0;
262

263
    /* Non-splittable task? */
264
265
    if ((t->ci == NULL) || (t->type == task_type_pair && t->cj == NULL) ||
        t->ci->count == 0 || (t->cj != NULL && t->cj->count == 0)) {
266
      t->type = task_type_none;
267
268
      t->subtype = task_subtype_none;
      t->cj = NULL;
269
270
271
      t->skip = 1;
      break;
    }
272

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

276
277
278
279
280
      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;

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

285
      /* Is this cell even split and the task does not violate h ? */
286
      if (cell_can_split_self_task(ci)) {
287

288
        /* Make a sub? */
289
        if (scheduler_dosub && ci->count < space_subsize_self) {
290

291
292
293
294
295
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

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

297
298
299
300
301
302
303
304
          /* 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++)
305
            if (ci->progeny[k] != NULL && ci->progeny[k]->count)
306
              scheduler_splittask_hydro(
307
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
308
                                    ci->progeny[k], NULL),
309
310
                  s);

311
312
          /* Make a task for each pair of progeny */
          for (int j = 0; j < 8; j++)
313
            if (ci->progeny[j] != NULL && ci->progeny[j]->count)
314
              for (int k = j + 1; k < 8; k++)
315
                if (ci->progeny[k] != NULL && ci->progeny[k]->count)
316
317
                  scheduler_splittask_hydro(
                      scheduler_addtask(s, task_type_pair, t->subtype,
318
                                        sub_sid_flag[j][k], 0, ci->progeny[j],
319
320
                                        ci->progeny[k]),
                      s);
321
        }
322
      } /* Cell is split */
323

324
    } /* Self interaction */
325

326
327
    /* Pair interaction? */
    else if (t->type == task_type_pair) {
328

329
330
331
      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
332

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

339
340
341
      /* 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
342
      const int sid = space_getsid(s->space, &ci, &cj, shift);
343

344
      /* Should this task be split-up? */
345
      if (cell_can_split_pair_task(ci) && cell_can_split_pair_task(cj)) {
346
347

        /* Replace by a single sub-task? */
348
349
        if (scheduler_dosub && /* Use division to avoid integer overflow. */
            ci->count * sid_scale[sid] < space_subsize_pair / cj->count &&
350
            !sort_is_corner(sid)) {
351
352
353
354
355

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

          /* Otherwise, split it. */
356
357
        } else {

358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
          /* 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;
374
              scheduler_splittask_hydro(
375
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
376
                                    ci->progeny[7], cj->progeny[1]),
377
                  s);
378
              scheduler_splittask_hydro(
379
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
380
                                    ci->progeny[6], cj->progeny[1]),
381
                  s);
382
              scheduler_splittask_hydro(
383
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
384
                                    ci->progeny[7], cj->progeny[0]),
385
386
387
388
389
390
391
392
393
394
395
396
397
                  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;
398
              scheduler_splittask_hydro(
399
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
400
                                    ci->progeny[7], cj->progeny[2]),
401
                  s);
402
              scheduler_splittask_hydro(
403
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
404
                                    ci->progeny[5], cj->progeny[2]),
405
                  s);
406
              scheduler_splittask_hydro(
407
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
408
                                    ci->progeny[7], cj->progeny[0]),
409
410
411
412
413
414
415
                  s);
              break;

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

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

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

            case 11: /* (  0 ,  1 , -1 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[1];
              t->flags = 11;
614
              scheduler_splittask_hydro(
615
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
616
                                    ci->progeny[6], cj->progeny[5]),
617
                  s);
618
              scheduler_splittask_hydro(
619
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
620
                                    ci->progeny[2], cj->progeny[5]),
621
                  s);
622
              scheduler_splittask_hydro(
623
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
624
                                    ci->progeny[6], cj->progeny[1]),
625
626
627
628
629
630
631
                  s);
              break;

            case 12: /* (  0 ,  0 ,  1 ) */
              t->ci = ci->progeny[1];
              t->cj = cj->progeny[0];
              t->flags = 12;
632
              scheduler_splittask_hydro(
633
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
634
                                    ci->progeny[3], cj->progeny[0]),
635
                  s);
636
              scheduler_splittask_hydro(
637
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
638
                                    ci->progeny[5], cj->progeny[0]),
639
                  s);
640
              scheduler_splittask_hydro(
641
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
642
                                    ci->progeny[7], cj->progeny[0]),
643
                  s);
644
              scheduler_splittask_hydro(
645
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
646
                                    ci->progeny[1], cj->progeny[2]),
647
                  s);
648
              scheduler_splittask_hydro(
649
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
650
                                    ci->progeny[3], cj->progeny[2]),
651
                  s);
652
              scheduler_splittask_hydro(
653
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
654
                                    ci->progeny[5], cj->progeny[2]),
655
                  s);
656
              scheduler_splittask_hydro(
657
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
658
                                    ci->progeny[7], cj->progeny[2]),
659
                  s);
660
              scheduler_splittask_hydro(
661
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
662
                                    ci->progeny[1], cj->progeny[4]),
663
                  s);
664
              scheduler_splittask_hydro(
665
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
666
                                    ci->progeny[3], cj->progeny[4]),
667
                  s);
668
              scheduler_splittask_hydro(
669
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
670
                                    ci->progeny[5], cj->progeny[4]),
671
                  s);
672
              scheduler_splittask_hydro(
673
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
674
                                    ci->progeny[7], cj->progeny[4]),
675
                  s);
676
              scheduler_splittask_hydro(
677
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
678
                                    ci->progeny[1], cj->progeny[6]),
679
                  s);
680
              scheduler_splittask_hydro(
681
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
682
                                    ci->progeny[3], cj->progeny[6]),
683
                  s);
684
              scheduler_splittask_hydro(
685
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
686
                                    ci->progeny[5], cj->progeny[6]),
687
                  s);
688
              scheduler_splittask_hydro(
689
                  scheduler_addtask(s, task_type_pair, t->subtype, 12, 0,
690
                                    ci->progeny[7], cj->progeny[6]),
691
692
693
                  s);
              break;
          } /* switch(sid) */
694
695
        }

696
697
698
699
700
701
702
703
704
705
706
        /* 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++)
707
          if (ci->progeny[j] != NULL && ci->progeny[j]->count)
708
            for (int k = 0; k < 8; k++)
709
              if (cj->progeny[k] != NULL && cj->progeny[k]->count) {
710
711
                struct task *tl =
                    scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
712
                                      ci->progeny[j], cj->progeny[k]);
713
                scheduler_splittask_hydro(tl, s);
714
715
716
717
718
719
720
                tl->flags = space_getsid(s->space, &t->ci, &t->cj, shift);
              }
      }
    } /* pair interaction? */
  }   /* iterate over the current task. */
}

721
722
723
724
725
726
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
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;
      }

757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
      /* 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);
785
        }