Submission: Investigation of Scratchpad Memory for Preemptive Multitasking
Wednesday, 16 May 2012
Today I submitted a paper to RTSS. It's a comparison of two ways to handle the local memory within an embedded real-time system that is also preemptively multitasking. If the local memory is cache, then preemption can evict useful cache blocks (i.e. cache blocks that are going to be reused by the preempted task). This increases the response time of the preempted task, because when an evicted blocked are accessed again, there is a cache miss. The effect has been named cache related preemption delay (CRPD) in previous work.If the local memory is scratchpad memory (SPM) then we cannot rely on tasks to reload the evicted blocks automatically. Instead the preempting task (or the OS) must somehow save the state of SPM upon preemption and restore it upon return. (This is the subject of an earlier paper.) This also increases the response time of the preempted task, because saving and restoring the SPM state takes time. We call this SPM-related preemption delay (SRPD).
So, in this paper, we are comparing CRPD and SRPD, to discover in what circumstances each is superior. The result is that SRPD is better if there is a lot of pressure for the local memory resource, because many tasks are sharing it. This happens for large task sets (many tasks) and when each task uses a large proportion of the local memory. More generally, CRPD and SRPD are incomparable, and there will always be task sets where one is better than the other.
This paper was coauthored with Sebastian Altmeyer (from Saarland University), with Rob Davis and Neil Audsley (from York) and Claire Maiza (from Verimag, INP Grenoble).
Abstract:
We present a multitasking scratchpad memory reuse scheme (MSRS) for the dynamic partitioning of scratchpad memory between tasks in a preemptive multitasking system. We specify a means to compute the worst-case response time (WCRT) and schedulability of task sets executed using MSRS. Our scratchpad-related preemption delay (SRPD) is an analog of cache-related preemption delay (CRPD), proposed in previous work as a way to compute the worst-case cost imposed upon a preempted task by preemption in a multitasking system. Unlike CRPD, however, SRPD is independent of the number of tasks and the local memory size.
We compare SRPD with CRPD by experiment and determine that neither dominates the other, i.e. either may be better for certain task sets. However, MSRS leads to improved schedulability versus cache when contention for local memory space is high, either because the local memory size is small, or because the task set is large, provided that the cost of loading blocks from external memory to scratchpad is similar to the cost of loading blocks into cach.