starpu_sched_node.h 9.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248
  1. #ifndef __SCHED_NODE_H__
  2. #define __SCHED_NODE_H__
  3. #include <starpu.h>
  4. #include <common/starpu_spinlock.h>
  5. #ifdef STARPU_HAVE_HWLOC
  6. #include <hwloc.h>
  7. #endif
  8. /* struct starpu_sched_node are scheduler modules, a scheduler is a tree-like
  9. * structure of them, some parts of scheduler can be shared by several contexes
  10. * to perform some local optimisations, so, for all nodes, a list of father is
  11. * defined indexed by sched_ctx_id
  12. *
  13. * they embed there specialised method in a pseudo object-style, so calls are like node->push_task(node,task)
  14. *
  15. */
  16. struct starpu_sched_node
  17. {
  18. /* node->push_task(node, task)
  19. * this function is called to push a task on node subtree, this can either
  20. * perform a recursive call on a child or store the task in the node, then
  21. * it will be returned by a further pop_task call
  22. *
  23. * the caller must ensure that node is able to execute task
  24. */
  25. int (*push_task)(struct starpu_sched_node *,
  26. struct starpu_task *);
  27. /* this function is called by workers to get a task on them fathers
  28. * this function should first return a localy stored task or perform
  29. * a recursive call on father
  30. *
  31. * a default implementation simply do a recursive call on father
  32. */
  33. struct starpu_task * (*pop_task)(struct starpu_sched_node *,
  34. unsigned sched_ctx_id);
  35. /* this function notify underlying worker that a task as been pushed
  36. * and would be returned by a pop_task call
  37. * it should be called each time a node localy store a task
  38. * default implementation simply perform a recursive call on childrens
  39. * this function can be called by a worker as it doesn't try to wake up himself
  40. */
  41. void (*available)(struct starpu_sched_node *);
  42. /* this function is an heuristic that compute load of subtree, basicaly
  43. * it compute
  44. * estimated_load(node) = sum(estimated_load(node_childs)) +
  45. * nb_local_tasks / average(relative_speedup(underlying_worker))
  46. */
  47. double (*estimated_load)(struct starpu_sched_node * node);
  48. double (*estimated_end)(struct starpu_sched_node * node);
  49. /* the numbers of node's childs
  50. */
  51. int nchilds;
  52. /* the vector of node's childs
  53. */
  54. struct starpu_sched_node ** childs;
  55. /* may be shared by several contexts
  56. * so we need several fathers
  57. */
  58. struct starpu_sched_node * fathers[STARPU_NMAX_SCHED_CTXS];
  59. /* the set of workers in the node's subtree
  60. */
  61. struct starpu_bitmap * workers;
  62. /* the workers available in context
  63. */
  64. struct starpu_bitmap * workers_in_ctx;
  65. /* is_homogeneous is 0 iff workers in the node's subtree are heterogeneous,
  66. * this field is set and updated automaticaly, you shouldn't write on it
  67. */
  68. int is_homogeneous;
  69. /* node's private data, no restriction on use
  70. */
  71. void * data;
  72. /* this function is called after all childs has been set, and the
  73. * workers member was filled, can be used to init data, or anything you want
  74. */
  75. void (*init_data)(struct starpu_sched_node *);
  76. /* this function is called to free data allocated by init_data
  77. * just before the call of starpu_sched_node_destroy(node)
  78. */
  79. void (*deinit_data)(struct starpu_sched_node *);
  80. #ifdef STARPU_HAVE_HWLOC
  81. /* in case of a hierarchical scheduler, this is set to the part of
  82. * topology that is binded to this node, eg: a numa node for a ws
  83. * node that would balance load between underlying sockets
  84. */
  85. hwloc_obj_t obj;
  86. #endif
  87. };
  88. struct starpu_sched_tree
  89. {
  90. struct starpu_sched_node * root;
  91. struct starpu_bitmap * workers;
  92. /* this lock is used to protect the scheduler,
  93. * it is taken in read mode pushing a task
  94. * and in write mode for adding or removing workers
  95. */
  96. starpu_pthread_rwlock_t lock;
  97. };
  98. int STARPU_WARN_UNUSED_RESULT starpu_sched_node_execute_preds(struct starpu_sched_node * node, struct starpu_task * task, double * length);
  99. double starpu_sched_node_transfer_length(struct starpu_sched_node * node, struct starpu_task * task);
  100. struct starpu_sched_node * starpu_sched_node_create(void);
  101. void starpu_sched_node_destroy(struct starpu_sched_node * node);
  102. void starpu_sched_node_set_father(struct starpu_sched_node *node, struct starpu_sched_node *father_node, unsigned sched_ctx_id);
  103. void starpu_sched_node_add_child(struct starpu_sched_node * node, struct starpu_sched_node * child);
  104. void starpu_sched_node_remove_child(struct starpu_sched_node * node, struct starpu_sched_node * child);
  105. int starpu_sched_node_can_execute_task(struct starpu_sched_node * node, struct starpu_task * task);
  106. /* no public create function for workers because we dont want to have several node_worker for a single workerid */
  107. struct starpu_sched_node * starpu_sched_node_worker_get(int workerid);
  108. /* this function compare the available function of the node with the standard available for worker nodes*/
  109. int starpu_sched_node_is_worker(struct starpu_sched_node * node);
  110. int starpu_sched_node_is_simple_worker(struct starpu_sched_node * node);
  111. int starpu_sched_node_is_combined_worker(struct starpu_sched_node * node);
  112. int starpu_sched_node_worker_get_workerid(struct starpu_sched_node * worker_node);
  113. struct starpu_sched_node * starpu_sched_node_fifo_create(void * arg STARPU_ATTRIBUTE_UNUSED);
  114. int starpu_sched_node_is_fifo(struct starpu_sched_node * node);
  115. //struct starpu_task_list starpu_sched_node_fifo_get_non_executable_tasks(struct starpu_sched_node * fifo_node);
  116. struct starpu_sched_node * starpu_sched_node_work_stealing_create(void);
  117. int starpu_sched_node_is_work_stealing(struct starpu_sched_node * node);
  118. struct starpu_sched_node * starpu_sched_node_random_create(void * arg STARPU_ATTRIBUTE_UNUSED);
  119. int starpu_sched_node_is_random(struct starpu_sched_node *);
  120. struct starpu_heft_data
  121. {
  122. double alpha;
  123. double beta;
  124. double gamma;
  125. double idle_power;
  126. struct starpu_sched_node * (*no_perf_model_node_create)(void * arg_no_perf_model);
  127. void * arg_no_perf_model;
  128. struct starpu_sched_node * (*calibrating_node_create)(void * arg_calibrating_node);
  129. void * arg_calibrating_node;
  130. };
  131. /* create a node with heft_data paremeters
  132. a copy the struct starpu_heft_data * given is performed during the init_data call
  133. the heft node doesnt do anything but pushing tasks on no_perf_model_node and calibrating_node
  134. */
  135. struct starpu_sched_node * starpu_sched_node_heft_create(struct starpu_heft_data * heft_data);
  136. int starpu_sched_node_is_heft(struct starpu_sched_node * node);
  137. /* compute predicted_end by taking in account the case of the predicted transfer and the predicted_end overlap
  138. */
  139. double starpu_sched_compute_expected_time(double now, double predicted_end, double predicted_length, double predicted_transfer);
  140. /* this node select the best implementation for the first worker in context that can execute task.
  141. * and fill task->predicted and task->predicted_transfer
  142. * cannot have several childs if push_task is called
  143. */
  144. struct starpu_sched_node * starpu_sched_node_best_implementation_create(void * arg STARPU_ATTRIBUTE_UNUSED);
  145. /* this node select an implementation that need to be calibrated.
  146. * cannot have several childs if push_task is called.
  147. */
  148. struct starpu_sched_node * starpu_sched_node_calibration_create(void * arg STARPU_ATTRIBUTE_UNUSED);
  149. /*create an empty tree
  150. */
  151. struct starpu_sched_tree * starpu_sched_tree_create(void);
  152. void starpu_sched_tree_destroy(struct starpu_sched_tree * tree, unsigned sched_ctx_id);
  153. /* destroy node and all his child
  154. * except if they are shared between several contexts
  155. */
  156. void starpu_sched_node_destroy_rec(struct starpu_sched_node * node, unsigned sched_ctx_id);
  157. int starpu_sched_tree_push_task(struct starpu_task * task);
  158. struct starpu_task * starpu_sched_tree_pop_task(unsigned sched_ctx_id);
  159. void starpu_sched_tree_add_workers(unsigned sched_ctx_id, int *workerids, unsigned nworkers);
  160. void starpu_sched_tree_remove_workers(unsigned sched_ctx_id, int *workerids, unsigned nworkers);
  161. void starpu_sched_node_worker_pre_exec_hook(struct starpu_task * task);
  162. void starpu_sched_node_worker_post_exec_hook(struct starpu_task * task);
  163. /* return the bitmap of worker that are allowed to use in this scheduling context
  164. */
  165. struct starpu_bitmap * _starpu_get_worker_mask(struct starpu_task * task);
  166. /* this function is called to initialize a scheduler tree
  167. */
  168. void starpu_sched_node_init_rec(struct starpu_sched_node * node);
  169. /* this function fill all the node->workers members
  170. */
  171. void _starpu_set_workers_bitmaps(void);
  172. /* this function call init data on all nodes in postfix order
  173. */
  174. void starpu_sched_tree_call_init_data(struct starpu_sched_tree * t);
  175. /* push task of list lower as possible in the tree, a non null value is returned if some task couldn't be pushed
  176. */
  177. int starpu_sched_node_push_tasks_to_firsts_suitable_parent(struct starpu_sched_node * node, struct starpu_task_list * list, int sched_ctx_id);
  178. struct starpu_bitmap;
  179. struct starpu_bitmap * starpu_bitmap_create(void);
  180. void starpu_bitmap_destroy(struct starpu_bitmap *);
  181. void starpu_bitmap_set(struct starpu_bitmap *, int);
  182. void starpu_bitmap_unset(struct starpu_bitmap *, int);
  183. void starpu_bitmap_unset_all(struct starpu_bitmap *);
  184. int starpu_bitmap_get(struct starpu_bitmap *, int);
  185. /* basicaly compute starpu_bitmap_unset_all(a) ; a = b & c; */
  186. void starpu_bitmap_unset_and(struct starpu_bitmap * a, struct starpu_bitmap * b, struct starpu_bitmap * c);
  187. /* this is basically compute a |= b;*/
  188. void starpu_bitmap_or(struct starpu_bitmap * a,
  189. struct starpu_bitmap * b);
  190. //return 1 iff e set in b1 AND e set in b2
  191. int starpu_bitmap_and_get(struct starpu_bitmap * b1,
  192. struct starpu_bitmap * b2,
  193. int e);
  194. int starpu_bitmap_cardinal(struct starpu_bitmap *);
  195. //return the index of first bit, -1 if none
  196. int starpu_bitmap_first(struct starpu_bitmap *);
  197. int starpu_bitmap_last(struct starpu_bitmap *);
  198. //return the index of bit right after e, -1 if none
  199. int starpu_bitmap_next(struct starpu_bitmap *, int e);
  200. #endif