search

HadrienG2 / phalanstery

Experiments with user-mode tasking in Ada
GNU General Public License v3.0
4 stars 0 forks source link

Compare queue-based scheduling with stack-based scheduling #28

Open HadrienG2 opened 7 years ago

HadrienG2 commented 7 years ago

Scheduling work on a FIFO queue has many advantages. First, it is intuitive: if you push a set of work-item to an executor in a certain order, you expect it to carry it out in that order. Second, it is fair: new tasks cannot prevent old tasks from ever being scheduled.

However, from the point of view of CPU cache locality and in the presence of recursive parallelism (see #27 ), stacks may be more appropriate, as they ensure that new tasks directly follow from old ones. In order to optimize your CPU cache usage, you probably want to finish a parallel quicksort before you move on to the other tasks that were spawned after that.

Thus, we may want to move to double-ended queues for task scheduling, and carefully study the implications of pushing jobs in one direction or another.

HadrienG2 commented 7 years ago

I provided clearer plans about a possible work queue redesign in this document : https://github.com/HadrienG2/phalanstery/blob/master/doc/Scalable_Recursive_Queue.pdf