abouteiller
commented
8 years ago Original comment by Thomas Herault (Bitbucket: herault, GitHub: therault).
I discussed with Reazul about this, I will try to summarize my point of view here:
- I agree there is a bug
- I consider that this bug is in the scheduling in general, not with the hbbuffer in particular
- I believe that there are multiple solutions, and I'll describe two lower in this mail
Concerning the bug:
- priority was never considered by the scheduling as a hard constraint, only as a user-level hint
- only AP follows strictly priorities. Other schedulers might completely ignore this, and I think that it is a feature we should keep.
- The issue is that with DAGUE_HOOK_RETURN_AGAIN, these task must be delayed, and other tasks that have not been tried must be tried, or we may enter a livelock
- Note that this appears for the superscalar interface, but the bug is not limited to it: a user' body that returns this value might suffer from the same issue
Solutions:
- Basically, we cannot keep unfair schedulers. Or more precisely, schedulers must be aware that some tasks that have not been tried before must be tried from time to time, or no progress might happen.
Enrich the scheduler API
- One way to do so would be to add a function to the scheduler interface:
- postpone() would take a task that returned DAGUE_HOOK_RETURN_AGAIN, and keep it for later selection
- the contract of the scheduler is that if there are tasks that have been pushed with schedule(), and tasks that have been pushed with postpone(), select() cannot return always tasks under postpone(), it has to return tasks under schedule().
- How and when to do so remains a scheduler decision
- AP would implement both schedule() and postpone() with the same function, simply by altering the priority of tasks to alternate between tasks of one category or the other
- LFQ, PBQ, would simply push_back() the tasks received by postpone() into the system_queue, ensuring that tasks received by schedule() are selected before.
Solve the problem at the higher level
- Another approach is to enforce a general policy for postponed tasks:
- in __dague_schedule, we define a dequeue of postponed tasks (per thread)
- If a task returns DAGUE_HOOK_RETURN_AGAIN, it is pushed_back to this thread postponed dequeue
- Each thread keeps a counter postponed_tasks_retry (MCA parameter), if select() returns NULL, or every postponed_tasks_retry executed tasks, tasks in the postponed dequeue must be tried instead of calling select()
I prefer the first approach, even if it requires to update all schedulers, because this leaves the policy to the scheduler, and does not enforce a general behavior.
I can do this first solution quickly, to show how it would look, unless people have a strong different opinion.
Original report by Reazul Hoque (Bitbucket: rhoque_icl, ).
To resolve anti-dependence in DTD, we thought of using DAGUE_HOOK_RETURN_AGAIN from prepare_input of a task that will write on a data having readers count of > 0.
The test generates a sequence of tasks(with the following operation on the same data) like below:
W->R->R->R->R->R->W
We generate 4 sequences like this. Think of a 2x2 matrix and for each tile we generate the above sequence. So at startup we have 4 W tasks on the 4 tiles (1 W task for each tile).
The LFQ has local hbbuffer of size 4. We ran with a single thread. The hbbuffer had all of it's cell filled with the startup W task on each tile.
After the first W task on the first tile execute we discover the subsequent 5 R task and the last W task on that tile. We will try to push all the discovered tasks (5 R tasks and the last W task) in the local hbbuffer. We have just one slot empty in the hbbuffer and because of the order in which we discover task we push the last task in there( which is the last W of the first tile). Point to be noted: all tasks starts with the same priority of 0. The 5 R(Read) tasks on that tile gets in the system queue.
The scheduler then pops the first task in the buffer which is the last W on the first tile. We go to the prepare_input of that task and return with DAGUE_HOOK_RETURN_AGAIN. We then decrease the priority of the task(last W on the first tile) and push it back. While pushing it back we push it in the same spot in the hbbuffer as before.
This steps repeat for the other 3 tiles, and we end up with the last W task on each tile in the hbbuffer. All the intermediate READ tasks on each tile ends up in the system queue. The scheduler then keeps popping the same last W task on each tile from the hbbuffer and we have a lock.