scheduler.c 57.3 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
/**
 * @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
125
126
void scheduler_write_dependencies(struct scheduler *s, int verbose) {
 
  const ticks tic = getticks();
127

Matthieu Schaller's avatar
Matthieu Schaller committed
128
129
  /* Conservative number of dependencies per task type */
  const int max_nber_dep = 128;
lhausamm's avatar
lhausamm committed
130

Matthieu Schaller's avatar
Matthieu Schaller committed
131
132
  /* Number of possibble relations between tasks */
  const int nber_relation = 2 * task_type_count * task_subtype_count * max_nber_dep;
133

Matthieu Schaller's avatar
Matthieu Schaller committed
134
135
136
137
  /* 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  */
138
  int *table = malloc(nber_relation * sizeof(int));
Matthieu Schaller's avatar
Matthieu Schaller committed
139
  if(table == NULL) error("Error allocating memory for task-dependency graph.");
lhausamm's avatar
lhausamm committed
140

Matthieu Schaller's avatar
Matthieu Schaller committed
141
142
  /* Reset everything */
  for (int i = 0; i < nber_relation; i++) table[i] = -1;
lhausamm's avatar
lhausamm committed
143

Matthieu Schaller's avatar
Matthieu Schaller committed
144
  /* Create file */
145
  char filename[200] = "dependency_graph.dot";
Matthieu Schaller's avatar
Matthieu Schaller committed
146
  FILE *f = open_and_check_file(filename, "w");
147

Matthieu Schaller's avatar
Matthieu Schaller committed
148
  /* Write header */
149
150
151
152
153
154
  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 */
Matthieu Schaller's avatar
Matthieu Schaller committed
155
156
  for (int i = 0; i < s->nr_tasks; i++) {
    const struct task *ta = &s->tasks[i];
lhausamm's avatar
lhausamm committed
157
158

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

lhausamm's avatar
lhausamm committed
162
      char tmp[200]; /* text to write */
163
164
      char ta_name[200];
      char tb_name[200];
Matthieu Schaller's avatar
Matthieu Schaller committed
165

lhausamm's avatar
lhausamm committed
166
      /* construct line */
167
      if (ta->subtype == task_subtype_none)
lhausamm's avatar
lhausamm committed
168
        sprintf(ta_name, "%s", taskID_names[ta->type]);
169
      else
lhausamm's avatar
lhausamm committed
170
171
        sprintf(ta_name, "\"%s %s\"", taskID_names[ta->type],
                subtaskID_names[ta->subtype]);
172
173

      if (tb->subtype == task_subtype_none)
lhausamm's avatar
lhausamm committed
174
        sprintf(tb_name, "%s", taskID_names[tb->type]);
175
      else
lhausamm's avatar
lhausamm committed
176
177
178
179
        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
180
181

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

184
185
      int ind = ta->type * task_subtype_count + ta->subtype;
      ind *= 2 * max_nber_dep;
lhausamm's avatar
lhausamm committed
186

187
188
      int k = 0;
      int *cur = &table[ind];
lhausamm's avatar
lhausamm committed
189
      while (k < max_nber_dep) {
Matthieu Schaller's avatar
Matthieu Schaller committed
190

lhausamm's avatar
lhausamm committed
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
        /* 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];
      }
207
208
209

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

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

Matthieu Schaller's avatar
Matthieu Schaller committed
219
  /* Be clean */
220
221
  fprintf(f, "}");
  fclose(f);
222
  free(table);
Matthieu Schaller's avatar
Matthieu Schaller committed
223
224
225
226

  if(verbose)
    message("Printing task graph took %.3f %s.",
	    clocks_from_ticks(getticks() - tic), clocks_getunit());
227
228
}

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

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

241
242
    /* Reset the redo flag. */
    redo = 0;
243

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

254
255
    /* Self-interaction? */
    if (t->type == task_type_self) {
256

257
258
259
260
261
      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;

      /* Foreign task? */
      if (ci->nodeID != s->nodeID) {
262
        t->skip = 1;
263
        break;
264
265
      }

266
      /* Is this cell even split and the task does not violate h ? */
267
      if (cell_can_split_self_task(ci)) {
268

269
        /* Make a sub? */
270
        if (scheduler_dosub && ci->count < space_subsize_self) {
271

272
273
274
275
276
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

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

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

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

305
    } /* Self interaction */
306

307
308
    /* Pair interaction? */
    else if (t->type == task_type_pair) {
309

310
311
312
      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
313

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

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

325
      /* Should this task be split-up? */
326
      if (cell_can_split_pair_task(ci) && cell_can_split_pair_task(cj)) {
327
328

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

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

          /* Otherwise, split it. */
337
338
        } else {

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

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

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

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

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

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

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

702
703
704
705
706
707
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
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
735
736
737
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;
      }

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
763
764
765
      /* 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);
766
        }
767
      } /* Cell is split */
768
769
770
771
772

    } /* Self interaction */

    /* Pair interaction? */
    else if (t->type == task_type_pair) {
773
774
775

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

      /* Foreign task? */
      if (ci->nodeID != s->nodeID && cj->nodeID != s->nodeID) {
        t->skip = 1;
        break;
      }
    } /* pair interaction? */
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
  }   /* iterate over the current task. */