Friday, 14 October 2011

Submitted: Explicit Reservation of Local Memory in a Predictable, Preemptive Multitasking Real-time System

I have submitted a paper to the RTAS conference. Neil and myself had been thinking about writing this paper for some time, because there are all sorts of questions about good ways to share scratchpad memory (SPM) space between multiple tasks. There's an obvious naive solution, namely splitting the SPM space into partitions, and assigning each one to a task statically. But this doesn't make good use of space. And there's another naive solution, where the whole SPM space is treated as part of the execution context, and the whole space is reloaded when preemption occur. But this doesn't make good use of time.

In this paper we tried to come up with a middle ground which would make good use of both space and time, by allowing each task to set its own tradeoff between context-switching time and available SPM space. We specified an implementation and even came up with a small operating system to demonstrate the principles.

Abstract:
This paper proposes Carousel, a mechanism to manage local memory space, i.e. cache or scratchpad memory (SPM), such that inter-task interference is completely eliminated. The cost of saving and restoring the local memory state across context switches is explicitly handled by the preempting task, rather than being imposed implicitly on preempted tasks. Unlike earlier attempts to eliminate inter-task interference, Carousel allows each task to use as much local memory space as it requires, permitting the approach to scale to large numbers of tasks.

Carousel is experimentally evaluated using a simulator. We demonstrate that preemption has no effect on task execution times, and that the Carousel technique compares well to the conventional approach to handling interference, where worst-case interference costs are simply added to the worst-case execution times (WCETs) of lower-priority tasks.