Re: [Algorithms] General purpose task parallel threading approach

[Jarkko L. <al...@gm...>]

There isn't "whole bunch of magic" outside the task you would need to do
with the first option. The task just adds another function to the job queue
which does the work after the wait. For second option it is job queues task
to schedule the tasks for optimal throughput, so for wait it could for
example favor tasks blocking the task from proceeding.

 

 

Cheers, Jarkko

 

  _____  

From: Sebastian Sylvan [mailto:seb...@gm...] 
Sent: Sunday, April 05, 2009 4:47 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] General purpose task parallel threading approach

 

 

On Sun, Apr 5, 2009 at 1:52 AM, Jarkko Lempiainen <al...@gm...> wrote:

You could also not have a wait for dependent tasks within a task, but rather
have job queue dependency system to take care of it by splitting the
function in two tasks. Or you could implement the wait by pulling tasks from
the job queue until the dependent tasks have been completed. There is no
context switches needed in either case though.

 

The first option seems limited to me - you really want to be able to just
stick a parallel for in a task and have it work without having to do a whole
bunch of magic outside the task itself to split it up. The Cilk model is
pretty much what we're going for.

The second is an option I guess, but it could lead to bubbles if you happen
to pick up a long running task. 

Imagine two massive parallel for loops, the first one finishes and syncs,
and then using your suggestion goes off and steals work from another thread
which takes a long time to complete, and only after that's finished can it
continue with the next parallel for loop (which spawns enough tasks to keep
the system saturated), but by that time the entire system may have been
starved for the duration of that long running task just because the original
worker handled its blocking by doing something else rather than yielding the
core. 

It's probably more attractive to just make sure no workers are blocked
needlessly in case the very first thing they do is to spawn more tasks
(again, I see this as quite common - lots of stuff where you fork tons of
tiny tasks, wait for them to finish, then spawn tons of tiny tasks again for
the next bit of work).

 

 

 

 


  _____  


From: Sebastian Sylvan [mailto:seb...@gm...] 
Sent: Sunday, April 05, 2009 3:31 AM


To: Game Development Algorithms
Subject: Re: [Algorithms] General purpose task parallel threading approach

 

 

On Sun, Apr 5, 2009 at 1:10 AM, Jarkko Lempiainen <al...@gm...> wrote:

I think you really need to target for both task and data level parallelism
to make your game engine truly scalable for many-core architectures. I don't
see why you would need to consider the cost of context switching in relation
to const of a task execution though since if you got a job queue, each
worker thread just pulls tasks from the queue without switching context.

 

The problem is when you have a task spawn N other tasks and then wait for
their results, the core running that worker needs to do something until the
two sub-tasks have completed. In practice, I do think that this kind of
synchronisation (specifically the fork-and-join model) will be extremely
common in the future, which means that context switch needs to be fast
(Windows 7's user mode scheduling may be useful here - in fact I believe
that's what Microsoft's native concurrency runtime uses, while the .Net one
is backed by thread pools, I believe).

 



-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862


----------------------------------------------------------------------------
--

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list




-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862