Intel Graphics Driver Sees Fair Low-Latency Scheduling Inspired In Part By BFS/MuQSS

Longtime open-source Intel Linux graphics driver developer Chris Wilson on Sunday sent out a big patch series that introduces a new fair low-latency scheduler for the Intel kernel graphics driver.

This fair low-latency scheduling code is inspired in part by the former BFS Linux CPU scheduler and its current incarnation as MuQSS. Here is how Chris sums up this new scheduler implementation:

The first "scheduler" was a topographical sorting of requests into priority order. The execution order was deterministic, the earliest submitted, highest priority request would be executed first. Priority inherited ensured that inversions were kept at bay, and allowed us to dynamically boost priorities (e.g. for interactive pageflips).

The minimalistic timeslicing scheme was an attempt to introduce fairness between long running requests, by evicting the active request at the end of a timeslice and moving it to the back of its priority queue (while ensuring that dependencies were kept in order). For short running requests from many clients of equal priority, the scheme is still very much FIFO submission ordering, and as unfair as before.

To impose fairness, we need an external metric that ensures that clients are interpersed, we don't execute one long chain from client A before executing any of client B. This could be imposed by the clients by using a fences based on an external clock, that is they only submit work for a "frame" at frame-interval, instead of submitting as much work as they are able to. The standard SwapBuffers approach is akin to double bufferring, where as one frame is being executed, the next is being submitted, such that there is always a maximum of two frames per client in the pipeline. Even this scheme exhibits unfairness under load as a single client will execute two frames back to back before the next, and with enough clients, deadlines will be missed.

The idea introduced by BFS/MuQSS is that fairness is introduced by metering with an external clock. Every request, when it becomes ready to execute is assigned a virtual deadline, and execution order is then determined by earliest deadline. Priority is used as a hint, rather than strict ordering, where high priority requests have earlier deadlines, but not necessarily earlier than outstanding work. Thus work is executed in order of 'readiness', with timeslicing to demote long running work.

The Achille's heel of this scheduler is its strong preference for low-latency and favouring of new queues. Whereas it was easy to dominate the old scheduler by flooding it with many requests over a short period of time, the new scheduler can be dominated by a 'synchronous' client that waits for each of its requests to complete before submitting the next. As such a client has no history, it is always considered ready-to-run and receives an earlier deadline than the long running requests.

For now the scheduler is just sitting as part of these 28 patches. It will be interesting to see how the review goes and if this improved Intel graphics scheduler code gets mainlined in the near future.