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-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 #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 }
43 
44 static inline void _starpu_prio_deque_destroy(struct _starpu_prio_deque *pdeque)
45 {
46  starpu_task_prio_list_deinit(&pdeque->list);
47 }
48 
50 static inline int _starpu_prio_deque_is_empty(struct _starpu_prio_deque *pdeque)
51 {
52  return pdeque->ntasks == 0;
53 }
54 
55 static inline void _starpu_prio_deque_erase(struct _starpu_prio_deque *pdeque, struct starpu_task *task)
56 {
57  starpu_task_prio_list_erase(&pdeque->list, task);
58 }
59 
61 static inline int _starpu_prio_deque_push_front_task(struct _starpu_prio_deque *pdeque, struct starpu_task *task)
62 {
63  starpu_task_prio_list_push_front(&pdeque->list, task);
64  pdeque->ntasks++;
65  return 0;
66 }
67 static inline int _starpu_prio_deque_push_back_task(struct _starpu_prio_deque *pdeque, struct starpu_task *task)
68 {
69  starpu_task_prio_list_push_back(&pdeque->list, task);
70  pdeque->ntasks++;
71  return 0;
72 }
73 int _starpu_prio_deque_push_back_task(struct _starpu_prio_deque *, struct starpu_task *);
74 
75 
76 static inline struct starpu_task * _starpu_prio_deque_highest_task(struct _starpu_prio_deque *pdeque)
77 {
78  struct starpu_task *task;
79  if (starpu_task_prio_list_empty(&pdeque->list))
80  return NULL;
81  task = starpu_task_prio_list_front_highest(&pdeque->list);
82  return task;
83 }
84 
89 static inline struct starpu_task * _starpu_prio_deque_pop_task(struct _starpu_prio_deque *pdeque)
90 {
91  struct starpu_task *task;
92  if (starpu_task_prio_list_empty(&pdeque->list))
93  return NULL;
94  task = starpu_task_prio_list_pop_front_highest(&pdeque->list);
95  pdeque->ntasks--;
96  return task;
97 }
98 
99 static inline struct starpu_task * _starpu_prio_deque_pop_back_task(struct _starpu_prio_deque *pdeque)
100 {
101  struct starpu_task *task;
102  if (starpu_task_prio_list_empty(&pdeque->list))
103  return NULL;
104  task = starpu_task_prio_list_pop_back_lowest(&pdeque->list);
105  pdeque->ntasks--;
106  return task;
107 }
108 
109 static inline int _starpu_prio_deque_pop_this_task(struct _starpu_prio_deque *pdeque, int workerid, struct starpu_task *task)
110 {
111  unsigned nimpl = 0;
112 #ifdef STARPU_DEBUG
113  STARPU_ASSERT(starpu_task_prio_list_ismember(&pdeque->list, task));
114 #endif
115 
116  if (workerid < 0 || starpu_worker_can_execute_task_first_impl(workerid, task, &nimpl))
117  {
118  starpu_task_set_implementation(task, nimpl);
119  starpu_task_prio_list_erase(&pdeque->list, task);
120  pdeque->ntasks--;
121  return 1;
122  }
123 
124  return 0;
125 }
126 
129 struct starpu_task * _starpu_prio_deque_pop_task_for_worker(struct _starpu_prio_deque *, int workerid, int *skipped);
130 
133 struct starpu_task * _starpu_prio_deque_deque_task_for_worker(struct _starpu_prio_deque *, int workerid, int *skipped);
134 
135 struct starpu_task *_starpu_prio_deque_deque_first_ready_task(struct _starpu_prio_deque *, unsigned workerid);
136 
137 #endif /* __PRIO_DEQUE_H__ */
task.h
_starpu_prio_deque_pop_task_for_worker
struct starpu_task * _starpu_prio_deque_pop_task_for_worker(struct _starpu_prio_deque *, int workerid, int *skipped)
_starpu_prio_deque_push_front_task
static int _starpu_prio_deque_push_front_task(struct _starpu_prio_deque *pdeque, struct starpu_task *task)
Definition: prio_deque.h:61
_starpu_prio_deque_pop_task
static struct starpu_task * _starpu_prio_deque_pop_task(struct _starpu_prio_deque *pdeque)
Definition: prio_deque.h:89
_starpu_prio_deque_deque_task_for_worker
struct starpu_task * _starpu_prio_deque_deque_task_for_worker(struct _starpu_prio_deque *, int workerid, int *skipped)
_starpu_prio_deque_is_empty
static int _starpu_prio_deque_is_empty(struct _starpu_prio_deque *pdeque)
Definition: prio_deque.h:50
_starpu_prio_deque
Definition: prio_deque.h:26