## Recommended Posts

##### Share on other sites
Quote:
 Original post by taliesinnzAt the moment i just want to write a basic task system which if required one day I could easily implement multithreadded aspects to it.

Multi-threaded task systems don't work that way. First there is data dependency which is non-trivial to express, so this type of task systems duplicates data or operates on multiple buffers.
Serial dependency must be minimized, so stuff like "one task after another" must be minimized. Usually, dependency would be on per-system basis, topologically sorted before each batch.
Complex hierarchies are highly undesirable since managing them is complex. Usually, there would be a handful of systems. They are topologically sorted, and each level of the graph is processed in parallel. Each of these systems might run in parallel as well, perhaps using TBB to process elements across multiple cores. The order in which they are processed is arbitrary, hence they need to not depend on each other.

After all of these systems are updated, the process is restarted.

Quote:
 and to have various sorting strategies for the sub tasks ( FIFO, Front to Back, Back to Front, etc) in a node.

You really don't want any kind of ordering. It will be impossible to debug (why does this thing move like this, is it a bug, is the FIFO order causing A22734 to be processed before B2231 but not before C8556?).

Quote:
 I am having a hard time trying to choose a way of storing the task lists with their child elements and being able to quickly access the Task while looping through the whole list. And keeping everything sorted in the correct order.

If you forget about child tasks (whatever purpose they might solve), then each system has a list. When updated, it processes all entries, either sequentially or in parallel without affecting anything else.

For any kind of concurrency, each of these systems will have old and new state, since it simplifies processing considerably and avoids ordering issues.

##### Share on other sites
Antheus has good advice above ;) Try to keep any dependencies to whole groups of tasks, not between individual tasks themselves. Being able to add tasks at any time introduces lots of synch overhead -- it's best to restrict any communication to occur at specifically scheduled times so you don't have to use locks everywhere. It's best if you can know the entire list of tasks you'll be processing one frame/cycle in advance if possible!

Task groups can specify a list of pointers to other tasks groups for data dependencies.

E.g. You might have a physics System and a rendering System.
These Systems both have their own Task Group.
Each object within those Systems has a Task, which is put into the System's Task Group.
The physics system's Task Group is put into the Schedule first, then the rendering system's Task Group specifies the physics Group as a dependency and it is also put into the Schedule.
There is a requirement that dependent groups are listed after their dependencies, which is why physics must be scheduled first. I have assertions in debug builds to check that this constraint isn't violated.

for each taskGroup in schedule  for each task in taskGroup    task->update
var threadIndex = ...var numThreads = ...var weight = 1.0/numThreadsfor each taskGroup in schedule  for each dependency of taskGroup //Wait for each prerequisite still executing    for( iThread=0; iThread<numThreads; ++iThread )      while dependency->m_IsExecuting[iThread]        Sleep(0)  var taskSize = taskGroup->size  var range ={-1,-1};  //find a range of tasks within the group for this thread to execute  for( iThread=0, itRange=0; iThread<numThreads; ++iThread )    var begin = itRange    var end    if iThread == numThreads-1 || iThread==taskSize-1 //last worker, make sure the whole range is covered      end = taskSize;    else      end = min( taskSize, int(begin + taskSize*weight) );    if iThread == idxThread //found the answer for this thread, break out of the loop      range.begin = begin;      range.end = end;      break;    itRange = end;  for each task in range in taskGroup    task->update  //Signal this thread has completed all tasks  m_IsExecuting[idxThread] = 0;//array of atomic/interlocked values

[Edit #2]Timothy Farrar's blog is always very dense, but I've found a lot of good food-for-thought there:
http://farrarfocus.blogspot.com/2009/04/atomic-operations-and-scheduling.html
http://farrarfocus.blogspot.com/2009/06/factoring-out-job-scheduler.html
http://farrarfocus.blogspot.com/2009/04/current-and-near-future-of-parallel.html

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627653
• Total Posts
2978433

• 10
• 12
• 22
• 13
• 33