WCET-Aware Stack Frame Management in Embedded Systems
"Explore the importance of managing stack frames in embedded systems using scratchpad memories for strict timing constraints and ensuring timing correctness by guaranteeing the absence of missed deadlines. Learn about challenges in static timing analyses and the benefits of Scratchpad Memories. Discover how Stack Frame Management plays a crucial role in optimizing system performance." (Character count: 375)
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
WCET-Aware Stack Frame Management of Embedded Systems using Scratchpad Memories Yooseong Kim, Mohammad Khayatian, Aviral Shrivastava Arizona State University CML
Hard Real-time Systems Strict timing constraints Tasks have deadlines to finish execution Sensing Deadlines! Actuation Timing determines correctness, not just performance Missing a deadline can be catastrophic! CML CML Image credit: JasonParis@Flickr Web page: aviral.lab.asu.edu
Ensuring Timing Correctness Guarantee the absence of missed deadlines Worst-case execution time (WCET) analysis occurrences Number of Execution Time WCET How? Testing based on measurement No Guarantee! Static analysis Use structural information of HW/SW CML CML Web page: aviral.lab.asu.edu
Challenges of Static Timing Analyses WCET is Pessimistic Microarchitectural state uncertainties Cache, branch predictors, pipelines, All execution scenarios Observed by testing Frequency of occurrence Analysis pessimism Execution Times WCET calculated by static analysis WCET observed by testing WCET CML CML Web page: aviral.lab.asu.edu
Scratchpad Memories (SPM) : A Promising Alternative Raw directly-addressable SRAM SPM 0 1 DMA load A to 0 DMA load B to 1 DMA load C to 0 Explicitly controlled by DMA (Direct Memory Access) A A B Provide time predictability C B Determine a memory access is a hit or miss Can completely avoid preemption delay 1 1 2 2 3 time CML CML Web page: aviral.lab.asu.edu
Stack Frame Management Perform code transformation Store frame stack in SPM before a function call Load frame stack from SPM after a function call Inserted code before a call DMA_store(); Sp_reset(); // DMA stores the stack in the main memory // reset the stack pointer Foo(); // call a function DMA_load(); Sp_restore(); // restore the stack pointer // DMA loads the stack from the main memory Inserted code after a call CML CML Web page: aviral.lab.asu.edu
Virtual Stack in Main Memory Moving stack frames needs previous execution history Previously evicted stack frames Main Memory SPM CPU Stack Evict/Restore stack frames by DMA CML CML Web page: aviral.lab.asu.edu
Problem Formulation from CFG Use inline Control Flow Graph (CFG) presentation ? is set of all basic blocks (??,??,?? ?) ? and are set of basic blocks containing Call and Return ?? A() { } B(); ?? ? ?? ?? = ? B(); ?? ?? ? \(? ) ?? ?? = ? return ; B() { } ?? ?? ?? ?? = ? return; CML CML (b) (a) Web page: aviral.lab.asu.edu
Formulate as a Minimization Problem Minimize the WCET (???) of the whole program. min??? ? ?? and ?? are the start and final basic blocks ?? execution frequency of basic block ? ?? Management cost of basic block ? ?? execution time of basic block ? ? is set of edges ?? ? ?? ?,? ?, ?? ?? + ?? ?? + ?? ??? = ??? (??? + ???) CML CML Web page: aviral.lab.asu.edu
Decision Variable Management Cost (??): ??= ????? if ??= 1 0 ? ?, if ??= 0 ??= ????? if ???(?)= 1 0 ? , if ???(?)= 0 ???? ,???? overheads of evicting and restoring ?? decision variable ??? ? decision variable of the called basic block CML CML Web page: aviral.lab.asu.edu
Testbed 13 Benchmarks from M lardalen WCET suite ARMv4 ISA SPM size of two memory configurations ? + 0.5(? ?) ? + 0.7(? ?) ? and ? are the min and max stack frames CML CML Web page: aviral.lab.asu.edu
WCET and Memory Overhead C COMPARING OMPARINGWITH WITH L LU UET ETAL AL. . ( (MEMORY MEMORYCONFIG C COMPARING OMPARINGWITH WITH L LIU IUAND AND Z ZHANG CONFIG CONFIG 1) 1) HANG( (MEMORY CONFIG 1) 1) MEMORY 100% Reduction in Cycles (%) Reduction in Cycles (%) 90% 100% Reduction in Cycles (%) Reduction in Cycles (%) 80% 80% 70% 60% 60% 40% 50% 40% 20% 30% 0% 20% -20% 10% 0% Reduction in WCET Reduction in WCET Reduction in Memory access overhead Reduction in Memory access overhead Reduction in WCET Reduction in WCET Reduction in Memory access overhead Reduction in Memory access overhead C COMPARING OMPARINGWITH WITH L LU UET ETAL AL. . ( (MEMORY MEMORYCONFIG C COMPARING OMPARINGWITH WITH L LIU CONFIG CONFIG 2) IUAND AND Z ZHANG 2) HANG( (MEMORY MEMORY CONFIG 2) 2) 100% Reduction in Cycles (%) Reduction in Cycles (%) 90% 100% Reduction in Cycles (%) Reduction in Cycles (%) 80% 80% 70% 60% 60% 40% 50% 40% 20% 30% 0% 20% -20% 10% 0% Reduction in WCET Reduction in WCET Reduction in Memory access overhead Reduction in Memory access overhead Reduction in WCET Reduction in WCET Reduction in Memory access overhead Reduction in Memory access overhead CML CML Web page: aviral.lab.asu.edu
Comparing with Caches CML CML Web page: aviral.lab.asu.edu
Conclusion We Proposed a technique to find optimallocations to perform stack management operations in order to minimize the WCET of a given program. We allocate the whole Stack in SPM which simplifies the WCET analysis. Up to 48% reduction in WCET is achieved. CML CML Web page: aviral.lab.asu.edu
