Task System Advice
Author
Hey
I'm currently working on a game in the early stages and I am having trouble deciding on how to design my task system.
At the moment i just want to write a basic task system which if required one day I could easily implement multithreadded aspects to it.
I have decided that the processing will be split into tasks ( Sound / AI / Graphics / Phsyics etc ). So if I have a character it will have a Update task, SOund task, graphics task, physics task. These tasks would be added and deleted when new characters are created or destroyed.
I want to be able to sort them into a tree so I can process them in a logical order for example. Also I want each task to be able to spawn sub tasks for more processing, and to have various sorting strategies for the sub tasks ( FIFO, Front to Back, Back to Front, etc) in a node.
Update Task Parent
. Character 1
. Character 2
. Character 3
. Monster 1
. Monster 2
Draw Tasks
. Draw Char 1
...
Physics
...
At the moment tasks will be derived from a virtual class called Task which at the moment only has one method Update, but will add more as required.
When it comes to processing I want it to run through the list calling any child processes in a continuous loop. If i decide to do a multi-thread game, each thread would go through and pick the next child off the list in order.
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.
Any suggestions or experiences on the matter would be welcomed.
PS I have heard of Intel TBB, and decided against using it.
Quote:Original post by taliesinnz
At 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.
Modifying and adding tasks is simply not viable due to overhead. Tasks are scheduled for next update.
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.
[Edit]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!
I only allow two "levels" of tasks in my system - Tasks (a single-threaded bit of work) and Task Groups (lists of Tasks). Task Groups are put into a Schedule (list of Task Groups).
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.
In a single-threaded implementation:In a multi-threaded implementation:
[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/06/thread-scheduling-part-1.html
http://farrarfocus.blogspot.com/2009/06/thread-scheduling-part-2.html
http://farrarfocus.blogspot.com/2009/06/thread-scheduling-part-3.html
http://farrarfocus.blogspot.com/2009/04/current-and-near-future-of-parallel.html
I only allow two "levels" of tasks in my system - Tasks (a single-threaded bit of work) and Task Groups (lists of Tasks). Task Groups are put into a Schedule (list of Task Groups).
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.
In a single-threaded implementation:
for each taskGroup in schedule for each task in taskGroup task->updatevar 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/06/thread-scheduling-part-1.html
http://farrarfocus.blogspot.com/2009/06/thread-scheduling-part-2.html
http://farrarfocus.blogspot.com/2009/06/thread-scheduling-part-3.html
http://farrarfocus.blogspot.com/2009/04/current-and-near-future-of-parallel.html
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
