Investigation of Scratchpad Memory for Preemptive Multitasking
Thursday, 6 December 2012
The paper "Investigation of Scratchpad Memory for Preemptive Multitasking" was presented by my colleague Rob Davis at RTSS this week. This paper was discussed in an earlier post.Rob kindly agreed to travel to RTSS to present it. I couldn't easily go, as I was travelling to Vienna the previous week.
Here is the paper: http://www.jwhitham.org/pubs/rtss12.pdf
Here is the presentation: http://www.jwhitham.org/pubs/srpd_rtss12_pres.pdf
There is also some experiment software and an FPGA design: http://www.jwhitham.org/pubs/msrs-dist-3.tar.bz2
The paper is a comparison of two ways to handle the local memory within an embedded real-time system that is also preemptively multitasking. Each task makes use of the local memory. With a cache, a preempting task evicts blocks used by the preempted task, which will have to reload them. With a scratchpad memory (SPM), we have to somehow save the state of the SPM during preemption, so that the preempted task can continue from where it left off.
The work is a formalised version of an earlier paper and I'm grateful to all of the coauthors for providing so much help in improving my earlier work and applying it to this comparison. It was written with the help of Sebastian Altmeyer (from Saarland University), Rob Davis and Neil Audsley (from York) and Claire Maiza (from Verimag, INP Grenoble).
The conclusion of the paper is that the SPM 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.
Most of the time, cache and SPM are actually quite similar as far as schedulability is concerned. This means that the choice between them can depend on other design considerations. This is good news for fans of SPM. The SPM equivalent of "cache related preemption delay" (CRPD), which is described in the paper, may also be a useful basis for further work.
Here is the 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 cache.