Scratchpad allocation for concurrent embedded software

ABSTRACT

Software-controlled scratchpad memory is increasingly employed in embedded systems as it offers better timing predictability compared to caches. Previous scratchpad allocation algorithms typically consider single process applications. But embedded applications are mostly multi-tasking with real-time constraints, where the scratchpad memory space has to be shared among interacting processes that may preempt each other. In this paper, we develop a novel dynamic scratchpad allocation technique that takes these process interferences into account to improve the performance and predictability of the memory system. We model the application as a Message Sequence Chart (MSC) to best capture the interprocess interactions. Our goal is to optimize the worst-case response time (WCRT) of the application through runtime reloading of the scratchpad memory content at appropriate execution points. We propose an iterative allocation algorithm that consists of two critical steps: (1) analyze the MSC along with the existing allocation to determine potential interference patterns, and (2) exploit this interference information to tune the scratchpad reloading points and content so as to best improve the WCRT. We evaluate our memory allocation scheme on a real-world embedded application controlling an Unmanned Aerial Vehicle (UAV).

REFERENCES

• 1: Rajeev Alur , Mihalis Yannakakis, Model Checking of Message Sequence Charts, Proceedings of the 10th International Conference on Concurrency Theory, p.114-129, August 24-27, 1999
• 2: Ilya Issenin , Erik Brockmeyer , Bart Durinck , Nikil Dutt, Multiprocessor system-on-chip data reuse analysis for exploring customized memory hierarchies, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146925]
• 3: ITU--T. 120: Message sequence chart (MSC). ITU-T, Geneva, 1996.
• 4: Mahmut Kandemir, Data locality enhancement for CMPs, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 5: M. Kandemir , O. Ozturk , M. Karakoy, Dynamic on-chip memory management for chip multiprocessors, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023838]
• 6: Chang-Gun Lee , Joosun Hahn , Yang-Min Seo , Sang Lyul Min , Rhan Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Analysis of Cache-Related Preemption Delay in Fixed-Priority Preemptive Scheduling, IEEE Transactions on Computers, v.47 n.6, p.700-713, June 1998 [doi>10.1109/12.689649]
• 7: H. S. Negi, T. Mitra, and A. Roychoudhury. Accurate estimation of cache-related preemption delay. In CODES+ISSS, 2003.
• 8: F. Nemer, H. Cassé, P. Sainrat, J-P. Bahsoun, and M. De Michiel. PapaBench: A free real-time benchmark. In WCET, 2006.
• 9: Isabelle Puaut, WCET-Centric Software-controlled Instruction Caches for Hard Real-Time Systems, Proceedings of the 18th Euromicro Conference on Real-Time Systems, p.217-226, July 05-07, 2006 [doi>10.1109/ECRTS.2006.32]
• 10: S. Steinke , L. Wehmeyer , B. Lee , P. Marwedel, Assigning Program and Data Objects to Scratchpad for Energy Reduction, Proceedings of the conference on Design, automation and test in Europe, p.409, March 04-08, 2002
• 11: Vivy Suhendra , Tulika Mitra , Abhik Roychoudhury , Ting Chen, Efficient detection and exploitation of infeasible paths for software timing analysis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147002]
• 12: Vivy Suhendra , Tulika Mitra , Abhik Roychoudhury , Ting Chen, WCET Centric Data Allocation to Scratchpad Memory, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.223-232, December 05-08, 2005 [doi>10.1109/RTSS.2005.45]
• 13: Vivy Suhendra , Chandrashekar Raghavan , Tulika Mitra, Integrated scratchpad memory optimization and task scheduling for MPSoC architectures, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176809]
• 14: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951747]
• 15: M. Verma, K. Petzold, L. Wehmeyer, H. Falk, and P. Marwedel. Scratchpad sharing strategies for multiprocess embedded systems: A first approach. In 3rd Workshop on Embedded Systems for Real-Time Multimedia, 2005.
• 16: D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85--87, 1967.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Performance

Keywords:
WCET, message sequence chart, scratchpad memory