   Job Scheduling Theory
  I'm looking for some reading materials on algorithms used for task-scheduling.Most of the material that I've found though is in the context of a generic preemptive OS process scheduler...My job system contains a finite list of jobs, arranged into a DAG via prerequisites. The estimated runtime of each job is known, the dependencies between jobs are known, and no jobs can be added or removed until all jobs have been processed. Also, jobs can't be preempted - they are all short in duration (less than 1 frame).What I need to do is take all this information at the start of a frame, and work out a schedule for executing the jobs.Any advice, links or references greatly appreciated ;)[edit]After a bit more searching, I think this is known in Computer Science as the Job Shop Scheduling problem. Anyone studied this area?[Edited by - Hodgman on June 14, 2009 10:31:32 PM]
  This is very high-level and probably not exactly what you're looking for, but Millington's "Artificial Intelligence for Games" has some information on basic job scheduling algorithms in the context of budgeting AI per frame. Specifically, some ideas he introduces are frequency scheduling, load balanced scheduling, hierarchical scheduling, and priority scheduling. He also briefly introduces Wright's method for determining which phase to assign an incoming job to, as well as his own analytic method for it. The book comes with a CD with implementations for most of the algorithms discussed; the CD contents are freely downloadable from the book's website.   ;  Depending on whether you want something superoptimocustimzable, or simply something nottooawful, the easiest way is to order the nodes in your DAG in a depth first fashion. From there you can place the nodes in to pools where all nodes in a given pool can be executed in parallel.Something like:# I hope you know a little Python.# But this is a translation from C++:# http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/file_dependency_example.htmldepthlist = depth_first_gather(mydag)pools = {} # maps node to pool indexfor node in depthlist:    # Find the maximum pool of any incoming node    maxpool = 0    for edge in node.incoming():   pool = pools[edge.head]   maxpool = max(pool, maxpool)    # The pool for the current node is one plus# the maximum pool of any incoming node    pools[node] = maxpool + 1# Now reorganise in to listspoollists = defaultdict(list)for node, pool in pools.iteritems():    poollists[pool].append(node)poollists = poollists.items()poollists.sort()poollists = [pl[1] for pl in poollists]# poollists is now a list of lists. # All nodes in each list can be executed in parallel.# Once a list has been completely processed, you can move on to the next one.I'm not sure if it's what you want, but it's working really rather well for me as part of a build-system "scheduler".   ;  I think the best starting point for solving any algorithmic problem is to take a look at the problem catalogue of Steve Skiena's Algorithm Design Manual. It has a chapter about job scheduling as well, and a good list of implementations and references.If you want more specific help from this forum, you should describe your problem in more detail. For example, do you need to find an optimal schedule and do you have a running time constraint for the algorithm?In any case, the first thing you'll have to do is to perform a topological sort on your graph, as pointed out by the previous poster.   ;  Thanks guys, you led to towards a few days of part-time reading and contemplation.I'm just thinking out loud now, but if anyone wants to point out flaws or problems that I might face then please do so.I think for simplicity's sake, I'm not going to implement task-level parallelism, only data-level parallelism.Tasks will be scheduled in a sequential order, and this order will be followed by all threads:Thread 0: T1---| T2---| T3---|Thread 1: T1---| T2---| T3---|Thread 2: T1---| T2---| T3---|So given a DAG of tasks, the schedule will basically say "Do task 1 on all threads, then do task 2 on all threads, etc...".I've just got to ensure that if task 1 depends on task 2, then #2 is done first, and I check a 'completion flag' has been set before starting #1. A near-enough-is-good-enough ordering should be fine.The code that waits for dependence to be completed is independent of the schedule (it's a feature of the class that executes a schedule, not part of the scheduler). So all the scheduler has to do is ensure the ordering is correct, some other system will insert the necessary 'waits' in like so:Thread 0: T2--| wait  T1---|Thread 1: T2--------| T1---|Thread 2: T2---| wait T1---|As an optimization, the scheduler could try keep dependant tasks separated if possible, so that waiting will be less likely (by the time T1 executes, T2's completion flag will likely be set, meaning no waiting will occur):Thread 0: T2--| T3---| T1---|Thread 1: T2--------| T3---| T1---|Thread 2: T2---| T3---| T1---|[Profiling/Timing]Whenever a task is executed, it's run time (on each thread) will be recorded.[Load Balancing]Every task is executed on all threads, but some tasks still might run serially e.g. in a 3-thread system, a task may just run on thread 0, and do no work at all on thread 1 / 2.When a task is executed, it is told the ID of the currently executing thread, and a "range" of the problem to tackle.By default (in a 3 thread system) thread 0 would be given the range of 0-33, thread 1 given 34-67 and thread 2 given 68-100. The task can then use these range values to split up the problem as it sees fit.Each task can indicate whether it actually supports these range values or not. Tasks with no support will always be given these default ranges (but will likely ignore them, spreading out work as it sees fit, black-box style), but other tasks may have their ranges calculated dynamically for load-balancing.Given two tasks, T1 and T2:Say T1 doesn't parallelise very well - T1 does not support dynamic load-balancing and always does most of it's work on thread 0.This will throw the rest of the schedule out of whack:T1-------| T2---|T1---| T2---|T1---| T2---|Based on past timings, the scheduler should know that T1 does not spread work evenly, and will then generate weightings to be passed to T2.It could use the ranges of 0:0-10, 1:11-55, 2:56-100 in order to balance the load.T1-------| T2-|T1---| T2----|T1---| T2----|;Quote:Original post by HodgmanThanks guys, you led to towards a few days of part-time reading and contemplation.I'm just thinking out loud now, but if anyone wants to point out flaws or problems that I might face then please do so.I think for simplicity's sake, I'm not going to implement task-level parallelism, only data-level parallelism.Tasks will be scheduled in a sequential order, and this order will be followed by all threads:Thread 0: T1---| T2---| T3---|Thread 1: T1---| T2---| T3---|Thread 2: T1---| T2---| T3---|So given a DAG of tasks, the schedule will basically say "Do task 1 on all threads, then do task 2 on all threads, etc...".I've just got to ensure that if task 1 depends on task 2, then #2 is done first, and I check a 'completion flag' has been set before starting #1. A near-enough-is-good-enough ordering should be fine.This "assembly-line" style pattern can be found in a bunch of places if you want to read further e.g. "Patterns for Parallel Programming" by Mattson et al and "Programming with POSIX Threads" by Butenhof, where it's called the "Pipeline pattern" in each case.Quote:The code that waits for dependence to be completed is independent of the schedule (it's a feature of the class that executes a schedule, not part of the scheduler). So all the scheduler has to do is ensure the ordering is correct, some other system will insert the necessary 'waits' in like so:Thread 0: T2--| wait  T1---|Thread 1: T2--------| T1---|Thread 2: T2---| wait T1---|As an optimization, the scheduler could try keep dependant tasks separated if possible, so that waiting will be less likely (by the time T1 executes, T2's completion flag will likely be set, meaning no waiting will occur):Thread 0: T2--| T3---| T1---|Thread 1: T2--------| T3---| T1---|Thread 2: T2---| T3---| T1---|You can go a more "implicit" route by using a future's mechanism e.g.double task1();float task2();int task3(const future<double> &d, const future<float> &f);void task4(const future<int> &i, const future<float> &f);Here task3 might take the output of task1 and task2. task4 might take the output of task3 and task2. By expressing the dependencies as futures the scheduling becomes implicit.Of course, you have to implement a future<> mechanism, but in the simplest case it's not a whole lot more than a wrapper around a condition variable. Here's a canned implementation you might want to play with. It spins up a new thread each time all existing threads are occupied with work. This probably isn't what you want, but you could use a fixed-size thread-pool underneath instead.Just some more food for thought...   