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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

115
116
117
118
119
120
/**
 * @brief Write a dot file with the task dependencies.
 *
 * See examples/task_graph for an example of how to use it
 * @param s The #scheduler we are working in.
 */
121
void scheduler_write_dependency(struct scheduler *s) {
122
#ifdef WITH_MPI
lhausamm's avatar
lhausamm committed
123
  if (engine_rank != 0) return;
124
#endif
125
126
127
128
129
130
131
  int i, j;

  int max_nber_dep = 5;
  /* 2 => we need 1 int for type and 1 for subtype */
  int nber_relation = 2 * task_type_count * task_subtype_count * max_nber_dep;
  /* For each type/subtype, a table of 2*max_nber_dep int is available =>
     max_nber_dep task with subtype available
lhausamm's avatar
lhausamm committed
132

133
134
135
136
137
138
139
140
     -1 means that it is not set yet

     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
   */
  int *table = malloc(nber_relation * sizeof(int));
lhausamm's avatar
lhausamm committed
141
  for (i = 0; i < nber_relation; i++) table[i] = -1;
lhausamm's avatar
lhausamm committed
142

143
  message("Writing dependencies");
lhausamm's avatar
lhausamm committed
144

145
  /* create file */
146
147
  char filename[200] = "dependency_graph.dot";
  FILE *f; /* file containing the output */
148
  f = open_and_check_file(filename, "w");
149
150
151
152
153
154
155
156

  /* write header */
  fprintf(f, "digraph task_dep {\n");
  fprintf(f, "\t compound=true;\n");
  fprintf(f, "\t ratio=0.66;\n");
  fprintf(f, "\t node[nodesep=0.15];\n");

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

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

lhausamm's avatar
lhausamm committed
166
      char tmp[200]; /* text to write */
167
168
      char ta_name[200];
      char tb_name[200];
lhausamm's avatar
lhausamm committed
169
      /* construct line */
170
      if (ta->subtype == task_subtype_none)
lhausamm's avatar
lhausamm committed
171
        sprintf(ta_name, "%s", taskID_names[ta->type]);
172
      else
lhausamm's avatar
lhausamm committed
173
174
        sprintf(ta_name, "\"%s %s\"", taskID_names[ta->type],
                subtaskID_names[ta->subtype]);
175
176

      if (tb->subtype == task_subtype_none)
lhausamm's avatar
lhausamm committed
177
        sprintf(tb_name, "%s", taskID_names[tb->type]);
178
      else
lhausamm's avatar
lhausamm committed
179
180
181
182
        sprintf(tb_name, "\"%s %s\"", taskID_names[tb->type],
                subtaskID_names[tb->subtype]);

      sprintf(tmp, "\t %s->%s;\n", ta_name, tb_name);
lhausamm's avatar
lhausamm committed
183
184

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

187
188
      int ind = ta->type * task_subtype_count + ta->subtype;
      ind *= 2 * max_nber_dep;
lhausamm's avatar
lhausamm committed
189

190
191
      int k = 0;
      int *cur = &table[ind];
lhausamm's avatar
lhausamm committed
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
      while (k < max_nber_dep) {
        /* 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];
      }
209
210
211

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

lhausamm's avatar
lhausamm committed
214
      /* Not written yet => write it */
215
      if (!written) {
lhausamm's avatar
lhausamm committed
216
217
        fprintf(f, tmp);
      }
218
    }
lhausamm's avatar
lhausamm committed
219
  }
lhausamm's avatar
lhausamm committed
220

221
222
  fprintf(f, "}");
  fclose(f);
223
  free(table);
224
225
}

226
/**
227
 * @brief Split a hydrodynamic task if too large.
228
 *
229
230
 * @param t The #task
 * @param s The #scheduler we are working in.
231
 */
232
static void scheduler_splittask_hydro(struct task *t, struct scheduler *s) {
233

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

238
239
    /* Reset the redo flag. */
    redo = 0;
240

241
    /* Non-splittable task? */
242
243
    if ((t->ci == NULL) || (t->type == task_type_pair && t->cj == NULL) ||
        t->ci->count == 0 || (t->cj != NULL && t->cj->count == 0)) {
244
      t->type = task_type_none;
245
246
      t->subtype = task_subtype_none;
      t->cj = NULL;
247
248
249
      t->skip = 1;
      break;
    }
250

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

254
255
256
257
258
      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;

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

263
      /* Is this cell even split and the task does not violate h ? */
264
      if (cell_can_split_self_task(ci)) {
265

266
        /* Make a sub? */
267
        if (scheduler_dosub && ci->count < space_subsize_self) {
268

269
270
271
272
273
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

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

275
276
277
278
279
280
281
282
          /* 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++)
283
            if (ci->progeny[k] != NULL && ci->progeny[k]->count)
284
              scheduler_splittask_hydro(
285
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
286
                                    ci->progeny[k], NULL),
287
288
                  s);

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

302
    } /* Self interaction */
303

304
305
    /* Pair interaction? */
    else if (t->type == task_type_pair) {
306

307
308
309
      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
310

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

317
318
319
      /* 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
320
      const int sid = space_getsid(s->space, &ci, &cj, shift);
321

322
      /* Should this task be split-up? */
323
      if (cell_can_split_pair_task(ci) && cell_can_split_pair_task(cj)) {
324
325

        /* Replace by a single sub-task? */
326
327
        if (scheduler_dosub && /* Use division to avoid integer overflow. */
            ci->count * sid_scale[sid] < space_subsize_pair / cj->count &&
328
            !sort_is_corner(sid)) {
329
330
331
332
333

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

          /* Otherwise, split it. */
334
335
        } else {

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

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

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

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

            case 11: /* (  0 ,  1 , -1 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[1];
              t->flags = 11;
592
              scheduler_splittask_hydro(
593
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
594
                                    ci->progeny[6], cj->progeny[5]),
595
                  s);
596
              scheduler_splittask_hydro(
597
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
598
                                    ci->progeny[2], cj->progeny[5]),
599
                  s);
600
              scheduler_splittask_hydro(
601
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
602
                                    ci->progeny[6], cj->progeny[1]),
603
604
605
606
607
608
609
                  s);
              break;

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

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

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

735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
      /* 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);
763
        }
764
      } /* Cell is split */
765
766
767
768
769

    } /* Self interaction */

    /* Pair interaction? */
    else if (t->type == task_type_pair) {
770
771
772

      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
773
774
775
776
777
778
779
780
      struct cell *cj = t->cj;

      /* Foreign task? */
      if (ci->nodeID != s->nodeID && cj->nodeID != s->nodeID) {
        t->skip = 1;
        break;
      }
    } /* pair interaction? */
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
  }   /* 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;
797

798
799
  for (int ind = 0; ind < num_elements; ind++) {
    struct task *t = &tasks[ind];
800
801
802
803
804
805
806
807
808
809

    /* Invoke the correct splitting strategy */
    if (t->subtype == task_subtype_density) {
      scheduler_splittask_hydro(t, s);
    } else if (t->subtype == task_subtype_external_grav) {
      scheduler_splittask_gravity(t, s);
    } else if (t->subtype == task_subtype_grav) {
      scheduler_splittask_gravity(t, s);
    } else if (t->type == task_type_grav_top_level ||
               t->type == task_type_grav_ghost) {
810
      /* For future use */
811
812
813
    } else {
      error("Unexpected task sub-type");
    }
814