Supporting Real-Time Parallel Task Models with Work-Stealing
Ref: HURRAY-TR-120301 Publication Date: 16, Mar, 2012
Supporting Real-Time Parallel Task Models with Work-Stealing
Ref: HURRAY-TR-120301 Publication Date: 16, Mar, 2012Abstract:
Dynamic parallel scheduling using work-stealing has gained popularity in academia and industry for its good performance, ease of implementation and theoretical bounds on space and time. Cores treat their own double-ended queues (deques) as a stack, pushing and popping threads from the bottom, but treat the deque of another randomly selected busy core as a queue, stealing threads only from the top, whenever they are idle.
However, this standard approach cannot be directly applied to real-time systems, where the importance of parallelising tasks is increasing due to the limitations of multiprocessor scheduling theory regarding parallelism. Using one deque per core is obviously a source of priority inversion since high priority tasks may eventually be enqueued after lower priority tasks, possibly leading to deadline misses as in this case the lower priority tasks are the candidates when a stealing operation occurs.
Our proposal is to replace the single non-priority deque of work-stealing with ordered per-processor priority deques of ready threads. The scheduling algorithm starts with a single deque per-core, but unlike traditional work-stealing, the total number of deques in the system may now exceed the number of processors. Instead of stealing randomly, cores steal from the highest priority deque.
Cláudio Maia
Luis Miguel Nogueira
Luis Miguel PinhoDocument:
View
DownloadPoster presented in DATE'12 Fourth Friday Workshop on Designing for Embedded Parallel Computing Platforms: Architectures, Design Tools, and Applications (DEPCP 2012).
Dresden, Germany.
Record Date: 16, Mar, 2012