Latency-optimized / job priorities / soft real-time parallel scheduling

[mratsim]

Most work-stealing schedulers work in a LIFO manner, the worker works on the task it just enqueued. The main reason is that this maximizes locality (the data needed for the just enqueued task is probably hot in cache).
As such, those schedulers are optimizing throughput (doing all the work as fast as possible) but are fundamentally unfair as the first task enqueued might not be done as soon as possible but only when there is nothing else to do. This is also how Weave works.

In many cases, for example:

• (soft) realtime audio-processing or video-processing
• game engines
• services where FIFO is expected, for example a service that processes a stream of images or a services that have users post tasks to it with user expecting the first one to be the first scheduled.

we want to optimize latency:

1. Assume that for optimizing latency, the early tasks scheduled are those that are logically needed first, i.e. FIFO scheduling
2. We might want to support job priorities.

There are several papers on soft-real-time scheduler (i.e. "Earliest Deadline First" scheduling) see:

• Saifullah et al, Multi-core Real-Time Scheduling for Generalized Parallel Task Models, https://www.cse.wustl.edu/~lu/papers/rtss11.pdf
• Cláudio Roberto Ribeiro Maia, PhD Thesis, Scheduling Parallel Real-Time Tasks inMultiprocessor Platforms, https://repositorio-aberto.up.pt/bitstream/10216/117806/2/304244.pdf
• Li et al, Randomized Work-Stealing for large scale soft real-time systems, https://www.cse.wustl.edu/~kunal/resources/Papers/fedws.pdf

However it seems relatively straightforward to have a latency optimized Weave switch.

FIFO scheduling

Instead of pop-ing the last task enqueued from the deque we can just pop the first task enqueued.
By default Weave add from the front

weave/weave/scheduler.nim

Line 275 in bf2ec2f

myWorker().deque.addFirst task

and pops from the front

weave/weave/scheduler.nim

Lines 137 to 144 in bf2ec2f

	proc nextTask*(childTask: static bool): Task {.inline.} =
	# TODO: rewrite as a finite state machine
	profile(enq_deq_task):
	if childTask:
	result = myWorker().deque.popFirstIfChild(myTask())
	else:
	result = myWorker().deque.popFirst()

We can just pop from the back instead.

Job priorities

Job priorities are important for certain workload for example game engines

• https://gdcvault.com/play/1022186/Parallelizing-the-Naughty-Dog-Engine
• http://twvideo01.ubm-us.net/o1/vault/gdc2015/presentations/Gyrling_Christian_Parallelizing_The_Naughty.pdf

Supporting priorities in Weave should just require adding a per-thread priority queue for priority tasks (and keep the deque for "best-effort tasks"). No need to solve the complex lock-free concurrent priority queue problem (and the associated thread-safe memory reclamation) when using a message-passing based runtime ✌️.

[mratsim]

superceded by #123 which hopefully proposes an elegant path forward for working with Weave as a threadpool that plays well with FIFO needs.

And as it process jobs in the order they were submitted, users can do their own priority queue before enqueueing them into with job system and think about whether priority 1 or priority 10 is the highest ;).