@@ -63,7 +63,7 @@ libgomp_la_SOURCES = alloc.c barrier.c critical.c env.c error.c iter.c \
task.c team.c work.c lock.c mutex.c proc.c sem.c bar.c ptrlock.c \
time.c fortran.c affinity.c target.c splay-tree.c libgomp-plugin.c \
oacc-parallel.c oacc-host.c oacc-init.c oacc-mem.c oacc-async.c \
- oacc-plugin.c oacc-cuda.c
+ oacc-plugin.c oacc-cuda.c priority_queue.c
include $(top_srcdir)/plugin/Makefrag.am
@@ -168,7 +168,7 @@ am_libgomp_la_OBJECTS = alloc.lo barrier.lo critical.lo env.lo \
fortran.lo affinity.lo target.lo splay-tree.lo \
libgomp-plugin.lo oacc-parallel.lo oacc-host.lo oacc-init.lo \
oacc-mem.lo oacc-async.lo oacc-plugin.lo oacc-cuda.lo \
- $(am__objects_1)
+ priority_queue.lo $(am__objects_1)
libgomp_la_OBJECTS = $(am_libgomp_la_OBJECTS)
DEFAULT_INCLUDES = -I.@am__isrc@
depcomp = $(SHELL) $(top_srcdir)/../depcomp
@@ -415,7 +415,7 @@ libgomp_la_SOURCES = alloc.c barrier.c critical.c env.c error.c iter.c \
bar.c ptrlock.c time.c fortran.c affinity.c target.c \
splay-tree.c libgomp-plugin.c oacc-parallel.c oacc-host.c \
oacc-init.c oacc-mem.c oacc-async.c oacc-plugin.c oacc-cuda.c \
- $(am__append_2)
+ priority_queue.c $(am__append_2)
# Nvidia PTX OpenACC plugin.
@PLUGIN_NVPTX_TRUE@libgomp_plugin_nvptx_version_info = -version-info $(libtool_VERSION)
@@ -589,6 +589,7 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/oacc-plugin.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ordered.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/parallel.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/priority_queue.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/proc.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ptrlock.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/sections.Plo@am__quote@
@@ -50,6 +50,22 @@
#include <stdlib.h>
#include <stdarg.h>
+/* Needed for memset in priority_queue.c. */
+#if _LIBGOMP_CHECKING_
+# ifdef STRING_WITH_STRINGS
+# include <string.h>
+# include <strings.h>
+# else
+# ifdef HAVE_STRING_H
+# include <string.h>
+# else
+# ifdef HAVE_STRINGS_H
+# include <strings.h>
+# endif
+# endif
+# endif
+#endif
+
#ifdef HAVE_ATTRIBUTE_VISIBILITY
# pragma GCC visibility push(hidden)
#endif
@@ -65,6 +81,44 @@ enum memmodel
MEMMODEL_SEQ_CST = 5
};
+/* alloc.c */
+
+extern void *gomp_malloc (size_t) __attribute__((malloc));
+extern void *gomp_malloc_cleared (size_t) __attribute__((malloc));
+extern void *gomp_realloc (void *, size_t);
+
+/* Avoid conflicting prototypes of alloca() in system headers by using
+ GCC's builtin alloca(). */
+#define gomp_alloca(x) __builtin_alloca(x)
+
+/* error.c */
+
+extern void gomp_vdebug (int, const char *, va_list);
+extern void gomp_debug (int, const char *, ...)
+ __attribute__ ((format (printf, 2, 3)));
+#define gomp_vdebug(KIND, FMT, VALIST) \
+ do { \
+ if (__builtin_expect (gomp_debug_var, 0)) \
+ (gomp_vdebug) ((KIND), (FMT), (VALIST)); \
+ } while (0)
+#define gomp_debug(KIND, ...) \
+ do { \
+ if (__builtin_expect (gomp_debug_var, 0)) \
+ (gomp_debug) ((KIND), __VA_ARGS__); \
+ } while (0)
+extern void gomp_verror (const char *, va_list);
+extern void gomp_error (const char *, ...)
+ __attribute__ ((format (printf, 1, 2)));
+extern void gomp_vfatal (const char *, va_list)
+ __attribute__ ((noreturn));
+extern void gomp_fatal (const char *, ...)
+ __attribute__ ((noreturn, format (printf, 1, 2)));
+
+struct gomp_task;
+struct gomp_taskgroup;
+struct htab;
+
+#include "priority_queue.h"
#include "sem.h"
#include "mutex.h"
#include "bar.h"
@@ -298,6 +352,7 @@ extern gomp_mutex_t gomp_managed_threads_lock;
#endif
extern unsigned long gomp_max_active_levels_var;
extern bool gomp_cancel_var;
+extern int gomp_max_task_priority_var;
extern unsigned long long gomp_spin_count_var, gomp_throttled_spin_count_var;
extern unsigned long gomp_available_cpus, gomp_managed_threads;
extern unsigned long *gomp_nthreads_var_list, gomp_nthreads_var_list_len;
@@ -321,10 +376,6 @@ enum gomp_task_kind
GOMP_TASK_TIED
};
-struct gomp_task;
-struct gomp_taskgroup;
-struct htab;
-
struct gomp_task_depend_entry
{
/* Address of dependency. */
@@ -352,8 +403,8 @@ struct gomp_taskwait
{
bool in_taskwait;
bool in_depend_wait;
+ /* Number of tasks we are waiting for. */
size_t n_depend;
- struct gomp_task *last_parent_depends_on;
gomp_sem_t taskwait_sem;
};
@@ -361,26 +412,10 @@ struct gomp_taskwait
struct gomp_task
{
- /* Parent circular list. See children description below. */
+ /* Parent of this task. */
struct gomp_task *parent;
- /* Circular list representing the children of this task.
-
- In this list we first have parent_depends_on ready to run tasks,
- then !parent_depends_on ready to run tasks, and finally already
- running tasks. */
- struct gomp_task *children;
- struct gomp_task *next_child;
- struct gomp_task *prev_child;
- /* Circular task_queue in `struct gomp_team'.
-
- GOMP_TASK_WAITING tasks come before GOMP_TASK_TIED tasks. */
- struct gomp_task *next_queue;
- struct gomp_task *prev_queue;
- /* Circular queue in gomp_taskgroup->children.
-
- GOMP_TASK_WAITING tasks come before GOMP_TASK_TIED tasks. */
- struct gomp_task *next_taskgroup;
- struct gomp_task *prev_taskgroup;
+ /* Children of this task. */
+ struct priority_queue children_queue;
/* Taskgroup this task belongs in. */
struct gomp_taskgroup *taskgroup;
/* Tasks that depend on this task. */
@@ -389,8 +424,19 @@ struct gomp_task
struct gomp_taskwait *taskwait;
/* Number of items in DEPEND. */
size_t depend_count;
- /* Number of tasks in the DEPENDERS field above. */
+ /* Number of tasks this task depends on. Once this counter reaches
+ 0, we have no unsatisfied dependencies, and this task can be put
+ into the various queues to be scheduled. */
size_t num_dependees;
+
+ /* Priority of this task. */
+ int priority;
+ /* The priority node for this task in each of the different queues.
+ We put this here to avoid allocating space for each priority
+ node. Then we play offsetof() games to convert between pnode[]
+ entries and the gomp_task in which they reside. */
+ struct priority_node pnode[3];
+
struct gomp_task_icv icv;
void (*fn) (void *);
void *fn_data;
@@ -410,12 +456,8 @@ struct gomp_task
struct gomp_taskgroup
{
struct gomp_taskgroup *prev;
- /* Circular list of tasks that belong in this taskgroup.
-
- Tasks are chained by next/prev_taskgroup within gomp_task, and
- are sorted by GOMP_TASK_WAITING tasks, and then GOMP_TASK_TIED
- tasks. */
- struct gomp_task *children;
+ /* Queue of tasks that belong in this taskgroup. */
+ struct priority_queue taskgroup_queue;
bool in_taskgroup_wait;
bool cancelled;
gomp_sem_t taskgroup_sem;
@@ -495,9 +537,8 @@ struct gomp_team
struct gomp_work_share work_shares[8];
gomp_mutex_t task_lock;
- /* Scheduled tasks. Chain fields are next/prev_queue within a
- gomp_task. */
- struct gomp_task *task_queue;
+ /* Scheduled tasks. */
+ struct priority_queue task_queue;
/* Number of all GOMP_TASK_{WAITING,TIED} tasks in the team. */
unsigned int task_count;
/* Number of GOMP_TASK_WAITING tasks currently waiting to be scheduled. */
@@ -627,39 +668,6 @@ extern bool gomp_affinity_init_level (int, unsigned long, bool);
extern void gomp_affinity_print_place (void *);
extern void gomp_get_place_proc_ids_8 (int, int64_t *);
-/* alloc.c */
-
-extern void *gomp_malloc (size_t) __attribute__((malloc));
-extern void *gomp_malloc_cleared (size_t) __attribute__((malloc));
-extern void *gomp_realloc (void *, size_t);
-
-/* Avoid conflicting prototypes of alloca() in system headers by using
- GCC's builtin alloca(). */
-#define gomp_alloca(x) __builtin_alloca(x)
-
-/* error.c */
-
-extern void gomp_vdebug (int, const char *, va_list);
-extern void gomp_debug (int, const char *, ...)
- __attribute__ ((format (printf, 2, 3)));
-#define gomp_vdebug(KIND, FMT, VALIST) \
- do { \
- if (__builtin_expect (gomp_debug_var, 0)) \
- (gomp_vdebug) ((KIND), (FMT), (VALIST)); \
- } while (0)
-#define gomp_debug(KIND, ...) \
- do { \
- if (__builtin_expect (gomp_debug_var, 0)) \
- (gomp_debug) ((KIND), __VA_ARGS__); \
- } while (0)
-extern void gomp_verror (const char *, va_list);
-extern void gomp_error (const char *, ...)
- __attribute__ ((format (printf, 1, 2)));
-extern void gomp_vfatal (const char *, va_list)
- __attribute__ ((noreturn));
-extern void gomp_fatal (const char *, ...)
- __attribute__ ((noreturn, format (printf, 1, 2)));
-
/* iter.c */
extern int gomp_iter_static_next (long *, long *);
@@ -741,6 +749,7 @@ extern void gomp_init_targets_once (void);
extern int gomp_get_num_devices (void);
extern void gomp_target_task_fn (void *);
+/* Splay tree definitions. */
typedef struct splay_tree_node_s *splay_tree_node;
typedef struct splay_tree_s *splay_tree;
typedef struct splay_tree_key_s *splay_tree_key;
@@ -800,6 +809,21 @@ struct splay_tree_key_s {
uintptr_t async_refcount;
};
+/* The comparison function. */
+
+static inline int
+splay_compare (splay_tree_key x, splay_tree_key y)
+{
+ if (x->host_start == x->host_end
+ && y->host_start == y->host_end)
+ return 0;
+ if (x->host_end <= y->host_start)
+ return -1;
+ if (x->host_start >= y->host_end)
+ return 1;
+ return 0;
+}
+
#include "splay-tree.h"
typedef struct acc_dispatch_t
@@ -1016,4 +1040,34 @@ extern int gomp_test_nest_lock_25 (omp_nest_lock_25_t *) __GOMP_NOTHROW;
# define ialias_call(fn) fn
#endif
+/* Helper function for priority_node_to_task() and
+ task_to_priority_node().
+
+ Return the offset from a task to its priority_node entry. The
+ priority_node entry is has a type of TYPE. */
+
+static inline size_t
+priority_queue_offset (enum priority_queue_type type)
+{
+ return offsetof (struct gomp_task, pnode[(int) type]);
+}
+
+/* Return the task associated with a priority NODE of type TYPE. */
+
+static inline struct gomp_task *
+priority_node_to_task (enum priority_queue_type type,
+ struct priority_node *node)
+{
+ return (struct gomp_task *) ((char *) node - priority_queue_offset (type));
+}
+
+/* Return the priority node of type TYPE for a given TASK. */
+
+static inline struct priority_node *
+task_to_priority_node (enum priority_queue_type type,
+ struct gomp_task *task)
+{
+ return (struct priority_node *) ((char *) task
+ + priority_queue_offset (type));
+}
#endif /* LIBGOMP_H */
@@ -31,7 +31,6 @@
#include "libgomp.h"
#include "gomp-constants.h"
#include "oacc-int.h"
-#include "splay-tree.h"
#include <stdint.h>
#include <assert.h>
new file mode 100644
@@ -0,0 +1,300 @@
+/* Copyright (C) 2015 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <aldyh@redhat.com>.
+
+ This file is part of the GNU Offloading and Multi Processing Library
+ (libgomp).
+
+ Libgomp is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3, or (at your option)
+ any later version.
+
+ Libgomp 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.
+
+ Under Section 7 of GPL version 3, you are granted additional
+ permissions described in the GCC Runtime Library Exception, version
+ 3.1, as published by the Free Software Foundation.
+
+ You should have received a copy of the GNU General Public License and
+ a copy of the GCC Runtime Library Exception along with this program;
+ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+ <http://www.gnu.org/licenses/>. */
+
+/* Priority queue implementation of GOMP tasks. */
+
+#include "libgomp.h"
+
+#if _LIBGOMP_CHECKING_
+#include <stdio.h>
+
+/* Sanity check to verify whether a TASK is in LIST. Return TRUE if
+ found, FALSE otherwise.
+
+ TYPE is the type of priority queue this task resides in. */
+
+static inline bool
+priority_queue_task_in_list_p (enum priority_queue_type type,
+ struct priority_list *list,
+ struct gomp_task *task)
+{
+ struct priority_node *p = list->tasks;
+ do
+ {
+ if (priority_node_to_task (type, p) == task)
+ return true;
+ p = p->next;
+ }
+ while (p != list->tasks);
+ return false;
+}
+
+/* Tree version of priority_queue_task_in_list_p. */
+
+static inline bool
+priority_queue_task_in_tree_p (enum priority_queue_type type,
+ struct priority_queue *head,
+ struct gomp_task *task)
+{
+ struct priority_list *list
+ = priority_queue_lookup_priority (head, task->priority);
+ if (!list)
+ return false;
+ return priority_queue_task_in_list_p (type, list, task);
+}
+
+/* Generic version of priority_queue_task_in_list_p that works for
+ trees or lists. */
+
+bool
+priority_queue_task_in_queue_p (enum priority_queue_type type,
+ struct priority_queue *head,
+ struct gomp_task *task)
+{
+ if (priority_queue_empty_p (head, MEMMODEL_RELAXED))
+ return false;
+ if (priority_queue_multi_p (head))
+ return priority_queue_task_in_tree_p (type, head, task);
+ else
+ return priority_queue_task_in_list_p (type, &head->l, task);
+}
+
+/* Sanity check LIST to make sure the tasks therein are in the right
+ order. LIST is a priority list of type TYPE.
+
+ The expected order is that GOMP_TASK_WAITING tasks come before
+ GOMP_TASK_TIED ones.
+
+ If CHECK_DEPS is TRUE, we also check that parent_depends_on WAITING
+ tasks come before !parent_depends_on WAITING tasks. This is only
+ applicable to the children queue, and the caller is expected to
+ ensure that we are verifying the children queue. */
+
+static void
+priority_list_verify (enum priority_queue_type type,
+ struct priority_list *list, bool check_deps)
+{
+ bool seen_tied = false;
+ bool seen_plain_waiting = false;
+ struct priority_node *p = list->tasks;
+ while (1)
+ {
+ struct gomp_task *t = priority_node_to_task (type, p);
+ if (seen_tied && t->kind == GOMP_TASK_WAITING)
+ gomp_fatal ("priority_queue_verify: WAITING task after TIED");
+ if (t->kind == GOMP_TASK_TIED)
+ seen_tied = true;
+ else if (check_deps && t->kind == GOMP_TASK_WAITING)
+ {
+ if (t->parent_depends_on)
+ {
+ if (seen_plain_waiting)
+ gomp_fatal ("priority_queue_verify: "
+ "parent_depends_on after !parent_depends_on");
+ }
+ else
+ seen_plain_waiting = true;
+ }
+ p = p->next;
+ if (p == list->tasks)
+ break;
+ }
+}
+
+/* Callback type for priority_tree_verify_callback. */
+struct cbtype
+{
+ enum priority_queue_type type;
+ bool check_deps;
+};
+
+/* Verify every task in NODE.
+
+ Callback for splay_tree_foreach. */
+
+static void
+priority_tree_verify_callback (prio_splay_tree_key key, void *data)
+{
+ struct cbtype *cb = (struct cbtype *) data;
+ priority_list_verify (cb->type, &key->l, cb->check_deps);
+}
+
+/* Generic version of priority_list_verify.
+
+ Sanity check HEAD to make sure the tasks therein are in the right
+ order. The priority_queue holds tasks of type TYPE.
+
+ If CHECK_DEPS is TRUE, we also check that parent_depends_on WAITING
+ tasks come before !parent_depends_on WAITING tasks. This is only
+ applicable to the children queue, and the caller is expected to
+ ensure that we are verifying the children queue. */
+
+void
+priority_queue_verify (enum priority_queue_type type,
+ struct priority_queue *head, bool check_deps)
+{
+ if (priority_queue_empty_p (head, MEMMODEL_RELAXED))
+ return;
+ if (priority_queue_multi_p (head))
+ {
+ struct cbtype cb = { type, check_deps };
+ prio_splay_tree_foreach (&head->t,
+ priority_tree_verify_callback, &cb);
+ }
+ else
+ priority_list_verify (type, &head->l, check_deps);
+}
+#endif /* _LIBGOMP_CHECKING_ */
+
+/* Remove NODE from priority queue HEAD, wherever it may be inside the
+ tree. HEAD contains tasks of type TYPE. */
+
+void
+priority_tree_remove (enum priority_queue_type type,
+ struct priority_queue *head,
+ struct priority_node *node)
+{
+ /* ?? The only reason this function is not inlined is because we
+ need to find the priority within gomp_task (which has not been
+ completely defined in the header file). If the lack of inlining
+ is a concern, we could pass the priority number as a
+ parameter, or we could move this to libgomp.h. */
+ int priority = priority_node_to_task (type, node)->priority;
+
+ /* ?? We could avoid this lookup by keeping a pointer to the key in
+ the priority_node. */
+ struct priority_list *list
+ = priority_queue_lookup_priority (head, priority);
+#if _LIBGOMP_CHECKING_
+ if (!list)
+ gomp_fatal ("Unable to find priority %d", priority);
+#endif
+ /* If NODE was the last in its priority, clean up the priority. */
+ if (priority_list_remove (list, node, MEMMODEL_RELAXED))
+ {
+ prio_splay_tree_remove (&head->t, (prio_splay_tree_key) list);
+ list->tasks = NULL;
+#if _LIBGOMP_CHECKING_
+ memset (list, 0xaf, sizeof (*list));
+#endif
+ free (list);
+ }
+}
+
+/* Return the highest priority WAITING task in a splay tree NODE. If
+ there are no WAITING tasks available, return NULL.
+
+ NODE is a priority list containing tasks of type TYPE.
+
+ The right most node in a tree contains the highest priority.
+ Recurse down to find such a node. If the task at that max node is
+ not WAITING, bubble back up and look at the remaining tasks
+ in-order. */
+
+static struct gomp_task *
+priority_tree_next_task_1 (enum priority_queue_type type,
+ prio_splay_tree_node node)
+{
+ again:
+ if (!node)
+ return NULL;
+ struct gomp_task *ret = priority_tree_next_task_1 (type, node->right);
+ if (ret)
+ return ret;
+ ret = priority_node_to_task (type, node->key.l.tasks);
+ if (ret->kind == GOMP_TASK_WAITING)
+ return ret;
+ node = node->left;
+ goto again;
+}
+
+/* Return the highest priority WAITING task from within Q1 and Q2,
+ while giving preference to tasks from Q1. Q1 is a queue containing
+ items of type TYPE1. Q2 is a queue containing items of type TYPE2.
+
+ Since we are mostly interested in Q1, if there are no WAITING tasks
+ in Q1, we don't bother checking Q2, and just return NULL.
+
+ As a special case, Q2 can be NULL, in which case, we just choose
+ the highest priority WAITING task in Q1. This is an optimization
+ to speed up looking through only one queue.
+
+ If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to
+ TRUE, otherwise it is set to FALSE. */
+
+struct gomp_task *
+priority_tree_next_task (enum priority_queue_type type1,
+ struct priority_queue *q1,
+ enum priority_queue_type type2,
+ struct priority_queue *q2,
+ bool *q1_chosen_p)
+{
+ struct gomp_task *t1 = priority_tree_next_task_1 (type1, q1->t.root);
+ if (!t1
+ /* Special optimization when only searching through one queue. */
+ || !q2)
+ {
+ *q1_chosen_p = true;
+ return t1;
+ }
+ struct gomp_task *t2 = priority_tree_next_task_1 (type2, q2->t.root);
+ if (!t2 || t1->priority > t2->priority)
+ {
+ *q1_chosen_p = true;
+ return t1;
+ }
+ if (t2->priority > t1->priority)
+ {
+ *q1_chosen_p = false;
+ return t2;
+ }
+ /* If we get here, the priorities are the same, so we must look at
+ parent_depends_on to make our decision. */
+#if _LIBGOMP_CHECKING_
+ if (t1 != t2)
+ gomp_fatal ("priority_tree_next_task: t1 != t2");
+#endif
+ if (t2->parent_depends_on && !t1->parent_depends_on)
+ {
+ *q1_chosen_p = false;
+ return t2;
+ }
+ *q1_chosen_p = true;
+ return t1;
+}
+
+/* Priority splay trees comparison function. */
+static inline int
+prio_splay_compare (prio_splay_tree_key x, prio_splay_tree_key y)
+{
+ if (x->l.priority == y->l.priority)
+ return 0;
+ return x->l.priority < y->l.priority ? -1 : 1;
+}
+
+/* Define another splay tree instantiation, for priority_list's. */
+#define splay_tree_prefix prio
+#define splay_tree_c
+#include "splay-tree.h"
new file mode 100644
@@ -0,0 +1,485 @@
+/* Copyright (C) 2015 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <aldyh@redhat.com>.
+
+ This file is part of the GNU Offloading and Multi Processing Library
+ (libgomp).
+
+ Libgomp is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3, or (at your option)
+ any later version.
+
+ Libgomp 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.
+
+ Under Section 7 of GPL version 3, you are granted additional
+ permissions described in the GCC Runtime Library Exception, version
+ 3.1, as published by the Free Software Foundation.
+
+ You should have received a copy of the GNU General Public License and
+ a copy of the GCC Runtime Library Exception along with this program;
+ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+ <http://www.gnu.org/licenses/>. */
+
+/* Header file for a priority queue of GOMP tasks. */
+
+/* ?? Perhaps all the priority_tree_* functions are complex and rare
+ enough to go out-of-line and be moved to priority_queue.c. ?? */
+
+#ifndef _PRIORITY_QUEUE_H_
+#define _PRIORITY_QUEUE_H_
+
+/* One task. */
+
+struct priority_node
+{
+ /* Next and previous chains in a circular doubly linked list for
+ tasks within this task's priority. */
+ struct priority_node *next, *prev;
+};
+
+/* All tasks within the same priority. */
+
+struct priority_list
+{
+ /* Priority of the tasks in this set. */
+ int priority;
+
+ /* Tasks. */
+ struct priority_node *tasks;
+
+ /* This points to the last of the higher priority WAITING tasks.
+ Remember that for the children queue, we have:
+
+ parent_depends_on WAITING tasks.
+ !parent_depends_on WAITING tasks.
+ TIED tasks.
+
+ This is a pointer to the last of the parent_depends_on WAITING
+ tasks which are essentially, higher priority items within their
+ priority. */
+ struct priority_node *last_parent_depends_on;
+};
+
+/* Another splay tree instantiation, for priority_list's. */
+typedef struct prio_splay_tree_node_s *prio_splay_tree_node;
+typedef struct prio_splay_tree_s *prio_splay_tree;
+typedef struct prio_splay_tree_key_s *prio_splay_tree_key;
+struct prio_splay_tree_key_s {
+ /* This structure must only containing a priority_list, as we cast
+ prio_splay_tree_key to priority_list throughout. */
+ struct priority_list l;
+};
+#define splay_tree_prefix prio
+#include "splay-tree.h"
+
+/* The entry point into a priority queue of tasks.
+
+ There are two alternate implementations with which to store tasks:
+ as a balanced tree of sorts, or as a simple list of tasks. If
+ there are only priority-0 items (ROOT is NULL), we use the simple
+ list, otherwise (ROOT is non-NULL) we use the tree. */
+
+struct priority_queue
+{
+ /* If t.root != NULL, this is a splay tree of priority_lists to hold
+ all tasks. This is only used if multiple priorities are in play,
+ otherwise we use the priority_list `l' below to hold all
+ (priority-0) tasks. */
+ struct prio_splay_tree_s t;
+
+ /* If T above is NULL, only priority-0 items exist, so keep them
+ in a simple list. */
+ struct priority_list l;
+};
+
+enum priority_insert_type {
+ /* Insert at the beginning of a priority list. */
+ PRIORITY_INSERT_BEGIN,
+ /* Insert at the end of a priority list. */
+ PRIORITY_INSERT_END
+};
+
+/* Used to determine in which queue a given priority node belongs in.
+ See pnode field of gomp_task. */
+
+enum priority_queue_type
+{
+ PQ_TEAM, /* Node belongs in gomp_team's task_queue. */
+ PQ_CHILDREN, /* Node belongs in parent's children_queue. */
+ PQ_TASKGROUP, /* Node belongs in taskgroup->taskgroup_queue. */
+ PQ_IGNORED = 999
+};
+
+/* Priority queue implementation prototypes. */
+
+extern bool priority_queue_task_in_queue_p (enum priority_queue_type,
+ struct priority_queue *,
+ struct gomp_task *);
+extern void priority_queue_dump (enum priority_queue_type,
+ struct priority_queue *);
+extern void priority_queue_verify (enum priority_queue_type,
+ struct priority_queue *, bool);
+extern void priority_tree_remove (enum priority_queue_type,
+ struct priority_queue *,
+ struct priority_node *);
+extern struct gomp_task *priority_tree_next_task (enum priority_queue_type,
+ struct priority_queue *,
+ enum priority_queue_type,
+ struct priority_queue *,
+ bool *);
+
+/* Return TRUE if there is more than one priority in HEAD. This is
+ used throughout to to choose between the fast path (priority 0 only
+ items) and a world with multiple priorities. */
+
+static inline bool
+priority_queue_multi_p (struct priority_queue *head)
+{
+ return __builtin_expect (head->t.root != NULL, 0);
+}
+
+/* Initialize a priority queue. */
+
+static inline void
+priority_queue_init (struct priority_queue *head)
+{
+ head->t.root = NULL;
+ /* To save a few microseconds, we don't initialize head->l.priority
+ to 0 here. It is implied that priority will be 0 if head->t.root
+ == NULL.
+
+ priority_tree_insert() will fix this when we encounter multiple
+ priorities. */
+ head->l.tasks = NULL;
+ head->l.last_parent_depends_on = NULL;
+}
+
+static inline void
+priority_queue_free (struct priority_queue *head)
+{
+ /* There's nothing to do, as tasks were freed as they were removed
+ in priority_queue_remove. */
+}
+
+/* Forward declarations. */
+static inline size_t priority_queue_offset (enum priority_queue_type);
+static inline struct gomp_task *priority_node_to_task
+ (enum priority_queue_type,
+ struct priority_node *);
+static inline struct priority_node *task_to_priority_node
+ (enum priority_queue_type,
+ struct gomp_task *);
+
+/* Return TRUE if priority queue HEAD is empty.
+
+ MODEL IS MEMMODEL_ACQUIRE if we should use an acquire atomic to
+ read from the root of the queue, otherwise MEMMODEL_RELAXED if we
+ should use a plain load. */
+
+static inline _Bool
+priority_queue_empty_p (struct priority_queue *head, enum memmodel model)
+{
+ /* Note: The acquire barriers on the loads here synchronize with
+ the write of a NULL in gomp_task_run_post_remove_parent. It is
+ not necessary that we synchronize with other non-NULL writes at
+ this point, but we must ensure that all writes to memory by a
+ child thread task work function are seen before we exit from
+ GOMP_taskwait. */
+ if (priority_queue_multi_p (head))
+ {
+ if (model == MEMMODEL_ACQUIRE)
+ return __atomic_load_n (&head->t.root, MEMMODEL_ACQUIRE) == NULL;
+ return head->t.root == NULL;
+ }
+ if (model == MEMMODEL_ACQUIRE)
+ return __atomic_load_n (&head->l.tasks, MEMMODEL_ACQUIRE) == NULL;
+ return head->l.tasks == NULL;
+}
+
+/* Look for a given PRIORITY in HEAD. Return it if found, otherwise
+ return NULL. This only applies to the tree variant in HEAD. There
+ is no point in searching for priorities in HEAD->L. */
+
+static inline struct priority_list *
+priority_queue_lookup_priority (struct priority_queue *head, int priority)
+{
+ if (head->t.root == NULL)
+ return NULL;
+ struct prio_splay_tree_key_s k;
+ k.l.priority = priority;
+ return (struct priority_list *)
+ prio_splay_tree_lookup (&head->t, &k);
+}
+
+/* Insert task in DATA, with PRIORITY, in the priority list in LIST.
+ LIST contains items of type TYPE.
+
+ If POS is PRIORITY_INSERT_BEGIN, the new task is inserted at the
+ top of its respective priority. If POS is PRIORITY_INSERT_END, the
+ task is inserted at the end of its priority.
+
+ If ADJUST_PARENT_DEPENDS_ON is TRUE, LIST is a children queue, and
+ we must keep track of higher and lower priority WAITING tasks by
+ keeping the queue's last_parent_depends_on field accurate. This
+ only applies to the children queue, and the caller must ensure LIST
+ is a children queue in this case.
+
+ If ADJUST_PARENT_DEPENDS_ON is TRUE, TASK_IS_PARENT_DEPENDS_ON is
+ set to the task's parent_depends_on field. If
+ ADJUST_PARENT_DEPENDS_ON is FALSE, this field is irrelevant.
+
+ Return the new priority_node. */
+
+static inline void
+priority_list_insert (enum priority_queue_type type,
+ struct priority_list *list,
+ struct gomp_task *task,
+ int priority,
+ enum priority_insert_type pos,
+ bool adjust_parent_depends_on,
+ bool task_is_parent_depends_on)
+{
+ struct priority_node *node = task_to_priority_node (type, task);
+ if (list->tasks)
+ {
+ /* If we are keeping track of higher/lower priority items,
+ but this is a lower priority WAITING task
+ (parent_depends_on != NULL), put it after all ready to
+ run tasks. See the comment in
+ priority_queue_upgrade_task for a visual on how tasks
+ should be organized. */
+ if (adjust_parent_depends_on
+ && pos == PRIORITY_INSERT_BEGIN
+ && list->last_parent_depends_on
+ && !task_is_parent_depends_on)
+ {
+ struct priority_node *last_parent_depends_on
+ = list->last_parent_depends_on;
+ node->next = last_parent_depends_on->next;
+ node->prev = last_parent_depends_on;
+ }
+ /* Otherwise, put it at the top/bottom of the queue. */
+ else
+ {
+ node->next = list->tasks;
+ node->prev = list->tasks->prev;
+ if (pos == PRIORITY_INSERT_BEGIN)
+ list->tasks = node;
+ }
+ node->next->prev = node;
+ node->prev->next = node;
+ }
+ else
+ {
+ node->next = node;
+ node->prev = node;
+ list->tasks = node;
+ }
+ if (adjust_parent_depends_on
+ && list->last_parent_depends_on == NULL
+ && task_is_parent_depends_on)
+ list->last_parent_depends_on = node;
+}
+
+/* Tree version of priority_list_insert. */
+
+static inline void
+priority_tree_insert (enum priority_queue_type type,
+ struct priority_queue *head,
+ struct gomp_task *task,
+ int priority,
+ enum priority_insert_type pos,
+ bool adjust_parent_depends_on,
+ bool task_is_parent_depends_on)
+{
+ if (__builtin_expect (head->t.root == NULL, 0))
+ {
+ /* The first time around, transfer any priority 0 items to the
+ tree. */
+ if (head->l.tasks != NULL)
+ {
+ prio_splay_tree_node k = gomp_malloc (sizeof (*k));
+ k->left = NULL;
+ k->right = NULL;
+ k->key.l.priority = 0;
+ k->key.l.tasks = head->l.tasks;
+ k->key.l.last_parent_depends_on = head->l.last_parent_depends_on;
+ prio_splay_tree_insert (&head->t, k);
+ head->l.tasks = NULL;
+ }
+ }
+ struct priority_list *list
+ = priority_queue_lookup_priority (head, priority);
+ if (!list)
+ {
+ prio_splay_tree_node k = gomp_malloc (sizeof (*k));
+ k->left = NULL;
+ k->right = NULL;
+ k->key.l.priority = priority;
+ k->key.l.tasks = NULL;
+ k->key.l.last_parent_depends_on = NULL;
+ prio_splay_tree_insert (&head->t, k);
+ list = &k->key.l;
+ }
+ priority_list_insert (type, list, task, priority, pos,
+ adjust_parent_depends_on,
+ task_is_parent_depends_on);
+}
+
+/* Generic version of priority_*_insert. */
+
+static inline void
+priority_queue_insert (enum priority_queue_type type,
+ struct priority_queue *head,
+ struct gomp_task *task,
+ int priority,
+ enum priority_insert_type pos,
+ bool adjust_parent_depends_on,
+ bool task_is_parent_depends_on)
+{
+#if _LIBGOMP_CHECKING_
+ if (priority_queue_task_in_queue_p (type, head, task))
+ gomp_fatal ("Attempt to insert existing task %p", task);
+#endif
+ if (priority_queue_multi_p (head) || __builtin_expect (priority > 0, 0))
+ priority_tree_insert (type, head, task, priority, pos,
+ adjust_parent_depends_on,
+ task_is_parent_depends_on);
+ else
+ priority_list_insert (type, &head->l, task, priority, pos,
+ adjust_parent_depends_on,
+ task_is_parent_depends_on);
+}
+
+/* If multiple priorities are in play, return the highest priority
+ task from within Q1 and Q2, while giving preference to tasks from
+ Q1. If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to
+ TRUE, otherwise it is set to FALSE.
+
+ If multiple priorities are not in play (only 0 priorities are
+ available), the next task is chosen exclusively from Q1.
+
+ As a special case, Q2 can be NULL, in which case, we just choose
+ the highest priority WAITING task in Q1. This is an optimization
+ to speed up looking through only one queue.
+
+ We assume Q1 has at least one item. */
+
+static inline struct gomp_task *
+priority_queue_next_task (enum priority_queue_type t1,
+ struct priority_queue *q1,
+ enum priority_queue_type t2,
+ struct priority_queue *q2,
+ bool *q1_chosen_p)
+{
+#if _LIBGOMP_CHECKING_
+ if (priority_queue_empty_p (q1, MEMMODEL_RELAXED))
+ gomp_fatal ("priority_queue_next_task: Q1 is empty");
+#endif
+ if (priority_queue_multi_p (q1))
+ {
+ struct gomp_task *t
+ = priority_tree_next_task (t1, q1, t2, q2, q1_chosen_p);
+ /* If T is NULL, there are no WAITING tasks in Q1. In which
+ case, return any old (non-waiting) task which will cause the
+ caller to do the right thing when checking T->KIND ==
+ GOMP_TASK_WAITING. */
+ if (!t)
+ {
+#if _LIBGOMP_CHECKING_
+ if (*q1_chosen_p == false)
+ gomp_fatal ("priority_queue_next_task inconsistency");
+#endif
+ return priority_node_to_task (t1, q1->t.root->key.l.tasks);
+ }
+ return t;
+ }
+ else
+ {
+ *q1_chosen_p = true;
+ return priority_node_to_task (t1, q1->l.tasks);
+ }
+}
+
+/* Remove NODE from LIST.
+
+ If we are removing the one and only item in the list, and MODEL is
+ MEMMODEL_RELEASE, use an atomic release to clear the list.
+
+ If the list becomes empty after the remove, return TRUE. */
+
+static inline bool
+priority_list_remove (struct priority_list *list,
+ struct priority_node *node,
+ enum memmodel model)
+{
+ bool empty = false;
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+ if (list->tasks == node)
+ {
+ if (node->next != node)
+ list->tasks = node->next;
+ else
+ {
+ /* We access task->children in GOMP_taskwait outside of
+ the task lock mutex region, so need a release barrier
+ here to ensure memory written by child_task->fn above
+ is flushed before the NULL is written. */
+ if (model == MEMMODEL_RELEASE)
+ __atomic_store_n (&list->tasks, NULL, MEMMODEL_RELEASE);
+ else
+ list->tasks = NULL;
+ empty = true;
+ goto remove_out;
+ }
+ }
+remove_out:
+#if _LIBGOMP_CHECKING_
+ memset (node, 0xaf, sizeof (*node));
+#endif
+ return empty;
+}
+
+/* This is the generic version of priority_list_remove.
+
+ Remove NODE from priority queue HEAD. HEAD contains tasks of type TYPE.
+
+ If we are removing the one and only item in the priority queue and
+ MODEL is MEMMODEL_RELEASE, use an atomic release to clear the queue.
+
+ If the queue becomes empty after the remove, return TRUE. */
+
+static inline bool
+priority_queue_remove (enum priority_queue_type type,
+ struct priority_queue *head,
+ struct gomp_task *task,
+ enum memmodel model)
+{
+#if _LIBGOMP_CHECKING_
+ if (!priority_queue_task_in_queue_p (type, head, task))
+ gomp_fatal ("Attempt to remove missing task %p", task);
+#endif
+ if (priority_queue_multi_p (head))
+ {
+ priority_tree_remove (type, head, task_to_priority_node (type, task));
+ if (head->t.root == NULL)
+ {
+ if (model == MEMMODEL_RELEASE)
+ /* Errr, we store NULL twice, the alternative would be to
+ use an atomic release directly in the splay tree
+ routines. Worth it? */
+ __atomic_store_n (&head->t.root, NULL, MEMMODEL_RELEASE);
+ return true;
+ }
+ return false;
+ }
+ else
+ return priority_list_remove (&head->l,
+ task_to_priority_node (type, task), model);
+}
+
+#endif /* _PRIORITY_QUEUE_H_ */
@@ -37,9 +37,6 @@
are amortized O(log n) time for a tree with n nodes. */
#include "libgomp.h"
-#include "splay-tree.h"
-
-extern int splay_compare (splay_tree_key, splay_tree_key);
/* Rotate the edge joining the left child N with its parent P. PP is the
grandparents' pointer to P. */
@@ -215,3 +212,27 @@ splay_tree_lookup (splay_tree sp, splay_tree_key key)
else
return NULL;
}
+
+/* Helper function for splay_tree_foreach.
+
+ Run FUNC on every node in KEY. */
+
+static void
+splay_tree_foreach_internal (splay_tree_node node, splay_tree_callback func,
+ void *data)
+{
+ if (!node)
+ return;
+ func (&node->key, data);
+ splay_tree_foreach_internal (node->left, func, data);
+ /* Yeah, whatever. GCC can fix my tail recursion. */
+ splay_tree_foreach_internal (node->right, func, data);
+}
+
+/* Run FUNC on each of the nodes in SP. */
+
+attribute_hidden void
+splay_tree_foreach (splay_tree sp, splay_tree_callback func, void *data)
+{
+ splay_tree_foreach_internal (sp->root, func, data);
+}
@@ -33,7 +33,17 @@ typedef struct splay_tree_node_s *splay_tree_node;
typedef struct splay_tree_s *splay_tree;
typedef struct splay_tree_key_s *splay_tree_key;
define splay_tree_key_s structure, and define
- splay_compare inline function. */
+ splay_compare inline function.
+
+ Alternatively, they can define splay_tree_prefix macro before
+ including this header and then all the above types, the
+ splay_compare function and the splay_tree_{lookup,insert_remove}
+ function will be prefixed by that prefix. If splay_tree_prefix
+ macro is defined, this header must be included twice: once where
+ you need the header file definitions, and once where you need the
+ .c implementation routines. In the latter case, you must also
+ define the macro splay_tree_c. See the include of splay-tree.h in
+ priority_queue.[hc] for an example. */
/* For an easily readable description of splay-trees, see:
@@ -43,8 +53,37 @@ typedef struct splay_tree_key_s *splay_tree_key;
The major feature of splay trees is that all basic tree operations
are amortized O(log n) time for a tree with n nodes. */
-#ifndef _SPLAY_TREE_H
-#define _SPLAY_TREE_H 1
+#ifdef splay_tree_prefix
+# define splay_tree_name_1(prefix, name) prefix ## _ ## name
+# define splay_tree_name(prefix, name) splay_tree_name_1 (prefix, name)
+# define splay_tree_node_s \
+ splay_tree_name (splay_tree_prefix, splay_tree_node_s)
+# define splay_tree_s \
+ splay_tree_name (splay_tree_prefix, splay_tree_s)
+# define splay_tree_key_s \
+ splay_tree_name (splay_tree_prefix, splay_tree_key_s)
+# define splay_tree_node \
+ splay_tree_name (splay_tree_prefix, splay_tree_node)
+# define splay_tree \
+ splay_tree_name (splay_tree_prefix, splay_tree)
+# define splay_tree_key \
+ splay_tree_name (splay_tree_prefix, splay_tree_key)
+# define splay_compare \
+ splay_tree_name (splay_tree_prefix, splay_compare)
+# define splay_tree_lookup \
+ splay_tree_name (splay_tree_prefix, splay_tree_lookup)
+# define splay_tree_insert \
+ splay_tree_name (splay_tree_prefix, splay_tree_insert)
+# define splay_tree_remove \
+ splay_tree_name (splay_tree_prefix, splay_tree_remove)
+# define splay_tree_foreach \
+ splay_tree_name (splay_tree_prefix, splay_tree_foreach)
+# define splay_tree_callback \
+ splay_tree_name (splay_tree_prefix, splay_tree_callback)
+#endif
+
+#ifndef splay_tree_c
+/* Header file definitions and prototypes. */
/* The nodes in the splay tree. */
struct splay_tree_node_s {
@@ -59,8 +98,33 @@ struct splay_tree_s {
splay_tree_node root;
};
+typedef void (*splay_tree_callback) (splay_tree_key, void *);
+
extern splay_tree_key splay_tree_lookup (splay_tree, splay_tree_key);
extern void splay_tree_insert (splay_tree, splay_tree_node);
extern void splay_tree_remove (splay_tree, splay_tree_key);
+extern void splay_tree_foreach (splay_tree, splay_tree_callback, void *);
+#else /* splay_tree_c */
+# ifdef splay_tree_prefix
+# include "splay-tree.c"
+# undef splay_tree_name_1
+# undef splay_tree_name
+# undef splay_tree_node_s
+# undef splay_tree_s
+# undef splay_tree_key_s
+# undef splay_tree_node
+# undef splay_tree
+# undef splay_tree_key
+# undef splay_compare
+# undef splay_tree_lookup
+# undef splay_tree_insert
+# undef splay_tree_remove
+# undef splay_tree_foreach
+# undef splay_tree_callback
+# undef splay_tree_c
+# endif
+#endif /* #ifndef splay_tree_c */
-#endif /* _SPLAY_TREE_H */
+#ifdef splay_tree_prefix
+# undef splay_tree_prefix
+#endif
@@ -92,23 +92,6 @@ gomp_realloc_unlock (void *old, size_t size)
return ret;
}
-/* The comparison function. */
-
-attribute_hidden int
-splay_compare (splay_tree_key x, splay_tree_key y)
-{
- if (x->host_start == x->host_end
- && y->host_start == y->host_end)
- return 0;
- if (x->host_end <= y->host_start)
- return -1;
- if (x->host_start >= y->host_end)
- return 1;
- return 0;
-}
-
-#include "splay-tree.h"
-
attribute_hidden void
gomp_init_targets_once (void)
{
@@ -65,6 +65,14 @@ void
gomp_init_task (struct gomp_task *task, struct gomp_task *parent_task,
struct gomp_task_icv *prev_icv)
{
+ /* It would seem that using memset here would be a win, but it turns
+ out that partially filling gomp_task allows us to keep the
+ overhead of task creation low. In the nqueens-1.c test, for a
+ sufficiently large N, we drop the overhead from 5-6% to 1%.
+
+ Note, the nqueens-1.c test in serial mode is a good test to
+ benchmark the overhead of creating tasks as there are millions of
+ tiny tasks created that all run undeferred. */
task->parent = parent_task;
task->icv = *prev_icv;
task->kind = GOMP_TASK_IMPLICIT;
@@ -73,7 +81,7 @@ gomp_init_task (struct gomp_task *task, struct gomp_task *parent_task,
task->final_task = false;
task->copy_ctors_done = false;
task->parent_depends_on = false;
- task->children = NULL;
+ priority_queue_init (&task->children_queue);
task->taskgroup = NULL;
task->dependers = NULL;
task->depend_hash = NULL;
@@ -92,24 +100,66 @@ gomp_end_task (void)
thr->task = task->parent;
}
-/* Orphan the task in CHILDREN and all its siblings. */
+/* Clear the parent field of every task in LIST. */
static inline void
-gomp_clear_parent (struct gomp_task *children)
+gomp_clear_parent_in_list (struct priority_list *list)
{
- struct gomp_task *task = children;
-
- if (task)
+ struct priority_node *p = list->tasks;
+ if (p)
do
{
- task->parent = NULL;
- task = task->next_child;
+ priority_node_to_task (PQ_CHILDREN, p)->parent = NULL;
+ p = p->next;
}
- while (task != children);
+ while (p != list->tasks);
}
-/* Helper function for GOMP_task and gomp_create_target_task. Depend clause
- handling for undeferred task creation. */
+/* Splay tree version of gomp_clear_parent_in_list.
+
+ Clear the parent field of every task in NODE within SP, and free
+ the node when done. */
+
+static void
+gomp_clear_parent_in_tree (prio_splay_tree sp, prio_splay_tree_node node)
+{
+ if (!node)
+ return;
+ prio_splay_tree_node left = node->left, right = node->right;
+ gomp_clear_parent_in_list (&node->key.l);
+#if _LIBGOMP_CHECKING_
+ memset (node, 0xaf, sizeof (*node));
+#endif
+ /* No need to remove the node from the tree. We're nuking
+ everything, so just free the nodes and our caller can clear the
+ entire splay tree. */
+ free (node);
+ gomp_clear_parent_in_tree (sp, left);
+ gomp_clear_parent_in_tree (sp, right);
+}
+
+/* Clear the parent field of every task in Q and remove every task
+ from Q. */
+
+static inline void
+gomp_clear_parent (struct priority_queue *q)
+{
+ if (priority_queue_multi_p (q))
+ {
+ gomp_clear_parent_in_tree (&q->t, q->t.root);
+ /* All the nodes have been cleared in gomp_clear_parent_in_tree.
+ No need to remove anything. We can just nuke everything. */
+ q->t.root = NULL;
+ }
+ else
+ gomp_clear_parent_in_list (&q->l);
+}
+
+/* Helper function for GOMP_task and gomp_create_target_task.
+
+ For a TASK with in/out dependencies, fill in the various dependency
+ queues. PARENT is the parent of said task. DEPEND is as in
+ GOMP_task. */
static void
gomp_task_handle_depend (struct gomp_task *task, struct gomp_task *parent,
@@ -260,8 +310,8 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
if ((flags & GOMP_TASK_FLAG_PRIORITY) == 0)
priority = 0;
- /* FIXME, use priority. */
- (void) priority;
+ else if (priority > gomp_max_task_priority_var)
+ priority = gomp_max_task_priority_var;
if (!if_clause || team == NULL
|| (thr->task && thr->task->final_task)
@@ -283,6 +333,7 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
task.kind = GOMP_TASK_UNDEFERRED;
task.final_task = (thr->task && thr->task->final_task)
|| (flags & GOMP_TASK_FLAG_FINAL);
+ task.priority = priority;
if (thr->task)
{
task.in_tied_task = thr->task->in_tied_task;
@@ -308,10 +359,10 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
child thread, but seeing a stale non-NULL value is not a
problem. Once past the task_lock acquisition, this thread
will see the real value of task.children. */
- if (task.children != NULL)
+ if (!priority_queue_empty_p (&task.children_queue, MEMMODEL_RELAXED))
{
gomp_mutex_lock (&team->task_lock);
- gomp_clear_parent (task.children);
+ gomp_clear_parent (&task.children_queue);
gomp_mutex_unlock (&team->task_lock);
}
gomp_end_task ();
@@ -333,6 +384,7 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
arg = (char *) (((uintptr_t) (task + 1) + depend_size + arg_align - 1)
& ~(uintptr_t) (arg_align - 1));
gomp_init_task (task, parent, gomp_icv (false));
+ task->priority = priority;
task->kind = GOMP_TASK_UNDEFERRED;
task->in_tied_task = parent->in_tied_task;
task->taskgroup = taskgroup;
@@ -368,53 +420,36 @@ GOMP_task (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
gomp_task_handle_depend (task, parent, depend);
if (task->num_dependees)
{
+ /* Tasks that depend on other tasks are not put into the
+ various waiting queues, so we are done for now. Said
+ tasks are instead put into the queues via
+ gomp_task_run_post_handle_dependers() after their
+ dependencies have been satisfied. After which, they
+ can be picked up by the various scheduling
+ points. */
gomp_mutex_unlock (&team->task_lock);
return;
}
}
- if (parent->children)
- {
- task->next_child = parent->children;
- task->prev_child = parent->children->prev_child;
- task->next_child->prev_child = task;
- task->prev_child->next_child = task;
- }
- else
- {
- task->next_child = task;
- task->prev_child = task;
- }
- parent->children = task;
+
+ priority_queue_insert (PQ_CHILDREN, &parent->children_queue,
+ task, priority,
+ PRIORITY_INSERT_BEGIN,
+ /*adjust_parent_depends_on=*/false,
+ task->parent_depends_on);
if (taskgroup)
- {
- /* If applicable, place task into its taskgroup. */
- if (taskgroup->children)
- {
- task->next_taskgroup = taskgroup->children;
- task->prev_taskgroup = taskgroup->children->prev_taskgroup;
- task->next_taskgroup->prev_taskgroup = task;
- task->prev_taskgroup->next_taskgroup = task;
- }
- else
- {
- task->next_taskgroup = task;
- task->prev_taskgroup = task;
- }
- taskgroup->children = task;
- }
- if (team->task_queue)
- {
- task->next_queue = team->task_queue;
- task->prev_queue = team->task_queue->prev_queue;
- task->next_queue->prev_queue = task;
- task->prev_queue->next_queue = task;
- }
- else
- {
- task->next_queue = task;
- task->prev_queue = task;
- team->task_queue = task;
- }
+ priority_queue_insert (PQ_TASKGROUP, &taskgroup->taskgroup_queue,
+ task, priority,
+ PRIORITY_INSERT_BEGIN,
+ /*adjust_parent_depends_on=*/false,
+ task->parent_depends_on);
+
+ priority_queue_insert (PQ_TEAM, &team->task_queue,
+ task, priority,
+ PRIORITY_INSERT_END,
+ /*adjust_parent_depends_on=*/false,
+ task->parent_depends_on);
+
++team->task_count;
++team->task_queued_count;
gomp_team_barrier_set_task_pending (&team->barrier);
@@ -514,49 +549,19 @@ gomp_create_target_task (struct gomp_device_descr *devicep,
return;
}
}
- if (parent->children)
- {
- task->next_child = parent->children;
- task->prev_child = parent->children->prev_child;
- task->next_child->prev_child = task;
- task->prev_child->next_child = task;
- }
- else
- {
- task->next_child = task;
- task->prev_child = task;
- }
- parent->children = task;
+ priority_queue_insert (PQ_CHILDREN, &parent->children_queue, task, 0,
+ PRIORITY_INSERT_BEGIN,
+ /*adjust_parent_depends_on=*/false,
+ task->parent_depends_on);
if (taskgroup)
- {
- /* If applicable, place task into its taskgroup. */
- if (taskgroup->children)
- {
- task->next_taskgroup = taskgroup->children;
- task->prev_taskgroup = taskgroup->children->prev_taskgroup;
- task->next_taskgroup->prev_taskgroup = task;
- task->prev_taskgroup->next_taskgroup = task;
- }
- else
- {
- task->next_taskgroup = task;
- task->prev_taskgroup = task;
- }
- taskgroup->children = task;
- }
- if (team->task_queue)
- {
- task->next_queue = team->task_queue;
- task->prev_queue = team->task_queue->prev_queue;
- task->next_queue->prev_queue = task;
- task->prev_queue->next_queue = task;
- }
- else
- {
- task->next_queue = task;
- task->prev_queue = task;
- team->task_queue = task;
- }
+ priority_queue_insert (PQ_TASKGROUP, &taskgroup->taskgroup_queue, task, 0,
+ PRIORITY_INSERT_BEGIN,
+ /*adjust_parent_depends_on=*/false,
+ task->parent_depends_on);
+ priority_queue_insert (PQ_TEAM, &team->task_queue, task, 0,
+ PRIORITY_INSERT_END,
+ /*adjust_parent_depends_on=*/false,
+ task->parent_depends_on);
++team->task_count;
++team->task_queued_count;
gomp_team_barrier_set_task_pending (&team->barrier);
@@ -567,208 +572,211 @@ gomp_create_target_task (struct gomp_device_descr *devicep,
gomp_team_barrier_wake (&team->barrier, 1);
}
-#if _LIBGOMP_CHECKING
-/* Sanity check TASK to make sure it is in its parent's children
- queue, and that the tasks therein are in the right order.
+/* Given a parent_depends_on task in LIST, move it to the front of its
+ priority so it is run as soon as possible.
- The expected order is:
- parent_depends_on WAITING tasks
- !parent_depends_on WAITING tasks
- TIED tasks
+ Care is taken to update the list's LAST_PARENT_DEPENDS_ON field.
- PARENT is the alleged parent of TASK. */
+ We rearrange the queue such that all parent_depends_on tasks are
+ first, and last_parent_depends_on points to the last such task we
+ rearranged. For example, given the following tasks in a queue
+ where PD[123] are the parent_depends_on tasks:
-static void
-verify_children_queue (struct gomp_task *task, struct gomp_task *parent)
-{
- if (task->parent != parent)
- gomp_fatal ("verify_children_queue: incompatible parents");
- /* It's OK, Annie was an orphan and she turned out all right. */
- if (!parent)
- return;
+ task->children
+ |
+ V
+ C1 -> C2 -> C3 -> PD1 -> PD2 -> PD3 -> C4
- bool seen_tied = false;
- bool seen_plain_waiting = false;
- bool found = false;
- struct gomp_task *t = parent->children;
- while (1)
+ We rearrange such that:
+
+ task->children
+ | +--- last_parent_depends_on
+ | |
+ V V
+ PD1 -> PD2 -> PD3 -> C1 -> C2 -> C3 -> C4. */
+
+static void inline
+priority_list_upgrade_task (struct priority_list *list,
+ struct priority_node *node)
+{
+ struct priority_node *last_parent_depends_on
+ = list->last_parent_depends_on;
+ if (last_parent_depends_on)
{
- if (t == task)
- found = true;
- if (seen_tied && t->kind == GOMP_TASK_WAITING)
- gomp_fatal ("verify_children_queue: WAITING task after TIED");
- if (t->kind == GOMP_TASK_TIED)
- seen_tied = true;
- else if (t->kind == GOMP_TASK_WAITING)
- {
- if (t->parent_depends_on)
- {
- if (seen_plain_waiting)
- gomp_fatal ("verify_children_queue: parent_depends_on after "
- "!parent_depends_on");
- }
- else
- seen_plain_waiting = true;
- }
- t = t->next_child;
- if (t == parent->children)
- break;
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+ node->prev = last_parent_depends_on;
+ node->next = last_parent_depends_on->next;
+ node->prev->next = node;
+ node->next->prev = node;
}
- if (!found)
- gomp_fatal ("verify_children_queue: child not found in parent queue");
+ else if (node != list->tasks)
+ {
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+ node->prev = list->tasks->prev;
+ node->next = list->tasks;
+ list->tasks = node;
+ node->prev->next = node;
+ node->next->prev = node;
+ }
+ list->last_parent_depends_on = node;
}
-/* Sanity check TASK to make sure it is in its taskgroup queue (if
- applicable), and that the tasks therein are in the right order.
+/* Given a parent_depends_on TASK in its parent's children_queue, move
+ it to the front of its priority so it is run as soon as possible.
- The expected order is that GOMP_TASK_WAITING tasks must come before
- GOMP_TASK_TIED tasks.
+ PARENT is passed as an optimization.
- TASK is the task. */
+ (This function could be defined in priority_queue.c, but we want it
+ inlined, and putting it in priority_queue.h is not an option, given
+ that gomp_task has not been properly defined at that point). */
-static void
-verify_taskgroup_queue (struct gomp_task *task)
+static void inline
+priority_queue_upgrade_task (struct gomp_task *task,
+ struct gomp_task *parent)
{
- struct gomp_taskgroup *taskgroup = task->taskgroup;
- if (!taskgroup)
- return;
-
- bool seen_tied = false;
- bool found = false;
- struct gomp_task *t = taskgroup->children;
- while (1)
+ struct priority_queue *head = &parent->children_queue;
+ struct priority_node *node = &task->pnode[PQ_CHILDREN];
+#if _LIBGOMP_CHECKING_
+ if (!task->parent_depends_on)
+ gomp_fatal ("priority_queue_upgrade_task: task must be a "
+ "parent_depends_on task");
+ if (!priority_queue_task_in_queue_p (PQ_CHILDREN, head, task))
+ gomp_fatal ("priority_queue_upgrade_task: cannot find task=%p", task);
+#endif
+ if (priority_queue_multi_p (head))
{
- if (t == task)
- found = true;
- if (t->kind == GOMP_TASK_WAITING && seen_tied)
- gomp_fatal ("verify_taskgroup_queue: WAITING task after TIED");
- if (t->kind == GOMP_TASK_TIED)
- seen_tied = true;
- t = t->next_taskgroup;
- if (t == taskgroup->children)
- break;
+ struct priority_list *list
+ = priority_queue_lookup_priority (head, task->priority);
+ priority_list_upgrade_task (list, node);
}
- if (!found)
- gomp_fatal ("verify_taskgroup_queue: child not found in parent queue");
+ else
+ priority_list_upgrade_task (&head->l, node);
}
-/* Verify that TASK is in the team's task queue. */
+/* Given a CHILD_TASK in LIST that is about to be executed, move it out of
+ the way in LIST so that other tasks can be considered for
+ execution. LIST contains tasks of type TYPE.
-static void
-verify_task_queue (struct gomp_task *task, struct gomp_team *team)
+ Care is taken to update the queue's LAST_PARENT_DEPENDS_ON field
+ if applicable. */
+
+static void inline
+priority_list_downgrade_task (enum priority_queue_type type,
+ struct priority_list *list,
+ struct gomp_task *child_task)
{
- struct gomp_task *t = team->task_queue;
- if (team)
- while (1)
- {
- if (t == task)
- return;
- t = t->next_queue;
- if (t == team->task_queue)
- break;
- }
- gomp_fatal ("verify_team_queue: child not in team");
+ struct priority_node *node = task_to_priority_node (type, child_task);
+ if (list->tasks == node)
+ list->tasks = node->next;
+ else if (node->next != list->tasks)
+ {
+ /* The task in NODE is about to become TIED and TIED tasks
+ cannot come before WAITING tasks. If we're about to
+ leave the queue in such an indeterminate state, rewire
+ things appropriately. However, a TIED task at the end is
+ perfectly fine. */
+ struct gomp_task *next_task = priority_node_to_task (type, node->next);
+ if (next_task->kind == GOMP_TASK_WAITING)
+ {
+ /* Remove from list. */
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+ /* Rewire at the end. */
+ node->next = list->tasks;
+ node->prev = list->tasks->prev;
+ list->tasks->prev->next = node;
+ list->tasks->prev = node;
+ }
+ }
+
+ /* If the current task is the last_parent_depends_on for its
+ priority, adjust last_parent_depends_on appropriately. */
+ if (__builtin_expect (child_task->parent_depends_on, 0)
+ && list->last_parent_depends_on == node)
+ {
+ struct gomp_task *prev_child = priority_node_to_task (type, node->prev);
+ if (node->prev != node
+ && prev_child->kind == GOMP_TASK_WAITING
+ && prev_child->parent_depends_on)
+ list->last_parent_depends_on = node->prev;
+ else
+ {
+ /* There are no more parent_depends_on entries waiting
+ to run, clear the list. */
+ list->last_parent_depends_on = NULL;
+ }
+ }
}
+
+/* Given a TASK in HEAD that is about to be executed, move it out of
+ the way so that other tasks can be considered for execution. HEAD
+ contains tasks of type TYPE.
+
+ Care is taken to update the queue's LAST_PARENT_DEPENDS_ON field
+ if applicable.
+
+ (This function could be defined in priority_queue.c, but we want it
+ inlined, and putting it in priority_queue.h is not an option, given
+ that gomp_task has not been properly defined at that point). */
+
+static void inline
+priority_queue_downgrade_task (enum priority_queue_type type,
+ struct priority_queue *head,
+ struct gomp_task *task)
+{
+#if _LIBGOMP_CHECKING_
+ if (!priority_queue_task_in_queue_p (type, head, task))
+ gomp_fatal ("Attempt to downgrade missing task %p", task);
#endif
+ if (priority_queue_multi_p (head))
+ {
+ struct priority_list *list
+ = priority_queue_lookup_priority (head, task->priority);
+ priority_list_downgrade_task (type, list, task);
+ }
+ else
+ priority_list_downgrade_task (type, &head->l, task);
+}
+
+/* Setup CHILD_TASK to execute. This is done by setting the task to
+ TIED, and updating all relevant queues so that CHILD_TASK is no
+ longer chosen for scheduling. Also, remove CHILD_TASK from the
+ overall team task queue entirely.
+
+ Return TRUE if task or its containing taskgroup has been
+ cancelled. */
static inline bool
gomp_task_run_pre (struct gomp_task *child_task, struct gomp_task *parent,
struct gomp_team *team)
{
-#if _LIBGOMP_CHECKING
- verify_children_queue (child_task, parent);
- verify_taskgroup_queue (child_task);
- verify_task_queue (child_task, team);
+#if _LIBGOMP_CHECKING_
+ if (child_task->parent)
+ priority_queue_verify (PQ_CHILDREN,
+ &child_task->parent->children_queue, true);
+ if (child_task->taskgroup)
+ priority_queue_verify (PQ_TASKGROUP,
+ &child_task->taskgroup->taskgroup_queue, false);
+ priority_queue_verify (PQ_TEAM, &team->task_queue, false);
#endif
+ /* Task is about to go tied, move it out of the way. */
if (parent)
- {
- /* Adjust children such that it will point to a next child,
- while the current one is scheduled to be executed. This way,
- GOMP_taskwait (and others) can schedule a next task while
- waiting.
-
- Do not remove it entirely from the circular list, as it is
- still a child, though not one we should consider first (say
- by GOMP_taskwait). */
- if (parent->children == child_task)
- parent->children = child_task->next_child;
- /* TIED tasks cannot come before WAITING tasks. If we're about
- to make this task TIED, rewire things appropriately.
- However, a TIED task at the end is perfectly fine. */
- else if (child_task->next_child->kind == GOMP_TASK_WAITING
- && child_task->next_child != parent->children)
- {
- /* Remove from the list. */
- child_task->prev_child->next_child = child_task->next_child;
- child_task->next_child->prev_child = child_task->prev_child;
- /* Rewire at the end of its siblings. */
- child_task->next_child = parent->children;
- child_task->prev_child = parent->children->prev_child;
- parent->children->prev_child->next_child = child_task;
- parent->children->prev_child = child_task;
- }
+ priority_queue_downgrade_task (PQ_CHILDREN, &parent->children_queue,
+ child_task);
- /* If the current task (child_task) is at the top of the
- parent's last_parent_depends_on, it's about to be removed
- from it. Adjust last_parent_depends_on appropriately. */
- if (__builtin_expect (child_task->parent_depends_on, 0)
- && parent->taskwait->last_parent_depends_on == child_task)
- {
- /* The last_parent_depends_on list was built with all
- parent_depends_on entries linked to the prev_child. Grab
- the next last_parent_depends_on head from this prev_child if
- available... */
- if (child_task->prev_child->kind == GOMP_TASK_WAITING
- && child_task->prev_child->parent_depends_on)
- parent->taskwait->last_parent_depends_on = child_task->prev_child;
- else
- {
- /* ...otherwise, there are no more parent_depends_on
- entries waiting to run. In which case, clear the
- list. */
- parent->taskwait->last_parent_depends_on = NULL;
- }
- }
- }
-
- /* Adjust taskgroup to point to the next taskgroup. See note above
- regarding adjustment of children as to why the child_task is not
- removed entirely from the circular list. */
+ /* Task is about to go tied, move it out of the way. */
struct gomp_taskgroup *taskgroup = child_task->taskgroup;
if (taskgroup)
- {
- if (taskgroup->children == child_task)
- taskgroup->children = child_task->next_taskgroup;
- /* TIED tasks cannot come before WAITING tasks. If we're about
- to make this task TIED, rewire things appropriately.
- However, a TIED task at the end is perfectly fine. */
- else if (child_task->next_taskgroup->kind == GOMP_TASK_WAITING
- && child_task->next_taskgroup != taskgroup->children)
- {
- /* Remove from the list. */
- child_task->prev_taskgroup->next_taskgroup
- = child_task->next_taskgroup;
- child_task->next_taskgroup->prev_taskgroup
- = child_task->prev_taskgroup;
- /* Rewire at the end of its taskgroup. */
- child_task->next_taskgroup = taskgroup->children;
- child_task->prev_taskgroup = taskgroup->children->prev_taskgroup;
- taskgroup->children->prev_taskgroup->next_taskgroup = child_task;
- taskgroup->children->prev_taskgroup = child_task;
- }
- }
+ priority_queue_downgrade_task (PQ_TASKGROUP, &taskgroup->taskgroup_queue,
+ child_task);
- /* Remove child_task from the task_queue. */
- child_task->prev_queue->next_queue = child_task->next_queue;
- child_task->next_queue->prev_queue = child_task->prev_queue;
- if (team->task_queue == child_task)
- {
- if (child_task->next_queue != child_task)
- team->task_queue = child_task->next_queue;
- else
- team->task_queue = NULL;
- }
+ priority_queue_remove (PQ_TEAM, &team->task_queue, child_task,
+ MEMMODEL_RELAXED);
+ child_task->pnode[PQ_TEAM].next = NULL;
+ child_task->pnode[PQ_TEAM].prev = NULL;
child_task->kind = GOMP_TASK_TIED;
if (--team->task_queued_count == 0)
@@ -808,8 +816,11 @@ gomp_task_run_post_handle_depend_hash (struct gomp_task *child_task)
}
}
-/* After CHILD_TASK has been run, adjust the various task queues to
- give higher priority to the tasks that depend on CHILD_TASK.
+/* After a CHILD_TASK has been run, adjust the dependency queue for
+ each task that depends on CHILD_TASK, to record the fact that there
+ is one less dependency to worry about. If a task that depended on
+ CHILD_TASK now has no dependencies, place it in the various queues
+ so it gets scheduled to run.
TEAM is the team to which CHILD_TASK belongs to. */
@@ -822,99 +833,60 @@ gomp_task_run_post_handle_dependers (struct gomp_task *child_task,
for (i = 0; i < count; i++)
{
struct gomp_task *task = child_task->dependers->elem[i];
+
+ /* CHILD_TASK satisfies a dependency for TASK. Keep track of
+ TASK's remaining dependencies. Once TASK has no other
+ depenencies, put it into the various queues so it will get
+ scheduled for execution. */
if (--task->num_dependees != 0)
continue;
struct gomp_taskgroup *taskgroup = task->taskgroup;
if (parent)
{
- if (parent->children)
- {
- /* If parent is in gomp_task_maybe_wait_for_dependencies
- and it doesn't need to wait for this task, put it after
- all ready to run tasks it needs to wait for. */
- if (parent->taskwait && parent->taskwait->last_parent_depends_on
- && !task->parent_depends_on)
- {
- /* Put depender in last_parent_depends_on. */
- struct gomp_task *last_parent_depends_on
- = parent->taskwait->last_parent_depends_on;
- task->next_child = last_parent_depends_on->next_child;
- task->prev_child = last_parent_depends_on;
- }
- else
- {
- /* Make depender a sibling of child_task, and place
- it at the top of said sibling list. */
- task->next_child = parent->children;
- task->prev_child = parent->children->prev_child;
- parent->children = task;
- }
- task->next_child->prev_child = task;
- task->prev_child->next_child = task;
- }
- else
- {
- /* Make depender a sibling of child_task. */
- task->next_child = task;
- task->prev_child = task;
- parent->children = task;
- }
+ priority_queue_insert (PQ_CHILDREN, &parent->children_queue,
+ task, task->priority,
+ PRIORITY_INSERT_BEGIN,
+ /*adjust_parent_depends_on=*/true,
+ task->parent_depends_on);
if (parent->taskwait)
{
if (parent->taskwait->in_taskwait)
{
+ /* One more task has had its dependencies met.
+ Inform any waiters. */
parent->taskwait->in_taskwait = false;
gomp_sem_post (&parent->taskwait->taskwait_sem);
}
else if (parent->taskwait->in_depend_wait)
{
+ /* One more task has had its dependencies met.
+ Inform any waiters. */
parent->taskwait->in_depend_wait = false;
gomp_sem_post (&parent->taskwait->taskwait_sem);
}
- if (parent->taskwait->last_parent_depends_on == NULL
- && task->parent_depends_on)
- parent->taskwait->last_parent_depends_on = task;
}
}
- /* If depender is in a taskgroup, put it at the TOP of its
- taskgroup. */
if (taskgroup)
{
- if (taskgroup->children)
- {
- task->next_taskgroup = taskgroup->children;
- task->prev_taskgroup = taskgroup->children->prev_taskgroup;
- task->next_taskgroup->prev_taskgroup = task;
- task->prev_taskgroup->next_taskgroup = task;
- }
- else
- {
- task->next_taskgroup = task;
- task->prev_taskgroup = task;
- }
- taskgroup->children = task;
+ priority_queue_insert (PQ_TASKGROUP, &taskgroup->taskgroup_queue,
+ task, task->priority,
+ PRIORITY_INSERT_BEGIN,
+ /*adjust_parent_depends_on=*/false,
+ task->parent_depends_on);
if (taskgroup->in_taskgroup_wait)
{
+ /* One more task has had its dependencies met.
+ Inform any waiters. */
taskgroup->in_taskgroup_wait = false;
gomp_sem_post (&taskgroup->taskgroup_sem);
}
}
- /* Put depender of child_task at the END of the team's
- task_queue. */
- if (team->task_queue)
- {
- task->next_queue = team->task_queue;
- task->prev_queue = team->task_queue->prev_queue;
- task->next_queue->prev_queue = task;
- task->prev_queue->next_queue = task;
- }
- else
- {
- task->next_queue = task;
- task->prev_queue = task;
- team->task_queue = task;
- }
+ priority_queue_insert (PQ_TEAM, &team->task_queue,
+ task, task->priority,
+ PRIORITY_INSERT_END,
+ /*adjust_parent_depends_on=*/false,
+ task->parent_depends_on);
++team->task_count;
++team->task_queued_count;
++ret;
@@ -964,27 +936,15 @@ gomp_task_run_post_remove_parent (struct gomp_task *child_task)
gomp_sem_post (&parent->taskwait->taskwait_sem);
}
- /* Remove CHILD_TASK from its sibling list. */
- child_task->prev_child->next_child = child_task->next_child;
- child_task->next_child->prev_child = child_task->prev_child;
- if (parent->children != child_task)
- return;
- if (child_task->next_child != child_task)
- parent->children = child_task->next_child;
- else
+ if (priority_queue_remove (PQ_CHILDREN, &parent->children_queue,
+ child_task, MEMMODEL_RELEASE)
+ && parent->taskwait && parent->taskwait->in_taskwait)
{
- /* We access task->children in GOMP_taskwait
- outside of the task lock mutex region, so
- need a release barrier here to ensure memory
- written by child_task->fn above is flushed
- before the NULL is written. */
- __atomic_store_n (&parent->children, NULL, MEMMODEL_RELEASE);
- if (parent->taskwait && parent->taskwait->in_taskwait)
- {
- parent->taskwait->in_taskwait = false;
- gomp_sem_post (&parent->taskwait->taskwait_sem);
- }
+ parent->taskwait->in_taskwait = false;
+ gomp_sem_post (&parent->taskwait->taskwait_sem);
}
+ child_task->pnode[PQ_CHILDREN].next = NULL;
+ child_task->pnode[PQ_CHILDREN].prev = NULL;
}
/* Remove CHILD_TASK from its taskgroup. */
@@ -995,8 +955,11 @@ gomp_task_run_post_remove_taskgroup (struct gomp_task *child_task)
struct gomp_taskgroup *taskgroup = child_task->taskgroup;
if (taskgroup == NULL)
return;
- child_task->prev_taskgroup->next_taskgroup = child_task->next_taskgroup;
- child_task->next_taskgroup->prev_taskgroup = child_task->prev_taskgroup;
+ bool empty = priority_queue_remove (PQ_TASKGROUP,
+ &taskgroup->taskgroup_queue,
+ child_task, MEMMODEL_RELAXED);
+ child_task->pnode[PQ_TASKGROUP].next = NULL;
+ child_task->pnode[PQ_TASKGROUP].prev = NULL;
if (taskgroup->num_children > 1)
--taskgroup->num_children;
else
@@ -1008,18 +971,10 @@ gomp_task_run_post_remove_taskgroup (struct gomp_task *child_task)
before the NULL is written. */
__atomic_store_n (&taskgroup->num_children, 0, MEMMODEL_RELEASE);
}
- if (taskgroup->children != child_task)
- return;
- if (child_task->next_taskgroup != child_task)
- taskgroup->children = child_task->next_taskgroup;
- else
+ if (empty && taskgroup->in_taskgroup_wait)
{
- taskgroup->children = NULL;
- if (taskgroup->in_taskgroup_wait)
- {
- taskgroup->in_taskgroup_wait = false;
- gomp_sem_post (&taskgroup->taskgroup_sem);
- }
+ taskgroup->in_taskgroup_wait = false;
+ gomp_sem_post (&taskgroup->taskgroup_sem);
}
}
@@ -1049,9 +1004,13 @@ gomp_barrier_handle_tasks (gomp_barrier_state_t state)
while (1)
{
bool cancelled = false;
- if (team->task_queue != NULL)
+ if (!priority_queue_empty_p (&team->task_queue, MEMMODEL_RELAXED))
{
- child_task = team->task_queue;
+ bool ignored;
+ child_task
+ = priority_queue_next_task (PQ_TEAM, &team->task_queue,
+ PQ_IGNORED, NULL,
+ &ignored);
cancelled = gomp_task_run_pre (child_task, child_task->parent,
team);
if (__builtin_expect (cancelled, 0))
@@ -1094,7 +1053,7 @@ gomp_barrier_handle_tasks (gomp_barrier_state_t state)
size_t new_tasks
= gomp_task_run_post_handle_depend (child_task, team);
gomp_task_run_post_remove_parent (child_task);
- gomp_clear_parent (child_task->children);
+ gomp_clear_parent (&child_task->children_queue);
gomp_task_run_post_remove_taskgroup (child_task);
to_free = child_task;
child_task = NULL;
@@ -1140,15 +1099,16 @@ GOMP_taskwait (void)
child thread task work function are seen before we exit from
GOMP_taskwait. */
if (task == NULL
- || __atomic_load_n (&task->children, MEMMODEL_ACQUIRE) == NULL)
+ || priority_queue_empty_p (&task->children_queue, MEMMODEL_ACQUIRE))
return;
memset (&taskwait, 0, sizeof (taskwait));
+ bool child_q = false;
gomp_mutex_lock (&team->task_lock);
while (1)
{
bool cancelled = false;
- if (task->children == NULL)
+ if (priority_queue_empty_p (&task->children_queue, MEMMODEL_RELAXED))
{
bool destroy_taskwait = task->taskwait != NULL;
task->taskwait = NULL;
@@ -1162,9 +1122,12 @@ GOMP_taskwait (void)
gomp_sem_destroy (&taskwait.taskwait_sem);
return;
}
- if (task->children->kind == GOMP_TASK_WAITING)
+ struct gomp_task *next_task
+ = priority_queue_next_task (PQ_CHILDREN, &task->children_queue,
+ PQ_TEAM, &team->task_queue, &child_q);
+ if (next_task->kind == GOMP_TASK_WAITING)
{
- child_task = task->children;
+ child_task = next_task;
cancelled
= gomp_task_run_pre (child_task, task, team);
if (__builtin_expect (cancelled, 0))
@@ -1180,8 +1143,10 @@ GOMP_taskwait (void)
}
else
{
- /* All tasks we are waiting for are already running
- in other threads. Wait for them. */
+ /* All tasks we are waiting for are either running in other
+ threads, or they are tasks that have not had their
+ dependencies met (so they're not even in the queue). Wait
+ for them. */
if (task->taskwait == NULL)
{
taskwait.in_depend_wait = false;
@@ -1217,21 +1182,16 @@ GOMP_taskwait (void)
size_t new_tasks
= gomp_task_run_post_handle_depend (child_task, team);
- /* Remove child_task from children list, and set up the next
- sibling to be run. */
- child_task->prev_child->next_child = child_task->next_child;
- child_task->next_child->prev_child = child_task->prev_child;
- if (task->children == child_task)
+ if (child_q)
{
- if (child_task->next_child != child_task)
- task->children = child_task->next_child;
- else
- task->children = NULL;
+ priority_queue_remove (PQ_CHILDREN, &task->children_queue,
+ child_task, MEMMODEL_RELAXED);
+ child_task->pnode[PQ_CHILDREN].next = NULL;
+ child_task->pnode[PQ_CHILDREN].prev = NULL;
}
- /* Orphan all the children of CHILD_TASK. */
- gomp_clear_parent (child_task->children);
- /* Remove CHILD_TASK from its taskgroup. */
+ gomp_clear_parent (&child_task->children_queue);
+
gomp_task_run_post_remove_taskgroup (child_task);
to_free = child_task;
@@ -1248,8 +1208,16 @@ GOMP_taskwait (void)
}
}
-/* This is like GOMP_taskwait, but we only wait for tasks that the
- upcoming task depends on.
+/* An undeferred task is about to run. Wait for all tasks that this
+ undeferred task depends on.
+
+ This is done by first putting all known ready dependencies
+ (dependencies that have their own dependencies met) at the top of
+ the scheduling queues. Then we iterate through these imminently
+ ready tasks (and possibly other high priority tasks), and run them.
+ If we run out of ready dependencies to execute, we either wait for
+ the reamining dependencies to finish, or wait for them to get
+ scheduled so we can run them.
DEPEND is as in GOMP_task. */
@@ -1261,7 +1229,6 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
struct gomp_team *team = thr->ts.team;
struct gomp_task_depend_entry elem, *ent = NULL;
struct gomp_taskwait taskwait;
- struct gomp_task *last_parent_depends_on = NULL;
size_t ndepend = (uintptr_t) depend[0];
size_t nout = (uintptr_t) depend[1];
size_t i;
@@ -1285,54 +1252,11 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
{
tsk->parent_depends_on = true;
++num_awaited;
- /* If a task we need to wait for is not already
- running and is ready to be scheduled, move it to
- front, so that we run it as soon as possible.
-
- We rearrange the children queue such that all
- parent_depends_on tasks are first, and
- last_parent_depends_on points to the last such task
- we rearranged. For example, given the following
- children where PD[123] are the parent_depends_on
- tasks:
-
- task->children
- |
- V
- C1 -> C2 -> C3 -> PD1 -> PD2 -> PD3 -> C4
-
- We rearrange such that:
-
- task->children
- | +--- last_parent_depends_on
- | |
- V V
- PD1 -> PD2 -> PD3 -> C1 -> C2 -> C3 -> C4
- */
-
+ /* If depenency TSK itself has no dependencies and is
+ ready to run, move it up front so that we run it as
+ soon as possible. */
if (tsk->num_dependees == 0 && tsk->kind == GOMP_TASK_WAITING)
- {
- if (last_parent_depends_on)
- {
- tsk->prev_child->next_child = tsk->next_child;
- tsk->next_child->prev_child = tsk->prev_child;
- tsk->prev_child = last_parent_depends_on;
- tsk->next_child = last_parent_depends_on->next_child;
- tsk->prev_child->next_child = tsk;
- tsk->next_child->prev_child = tsk;
- }
- else if (tsk != task->children)
- {
- tsk->prev_child->next_child = tsk->next_child;
- tsk->next_child->prev_child = tsk->prev_child;
- tsk->prev_child = task->children->prev_child;
- tsk->next_child = task->children;
- task->children = tsk;
- tsk->prev_child->next_child = tsk;
- tsk->next_child->prev_child = tsk;
- }
- last_parent_depends_on = tsk;
- }
+ priority_queue_upgrade_task (tsk, task);
}
}
}
@@ -1344,7 +1268,6 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
memset (&taskwait, 0, sizeof (taskwait));
taskwait.n_depend = num_awaited;
- taskwait.last_parent_depends_on = last_parent_depends_on;
gomp_sem_init (&taskwait.taskwait_sem, 0);
task->taskwait = &taskwait;
@@ -1363,9 +1286,28 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
gomp_sem_destroy (&taskwait.taskwait_sem);
return;
}
- if (task->children->kind == GOMP_TASK_WAITING)
+
+ /* Theoretically when we have multiple priorities, we should
+ chose between the highest priority item in
+ task->children_queue and team->task_queue here, so we should
+ use priority_queue_next_task(). However, since we are
+ running an undeferred task, perhaps that makes all tasks it
+ depends on undeferred, thus a priority of INF? This would
+ make it unnecessary to take anything into account here,
+ but the dependencies.
+
+ On the other hand, if we want to use priority_queue_next_task(),
+ care should be taken to only use priority_queue_remove()
+ below if the task was actually removed from the children
+ queue. */
+ bool ignored;
+ struct gomp_task *next_task
+ = priority_queue_next_task (PQ_CHILDREN, &task->children_queue,
+ PQ_IGNORED, NULL, &ignored);
+
+ if (next_task->kind == GOMP_TASK_WAITING)
{
- child_task = task->children;
+ child_task = next_task;
cancelled
= gomp_task_run_pre (child_task, task, team);
if (__builtin_expect (cancelled, 0))
@@ -1380,8 +1322,10 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
}
}
else
- /* All tasks we are waiting for are already running
- in other threads. Wait for them. */
+ /* All tasks we are waiting for are either running in other
+ threads, or they are tasks that have not had their
+ dependencies met (so they're not even in the queue). Wait
+ for them. */
taskwait.in_depend_wait = true;
gomp_mutex_unlock (&team->task_lock);
if (do_wake)
@@ -1412,18 +1356,12 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
if (child_task->parent_depends_on)
--taskwait.n_depend;
- /* Remove child_task from sibling list. */
- child_task->prev_child->next_child = child_task->next_child;
- child_task->next_child->prev_child = child_task->prev_child;
- if (task->children == child_task)
- {
- if (child_task->next_child != child_task)
- task->children = child_task->next_child;
- else
- task->children = NULL;
- }
+ priority_queue_remove (PQ_CHILDREN, &task->children_queue,
+ child_task, MEMMODEL_RELAXED);
+ child_task->pnode[PQ_CHILDREN].next = NULL;
+ child_task->pnode[PQ_CHILDREN].prev = NULL;
- gomp_clear_parent (child_task->children);
+ gomp_clear_parent (&child_task->children_queue);
gomp_task_run_post_remove_taskgroup (child_task);
to_free = child_task;
child_task = NULL;
@@ -1463,7 +1401,7 @@ GOMP_taskgroup_start (void)
return;
taskgroup = gomp_malloc (sizeof (struct gomp_taskgroup));
taskgroup->prev = task->taskgroup;
- taskgroup->children = NULL;
+ priority_queue_init (&taskgroup->taskgroup_queue);
taskgroup->in_taskgroup_wait = false;
taskgroup->cancelled = false;
taskgroup->num_children = 0;
@@ -1495,17 +1433,23 @@ GOMP_taskgroup_end (void)
if (__atomic_load_n (&taskgroup->num_children, MEMMODEL_ACQUIRE) == 0)
goto finish;
+ bool unused;
gomp_mutex_lock (&team->task_lock);
while (1)
{
bool cancelled = false;
- if (taskgroup->children == NULL)
+ if (priority_queue_empty_p (&taskgroup->taskgroup_queue,
+ MEMMODEL_RELAXED))
{
if (taskgroup->num_children)
{
- if (task->children == NULL)
+ if (priority_queue_empty_p (&task->children_queue,
+ MEMMODEL_RELAXED))
goto do_wait;
- child_task = task->children;
+ child_task
+ = priority_queue_next_task (PQ_CHILDREN, &task->children_queue,
+ PQ_TEAM, &team->task_queue,
+ &unused);
}
else
{
@@ -1519,7 +1463,9 @@ GOMP_taskgroup_end (void)
}
}
else
- child_task = taskgroup->children;
+ child_task
+ = priority_queue_next_task (PQ_TASKGROUP, &taskgroup->taskgroup_queue,
+ PQ_TEAM, &team->task_queue, &unused);
if (child_task->kind == GOMP_TASK_WAITING)
{
cancelled
@@ -1539,8 +1485,10 @@ GOMP_taskgroup_end (void)
{
child_task = NULL;
do_wait:
- /* All tasks we are waiting for are already running
- in other threads. Wait for them. */
+ /* All tasks we are waiting for are either running in other
+ threads, or they are tasks that have not had their
+ dependencies met (so they're not even in the queue). Wait
+ for them. */
taskgroup->in_taskgroup_wait = true;
}
gomp_mutex_unlock (&team->task_lock);
@@ -1570,7 +1518,7 @@ GOMP_taskgroup_end (void)
size_t new_tasks
= gomp_task_run_post_handle_depend (child_task, team);
gomp_task_run_post_remove_parent (child_task);
- gomp_clear_parent (child_task->children);
+ gomp_clear_parent (&child_task->children_queue);
gomp_task_run_post_remove_taskgroup (child_task);
to_free = child_task;
child_task = NULL;
@@ -155,8 +155,8 @@ GOMP_taskloop (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
else
ialias_call (GOMP_taskgroup_start) ();
- /* FIXME, use priority. */
- (void) priority;
+ if (priority > gomp_max_task_priority_var)
+ priority = gomp_max_task_priority_var;
if ((flags & GOMP_TASK_FLAG_IF) == 0 || team == NULL
|| (thr->task && thr->task->final_task)
@@ -175,6 +175,7 @@ GOMP_taskloop (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
for (i = 0; i < num_tasks; i++)
{
gomp_init_task (&task[i], parent, gomp_icv (false));
+ task[i].priority = priority;
task[i].kind = GOMP_TASK_UNDEFERRED;
task[i].final_task = (thr->task && thr->task->final_task)
|| (flags & GOMP_TASK_FLAG_FINAL);
@@ -198,10 +199,11 @@ GOMP_taskloop (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
task_step -= step;
fn (arg);
arg += arg_size;
- if (task[i].children != NULL)
+ if (!priority_queue_empty_p (&task[i].children_queue,
+ MEMMODEL_RELAXED))
{
gomp_mutex_lock (&team->task_lock);
- gomp_clear_parent (task[i].children);
+ gomp_clear_parent (&task[i].children_queue);
gomp_mutex_unlock (&team->task_lock);
}
gomp_end_task ();
@@ -213,6 +215,7 @@ GOMP_taskloop (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
struct gomp_task task;
gomp_init_task (&task, thr->task, gomp_icv (false));
+ task.priority = priority;
task.kind = GOMP_TASK_UNDEFERRED;
task.final_task = (thr->task && thr->task->final_task)
|| (flags & GOMP_TASK_FLAG_FINAL);
@@ -228,10 +231,11 @@ GOMP_taskloop (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
if (i == nfirst)
task_step -= step;
fn (data);
- if (task.children != NULL)
+ if (!priority_queue_empty_p (&task.children_queue,
+ MEMMODEL_RELAXED))
{
gomp_mutex_lock (&team->task_lock);
- gomp_clear_parent (task.children);
+ gomp_clear_parent (&task.children_queue);
gomp_mutex_unlock (&team->task_lock);
}
gomp_end_task ();
@@ -254,6 +258,7 @@ GOMP_taskloop (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
arg = (char *) (((uintptr_t) (task + 1) + arg_align - 1)
& ~(uintptr_t) (arg_align - 1));
gomp_init_task (task, parent, gomp_icv (false));
+ task->priority = priority;
task->kind = GOMP_TASK_UNDEFERRED;
task->in_tied_task = parent->in_tied_task;
task->taskgroup = taskgroup;
@@ -298,48 +303,20 @@ GOMP_taskloop (void (*fn) (void *), void *data, void (*cpyfn) (void *, void *),
for (i = 0; i < num_tasks; i++)
{
struct gomp_task *task = tasks[i];
- if (parent->children)
- {
- task->next_child = parent->children;
- task->prev_child = parent->children->prev_child;
- task->next_child->prev_child = task;
- task->prev_child->next_child = task;
- }
- else
- {
- task->next_child = task;
- task->prev_child = task;
- }
- parent->children = task;
+ priority_queue_insert (PQ_CHILDREN, &parent->children_queue,
+ task, priority,
+ PRIORITY_INSERT_BEGIN,
+ /*last_parent_depends_on=*/false,
+ task->parent_depends_on);
if (taskgroup)
- {
- if (taskgroup->children)
- {
- task->next_taskgroup = taskgroup->children;
- task->prev_taskgroup = taskgroup->children->prev_taskgroup;
- task->next_taskgroup->prev_taskgroup = task;
- task->prev_taskgroup->next_taskgroup = task;
- }
- else
- {
- task->next_taskgroup = task;
- task->prev_taskgroup = task;
- }
- taskgroup->children = task;
- }
- if (team->task_queue)
- {
- task->next_queue = team->task_queue;
- task->prev_queue = team->task_queue->prev_queue;
- task->next_queue->prev_queue = task;
- task->prev_queue->next_queue = task;
- }
- else
- {
- task->next_queue = task;
- task->prev_queue = task;
- team->task_queue = task;
- }
+ priority_queue_insert (PQ_TASKGROUP, &taskgroup->taskgroup_queue,
+ task, priority, PRIORITY_INSERT_BEGIN,
+ /*last_parent_depends_on=*/false,
+ task->parent_depends_on);
+ priority_queue_insert (PQ_TEAM, &team->task_queue, task, priority,
+ PRIORITY_INSERT_END,
+ /*last_parent_depends_on=*/false,
+ task->parent_depends_on);
++team->task_count;
++team->task_queued_count;
}
@@ -193,7 +193,7 @@ gomp_new_team (unsigned nthreads)
team->ordered_release = (void *) &team->implicit_task[nthreads];
team->ordered_release[0] = &team->master_release;
- team->task_queue = NULL;
+ priority_queue_init (&team->task_queue);
team->task_count = 0;
team->task_queued_count = 0;
team->task_running_count = 0;
@@ -214,6 +214,7 @@ free_team (struct gomp_team *team)
#endif
gomp_barrier_destroy (&team->barrier);
gomp_mutex_destroy (&team->task_lock);
+ priority_queue_free (&team->task_queue);
free (team);
}
new file mode 100644
@@ -0,0 +1,62 @@
+/* { dg-do run } */
+/* { dg-set-target-env-var OMP_MAX_TASK_PRIORITY "10" } */
+
+/* This test verifies that the "priority" clause of omp task works as
+ advertised.
+
+ Testing the OpenMP task scheduler is a bit tricky, especially when
+ trying to determine what ran first (without explicitly calling
+ time() and/or synchronizing between threads). What we do here is
+ run in single threaded mode which guarantees that we won't run into
+ data races while accessing the "prio" array.
+
+ We give each task a priority from 0..63, while setting
+ OMP_MAX_TASK_PRIORITY to 10, which basically gives us 10 lower
+ priority tasks, and the rest scheduled to run earlier. We verify
+ that the priority < 10 tasks run last. */
+
+#include <omp.h>
+#include <stdlib.h>
+
+#define N 64
+
+int main()
+{
+ int tsknum=0, prio[N];
+ int max_priority = omp_get_max_task_priority ();
+ int saved_tsknum = -1;
+ int i;
+
+#pragma omp parallel num_threads(1)
+#pragma omp single private (i)
+ {
+ for (i = 0; i < N; i++)
+ #pragma omp task priority(i ^ 1)
+ {
+ int t;
+ #pragma omp atomic capture seq_cst
+ t = tsknum++;
+ prio[t] = i ^ 1;
+ }
+ #pragma omp atomic read seq_cst
+ saved_tsknum = tsknum;
+ }
+
+ /* If any of the tasks have run before all tasks were created, don't
+ make any assumption on the task order. Otherwise, we should have
+ tasks with >= max_priority scheduled first in arbitrary order,
+ followed by the rest of tasks in decreasing priority order, as
+ there is only one thread that can schedule them. */
+ if (saved_tsknum == 0)
+ {
+ for (i = 0; i < N; i++)
+ if (i < N - max_priority)
+ {
+ if (prio[i] < max_priority)
+ abort ();
+ }
+ else if (i != N - prio[i] - 1)
+ abort ();
+ }
+ return 0;
+}