WCET Centric Data Allocation to Scratchpad Memory
- 4 October 2006
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 10 pp.-232
- https://doi.org/10.1109/rtss.2005.45
Abstract
Scratchpad memory is a popular choice for on-chip storage in real-time embedded systems. The allocation of code/data to scratchpad memory is performed at compile time leading to predictable memory access latencies. Current scratchpad memory allocation techniques improve the average-case execution time of tasks. For hard real-time systems, on the other hand, worst case execution time (WCET) is a key metric. In this paper, we propose scratchpad allocation techniques for data memory that aim to minimize a task's WCET. We first develop an integer linear programming (ILP) based solution which constructs the optimal allocation assuming that all program paths are feasible. Next, we employ branch-and-bound search to more accurately construct the optimal allocation by exploiting infeasible path information. However, the branch-and-bound search is too time-consuming in practice. Therefore, we design fast heuristic searches that achieve near-optimal allocations for all our benchmarksKeywords
This publication has 14 references indexed in Scilit:
- A WCET-Oriented Static Branch Prediction Scheme for Real Time SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Improving WCET by applying a WC code-positioning optimizationACM Transactions on Architecture and Code Optimization, 2005
- A Compiler-Based Approach for Dynamically Managing Scratch-Pad Memories in Embedded SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004
- Dynamic overlay of scratchpad memory for energy minimizationPublished by Association for Computing Machinery (ACM) ,2004
- Scratchpad memory: a design alternative for cache on-chip memory in embedded systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An optimal memory allocation scheme for scratch-pad-based embedded systemsACM Transactions on Embedded Computing Systems, 2002
- SimpleScalar: an infrastructure for computer system modelingComputer, 2002
- Storage allocation for embedded processorsPublished by Association for Computing Machinery (ACM) ,2001
- On-chip vs. off-chip memoryACM Transactions on Design Automation of Electronic Systems, 2000
- Predicting program execution times by analyzing static and dynamic program pathsReal-Time Systems, 1993