I am wondering what would happen if the task system found that the header task can not be run because of some dependencies. Would it stall the task? Or grab it out and enqueue it again?
I would also like to know more about the detail details of task systems that support non-independent task.
althalus
I believe if there are dependencies, the only thing that would happen is that no other cores would be able to steal that task since by the time the task which it is dependent on is done running, the next dependent task can be grabbed by the same core.
So if the header task can not be run, the scheduler simply finds the next task which can be run instead of stalling until the dependencies are fulfilled.
cyl
To do the Topological sort, we have to do something like the DFS first, isn't that a large overhead which is linear to the data amount?
ojd
@PandaX: There are several ways of going about it and they all have various benefits. Another possible implementation (that I actually like) is having the task handle its own dependency management, which can be nice if you're writing your own scheduler since you can get the 0-dependency version working very quickly and then have each task use whatever works best for it.
@dzxburning: That's one way of doing it. A slight problem is that in practice, it can interact poorly with work-stealing. Some work stealing techniques require pulling multiple tasks over. Maintaining a reasonable work balance becomes difficult in this case. For example, one thread might pull over a task that's waiting for another task, leaving it in exactly the same position it was in before, or worse if that job would have actually performed better on its original thread. Some work-stealing algorithms also require pulling over half the queue at a time, which can make this even worse.
I am wondering what would happen if the task system found that the header task can not be run because of some dependencies. Would it stall the task? Or grab it out and enqueue it again?
I would also like to know more about the detail details of task systems that support non-independent task.
I believe if there are dependencies, the only thing that would happen is that no other cores would be able to steal that task since by the time the task which it is dependent on is done running, the next dependent task can be grabbed by the same core.
I guess in this task system, the scheduler chooses which task to run first according to topological order (https://en.wikipedia.org/wiki/Topological_sorting) instead of FIFO order.
So if the header task can not be run, the scheduler simply finds the next task which can be run instead of stalling until the dependencies are fulfilled.
To do the Topological sort, we have to do something like the DFS first, isn't that a large overhead which is linear to the data amount?
@PandaX: There are several ways of going about it and they all have various benefits. Another possible implementation (that I actually like) is having the task handle its own dependency management, which can be nice if you're writing your own scheduler since you can get the 0-dependency version working very quickly and then have each task use whatever works best for it.
@dzxburning: That's one way of doing it. A slight problem is that in practice, it can interact poorly with work-stealing. Some work stealing techniques require pulling multiple tasks over. Maintaining a reasonable work balance becomes difficult in this case. For example, one thread might pull over a task that's waiting for another task, leaving it in exactly the same position it was in before, or worse if that job would have actually performed better on its original thread. Some work-stealing algorithms also require pulling over half the queue at a time, which can make this even worse.