StarPU Internal Handbook
prio_deque.h
Go to the documentation of this file.
1 /* StarPU --- Runtime system for heterogeneous multicore architectures.
2  *
3  * Copyright (C) 2013-2021 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 #ifndef __PRIO_DEQUE_H__
18 #define __PRIO_DEQUE_H__
19 #include <starpu.h>
20 #include <starpu_scheduler.h>
21 #include <core/task.h>
22 
26 {
27  struct starpu_task_prio_list list;
28  unsigned ntasks;
29  unsigned nprocessed;
30  // Assumptions:
31  // exp_len is the sum of predicted_length + predicted_tansfer of all tasks in list
32  // exp_start is the time at which the first task of list can start
33  // exp_end = exp_start + exp_end
34  // Careful: those are NOT maintained by the prio_queue operations
35  double exp_start, exp_end, exp_len;
36 };
37 
38 static inline void _starpu_prio_deque_init(struct _starpu_prio_deque *pdeque)
39 {
40  memset(pdeque,0,sizeof(*pdeque));
41  starpu_task_prio_list_init(&pdeque->list);
42  STARPU_HG_DISABLE_CHECKING(pdeque->exp_start);
43  STARPU_HG_DISABLE_CHECKING(pdeque->exp_end);
44  STARPU_HG_DISABLE_CHECKING(pdeque->exp_len);
45 }
46 
47 static inline void _starpu_prio_deque_destroy(struct _starpu_prio_deque *pdeque)
48 {
49  starpu_task_prio_list_deinit(&pdeque->list);
50 }
51 
53 static inline int _starpu_prio_deque_is_empty(struct _starpu_prio_deque *pdeque)
54 {
55  return pdeque->ntasks == 0;
56 }
57 
58 static inline void _starpu_prio_deque_erase(struct _starpu_prio_deque *pdeque, struct starpu_task *task)
59 {
60  starpu_task_prio_list_erase(&pdeque->list, task);
61 }
62 
64 static inline int _starpu_prio_deque_push_front_task(struct _starpu_prio_deque *pdeque, struct starpu_task *task)
65 {
66  starpu_task_prio_list_push_front(&pdeque->list, task);
67  pdeque->ntasks++;
68  return 0;
69 }
70 static inline int _starpu_prio_deque_push_back_task(struct _starpu_prio_deque *pdeque, struct starpu_task *task)
71 {
72  starpu_task_prio_list_push_back(&pdeque->list, task);
73  pdeque->ntasks++;
74  return 0;
75 }
76 int _starpu_prio_deque_push_back_task(struct _starpu_prio_deque *, struct starpu_task *);
77 
78 
79 static inline struct starpu_task * _starpu_prio_deque_highest_task(struct _starpu_prio_deque *pdeque)
80 {
81  struct starpu_task *task;
82  if (starpu_task_prio_list_empty(&pdeque->list))
83  return NULL;
84  task = starpu_task_prio_list_front_highest(&pdeque->list);
85  return task;
86 }
87 
92 static inline struct starpu_task * _starpu_prio_deque_pop_task(struct _starpu_prio_deque *pdeque)
93 {
94  struct starpu_task *task;
95  if (starpu_task_prio_list_empty(&pdeque->list))
96  return NULL;
97  task = starpu_task_prio_list_pop_front_highest(&pdeque->list);
98  pdeque->ntasks--;
99  return task;
100 }
101 
102 static inline struct starpu_task * _starpu_prio_deque_pop_back_task(struct _starpu_prio_deque *pdeque)
103 {
104  struct starpu_task *task;
105  if (starpu_task_prio_list_empty(&pdeque->list))
106  return NULL;
107  task = starpu_task_prio_list_pop_back_lowest(&pdeque->list);
108  pdeque->ntasks--;
109  return task;
110 }
111 
112 static inline int _starpu_prio_deque_pop_this_task(struct _starpu_prio_deque *pdeque, int workerid, struct starpu_task *task)
113 {
114  unsigned nimpl = 0;
115 #ifdef STARPU_DEBUG
116  STARPU_ASSERT(starpu_task_prio_list_ismember(&pdeque->list, task));
117 #endif
118 
119  if (workerid < 0 || starpu_worker_can_execute_task_first_impl(workerid, task, &nimpl))
120  {
121  starpu_task_set_implementation(task, nimpl);
122  starpu_task_prio_list_erase(&pdeque->list, task);
123  pdeque->ntasks--;
124  return 1;
125  }
126 
127  return 0;
128 }
129 
132 struct starpu_task * _starpu_prio_deque_pop_task_for_worker(struct _starpu_prio_deque *, int workerid, int *skipped);
133 
136 struct starpu_task * _starpu_prio_deque_deque_task_for_worker(struct _starpu_prio_deque *, int workerid, int *skipped);
137 
138 struct starpu_task *_starpu_prio_deque_deque_first_ready_task(struct _starpu_prio_deque *, unsigned workerid);
139 
140 #endif /* __PRIO_DEQUE_H__ */
static struct starpu_task * _starpu_prio_deque_pop_task(struct _starpu_prio_deque *pdeque)
Definition: prio_deque.h:92
struct starpu_task * _starpu_prio_deque_deque_task_for_worker(struct _starpu_prio_deque *, int workerid, int *skipped)
struct starpu_task * _starpu_prio_deque_pop_task_for_worker(struct _starpu_prio_deque *, int workerid, int *skipped)
static int _starpu_prio_deque_is_empty(struct _starpu_prio_deque *pdeque)
Definition: prio_deque.h:53
static int _starpu_prio_deque_push_front_task(struct _starpu_prio_deque *pdeque, struct starpu_task *task)
Definition: prio_deque.h:64
Definition: prio_deque.h:26