Priority inversion when executing jobs of heterogeneous length

[JoeyBF]

We're using rayon to power our mathematical software for HPC and we're running into this issue: SpectralSequences/sseq#105. Here's a high-level overview.

We have two kinds of jobs, long ones that take several hours, and short ones that take milliseconds. Short jobs are spawned by par_iter_mut, they are independent and do not spawn other jobs themselves. Long jobs on the other hand have nontrivial dependencies on each other. We schedule them using channels and spawn them using spawn on an in_place_scope. Each long job will spawn potentially millions of short jobs that will need to finish before the long job returns. The inversion happens in the following situation:

• Thread 1 starts computing long job A.
• Thread 1 enters the par_iter_mut, which calls join_context, which itself spawns (say) two short jobs a and b.
• Thread 1 starts executing a while thread 2 starts b.
• Some other thread 3 finishes a long job, and now a new long job B is available.
• Thread 1 finishes the short job, sees that thread 2 is still busy, and starts looking for other things to do in the meantime.
• Thread 1 picks up job B.
• Thread 2 finishes, but by then thread 1 is stuck in B, and job A stalls.

Note that this is different from #630 because in our case the short jobs are called by the long jobs, and I also don't see how affinity would solve this problem.

I tried building different threadpools in https://github.com/JoeyBF/sseq/tree/bandaid, and while the performance seems to improve, the logs still show that long jobs sometimes stall.

My proposal is to implement priorities in a very naive way. It would be sufficient to have to ability to tag jobs with priority values (say an i32 defaulting to 0) and to have access to a new join_priority function that only allows waiting threads to steal jobs of equal or higher priority relative to the job it just finished

[cuviper]

I tried building different threadpools in https://github.com/JoeyBF/sseq/tree/bandaid, and while the performance seems to improve, the logs still show that long jobs sometimes stall.

I don't have the domain knowledge for your problem, but AFAICS you're only separating "matrix" and "nassau" pools there -- are those your A and B type of jobs? If you have multiple "matrix" jobs running, then those can still steal from each other in that shared pool. But it looks like you are creating "nassau" pools on the fly each time, so those should run independently, as long as they don't also call into that shared "matrix" pool.

My proposal is to implement priorities in a very naive way. It would be sufficient to have to ability to tag jobs with priority values (say an i32 defaulting to 0) and to have access to a new join_priority function that only allows waiting threads to steal jobs of equal or higher priority relative to the job it just finished

Wouldn't long jobs A and B have the same priority? Then "Thread 1 picks up job B" could still happen...

However, we don't have any support in our data structures (from crossbeam-deque) to be picky about which job we will steal, unless we create completely separate deques by priority and try all that are "allowed".

[JoeyBF]

Yeah "matrix" jobs are the short ones and "nassau" jobs are the long ones. It's ok if all the matrix jobs steal from each other because they never stall (in practice each call to par_iter_mut creates a ton of jobs but they collectively finish within a few seconds).

The function where the "nassau" pool is created is essentially like a main function, and the software will spend all of its time (potentially weeks) in that single call to in_place_scope. So the "nassau" pool is unique in practice.

Wouldn't long jobs A and B have the same priority? Then "Thread 1 picks up job B" could still happen...

In that case thread 1 would be waiting for jobs inside of join_priority with a high priority, so it wouldn't be allowed to start lower priority jobs like job B.

However, we don't have any support in our data structures (from crossbeam-deque) to be picky about which job we will steal, unless we create completely separate deques by priority and try all that are "allowed".

Switching to a priority queue does seem like a pretty big change. In our case we could probably do something really naive like popping jobs until we find one with a high enough priority and requeue the others, but that sounds inefficient in general