From: Aldy Hernandez <aldyh@redhat.com>
To: Jakub Jelinek <jakub@redhat.com>, gcc-patches <gcc-patches@gcc.gnu.org>
Subject: [gomp4.1] fix dependency scheduling problem
Date: Fri, 02 Oct 2015 22:47:00 -0000 [thread overview]
Message-ID: <560F0963.1030102@redhat.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 2246 bytes --]
Hi.
As I may have mentioned earlier, I'm implementing OpenMP 4.1's task
priorities for GCC's libgomp. This has had me looking at how we
currently implement scheduling, and I believe we have a problem in how
we rearrange dependencies.
Currently in gomp_task_maybe_wait_for_dependencies(), we have the
following code for rearranging the first dependency (tsk) from a list of
dependencies.
else if (tsk != task->children)
{
/* Remove tsk from the sibling list... */
tsk->prev_child->next_child = tsk->next_child;
tsk->next_child->prev_child = tsk->prev_child;
/* ...and insert it into the running task's
children. */
-->BAD tsk->prev_child = task->children;
-->BAD tsk->next_child = task->children->next_child;
task->children = tsk;
tsk->prev_child->next_child = tsk;
tsk->next_child->prev_child = tsk;
}
If say, you have a parent_depends_on task PD1 that is in the following
children queue:
C1 -> C2 -> C3 -> PD1 -> C4
(Where parent->children points to C1 and C4 wraps around to C1 as per
the circular list.)
The above code will transform the children queue into:
PD1 -> C2 -> C3 -> C4 -> C1
The surrounding code looks sane, but this particular snippet quoted
above has us moving the first child to the end of the queue, which is
probably not what we want. However, at least we're still keeping the
parent_depends_on tasks first, just that we moved other previously
unaffected children to the end of the queue.
What we really want is:
PD1 -> C1 -> C2 -> C3 -> C4
The attached patch does just that. I have also rewritten the comments
now that I actually understand what's going on :). Eventually this will
all become clearer with my upcoming/proposed API for dealing with all
these queues.
As discussed on IRC, there is another issue you pointed out in
gomp_task_run_pre(), which I will address in a followup patch.
Tested on x86-64 Linux by running "make check-target-libgomp" with
OMP_NUM_THREADS={1,2,55}.
OK for branch?
[-- Attachment #2: curr --]
[-- Type: text/plain, Size: 2708 bytes --]
commit 6d8f6db0583326d803c7c7abd8ea26cc842643fc
Author: Aldy Hernandez <aldyh@redhat.com>
Date: Fri Oct 2 15:40:30 2015 -0700
* task.c (gomp_task_maybe_wait_for_dependencies): Fix scheduling
problem such that the first non parent_depends_on task does not
end up at the end of the children queue.
diff --git a/libgomp/task.c b/libgomp/task.c
index f6a67eb..5c412fc 100644
--- a/libgomp/task.c
+++ b/libgomp/task.c
@@ -1140,17 +1140,37 @@ 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 (tsk->num_dependees == 0 && tsk->kind == GOMP_TASK_WAITING)
{
- /* 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. */
if (last_parent_depends_on)
{
- /* Remove tsk from the sibling list... */
tsk->prev_child->next_child = tsk->next_child;
tsk->next_child->prev_child = tsk->prev_child;
- /* ...and insert it into last_parent_depends_on. */
tsk->prev_child = last_parent_depends_on;
tsk->next_child = last_parent_depends_on->next_child;
tsk->prev_child->next_child = tsk;
@@ -1158,21 +1178,14 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
}
else if (tsk != task->children)
{
- /* Remove tsk from the sibling list... */
tsk->prev_child->next_child = tsk->next_child;
tsk->next_child->prev_child = tsk->prev_child;
- /* ...and insert it into the running task's
- children. */
- tsk->prev_child = task->children;
- tsk->next_child = task->children->next_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;
}
- else
- {
- /* It's already in task->children. Nothing to do. */;
- }
last_parent_depends_on = tsk;
}
}
next reply other threads:[~2015-10-02 22:47 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-10-02 22:47 Aldy Hernandez [this message]
2015-10-09 14:22 ` Jakub Jelinek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=560F0963.1030102@redhat.com \
--to=aldyh@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).