scheduler.c 76.7 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
32
#include <sys/stat.h>
33

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

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

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

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

63
64
65
66
67
68
69
/**
 * @brief Increase the space available for unlocks. Only call when
 *        current index == s->size_unlock;
 */
static void scheduler_extend_unlocks(struct scheduler *s) {
  /* Allocate the new buffer. */
  const int size_unlocks_new = s->size_unlocks * 2;
70
71
72
73
  struct task **unlocks_new = (struct task **)swift_malloc(
      "unlocks", sizeof(struct task *) * size_unlocks_new);
  int *unlock_ind_new =
      (int *)swift_malloc("unlock_ind", sizeof(int) * size_unlocks_new);
74
75
76
77
78
79
80
81
82
83
  if (unlocks_new == NULL || unlock_ind_new == NULL)
    error("Failed to re-allocate unlocks.");

  /* Wait for all writes to the old buffer to complete. */
  while (s->completed_unlock_writes < s->size_unlocks)
    ;

  /* Copy the buffers. */
  memcpy(unlocks_new, s->unlocks, sizeof(struct task *) * s->size_unlocks);
  memcpy(unlock_ind_new, s->unlock_ind, sizeof(int) * s->size_unlocks);
84
85
  swift_free("unlocks", s->unlocks);
  swift_free("unlock_ind", s->unlock_ind);
86
87
88
89
90
91
92
  s->unlocks = unlocks_new;
  s->unlock_ind = unlock_ind_new;

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

93
94
95
96
97
98
/**
 * @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.
99

100
 */
101
102
void scheduler_addunlock(struct scheduler *s, struct task *ta,
                         struct task *tb) {
103
104
105
106
107
#ifdef SWIFT_DEBUG_CHECKS
  if (ta == NULL) error("Unlocking task is NULL.");
  if (tb == NULL) error("Unlocked task is NULL.");
#endif

108
109
110
111
  /* Get an index at which to store this unlock. */
  const int ind = atomic_inc(&s->nr_unlocks);

  /* Does the buffer need to be grown? */
112
113
114
115
116
117
  if (ind == s->size_unlocks) scheduler_extend_unlocks(s);

#ifdef SWIFT_DEBUG_CHECKS
  if (ind > s->size_unlocks * 2)
    message("unlocks guard enabled: %d / %d", ind, s->size_unlocks);
#endif
118

119
  /* Wait for there to actually be space at my index. */
120
121
  while (ind > s->size_unlocks)
    ;
122

123
  /* Guard against case when more than (old) s->size_unlocks unlocks
124
125
126
   * are now pending. */
  if (ind == s->size_unlocks) scheduler_extend_unlocks(s);

127
128
129
  /* Write the unlock to the scheduler. */
  s->unlocks[ind] = tb;
  s->unlock_ind[ind] = ta - s->tasks;
130
  atomic_inc(&s->completed_unlock_writes);
131
132
}

133
/**
134
 * @brief compute the number of similar dependencies
135
 *
136
137
138
139
140
141
142
 * @param s The #scheduler
 * @param ta The #task
 * @param tb The dependent #task
 *
 * @return Number of dependencies
 */
int scheduler_get_number_relation(const struct scheduler *s,
143
144
                                  const struct task *ta,
                                  const struct task *tb) {
145
146
147
148
149
150
151
152
153
154
  int count = 0;

  /* loop over all tasks */
  for (int i = 0; i < s->nr_tasks; i++) {
    const struct task *ta_tmp = &s->tasks[i];

    /* and their dependencies */
    for (int j = 0; j < ta->nr_unlock_tasks; j++) {
      const struct task *tb_tmp = ta->unlock_tasks[j];

155
156
157
      if (ta->type == ta_tmp->type && ta->subtype == ta_tmp->subtype &&
          tb->type == tb_tmp->type && tb->subtype == tb_tmp->subtype) {
        count += 1;
158
159
160
161
162
163
      }
    }
  }
  return count;
}

164
/* Conservative number of dependencies per task type */
165
#define MAX_NUMBER_DEP 128
166
167
168
169
170
171
172
173
174

/**
 * @brief Informations about all the task dependencies of
 *   a single task.
 */
struct task_dependency {
  /* Main task */
  /* ID of the task */
  int type_in;
175

176
177
178
179
180
181
182
183
  /* ID of the subtask */
  int subtype_in;

  /* Is the task implicit */
  int implicit_in;

  /* Dependent task */
  /* ID of the dependent task */
184
  int type_out[MAX_NUMBER_DEP];
185
186

  /* ID of the dependent subtask */
187
188
  int subtype_out[MAX_NUMBER_DEP];

189
  /* Is the dependent task implicit */
190
  int implicit_out[MAX_NUMBER_DEP];
191
192
193

  /* Statistics */
  /* number of link between the two task type */
194
  int number_link[MAX_NUMBER_DEP];
195
196

  /* number of ranks having this relation */
197
  int number_rank[MAX_NUMBER_DEP];
198
199
200
};

#ifdef WITH_MPI
201

202
203
/**
 * @brief Define the #task_dependency for MPI
204
 *
205
 * @param tstype The MPI_Datatype to initialize
206
 */
207
208
209
210
211
212
213
214
void task_dependency_define(MPI_Datatype *tstype) {
  /* Define the variables */
  const int count = 8;
  int blocklens[count];
  MPI_Datatype types[count];
  MPI_Aint disps[count];

  /* all the type are int */
215
  for (int i = 0; i < count; i++) {
216
217
218
219
220
221
222
223
224
225
226
227
228
    types[i] = MPI_INT;
  }

  /* Task in */
  disps[0] = offsetof(struct task_dependency, type_in);
  blocklens[0] = 1;
  disps[1] = offsetof(struct task_dependency, subtype_in);
  blocklens[1] = 1;
  disps[2] = offsetof(struct task_dependency, implicit_in);
  blocklens[2] = 1;

  /* Task out */
  disps[3] = offsetof(struct task_dependency, type_out);
229
  blocklens[3] = MAX_NUMBER_DEP;
230
  disps[4] = offsetof(struct task_dependency, subtype_out);
231
  blocklens[4] = MAX_NUMBER_DEP;
232
  disps[5] = offsetof(struct task_dependency, implicit_out);
233
  blocklens[5] = MAX_NUMBER_DEP;
234
235
236

  /* statistics */
  disps[6] = offsetof(struct task_dependency, number_link);
237
  blocklens[6] = MAX_NUMBER_DEP;
238
  disps[7] = offsetof(struct task_dependency, number_rank);
239
  blocklens[7] = MAX_NUMBER_DEP;
240
241
242
243

  /* define it for MPI */
  MPI_Type_create_struct(count, blocklens, disps, types, tstype);
  MPI_Type_commit(tstype);
244
245
}

246
247
248
249
250
251
252
/**
 * @brief Sum operator of #task_dependency for MPI
 *
 * @param in_p The #task_dependency to add
 * @param out_p The #task_dependency where in_p is added
 * @param len The length of the arrays
 * @param type The MPI datatype
253
 */
254
255
void task_dependency_sum(void *in_p, void *out_p, int *len,
                         MPI_Datatype *type) {
256
  /* change pointer type */
257
258
  struct task_dependency *in = (struct task_dependency *)in_p;
  struct task_dependency *out = (struct task_dependency *)out_p;
259
260
261
262

  /* Loop over all the current objects */
  for (int i = 0; i < *len; i++) {
    /* loop over all the object set in invals */
263
    for (int j = 0; j < MAX_NUMBER_DEP; j++) {
264
265
      /* Have we reached the end of the links? */
      if (in[i].number_link[j] == -1) {
266
        break;
267
268
269
270
271
272
273
274
275
      }

      /* get a few variables */
      int tb_type = in[i].type_out[j];
      int tb_subtype = in[i].subtype_out[j];

#ifdef SWIFT_DEBUG_CHECKS
      /* Check tasks */
      if (tb_type >= task_type_count) {
276
        error("Unknown task type %i", tb_type);
277
278
279
      }

      if (tb_subtype >= task_subtype_count) {
280
        error("Unknown subtask type %i", tb_subtype);
281
282
283
284
285
      }
#endif

      /* find the corresponding id */
      int k = 0;
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
      while (k < MAX_NUMBER_DEP) {
        /* have we reached the end of the links? */
        if (out[i].number_link[k] == -1) {
          /* reset the counter in order to be safe */
          out[i].number_link[k] = 0;
          out[i].number_rank[k] = 0;

          /* set the relation */
          out[i].type_in = in[i].type_in;
          out[i].subtype_in = in[i].subtype_in;
          out[i].implicit_in = in[i].implicit_in;

          out[i].type_out[k] = in[i].type_out[j];
          out[i].subtype_out[k] = in[i].subtype_out[j];
          out[i].implicit_out[k] = in[i].implicit_out[j];
          break;
        }

        /* do we have the same relation? */
        if (out[i].type_out[k] == tb_type &&
            out[i].subtype_out[k] == tb_subtype) {
          break;
        }

        k++;
311
312
313
      }

      /* Check if we are still in the memory */
314
315
      if (k == MAX_NUMBER_DEP) {
        error("Not enough memory, please increase MAX_NUMBER_DEP");
316
317
318
319
320
      }

#ifdef SWIFT_DEBUG_CHECKS
      /* Check if correct relation */
      if (out[i].type_in != in[i].type_in ||
321
322
323
324
325
326
          out[i].subtype_in != in[i].subtype_in ||
          out[i].implicit_in != in[i].implicit_in ||
          out[i].type_out[k] != in[i].type_out[j] ||
          out[i].subtype_out[k] != in[i].subtype_out[j] ||
          out[i].implicit_out[k] != in[i].implicit_out[j]) {
        error("Tasks do not correspond");
327
328
329
330
331
332
333
334
335
336
      }
#endif

      /* sum the contributions */
      out[i].number_link[k] += in[i].number_link[j];
      out[i].number_rank[k] += in[i].number_rank[j];
    }
  }

  return;
337
338
}

339
#endif  // WITH_MPI
340

341
342
343
/**
 * @brief Write a dot file with the task dependencies.
 *
Matthieu Schaller's avatar
Matthieu Schaller committed
344
345
346
 * Run plot_task_dependencies.sh for an example of how to use it
 * to generate the figure.
 *
347
 * @param s The #scheduler we are working in.
Matthieu Schaller's avatar
Matthieu Schaller committed
348
 * @param verbose Are we verbose about this?
349
 */
Matthieu Schaller's avatar
Matthieu Schaller committed
350
351
void scheduler_write_dependencies(struct scheduler *s, int verbose) {
  const ticks tic = getticks();
352

Peter W. Draper's avatar
Peter W. Draper committed
353
  /* Number of possible relations between tasks */
354
  const int nber_tasks = task_type_count * task_subtype_count;
355

356
357
  /* To get the table for a task:
   * ind = (ta * task_subtype_count + sa)
Matthieu Schaller's avatar
Matthieu Schaller committed
358
359
   * where ta is the value of task_type and sa is the value of
   * task_subtype  */
360
  struct task_dependency *task_dep = (struct task_dependency *)malloc(
361
      nber_tasks * sizeof(struct task_dependency));
362

363
364
  if (task_dep == NULL)
    error("Error allocating memory for task-dependency graph (table).");
365

366
367
  /* Reset counter */
  for (int i = 0; i < nber_tasks; i++) {
368
    for (int j = 0; j < MAX_NUMBER_DEP; j++) {
369
370
      /* Use number_link as indicator of the existance of a relation */
      task_dep[i].number_link[j] = -1;
371
372
    }
  }
373
374

  /* loop over all tasks */
Matthieu Schaller's avatar
Matthieu Schaller committed
375
376
  for (int i = 0; i < s->nr_tasks; i++) {
    const struct task *ta = &s->tasks[i];
lhausamm's avatar
lhausamm committed
377

378
    /* Current index */
379
    const int ind = ta->type * task_subtype_count + ta->subtype;
380
381
382
383
384
385
386
387

    struct task_dependency *cur = &task_dep[ind];

    /* Set ta */
    cur->type_in = ta->type;
    cur->subtype_in = ta->subtype;
    cur->implicit_in = ta->implicit;

Peter W. Draper's avatar
Peter W. Draper committed
388
    /* and their dependencies */
Matthieu Schaller's avatar
Matthieu Schaller committed
389
390
    for (int j = 0; j < ta->nr_unlock_tasks; j++) {
      const struct task *tb = ta->unlock_tasks[j];
lhausamm's avatar
lhausamm committed
391

392
      int k = 0;
393
      while (k < MAX_NUMBER_DEP) {
lhausamm's avatar
lhausamm committed
394
        /* not written yet */
395
        if (cur->number_link[k] == -1) {
396
          /* set tb */
397
398
          cur->type_out[k] = tb->type;
          cur->subtype_out[k] = tb->subtype;
399
400
401
          cur->implicit_out[k] = tb->implicit;

          /* statistics */
402
          const int count = scheduler_get_number_relation(s, ta, tb);
403
404
          cur->number_link[k] = count;
          cur->number_rank[k] = 1;
405

lhausamm's avatar
lhausamm committed
406
407
408
409
          break;
        }

        /* already written */
410
411
        if (cur->type_out[k] == tb->type &&
            cur->subtype_out[k] == tb->subtype) {
lhausamm's avatar
lhausamm committed
412
413
414
415
416
          break;
        }

        k += 1;
      }
417

418
419
420
      /* MAX_NUMBER_DEP is too small */
      if (k == MAX_NUMBER_DEP)
        error("Not enough memory, please increase MAX_NUMBER_DEP");
421
422
    }
  }
lhausamm's avatar
lhausamm committed
423

424
425
426
427
#ifdef WITH_MPI
  /* create MPI operator */
  MPI_Datatype data_type;
  task_dependency_define(&data_type);
lhausamm's avatar
lhausamm committed
428

429
  MPI_Op sum;
430
  MPI_Op_create(task_dependency_sum, /* commute */ 1, &sum);
431

432
433
  /* create recv buffer */
  struct task_dependency *recv = NULL;
Matthieu Schaller's avatar
Matthieu Schaller committed
434

435
  if (s->nodeID == 0) {
436
437
    recv = (struct task_dependency *)malloc(nber_tasks *
                                            sizeof(struct task_dependency));
Matthieu Schaller's avatar
Matthieu Schaller committed
438

439
440
    /* reset counter */
    for (int i = 0; i < nber_tasks; i++) {
441
442
443
      for (int j = 0; j < MAX_NUMBER_DEP; j++) {
        /* Use number_link as indicator of the existance of a relation */
        recv[i].number_link[j] = -1;
lhausamm's avatar
lhausamm committed
444
      }
445
    }
lhausamm's avatar
lhausamm committed
446
  }
lhausamm's avatar
lhausamm committed
447

448
  /* Do the reduction */
449
450
451
  int test =
      MPI_Reduce(task_dep, recv, nber_tasks, data_type, sum, 0, MPI_COMM_WORLD);
  if (test != MPI_SUCCESS) error("MPI reduce failed");
452

453
454
455
456
  /* free some memory */
  if (s->nodeID == 0) {
    free(task_dep);
    task_dep = recv;
457
  }
458
#endif
459

460
461
  if (s->nodeID == 0) {
    /* Create file */
Peter W. Draper's avatar
Peter W. Draper committed
462
    const char *filename = "dependency_graph.csv";
463
464
465
466
467
    FILE *f = fopen(filename, "w");
    if (f == NULL) error("Error opening dependency graph file.");

    /* Write header */
    fprintf(f, "# %s\n", git_revision());
468
469
470
471
472
473
474
475
476
477
478
479
480
    fprintf(
        f,
        "task_in,task_out,implicit_in,implicit_out,mpi_in,mpi_out,cluster_in,"
        "cluster_out,number_link,number_rank\n");

    for (int i = 0; i < nber_tasks; i++) {
      for (int j = 0; j < MAX_NUMBER_DEP; j++) {
        /* Does this link exists */
        if (task_dep[i].number_link[j] == -1) {
          continue;
        }

        /* Define a few variables */
481
482
483
        const int ta_type = task_dep[i].type_in;
        const int ta_subtype = task_dep[i].subtype_in;
        const int ta_implicit = task_dep[i].implicit_in;
484

485
486
487
        const int tb_type = task_dep[i].type_out[j];
        const int tb_subtype = task_dep[i].subtype_out[j];
        const int tb_implicit = task_dep[i].implicit_out[j];
488

489
490
        const int count = task_dep[i].number_link[j];
        const int number_rank = task_dep[i].number_rank[j];
491

492
        /* text to write */
493
494
495
        char ta_name[200];
        char tb_name[200];

496
497
498
499
500
501
502
        /* construct line */
        task_get_full_name(ta_type, ta_subtype, ta_name);
        task_get_full_name(tb_type, tb_subtype, tb_name);

        /* Check if MPI */
        int ta_mpi = 0;
        if (ta_type == task_type_send || ta_type == task_type_recv) ta_mpi = 1;
503

504
505
        int tb_mpi = 0;
        if (tb_type == task_type_send || tb_type == task_type_recv) tb_mpi = 1;
506

507
508
509
510
511
512
513
514
515
        /* Get group name */
        char ta_cluster[20];
        char tb_cluster[20];
        task_get_group_name(ta_type, ta_subtype, ta_cluster);
        task_get_group_name(tb_type, tb_subtype, tb_cluster);

        fprintf(f, "%s,%s,%d,%d,%d,%d,%s,%s,%d,%d\n", ta_name, tb_name,
                ta_implicit, tb_implicit, ta_mpi, tb_mpi, ta_cluster,
                tb_cluster, count, number_rank);
516
517
      }
    }
518
519
    /* Close the file */
    fclose(f);
520
521
  }

522
  /* Be clean */
523
  free(task_dep);
Matthieu Schaller's avatar
Matthieu Schaller committed
524

Matthieu Schaller's avatar
Matthieu Schaller committed
525
  if (verbose)
Matthieu Schaller's avatar
Matthieu Schaller committed
526
    message("Printing task graph took %.3f %s.",
Matthieu Schaller's avatar
Matthieu Schaller committed
527
            clocks_from_ticks(getticks() - tic), clocks_getunit());
528
529
}

530
/**
531
 * @brief Split a hydrodynamic task if too large.
532
 *
533
534
 * @param t The #task
 * @param s The #scheduler we are working in.
535
 */
536
static void scheduler_splittask_hydro(struct task *t, struct scheduler *s) {
537
538
539
540
  /* Are we considering both stars and hydro when splitting? */
  /* Note this is not very clean as the scheduler should not really
     access the engine... */
  const int with_feedback = (s->space->e->policy & engine_policy_feedback);
541
  const int with_stars = (s->space->e->policy & engine_policy_stars);
542
543
  const int with_black_holes =
      (s->space->e->policy & engine_policy_black_holes);
544

545
546
547
548
549
  /* Iterate on this task until we're done with it. */
  int redo = 1;
  while (redo) {
    /* Reset the redo flag. */
    redo = 0;
550

551
552
553
    /* Is this a non-empty self-task? */
    const int is_self =
        (t->type == task_type_self) && (t->ci != NULL) &&
554
555
        ((t->ci->hydro.count > 0) || (with_stars && t->ci->stars.count > 0) ||
         (with_black_holes && t->ci->black_holes.count > 0));
556
557

    /* Is this a non-empty pair-task? */
558
559
560
561
562
563
564
565
    const int is_pair = (t->type == task_type_pair) && (t->ci != NULL) &&
                        (t->cj != NULL) &&
                        ((t->ci->hydro.count > 0) ||
                         (with_feedback && t->ci->stars.count > 0) ||
                         (with_black_holes && t->ci->black_holes.count > 0)) &&
                        ((t->cj->hydro.count > 0) ||
                         (with_feedback && t->cj->stars.count > 0) ||
                         (with_black_holes && t->cj->black_holes.count > 0));
566

Loic Hausammann's avatar
Loic Hausammann committed
567
    /* Empty task? */
568
    if (!is_self && !is_pair) {
569
      t->type = task_type_none;
570
      t->subtype = task_subtype_none;
571
      t->ci = NULL;
572
      t->cj = NULL;
573
574
575
      t->skip = 1;
      break;
    }
576

577
578
579
580
581
582
583
    /* 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) {
584
        t->skip = 1;
585
        break;
586
587
      }

588
      /* Is this cell even split and the task does not violate h ? */
589
      if (cell_can_split_self_hydro_task(ci)) {
590
        /* Make a sub? */
591
592
        if (scheduler_dosub && (ci->hydro.count < space_subsize_self_hydro) &&
            (ci->stars.count < space_subsize_self_stars)) {
593
594
595
596
597
598
599
600
601
602
603
604
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

          /* 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];
605
606
607
608
609
          for (int k = first_child + 1; k < 8; k++) {
            /* Do we have a non-empty progenitor? */
            if (ci->progeny[k] != NULL &&
                (ci->progeny[k]->hydro.count ||
                 (with_feedback && ci->progeny[k]->stars.count))) {
610
              scheduler_splittask_hydro(
611
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
612
                                    ci->progeny[k], NULL),
613
                  s);
614
615
            }
          }
616

617
          /* Make a task for each pair of progeny */
618
619
620
621
622
623
624
625
626
627
          for (int j = 0; j < 8; j++) {
            /* Do we have a non-empty progenitor? */
            if (ci->progeny[j] != NULL &&
                (ci->progeny[j]->hydro.count ||
                 (with_feedback && ci->progeny[j]->stars.count))) {
              for (int k = j + 1; k < 8; k++) {
                /* Do we have a second non-empty progenitor? */
                if (ci->progeny[k] != NULL &&
                    (ci->progeny[k]->hydro.count ||
                     (with_feedback && ci->progeny[k]->stars.count))) {
628
629
                  scheduler_splittask_hydro(
                      scheduler_addtask(s, task_type_pair, t->subtype,
630
                                        sub_sid_flag[j][k], 0, ci->progeny[j],
631
632
                                        ci->progeny[k]),
                      s);
633
634
635
636
                }
              }
            }
          }
637
        }
638

639
      } /* Cell is split */
640

641
    } /* Self interaction */
642

643
644
    /* Pair interaction? */
    else if (t->type == task_type_pair) {
645
646
647
      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
648

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

655
656
657
      /* 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
658
      const int sid = space_getsid(s->space, &ci, &cj, shift);
659

660
661
662
663
664
665
#ifdef SWIFT_DEBUG_CHECKS
      if (sid != t->flags)
        error("Got pair task with incorrect flags: sid=%d flags=%lld", sid,
              t->flags);
#endif

666
      /* Should this task be split-up? */
Matthieu Schaller's avatar
Matthieu Schaller committed
667
668
      if (cell_can_split_pair_hydro_task(ci) &&
          cell_can_split_pair_hydro_task(cj)) {
669
670
671
672
673
674
675

        const int h_count_i = ci->hydro.count;
        const int h_count_j = cj->hydro.count;

        const int s_count_i = ci->stars.count;
        const int s_count_j = cj->stars.count;

676
677
678
        int do_sub_hydro = 1;
        int do_sub_stars_i = 1;
        int do_sub_stars_j = 1;
679
        if (h_count_i > 0 && h_count_j > 0) {
680
681

          /* Note: Use division to avoid integer overflow. */
682
          do_sub_hydro =
683
              h_count_i * sid_scale[sid] < space_subsize_pair_hydro / h_count_j;
684
685
        }
        if (s_count_i > 0 && h_count_j > 0) {
686
687

          /* Note: Use division to avoid integer overflow. */
688
          do_sub_stars_i =
689
690
691
              s_count_i * sid_scale[sid] < space_subsize_pair_stars / h_count_j;
        }
        if (s_count_j > 0 && h_count_i > 0) {
692
693

          /* Note: Use division to avoid integer overflow. */
694
          do_sub_stars_j =
695
696
697
              s_count_j * sid_scale[sid] < space_subsize_pair_stars / h_count_i;
        }

698
        /* Replace by a single sub-task? */
699
700
        if (scheduler_dosub &&
            (do_sub_hydro && do_sub_stars_i && do_sub_stars_j) &&
701
            !sort_is_corner(sid)) {
702

703
704
705
706
          /* Make this task a sub task. */
          t->type = task_type_sub_pair;

          /* Otherwise, split it. */
707
        } else {
708
709
710
          /* Take a step back (we're going to recycle the current task)... */
          redo = 1;

711
712
713
714
715
716
717
718
719
720
721
722
723
724
          /* Loop over the sub-cell pairs for the current sid and add new tasks
           * for them. */
          struct cell_split_pair *csp = &cell_split_pairs[sid];
          t->ci = ci->progeny[csp->pairs[0].pid];
          t->cj = cj->progeny[csp->pairs[0].pjd];
          t->flags = csp->pairs[0].sid;
          for (int k = 1; k < csp->count; k++) {
            scheduler_splittask_hydro(
                scheduler_addtask(s, task_type_pair, t->subtype,
                                  csp->pairs[k].sid, 0,
                                  ci->progeny[csp->pairs[k].pid],
                                  cj->progeny[csp->pairs[k].pjd]),
                s);
          }
725
726
        }

727
728
        /* Otherwise, break it up if it is too large? */
      } else if (scheduler_doforcesplit && ci->split && cj->split &&
729
730
731
                 (ci->hydro.count > space_maxsize / cj->hydro.count)) {
        // message( "force splitting pair with %i and %i parts." ,
        // ci->hydro.count , cj->hydro.count );
732
733
734
735
736

        /* Replace the current task. */
        t->type = task_type_none;

        for (int j = 0; j < 8; j++)
737
          if (ci->progeny[j] != NULL && ci->progeny[j]->hydro.count)
738
            for (int k = 0; k < 8; k++)
739
              if (cj->progeny[k] != NULL && cj->progeny[k]->hydro.count) {
740
741
                struct task *tl =
                    scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
742
                                      ci->progeny[j], cj->progeny[k]);
743
                scheduler_splittask_hydro(tl, s);
744
745
746
747
748
749
750
                tl->flags = space_getsid(s->space, &t->ci, &t->cj, shift);
              }
      }
    } /* pair interaction? */
  }   /* iterate over the current task. */
}

751
752
753
754
755
756
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
757
static void scheduler_splittask_gravity(struct task *t, struct scheduler *s) {
758
  const struct space *sp = s->space;
759
  struct engine *e = sp->e;
760

761
762
763
764
765
766
767
768
769
770
  /* 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;
771
      t->ci = NULL;
772
773
774
775
776
777
778
779
      t->cj = NULL;
      t->skip = 1;
      break;
    }

    /* Self-interaction? */
    if (t->type == task_type_self) {
      /* Get a handle on the cell involved. */
780
      const struct cell *ci = t->ci;
781
782
783
784
785
786
787

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

788
      /* Should we split this task? */
789
      if (cell_can_split_self_gravity_task(ci)) {
790
        if (scheduler_dosub && ci->grav.count < space_subsize_self_grav) {
791
792
793
794
795
796
797
798
799
          /* Otherwise, split it. */
        } 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];
800

801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
          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);

          } /* Self-gravity only */
        }   /* Make tasks explicitly */
      }     /* Cell is split */
    }       /* Self interaction */
824
825
826

    /* Pair interaction? */
    else if (t->type == task_type_pair) {
827
      /* Get a handle on the cells involved. */
828
829
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
830
831
832
833
834
835

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

      /* Should this task be split-up? */
Matthieu Schaller's avatar
Matthieu Schaller committed
838
839
      if (cell_can_split_pair_gravity_task(ci) &&
          cell_can_split_pair_gravity_task(cj)) {
840
841
        const long long gcount_i = ci->grav.count;
        const long long gcount_j = cj->grav.count;
842

843
        /* Replace by a single sub-task? */
844
        if (scheduler_dosub &&
Matthieu Schaller's avatar
Matthieu Schaller committed
845
            gcount_i * gcount_j < ((long long)space_subsize_pair_grav)) {
846
847
          /* Otherwise, split it. */
        } else {
848
849
850
851
          /* Turn the task into a M-M task that will take care of all the
           * progeny pairs */
          t->type = task_type_grav_mm;
          t->subtype = task_subtype_none;
852
          t->flags = 0;
853
854

          /* Make a task for every other pair of progeny */
855
          for (int i = 0; i < 8; i++) {
856
            if (ci->progeny[i] != NULL) {
857
              for (int j = 0; j < 8; j++) {
858
                if (cj->progeny[j] != NULL) {
859
860
861
                  /* Can we use a M-M interaction here? */
                  if (cell_can_use_pair_mm_rebuild(ci->progeny[i],
                                                   cj->progeny[j], e, sp)) {
862
863
864
865
866
                    /* Flag this pair as being treated by the M-M task.
                     * We use the 64 bits in the task->flags field to store
                     * this information. The corresponding taks will unpack
                     * the information and operate according to the choices
                     * made here. */
867
                    const int flag = i * 8 + j;
868
                    t->flags |= (1ULL << flag);
869
870
871

                  } else {
                    /* Ok, we actually have to create a task */
872
873
874
875
876
                    scheduler_splittask_gravity(
                        scheduler_addtask(s, task_type_pair, task_subtype_grav,
                                          0, 0, ci->progeny[i], cj->progeny[j]),
                        s);
                  }
877
878
879
880
                }
              }
            }
          }
881
882
883
884
885
886
887
888
889
890

          /* Can none of the progenies use M-M calculations? */
          if (t->flags == 0) {
            t->type = task_type_none;
            t->subtype = task_subtype_none;
            t->ci = NULL;
            t->cj = NULL;
            t->skip = 1;
          }

891
892
        } /* Split the pair */
      }
Matthieu Schaller's avatar
Matthieu Schaller committed
893
894
    } /* pair interaction? */
  }   /* iterate over the current task. */
895
896
}

897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
/**
 * @brief Split a FOF task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
static void scheduler_splittask_fof(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_fof_pair && t->cj == NULL) ||
        t->ci->grav.count == 0 || (t->cj != NULL && t->cj->grav.count == 0)) {
      t->type = task_type_none;
      t->subtype = task_subtype_none;
917
      t->ci = NULL;
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
      t->cj = NULL;
      t->skip = 1;
      break;
    }

    /* Self-interaction? */
    if (t->type == task_type_fof_self) {

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

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

935
      /* Is this cell even split? */
936
937
938
939
940
941
942
943
944
945
946
947
948
      if (cell_can_split_self_fof_task(ci)) {

        /* 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 && ci->progeny[k]->grav.count)
            scheduler_splittask_fof(
                scheduler_addtask(s, task_type_fof_self, t->subtype, 0, 0,
949
                                  ci->progeny[k], NULL),
950
951
952
953
954
955
956
957
                s);

        /* Make a task for each pair of progeny */
        for (int j = 0; j < 8; j++)
          if (ci->progeny[j] != NULL && ci->progeny[j]->grav.count)
            for (int k = j + 1; k < 8; k++)
              if (ci->progeny[k] != NULL && ci->progeny[k]->grav.count)
                scheduler_splittask_fof(
958
959
                    scheduler_addtask(s, task_type_fof_pair, t->subtype, 0, 0,
                                      ci->progeny[j], ci->progeny[k]),
960
961
962
963
964
965
966
967
                    s);
      } /* Cell is split */

    } /* Self interaction */

  } /* iterate over the current task. */
}

968
/**
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
 * @brief Mapper function to split FOF 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_fof_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;

  for (int ind = 0; ind < num_elements; ind++) {
    struct task *t = &tasks[ind];

    /* Invoke the correct splitting strategy */
    if (t->type == task_type_fof_self || t->type == task_type_fof_pair) {
      scheduler_splittask_fof(t, s);
    }
  }
}

/**
 * @brief Mapper function to split non-FOF tasks that may be too large.
993
994
995
996
997
998
999
1000
 *
 * @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. */
For faster browsing, not all history is shown. View entire blame