Paper Info
Title
WCET-aware data selection and allocation for scratchpad memory
Abstract
In embedded systems, SPM (scratchpad memory) is an attractive alternative to cache memory due to its lower energy consumption and higher predictability of program execution. This paper studies the problem of placing variables of a program into an SPM such that its WCET (worst-case execution time) is minimized. We propose an efficient dynamic approach that comprises two novel heuristics. The first heuristic iteratively selects a most beneficial variable as an SPM resident candidate based on its impact on the k longest paths of the program. The second heuristic incrementally allocates each SPM resident candidate to the SPM based on graph coloring and acyclic graph orientation. We have evaluated our approach by comparing with an ILP-based approach and a longest-path-based greedy approach using the eight benchmarks selected from Powerstone and Mälardalen WCET Benchmark suites under three different SPM configurations. Our approach achieves up to 21% and 43% improvements in WCET reduction over the ILP-based approach and the greedy approach, respectively.
Year
DOI
Venue
2012
10.1145/2248418.2248425
LCTES
Keywords
Field
DocType
longest-path-based greedy approach,ilp-based approach,scratchpad memory,efficient dynamic approach,program execution,greedy approach,spm resident candidate,wcet-aware data selection,wcet reduction,acyclic graph orientation,different spm configuration,lardalen wcet benchmark suite,graph coloring,embedded system,memory allocation,longest path,worst case execution time,cache memory
Heuristic,Worst-case execution time,CPU cache,Computer science,Parallel computing,Scratchpad memory,Real-time computing,Directed acyclic graph,Heuristics,Energy consumption,Graph coloring
Conference
Volume
Issue
ISSN
47
5
0362-1340
Citations 
PageRank 
References 
15
0.59
26
Authors
3
Name
Order
Citations
PageRank
Qing Wan1295.03
Hui Wu26613.24
Jingling Xue31627124.20