The Limits of TDMA Based Memory Access Scheduling
Tuesday, 6 December 2011
I have published a technical report, co-authored with Martin Schoeberl. This paper was first written during the JEOPARD project. We wanted to see how well the TDMA (time-division multiple access) policy for bus arbitration could work in ideal circumstances, i.e. if the arbiter was somehow able to predict all requests that might be issued over the bus. The unfortunate finding is that even if the arbiter was able to do this, the devices attached to the bus would still spend much of their time blocked, waiting for the bus... an effect which would become worse and worse as their number increased. That is, TDMA won't scale.
Abstract:
In a multicore system, several CPUs frequently require access to a shared memory. If this access is required to be time-predictable to enable worst-case execution time (WCET) analysis of tasks, a form of TDMA based bus arbitration is usually used. A global TDMA schedule controls when each CPU may make use of the bus. This schedule is normally static. It has been suggested that the TDMA schedule could be specialized to reduce the WCET for particular tasks. In this paper, we show that there is a hard limit to the potential of this technique within a general-purpose system. We simulate single- path tasks running within a multitask, multicore system and apply TDMA slot scheduling on the memory access traces. For medium numbers of CPU cores and low memory latencies, CPU utilization can be improved by up to 25%, but as more cores are used and memory latency increases, the bus gets saturated and the difference between a specialized schedule and a generic schedule disappears.