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

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

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

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

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

41
42
/* Local headers. */
#include "atomic.h"
43
#include "cycle.h"
44
#include "engine.h"
45
#include "error.h"
46
#include "intrinsics.h"
47
#include "kernel_hydro.h"
48
#include "queue.h"
49
#include "sort_part.h"
50
51
#include "space.h"
#include "task.h"
52
#include "timers.h"
53
#include "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
221
222
223
224
225
226
227
228
229
230
231

	/* Change style for MPI communications */
	if(ta->type == task_type_send || ta->type == task_type_recv)
	  fprintf(f, "\t %s [shape = box];\n", ta_name);
	if(tb->type == task_type_send || tb->type == task_type_recv)
	  fprintf(f, "\t %s [shape = box];\n", tb_name);

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

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

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

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

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

258
259
    /* Reset the redo flag. */
    redo = 0;
260

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

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

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

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

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

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

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

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

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

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

322
    } /* Self interaction */
323

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

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

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

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

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

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

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

          /* Otherwise, split it. */
354
355
        } else {

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

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

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

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

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

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

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

719
720
721
722
723
724
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
725
726
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
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;
      }

755
756
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
      /* 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);
783
        }
784
      } /* Cell is split */
785
786
787
788
789

    } /* Self interaction */

    /* Pair interaction? */
    else if (t->type == task_type_pair) {
790
791
792

      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
793
794