scheduler.c 75 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
571
      t->subtype = task_subtype_none;
      t->cj = NULL;
572
573
574
      t->skip = 1;
      break;
    }
575

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

587
      /* Is this cell even split and the task does not violate h ? */
588
      if (cell_can_split_self_hydro_task(ci)) {
589
        /* Make a sub? */
590
        if (scheduler_dosub && ci->hydro.count < space_subsize_self_hydro) {
591
592
593
594
595
596
597
598
599
600
601
602
          /* 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];
603
604
605
606
607
          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))) {
608
              scheduler_splittask_hydro(
609
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
610
                                    ci->progeny[k], NULL),
611
                  s);
612
613
            }
          }
614

615
          /* Make a task for each pair of progeny */
616
617
618
619
620
621
622
623
624
625
          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))) {
626
627
                  scheduler_splittask_hydro(
                      scheduler_addtask(s, task_type_pair, t->subtype,
628
                                        sub_sid_flag[j][k], 0, ci->progeny[j],
629
630
                                        ci->progeny[k]),
                      s);
631
632
633
634
                }
              }
            }
          }
635
        }
636

637
      } /* Cell is split */
638

639
    } /* Self interaction */
640

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

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

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

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

664
      /* Should this task be split-up? */
Matthieu Schaller's avatar
Matthieu Schaller committed
665
666
      if (cell_can_split_pair_hydro_task(ci) &&
          cell_can_split_pair_hydro_task(cj)) {
667
        /* Replace by a single sub-task? */
668
        if (scheduler_dosub && /* Use division to avoid integer overflow. */
669
670
            ci->hydro.count * sid_scale[sid] <
                space_subsize_pair_hydro / cj->hydro.count &&
671
            !sort_is_corner(sid)) {
672
673
674
675
          /* Make this task a sub task. */
          t->type = task_type_sub_pair;

          /* Otherwise, split it. */
676
        } else {
677
678
679
          /* Take a step back (we're going to recycle the current task)... */
          redo = 1;

680
681
682
683
684
685
686
687
688
689
690
691
692
693
          /* 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);
          }
694
695
        }

696
697
        /* Otherwise, break it up if it is too large? */
      } else if (scheduler_doforcesplit && ci->split && cj->split &&
698
699
700
                 (ci->hydro.count > space_maxsize / cj->hydro.count)) {
        // message( "force splitting pair with %i and %i parts." ,
        // ci->hydro.count , cj->hydro.count );
701
702
703
704
705

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

        for (int j = 0; j < 8; j++)
706
          if (ci->progeny[j] != NULL && ci->progeny[j]->hydro.count)
707
            for (int k = 0; k < 8; k++)
708
              if (cj->progeny[k] != NULL && cj->progeny[k]->hydro.count) {
709
710
                struct task *tl =
                    scheduler_addtask(s, task_type_pair, t->subtype, 0, 0,
711
                                      ci->progeny[j], cj->progeny[k]);
712
                scheduler_splittask_hydro(tl, s);
713
714
715
716
717
718
719
                tl->flags = space_getsid(s->space, &t->ci, &t->cj, shift);
              }
      }
    } /* pair interaction? */
  }   /* iterate over the current task. */
}

720
721
722
723
724
725
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
726
static void scheduler_splittask_gravity(struct task *t, struct scheduler *s) {
727
  const struct space *sp = s->space;
728
  struct engine *e = sp->e;
729

730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
  /* 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. */
748
      const struct cell *ci = t->ci;
749
750
751
752
753
754
755

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

756
      /* Should we split this task? */
757
      if (cell_can_split_self_gravity_task(ci)) {
758
        if (scheduler_dosub && ci->grav.count < space_subsize_self_grav) {
759
760
761
762
763
764
765
766
767
          /* 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];
768

769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
          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 */
792
793
794

    /* Pair interaction? */
    else if (t->type == task_type_pair) {
795
      /* Get a handle on the cells involved. */
796
797
      struct cell *ci = t->ci;
      struct cell *cj = t->cj;
798
799
800
801
802
803

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

      /* Should this task be split-up? */
Matthieu Schaller's avatar
Matthieu Schaller committed
806
807
      if (cell_can_split_pair_gravity_task(ci) &&
          cell_can_split_pair_gravity_task(cj)) {
808
809
        const long long gcount_i = ci->grav.count;
        const long long gcount_j = cj->grav.count;
810

811
        /* Replace by a single sub-task? */
812
        if (scheduler_dosub &&
Matthieu Schaller's avatar
Matthieu Schaller committed
813
            gcount_i * gcount_j < ((long long)space_subsize_pair_grav)) {
814
815
          /* Otherwise, split it. */
        } else {
816
817
818
819
          /* 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;
820
          t->flags = 0;
821
822

          /* Make a task for every other pair of progeny */
823
          for (int i = 0; i < 8; i++) {
824
            if (ci->progeny[i] != NULL) {
825
              for (int j = 0; j < 8; j++) {
826
                if (cj->progeny[j] != NULL) {
827
828
829
                  /* Can we use a M-M interaction here? */
                  if (cell_can_use_pair_mm_rebuild(ci->progeny[i],
                                                   cj->progeny[j], e, sp)) {
830
831
832
833
834
                    /* 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. */
835
                    const int flag = i * 8 + j;
836
                    t->flags |= (1ULL << flag);
837
838
839

                  } else {
                    /* Ok, we actually have to create a task */
840
841
842
843
844
                    scheduler_splittask_gravity(
                        scheduler_addtask(s, task_type_pair, task_subtype_grav,
                                          0, 0, ci->progeny[i], cj->progeny[j]),
                        s);
                  }
845
846
847
848
                }
              }
            }
          }
849
850
851
852
853
854
855
856
857
858

          /* 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;
          }

859
860
        } /* Split the pair */
      }
Matthieu Schaller's avatar
Matthieu Schaller committed
861
862
    } /* pair interaction? */
  }   /* iterate over the current task. */
863
864
}

865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
/**
 * @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;
      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;
      }

902
      /* Is this cell even split? */
903
904
905
906
907
908
909
910
911
912
913
914
915
      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,
916
                                  ci->progeny[k], NULL),
917
918
919
920
921
922
923
924
                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(
925
926
                    scheduler_addtask(s, task_type_fof_pair, t->subtype, 0, 0,
                                      ci->progeny[j], ci->progeny[k]),
927
928
929
930
931
932
933
934
                    s);
      } /* Cell is split */

    } /* Self interaction */

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

935
/**
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
 * @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.
960
961
962
963
964
965
966
967
968
969
 *
 * @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;
970

971
972
  for (int ind = 0; ind < num_elements; ind++) {
    struct task *t = &tasks[ind];
973
974
975
976
977
978
979
980

    /* 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);
981
    } else if (t->type == task_type_grav_mesh) {
982
      /* For future use */
983
    } else {
984
#ifdef SWIFT_DEBUG_CHECKS
985
986
      error("Unexpected task sub-type %s/%s", taskID_names[t->type],
            subtaskID_names[t->subtype]);
987
#endif
988
    }
989
  }
990
}
991

Matthieu Schaller's avatar
Matthieu Schaller committed
992
993
994
995
/**
 * @brief Splits all the tasks in the scheduler that are too large.
 *
 * @param s The #scheduler.
996
997
 * @param fof_tasks Are we splitting the FOF tasks (1)? Or the regular tasks
 * (0)?
Matthieu Schaller's avatar
Matthieu Schaller committed
998
 */
999
1000
void scheduler_splittasks(struct scheduler *s, const int fof_tasks) {

For faster browsing, not all history is shown. View entire blame