scheduler.c 57.6 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

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

59
60
61
62
63
64
65
/**
 * @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.
 */
66
67
void scheduler_addunlock(struct scheduler *s, struct task *ta,
                         struct task *tb) {
68
69
70
71
72
#ifdef SWIFT_DEBUG_CHECKS
  if (ta == NULL) error("Unlocking task is NULL.");
  if (tb == NULL) error("Unlocked task is NULL.");
#endif

73
74
75
76
77
  /* 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) {
78
    /* Allocate the new buffer. */
79
80
81
    struct task **unlocks_new;
    int *unlock_ind_new;
    const int size_unlocks_new = s->size_unlocks * 2;
82
83
    if ((unlocks_new = (struct task **)malloc(sizeof(struct task *) *
                                              size_unlocks_new)) == NULL ||
84
85
        (unlock_ind_new = (int *)malloc(sizeof(int) * size_unlocks_new)) ==
            NULL)
86
      error("Failed to re-allocate unlocks.");
87

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

92
    /* Copy the buffers. */
93
94
95
96
97
98
    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;
99

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

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

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

114
/**
115
 * @brief Split a hydrodynamic task if too large.
116
 *
117
118
 * @param t The #task
 * @param s The #scheduler we are working in.
119
 */
120
static void scheduler_splittask_hydro(struct task *t, struct scheduler *s) {
121

122
123
124
  /* Iterate on this task until we're done with it. */
  int redo = 1;
  while (redo) {
125

126
127
    /* Reset the redo flag. */
    redo = 0;
128

129
    /* Non-splittable task? */
130
    if ((t->ci == NULL) || (t->type == task_type_pair && t->cj == NULL)) {
131
      t->type = task_type_none;
132
133
      t->subtype = task_subtype_none;
      t->cj = NULL;
134
135
136
      t->skip = 1;
      break;
    }
137

138
139
    /* Self-interaction? */
    if (t->type == task_type_self) {
140

141
142
      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;
143
      const double width = ci->dmin;
144
145
146

      /* Foreign task? */
      if (ci->nodeID != s->nodeID) {
147
        t->skip = 1;
148
        break;
149
150
      }

151
152
      /* Is this cell even split and the task does not violate h ? */
      if (ci->split && 2.f * kernel_gamma * ci->h_max * space_stretch < width) {
153

154
        /* Make a sub? */
155
        if (scheduler_dosub && /* Note division here to avoid overflow */
156
            (ci->count > 0 && ci->count < space_subsize / ci->count)) {
157

158
159
160
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

161
162
          /* Depend on local sorts on this cell. */
          if (ci->sorts != NULL) scheduler_addunlock(s, ci->sorts, t);
Pedro Gonnet's avatar
Pedro Gonnet committed
163

164
165
          /* Otherwise, make tasks explicitly. */
        } else {
166

167
168
169
170
171
172
173
174
175
          /* 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)
176
              scheduler_splittask_hydro(
177
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
178
                                    ci->progeny[k], NULL),
179
180
                  s);

181
182
183
184
185
186
187
          /* Make a task for each pair of progeny */
          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_hydro(
                      scheduler_addtask(s, task_type_pair, t->subtype,
188
                                        sub_sid_flag[j][k], 0, ci->progeny[j],
189
190
                                        ci->progeny[k]),
                      s);
191
        }
192
      } /* Cell is split */
193

194
      /* Otherwise, make sure the self task has a drift task */
195
      else {
196

197
        lock_lock(&ci->lock);
198

199
        if (ci->drift_part == NULL)
200
201
          ci->drift_part = scheduler_addtask(s, task_type_drift_part,
                                             task_subtype_none, 0, 0, ci, NULL);
202
203
        lock_unlock_blind(&ci->lock);
      }
204
    } /* Self interaction */
205

206
207
    /* Pair interaction? */
    else if (t->type == task_type_pair) {
208

209
210
211
      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
212

213
214
215
216
217
      /* Foreign task? */
      if (ci->nodeID != s->nodeID && cj->nodeID != s->nodeID) {
        t->skip = 1;
        break;
      }
218

219
220
221
      /* 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
222
      const int sid = space_getsid(s->space, &ci, &cj, shift);
223

224
225
226
      const double width_i = ci->dmin;
      const double width_j = cj->dmin;

227
228
      /* Should this task be split-up? */
      if (ci->split && cj->split &&
229
230
          2.f * kernel_gamma * space_stretch * ci->h_max < width_i &&
          2.f * kernel_gamma * space_stretch * cj->h_max < width_j) {
231
232
233

        /* Replace by a single sub-task? */
        if (scheduler_dosub &&
234
            ci->count * sid_scale[sid] < space_subsize / cj->count &&
235
            !sort_is_corner(sid)) {
236
237
238
239

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

240
241
242
          /* Depend on the sort tasks of both cells. */
          if (ci->sorts != NULL) scheduler_addunlock(s, ci->sorts, t);
          if (cj->sorts != NULL) scheduler_addunlock(s, cj->sorts, t);
Pedro Gonnet's avatar
Pedro Gonnet committed
243

244
          /* Otherwise, split it. */
245
246
        } else {

247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
          /* 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;
263
              scheduler_splittask_hydro(
264
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
265
                                    ci->progeny[7], cj->progeny[1]),
266
                  s);
267
              scheduler_splittask_hydro(
268
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
269
                                    ci->progeny[6], cj->progeny[1]),
270
                  s);
271
              scheduler_splittask_hydro(
272
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
273
                                    ci->progeny[7], cj->progeny[0]),
274
275
276
277
278
279
280
281
282
283
284
285
286
                  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;
287
              scheduler_splittask_hydro(
288
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
289
                                    ci->progeny[7], cj->progeny[2]),
290
                  s);
291
              scheduler_splittask_hydro(
292
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
293
                                    ci->progeny[5], cj->progeny[2]),
294
                  s);
295
              scheduler_splittask_hydro(
296
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
297
                                    ci->progeny[7], cj->progeny[0]),
298
299
300
301
302
303
304
                  s);
              break;

            case 4: /* (  1 ,  0 ,  0 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[0];
              t->flags = 4;
305
              scheduler_splittask_hydro(
306
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
307
                                    ci->progeny[5], cj->progeny[0]),
308
                  s);
309
              scheduler_splittask_hydro(
310
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
311
                                    ci->progeny[6], cj->progeny[0]),
312
                  s);
313
              scheduler_splittask_hydro(
314
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
315
                                    ci->progeny[7], cj->progeny[0]),
316
                  s);
317
              scheduler_splittask_hydro(
318
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
319
                                    ci->progeny[4], cj->progeny[1]),
320
                  s);
321
              scheduler_splittask_hydro(
322
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
323
                                    ci->progeny[5], cj->progeny[1]),
324
                  s);
325
              scheduler_splittask_hydro(
326
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
327
                                    ci->progeny[6], cj->progeny[1]),
328
                  s);
329
              scheduler_splittask_hydro(
330
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
331
                                    ci->progeny[7], cj->progeny[1]),
332
                  s);
333
              scheduler_splittask_hydro(
334
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
335
                                    ci->progeny[4], cj->progeny[2]),
336
                  s);
337
              scheduler_splittask_hydro(
338
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
339
                                    ci->progeny[5], cj->progeny[2]),
340
                  s);
341
              scheduler_splittask_hydro(
342
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
343
                                    ci->progeny[6], cj->progeny[2]),
344
                  s);
345
              scheduler_splittask_hydro(
346
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
347
                                    ci->progeny[7], cj->progeny[2]),
348
                  s);
349
              scheduler_splittask_hydro(
350
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
351
                                    ci->progeny[4], cj->progeny[3]),
352
                  s);
353
              scheduler_splittask_hydro(
354
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
355
                                    ci->progeny[5], cj->progeny[3]),
356
                  s);
357
              scheduler_splittask_hydro(
358
                  scheduler_addtask(s, task_type_pair, t->subtype, 3, 0,
359
                                    ci->progeny[6], cj->progeny[3]),
360
                  s);
361
              scheduler_splittask_hydro(
362
                  scheduler_addtask(s, task_type_pair, t->subtype, 4, 0,
363
                                    ci->progeny[7], cj->progeny[3]),
364
365
366
367
368
369
370
                  s);
              break;

            case 5: /* (  1 ,  0 , -1 ) */
              t->ci = ci->progeny[4];
              t->cj = cj->progeny[1];
              t->flags = 5;
371
              scheduler_splittask_hydro(
372
                  scheduler_addtask(s, task_type_pair, t->subtype, 5, 0,
373
                                    ci->progeny[6], cj->progeny[3]),
374
                  s);
375
              scheduler_splittask_hydro(
376
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
377
                                    ci->progeny[4], cj->progeny[3]),
378
                  s);
379
              scheduler_splittask_hydro(
380
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
381
                                    ci->progeny[6], cj->progeny[1]),
382
383
384
385
386
387
388
389
390
391
392
393
394
                  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;
395
              scheduler_splittask_hydro(
396
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
397
                                    ci->progeny[5], cj->progeny[2]),
398
                  s);
399
              scheduler_splittask_hydro(
400
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
401
                                    ci->progeny[4], cj->progeny[2]),
402
                  s);
403
              scheduler_splittask_hydro(
404
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
405
                                    ci->progeny[5], cj->progeny[3]),
406
407
408
409
410
411
412
413
414
415
416
417
418
                  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;
419
              scheduler_splittask_hydro(
420
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
421
                                    ci->progeny[7], cj->progeny[4]),
422
                  s);
423
              scheduler_splittask_hydro(
424
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
425
                                    ci->progeny[3], cj->progeny[4]),
426
                  s);
427
              scheduler_splittask_hydro(
428
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
429
                                    ci->progeny[7], cj->progeny[0]),
430
431
432
433
434
435
436
                  s);
              break;

            case 10: /* (  0 ,  1 ,  0 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[0];
              t->flags = 10;
437
              scheduler_splittask_hydro(
438
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
439
                                    ci->progeny[3], cj->progeny[0]),
440
                  s);
441
              scheduler_splittask_hydro(
442
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
443
                                    ci->progeny[6], cj->progeny[0]),
444
                  s);
445
              scheduler_splittask_hydro(
446
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
447
                                    ci->progeny[7], cj->progeny[0]),
448
                  s);
449
              scheduler_splittask_hydro(
450
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
451
                                    ci->progeny[2], cj->progeny[1]),
452
                  s);
453
              scheduler_splittask_hydro(
454
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
455
                                    ci->progeny[3], cj->progeny[1]),
456
                  s);
457
              scheduler_splittask_hydro(
458
                  scheduler_addtask(s, task_type_pair, t->subtype, 8, 0,
459
                                    ci->progeny[6], cj->progeny[1]),
460
                  s);
461
              scheduler_splittask_hydro(
462
                  scheduler_addtask(s, task_type_pair, t->subtype, 7, 0,
463
                                    ci->progeny[7], cj->progeny[1]),
464
                  s);
465
              scheduler_splittask_hydro(
466
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
467
                                    ci->progeny[2], cj->progeny[4]),
468
                  s);
469
              scheduler_splittask_hydro(
470
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
471
                                    ci->progeny[3], cj->progeny[4]),
472
                  s);
473
              scheduler_splittask_hydro(
474
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
475
                                    ci->progeny[6], cj->progeny[4]),
476
                  s);
477
              scheduler_splittask_hydro(
478
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
479
                                    ci->progeny[7], cj->progeny[4]),
480
                  s);
481
              scheduler_splittask_hydro(
482
                  scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
483
                                    ci->progeny[2], cj->progeny[5]),
484
                  s);
485
              scheduler_splittask_hydro(
486
                  scheduler_addtask(s, task_type_pair, t->subtype, 1, 0,
487
                                    ci->progeny[3], cj->progeny[5]),
488
                  s);
489
              scheduler_splittask_hydro(
490
                  scheduler_addtask(s, task_type_pair, t->subtype, 9, 0,
491
                                    ci->progeny[6], cj->progeny[5]),
492
                  s);
493
              scheduler_splittask_hydro(
494
                  scheduler_addtask(s, task_type_pair, t->subtype, 10, 0,
495
                                    ci->progeny[7], cj->progeny[5]),
496
497
498
499
500
501
502
                  s);
              break;

            case 11: /* (  0 ,  1 , -1 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[1];
              t->flags = 11;
503
              scheduler_splittask_hydro(
504
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
505
                                    ci->progeny[6], cj->progeny[5]),
506
                  s);
507
              scheduler_splittask_hydro(
508
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
509
                                    ci->progeny[2], cj->progeny[5]),
510
                  s);
511
              scheduler_splittask_hydro(
512
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
513
                                    ci->progeny[6], cj->progeny[1]),
514
515
516
517
518
519
520
                  s);
              break;

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

585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
        /* 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++)
          if (ci->progeny[j] != NULL)
            for (int k = 0; k < 8; k++)
              if (cj->progeny[k] != NULL) {
                struct task *tl =
                    scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
601
                                      ci->progeny[j], cj->progeny[k]);
602
                scheduler_splittask_hydro(tl, s);
603
604
605
                tl->flags = space_getsid(s->space, &t->ci, &t->cj, shift);
              }

606
        /* Otherwise, if not spilt, stitch-up the sorting. */
607
608
      } else {

609
        /* Create the drift and sort for ci. */
610
        lock_lock(&ci->lock);
611
612
613
        if (ci->drift_part == NULL && ci->nodeID == engine_rank)
          ci->drift_part = scheduler_addtask(s, task_type_drift_part,
                                             task_subtype_none, 0, 0, ci, NULL);
614
615
        if (ci->sorts == NULL)
          ci->sorts = scheduler_addtask(s, task_type_sort, task_subtype_none,
616
                                        1 << sid, 0, ci, NULL);
617
618
        else
          ci->sorts->flags |= (1 << sid);
619
        lock_unlock_blind(&ci->lock);
620
621
        scheduler_addunlock(s, ci->sorts, t);

622
        /* Create the drift and sort for cj. */
623
        lock_lock(&cj->lock);
624
625
626
        if (cj->drift_part == NULL && cj->nodeID == engine_rank)
          cj->drift_part = scheduler_addtask(s, task_type_drift_part,
                                             task_subtype_none, 0, 0, cj, NULL);
627
628
        if (cj->sorts == NULL)
          cj->sorts = scheduler_addtask(s, task_type_sort, task_subtype_none,
629
                                        1 << sid, 0, cj, NULL);
630
631
        else
          cj->sorts->flags |= (1 << sid);
632
        lock_unlock_blind(&cj->lock);
633
634
635
636
637
638
        scheduler_addunlock(s, cj->sorts, t);
      }
    } /* pair interaction? */
  }   /* iterate over the current task. */
}

639
640
641
642
643
644
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
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
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
763
764
765
766
767
768
769
770
771
772
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;
      }

      /* Is this cell even split? */
      if (ci->split) {

        /* Make a sub? */
        if (scheduler_dosub && /* Note division here to avoid overflow */
            (ci->gcount > 0 && ci->gcount < space_subsize / ci->gcount)) {

          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

          /* Make sure we have a drift task (MATTHIEU temp. fix) */
          lock_lock(&ci->lock);
          if (ci->drift_gpart == NULL)
            ci->drift_gpart = scheduler_addtask(
                s, task_type_drift_gpart, task_subtype_none, 0, 0, ci, NULL);
          lock_unlock_blind(&ci->lock);

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

          /* 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);
          }
        }
      } /* Cell is split */

      /* Otherwise, make sure the self task has a drift task */
      else {

        lock_lock(&ci->lock);

        if (ci->drift_gpart == NULL)
          ci->drift_gpart = scheduler_addtask(
              s, task_type_drift_gpart, task_subtype_none, 0, 0, ci, NULL);
        lock_unlock_blind(&ci->lock);
      }
    } /* Self interaction */

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

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

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

      /* Should this task be split-up? */
      if (ci->split && cj->split) {

        // MATTHIEU: nothing here for now

      } else {

        /* Create the drift for ci. */
        lock_lock(&ci->lock);
        if (ci->drift_gpart == NULL && ci->nodeID == engine_rank)
          ci->drift_gpart = scheduler_addtask(
              s, task_type_drift_gpart, task_subtype_none, 0, 0, ci, NULL);
        lock_unlock_blind(&ci->lock);

        /* Create the drift for cj. */
        lock_lock(&cj->lock);
        if (cj->drift_gpart == NULL && cj->nodeID == engine_rank)
          cj->drift_gpart = scheduler_addtask(
              s, task_type_drift_gpart, task_subtype_none, 0, 0, cj, NULL);
        lock_unlock_blind(&cj->lock);
      }
    } /* pair interaction? */
  }   /* iterate over the current task. */
}
773

774
775
776
777
778
779
780
781
782
783
784
785
786
/**
 * @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;
787

788
789
  for (int ind = 0; ind < num_elements; ind++) {
    struct task *t = &tasks[ind];
790
791
792
793
794
795
796
797
798
799
800
801
802
803

    /* 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) {
      // MATTHIEU: for the future
    } else {
      error("Unexpected task sub-type");
    }
804
  }
805
}
806

Matthieu Schaller's avatar
Matthieu Schaller committed
807
808
809
810
811
/**
 * @brief Splits all the tasks in the scheduler that are too large.
 *
 * @param s The #scheduler.
 */
812
void scheduler_splittasks(struct scheduler *s) {
813

814
815
  /* Call the mapper on each current task. */
  threadpool_map(s->threadpool, scheduler_splittasks_mapper, s->tasks,
816
                 s->nr_tasks, sizeof(struct task), 1000, s);
817
818
}

819
820
821
822
823
824
825
/**
 * @brief Add a #task to the #scheduler.
 *
 * @param s The #scheduler we are working in.
 * @param type The type of the task.
 * @param subtype The sub-type of the task.
 * @param flags The flags of the task.
Matthieu Schaller's avatar
Matthieu Schaller committed
826
 * @param wait The number of unsatisfied dependencies of this task.
827
828
829
 * @param ci The first cell to interact.
 * @param cj The second cell to interact.
 */
830
831
struct task *scheduler_addtask(struct scheduler *s, enum task_types type,
                               enum task_subtypes subtype, int flags, int wait,
832
                               struct cell *ci, struct cell *cj) {
833

834
835
836
837
838
839
#ifdef SWIFT_DEBUG_CHECKS
  if (ci == NULL && cj != NULL)
    error("Added a task with ci==NULL and cj!=NULL type=%s/%s",
          taskID_names[type], subtaskID_names[subtype]);
#endif

840
  /* Get the next free task. */
Pedro Gonnet's avatar
Pedro Gonnet committed
841
  const int ind = atomic_inc(&s->tasks_next);
Matthieu Schaller's avatar
Matthieu Schaller committed
842

843
844
845
846
  /* Overflow? */
  if (ind >= s->size) error("Task list overflow.");

  /* Get a pointer to the new task. */
Pedro Gonnet's avatar
Pedro Gonnet committed
847
  struct task *t = &s->tasks[ind];
848
849