prio_deque.c 3.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125
  1. /* StarPU --- Runtime system for heterogeneous multicore architectures.
  2. *
  3. * Copyright (C) 2013-2020 Université de Bordeaux, CNRS (LaBRI UMR 5800), Inria
  4. * Copyright (C) 2013 Simon Archipoff
  5. *
  6. * StarPU is free software; you can redistribute it and/or modify
  7. * it under the terms of the GNU Lesser General Public License as published by
  8. * the Free Software Foundation; either version 2.1 of the License, or (at
  9. * your option) any later version.
  10. *
  11. * StarPU is distributed in the hope that it will be useful, but
  12. * WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  14. *
  15. * See the GNU Lesser General Public License in COPYING.LGPL for more details.
  16. */
  17. #include <core/workers.h>
  18. #include "prio_deque.h"
  19. #include "fifo_queues.h"
  20. /* a little dirty code factorization */
  21. static inline int pred_true(struct starpu_task * t STARPU_ATTRIBUTE_UNUSED, void * v STARPU_ATTRIBUTE_UNUSED)
  22. {
  23. return 1;
  24. }
  25. static inline int pred_can_execute(struct starpu_task * t, void * pworkerid)
  26. {
  27. int i;
  28. for(i = 0; i < STARPU_MAXIMPLEMENTATIONS; i++)
  29. if(starpu_worker_can_execute_task(*(int*)pworkerid, t,i))
  30. {
  31. starpu_task_set_implementation(t, i);
  32. return 1;
  33. }
  34. return 0;
  35. }
  36. #define REMOVE_TASK(pdeque, first_task_field, next_task_field, predicate, parg) \
  37. { \
  38. struct starpu_task * t; \
  39. for (t = starpu_task_prio_list_begin(&pdeque->list); \
  40. t != starpu_task_prio_list_end(&pdeque->list); \
  41. t = starpu_task_prio_list_next(&pdeque->list, t)) \
  42. { \
  43. if (predicate(t, parg)) \
  44. { \
  45. starpu_task_prio_list_erase(&pdeque->list, t); \
  46. pdeque->ntasks--; \
  47. return t; \
  48. } \
  49. else \
  50. if (skipped) \
  51. *skipped = 1; \
  52. } \
  53. return NULL; \
  54. }
  55. /* deque a task of the higher priority available */
  56. /* From the front of the list for the highest priority */
  57. struct starpu_task * _starpu_prio_deque_pop_task_for_worker(struct _starpu_prio_deque * pdeque, int workerid, int *skipped)
  58. {
  59. STARPU_ASSERT(pdeque);
  60. STARPU_ASSERT(workerid >= 0 && (unsigned) workerid < starpu_worker_get_count());
  61. REMOVE_TASK(pdeque, _head, prev, pred_can_execute, &workerid);
  62. }
  63. /* From the back of the list for the highest priority */
  64. struct starpu_task * _starpu_prio_deque_deque_task_for_worker(struct _starpu_prio_deque * pdeque, int workerid, int *skipped)
  65. {
  66. STARPU_ASSERT(pdeque);
  67. STARPU_ASSERT(workerid >= 0 && (unsigned) workerid < starpu_worker_get_count());
  68. REMOVE_TASK(pdeque, _tail, next, pred_can_execute, &workerid);
  69. }
  70. struct starpu_task *_starpu_prio_deque_deque_first_ready_task(struct _starpu_prio_deque * pdeque, unsigned workerid)
  71. {
  72. struct starpu_task *task = NULL, *current;
  73. if (starpu_task_prio_list_empty(&pdeque->list))
  74. return NULL;
  75. if (pdeque->ntasks > 0)
  76. {
  77. pdeque->ntasks--;
  78. task = starpu_task_prio_list_front_highest(&pdeque->list);
  79. if (STARPU_UNLIKELY(!task))
  80. return NULL;
  81. int first_task_priority = task->priority;
  82. int non_ready_best = INT_MAX;
  83. for (current = starpu_task_prio_list_begin(&pdeque->list);
  84. current != starpu_task_prio_list_end(&pdeque->list);
  85. current = starpu_task_prio_list_next(&pdeque->list, current))
  86. {
  87. int priority = current->priority;
  88. if (priority >= first_task_priority)
  89. {
  90. int non_ready = _starpu_count_non_ready_buffers(current, workerid);
  91. if (non_ready < non_ready_best)
  92. {
  93. non_ready_best = non_ready;
  94. task = current;
  95. if (non_ready == 0)
  96. break;
  97. }
  98. }
  99. }
  100. starpu_task_prio_list_erase(&pdeque->list, task);
  101. }
  102. return task;
  103. }