WCET-Guided Optimal Data Allocation to Scratchpad Memory

Scratchpad memory is a popular choice for on-chip storage in real-time embedded systems. The allocation of program elements to scratchpad memory is performed at compile time leading to predictable memory access latencies. Current scratchpad memory allocation techniques mainly improve the average-case execution time of tasks. For hard real-time systems, however, worst case execution time (WCET) is a more important key metric. In this paper, we propose scratchpad allocation techniques for data memory that aim to minimize a tasks WCET. We first analyze main problem of optimal allocation process and current works of allocation algorithms. Then, based on common degree of variables, we design a new heuristic searches algorithm that achieves better optimal performance for all our benchmarks.