Task Variants with Different Scratchpad Memory Consumption in Multi-Task Environments
Pages 143 - 156
Abstract
We present an approach which schedules task sets using scratchpad memory SPM in an embedded multi-task system with real-time constraints. A new task model is introduced, where each task is represented by different pre-compiled variants which differ in the amount of scratchpad memory used. A higher use of SPM leads to smaller run-times of a task. Moreover, the energy consumption is reduced by replacing memory accesses by SPM accesses. Our heuristic method assembles a task set of these variants by choosing one variant per task. After selecting candidates from the pre-computed set of task variants, the task set can be handled by a real-time scheduler like EDF. Our approach is able to build a new incremental task set and feasible transition in dynamically changing environments. Furthermore we show an extension of our approach to multicore environments.
References
[1]
Angiolini, F., Menichelli, F., Ferrero, A., Benini, L., Olivieri, M.: A post-compiler approach to scratchpad mapping of code. In: CASES 2004
[2]
Avissar, O., Barua, R., Stewart, D.: An optimal memory allocation scheme for scratch-pad-based embedded systems. ACM Trans. Embed. Comput. Syst. 1, 6---26 2002
[3]
Banakar, R., Steinke, S., Lee, B.S., Balakrishnan, M., Marwedel, P.: Scratchpad memory: a design alternative for cache on-chip memory in embedded systems. In: CODES 2002
[4]
Benini, L., Bertozzi, D., Bogliolo, A., Menichelli, F., Olivieri, M.: MPARM: Exploring the multi-processor SOC design space with systemc. J. VLSI Signal Process. Syst. 41, 169---182 2005
[5]
Dominguez, A., Udayakumaran, S., Barua, R.: Heap data allocation to scratch-pad memory in embedded systems. J. Embed. Comput. 1, 521---540 2005
[6]
Dudziński, K., Walukiewicz, S.: Exact methods for the knapsack problem and its generalizations. Eur. J. Oper. Res. 28, 2---3 1987
[7]
Egger, B., Lee, J., Shin, H.: Dynamic scratchpad memory management for code in portable systems with an MMU. ACM Trans. Embed. Comput. Syst. 7, 11 2008
[8]
Falk, H., Kleinsorge, J.: Optimal static wcet-aware scratchpad allocation of program code. In: DAC 2009
[9]
Falk, H., Lokuciejewski, P.: A compiler framework for the reduction of worst-case execution times. Real-Time Syst. 46, 251---300 2010
[10]
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York 1979
[11]
Guthaus, M.R., Ringenberg, J.S., Ernst, D., Austin, T.M., Mudge, T., Brown, R.B.: Mibench: A free, commercially representative embedded benchmark suite. In: WWC-4 2001
[12]
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg 2004
[13]
Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 46---61 1973
[14]
Optimization, G., et al.: Gurobi optimizer reference manual 2012. http://www.gurobi.com
[15]
Panda, P.R., Dutt, N.D., Nicolau, A.: Efficient utilization of scratch-pad memory in embedded processor applications. In: ED & TC 1997
[16]
Pisinger, D.: Algorithms for Knapsack Problems. Ph.D. thesis, DIKU, University of Copenhagen, Denmark 1995
[17]
Poletti, F., Marchal, P., Atienza, D., Benini, L., Catthoor, F., Mendias, J.M.: An integrated hardware/software approach for run-time scratchpad management. In: DAC 2004
[18]
Sjödin, J., von Platen, C.: Storage allocation for embedded processors. In: CASES 2001
[19]
Steinke, S., Wehmeyer, L., Lee, B., Marwedel, P.: Assigning program and data objects to scratchpad for energy reduction. In: DATE 2002
[20]
Suhendra, V., Mitra, T., Roychoudhury, A., Chen, T.: WCET centric data allocation to scratchpad memory. In: RTSS 2005
[21]
Udayakumaran, S., Barua, R.: Compiler-decided dynamic memory allocation for scratch-pad based embedded systems. In: CASES 2003
[22]
Verma, M., Petzold, K., Wehmeyer, L., Falk, H., Marwedel, P.: Scratchpad sharing strategies for multiprocess embedded systems: a first approach. In: Embedded Systems for Real-Time Multimedia 2005
[23]
Verma, M., Wehmeyer, L., Marwedel, P.: Cache-aware scratchpad allocation algorithm. In: DATE 2004
[24]
Verma, M., Wehmeyer, L., Pyka, R., Marwedel, P., Benini, L.: Compilation and simulation tool chain for memory aware energy optimizations. In: Vassiliadis, S., Wong, S., Hämäläinen, T.D. eds. SAMOS 2006. LNCS, vol. 4017, pp. 279---288. Springer, Heidelberg 2006
[25]
Whitham, J., Audsley, N.: Explicit reservation of local memory in a predictable, preemptive multitasking real-time system. In: RTAS 2012
[26]
Whitham, J., Davis, R.I., Audsley, N.C., Altmeyer, S., Maiza, C.: Investigation of scratchpad memory for preemptive multitasking. In: RTSS 2012
Recommendations
Minimizing inter-task interferences in scratch-pad memory usage for reducing the energy consumption of multi-task systems
CASES '10: Proceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systemsThis paper presents a new technique for reducing the energy consumption of a multi-task system by sharing its scratchpad memory (SPM) space among the tasks. With this technique, tasks can interfere by using common areas of the SPM. However, this ...
Energy efficient task allocation for hybrid main memory architecture
Compared with the conventional dynamic random access memory (DRAM), emerging non-volatile memory technologies provide better density and energy efficiency. However, current NVM devices typically suffer from high write power, long write latency and low ...
Hyper switching memory utilization on hybrid main memory for improved task execution and reduced power consumption
AbstractThe problem of lifetime maximization of PCM has been well studied. The arrival of non-volatile memory devices has replaced the traditional DRAM. Still the DRAM has many limitations on endurance and high power write operations. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2016
378 pages
ISBN:9783319306940
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 04 April 2016
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025