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

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

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

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

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

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

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

60
61
62
63
64
65
66
/**
 * @brief Add an unlock_task to the given task.
 *
 * @param s The #scheduler.
 * @param ta The unlocking #task.
 * @param tb The #task that will be unlocked.
 */
67
68
void scheduler_addunlock(struct scheduler *s, struct task *ta,
                         struct task *tb) {
69
70
71
72
73
#ifdef SWIFT_DEBUG_CHECKS
  if (ta == NULL) error("Unlocking task is NULL.");
  if (tb == NULL) error("Unlocked task is NULL.");
#endif

74
75
76
77
78
  /* Get an index at which to store this unlock. */
  const int ind = atomic_inc(&s->nr_unlocks);

  /* Does the buffer need to be grown? */
  if (ind == s->size_unlocks) {
79
    /* Allocate the new buffer. */
80
81
82
    struct task **unlocks_new;
    int *unlock_ind_new;
    const int size_unlocks_new = s->size_unlocks * 2;
83
84
    if ((unlocks_new = (struct task **)malloc(sizeof(struct task *) *
                                              size_unlocks_new)) == NULL ||
85
86
        (unlock_ind_new = (int *)malloc(sizeof(int) * size_unlocks_new)) ==
            NULL)
87
      error("Failed to re-allocate unlocks.");
88

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

93
    /* Copy the buffers. */
94
95
96
97
98
99
    memcpy(unlocks_new, s->unlocks, sizeof(struct task *) * ind);
    memcpy(unlock_ind_new, s->unlock_ind, sizeof(int) * ind);
    free(s->unlocks);
    free(s->unlock_ind);
    s->unlocks = unlocks_new;
    s->unlock_ind = unlock_ind_new;
100

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

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

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

115
116
117
118
119
120
/**
 * @brief Write a dot file with the task dependencies.
 *
 * See examples/task_graph for an example of how to use it
 * @param s The #scheduler we are working in.
 */
121
void scheduler_write_dependency(struct scheduler *s) {
122
#ifdef WITH_MPI
lhausamm's avatar
lhausamm committed
123
  if (engine_rank != 0) return;
124
#endif
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
  int i, j;

  int max_nber_dep = 5;
  /* 2 => we need 1 int for type and 1 for subtype */
  int nber_relation = 2 * task_type_count * task_subtype_count * max_nber_dep;
  /* For each type/subtype, a table of 2*max_nber_dep int is available =>
     max_nber_dep task with subtype available
     
     -1 means that it is not set yet

     to get the table of max_nber_dep for a task:
     ind = (ta * task_subtype_count + sa) * max_nber_dep * 2
     where ta is the value of task_type and sa is the value of
     task_subtype
   */
  int *table = malloc(nber_relation * sizeof(int));
  for(i=0; i < nber_relation; i++)
    table[i] = -1;
lhausamm's avatar
lhausamm committed
143

144
  message("Writing dependencies");
lhausamm's avatar
lhausamm committed
145

146
  /* create file */
147
148
  char filename[200] = "dependency_graph.dot";
  FILE *f; /* file containing the output */
149
  f = open_and_check_file(filename, "w");
150
151
152
153
154
155
156
157

  /* write header */
  fprintf(f, "digraph task_dep {\n");
  fprintf(f, "\t compound=true;\n");
  fprintf(f, "\t ratio=0.66;\n");
  fprintf(f, "\t node[nodesep=0.15];\n");

  /* loop over all tasks */
lhausamm's avatar
lhausamm committed
158
  for (i = 0; i < s->nr_tasks; i++) {
159
    struct task *ta;    
lhausamm's avatar
lhausamm committed
160
161
162
163
    ta = &s->tasks[i];

    /* and theirs dependencies */
    for (j = 0; j < ta->nr_unlock_tasks; j++) {
164
      struct task *tb;
lhausamm's avatar
lhausamm committed
165
166
      tb = ta->unlock_tasks[j];

167

168
      char tmp[200];     /* text to write */
169
170
      char ta_name[200];
      char tb_name[200];
lhausamm's avatar
lhausamm committed
171
      /* construct line */
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
      if (ta->subtype == task_subtype_none)
	sprintf(ta_name, "%s", taskID_names[ta->type]);
      else
	sprintf(ta_name, "\"%s %s\"",
		taskID_names[ta->type],
		subtaskID_names[ta->subtype]);

      if (tb->subtype == task_subtype_none)
	sprintf(tb_name, "%s", taskID_names[tb->type]);
      else
	sprintf(tb_name, "\"%s %s\"",
		taskID_names[tb->type],
		subtaskID_names[tb->subtype]);
      
      sprintf(tmp, "\t %s->%s;\n",
	      ta_name,
	      tb_name);
lhausamm's avatar
lhausamm committed
189
190

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

193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
      int ind = ta->type * task_subtype_count + ta->subtype;
      ind *= 2 * max_nber_dep;
      
      int k = 0;
      int *cur = &table[ind];
      while (k < max_nber_dep)
	{
	  /* not written yet */
	  if (cur[0] == -1)
	    {
	      cur[0] = tb->type;
	      cur[1] = tb->subtype;
	      break;
	    }

	  /* already written */
	  if (cur[0] == tb->type && cur[1] == tb->subtype)
	    {
	      written = 1;
	      break;
	    }

	  k += 1;
	  cur = &cur[3];
	}

      /* max_nber_dep is too small */
      if (k == max_nber_dep)
	error("Not enough memory, please increase max_nber_dep");
	
lhausamm's avatar
lhausamm committed
223
      /* Not written yet => write it */
224
      if (!written) {
lhausamm's avatar
lhausamm committed
225
226
        fprintf(f, tmp);
      }
227
    }
lhausamm's avatar
lhausamm committed
228
  }
lhausamm's avatar
lhausamm committed
229

230
231
  fprintf(f, "}");
  fclose(f);
232
  free(table);
233
234
}

235
/**
236
 * @brief Split a hydrodynamic task if too large.
237
 *
238
239
 * @param t The #task
 * @param s The #scheduler we are working in.
240
 */
241
static void scheduler_splittask_hydro(struct task *t, struct scheduler *s) {
242

243
244
245
  /* Iterate on this task until we're done with it. */
  int redo = 1;
  while (redo) {
246

247
248
    /* Reset the redo flag. */
    redo = 0;
249

250
    /* Non-splittable task? */
251
252
    if ((t->ci == NULL) || (t->type == task_type_pair && t->cj == NULL) ||
        t->ci->count == 0 || (t->cj != NULL && t->cj->count == 0)) {
253
      t->type = task_type_none;
254
255
      t->subtype = task_subtype_none;
      t->cj = NULL;
256
257
258
      t->skip = 1;
      break;
    }
259

260
261
    /* Self-interaction? */
    if (t->type == task_type_self) {
262

263
264
265
266
267
      /* Get a handle on the cell involved. */
      struct cell *ci = t->ci;

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

272
      /* Is this cell even split and the task does not violate h ? */
273
      if (cell_can_split_self_task(ci)) {
274

275
        /* Make a sub? */
276
        if (scheduler_dosub && ci->count < space_subsize_self) {
277

278
279
280
281
282
          /* convert to a self-subtask. */
          t->type = task_type_sub_self;

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

284
285
286
287
288
289
290
291
          /* 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++)
292
            if (ci->progeny[k] != NULL && ci->progeny[k]->count)
293
              scheduler_splittask_hydro(
294
                  scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
295
                                    ci->progeny[k], NULL),
296
297
                  s);

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

311
    } /* Self interaction */
312

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

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

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

326
327
328
      /* 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
329
      const int sid = space_getsid(s->space, &ci, &cj, shift);
330

331
      /* Should this task be split-up? */
332
      if (cell_can_split_pair_task(ci) && cell_can_split_pair_task(cj)) {
333
334

        /* Replace by a single sub-task? */
335
336
        if (scheduler_dosub && /* Use division to avoid integer overflow. */
            ci->count * sid_scale[sid] < space_subsize_pair / cj->count &&
337
            !sort_is_corner(sid)) {
338
339
340
341
342

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

          /* Otherwise, split it. */
343
344
        } else {

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

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

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

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

            case 11: /* (  0 ,  1 , -1 ) */
              t->ci = ci->progeny[2];
              t->cj = cj->progeny[1];
              t->flags = 11;
601
              scheduler_splittask_hydro(
602
                  scheduler_addtask(s, task_type_pair, t->subtype, 11, 0,
603
                                    ci->progeny[6], cj->progeny[5]),
604
                  s);
605
              scheduler_splittask_hydro(
606
                  scheduler_addtask(s, task_type_pair, t->subtype, 2, 0,
607
                                    ci->progeny[2], cj->progeny[5]),
608
                  s);
609
              scheduler_splittask_hydro(
610
                  scheduler_addtask(s, task_type_pair, t->subtype, 6, 0,
611
                                    ci->progeny[6], cj->progeny[1]),
612
613
614
615
616
617
618
                  s);
              break;

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

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

708
709
710
711
712
713
/**
 * @brief Split a gravity task if too large.
 *
 * @param t The #task
 * @param s The #scheduler we are working in.
 */
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
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;
      }

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
      /* Should we split this task? */
      if (ci->split && ci->gcount > space_subsize_self_grav) {

        /* Take a step back (we're going to recycle the current task)... */
        redo = 1;

        /* Add the self tasks. */
        int first_child = 0;
        while (ci->progeny[first_child] == NULL) first_child++;
        t->ci = ci->progeny[first_child];
        for (int k = first_child + 1; k < 8; k++)
          if (ci->progeny[k] != NULL)
            scheduler_splittask_gravity(
                scheduler_addtask(s, task_type_self, t->subtype, 0, 0,
                                  ci->progeny[k], NULL),
                s);

        /* Make a task for each pair of progeny */
        if (t->subtype != task_subtype_external_grav) {
          for (int j = 0; j < 8; j++)
            if (ci->progeny[j] != NULL)
              for (int k = j + 1; k < 8; k++)
                if (ci->progeny[k] != NULL)
                  scheduler_splittask_gravity(
                      scheduler_addtask(s, task_type_pair, t->subtype,
                                        sub_sid_flag[j][k], 0, ci->progeny[j],
                                        ci->progeny[k]),
                      s);
772
        }
773
      } /* Cell is split */
774
775
776
777
778

    } /* Self interaction */

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

      /* Get a handle on the cells involved. */
      struct cell *ci = t->ci;
782
783
784
785
786
787
788
789
      struct cell *cj = t->cj;

      /* Foreign task? */
      if (ci->nodeID != s->nodeID && cj->nodeID != s->nodeID) {
        t->skip = 1;
        break;
      }
    } /* pair interaction? */
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
  }   /* iterate over the current task. */
}

/**
 * @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;
806

807
808
  for (int ind = 0; ind < num_elements; ind++) {
    struct task *t = &tasks[ind];
809
810
811
812
813
814
815
816
817
818

    /* 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) {
819
      /* For future use */
820
821
822
    } else {
      error("Unexpected task sub-type");
    }
823
  }
824
}
825

Matthieu Schaller's avatar
Matthieu Schaller committed
826
827
828
829
830
/**
 * @brief Splits all the tasks in the scheduler that are too large.
 *
 * @param s The #scheduler.
 */
831
void scheduler_splittasks(struct scheduler *s) {
832

833
834
  /* Call the mapper on each current task. */
  threadpool_map(s->threadpool, scheduler_splittasks_mapper, s->tasks,
835
                 s->nr_tasks, sizeof(struct task), 0, s);
836
837
}

838