More Web Proxy on the site http://driver.im/

research-article

Partitioning and allocation of scratch-pad memory for priority-based preemptive multi-task systems

Authors:

Hiroyuki Tomiyama,

Hiroaki TakadaAuthors Info & Claims

DATE '10: Proceedings of the Conference on Design, Automation and Test in Europe

Pages 1124 - 1129

Published: 08 March 2010 Publication History

Abstract

Scratch-pad memory has been employed as a partial or entire replacement for cache memory due to its better energy efficiency. In this paper, we propose scratch-pad memory management techniques for priority-based preemptive multitask systems. Our techniques are applicable to a real-time environment. The three methods which we propose, i.e., spatial, temporal, and hybrid methods, bring about effective usage of the scratch-pad memory space, and achieve energy reduction in the instruction memory subsystems. We formulate each method as an integer programming problem that simultaneously determines (1) partitioning of scratch-pad memory space for the tasks, and (2) allocation of program code to scratch-pad memory space for each task. It is remarkable that periods and priorities of tasks are considered in the formulas. Additionally, we implement an RTOS-hardware cooperative support mechanism for a runtime code allocation to the scratch-pad memory space. We have made the experiments with the fully functional real-time operating system. The experimental results with four task sets have demonstrated the effectiveness of our techniques. Up to 73% energy reduction compared to a standard method was achieved.

References

[1]

S. Segars, "Low power design techniques for microprocessors," presented at IEEE International Solid-State Circuits Conference (Tutorial), Feb. 2001.

[2]

R. Banakar, S. Steinke, B.-S. Lee, M. Balakrishnan, and P. Marwedel, "Scratchpad memory: A design alternative for cache on-chip memory in embedded systems," in Proceedings of International Symposium on Hardware/Software Codesign (CODES), Colorado, USA, May 2002, pp. 73--78.

Digital Library

[3]

O. Avissar, R. Barua, and D. Stewart, "An optimal memory allocation scheme for scratch-pad-based embedded systems," ACM Transaction on Embedded Computing Systems (TECS), vol. 1, no. 1, pp. 6--26, 2002.

Digital Library

[4]

S. Steinke, L. Wehmeyer, B. Lee, and P. Marwedel, "Assigning program and data objects to scratchpad for energy reduction," in Proceedings of the Conference on Design, Automation and Test in Europe (DATE), Paris, France, Mar. 2002, pp. 409--415.

Digital Library

[5]

P. R. Panda, A. Nicolau, and N. Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration. Kluwer Academic Publishers, 1998.

Digital Library

[6]

F. Angiolini, L. Benini, and A. Caprara, "An efficient profile-based algorithm for scratchpad memory partitioning," IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 11, pp. 1660--1676, 2005.

Digital Library

[7]

A. Janapsatya, A. Ignjatovic, and S. Parameswaran, "Exploiting statistical information for implementation of instruction scratchpad memory in embedded system," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 14, no. 8, pp. 816--829, 2006.

Digital Library

[8]

S. Steinke, N. Grunwald, L. Wehmeyer, R. Banakar, M. Balakrishnan, and P. Marwedel, "Reducing energy consumption by dynamic copying of instructions onto onchip memory," in Proceedings of the 15th International Symposium on System Synthesis (ISSS), Kyoto, Japan, 2002, pp. 213--218.

Digital Library

[9]

A. Janapsatya, S. Parameswaran, and A. Ignjatovic, "Hardware/software managed scratchpad memory for embedded system," in Proceedings of the 2004 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), New Jersey, USA, Nov. 2004, pp. 370--377.

Digital Library

[10]

M. Verma, K. Petzold, L. Wehmeyer, H. Falk, and P. Marwedel, "Scratchpad sharing strategies for multiprocess embedded systems: A first approach," in Proceedings of IEEE 3rd Workshop on Embedded System for Real-Time Multimedia (ESTIMedia), Jersey City, USA, Sep. 2005, pp. 115--200.

[11]

R. Pyka, C. Fasbach, M. Verma, H. Falk, and P. Marwedel, "Operating system integrated energy aware scratchpad allocation strategies for multiprocess applications," in Proceedings of 10th International Workshop on Software & Compilers for Embedded Systems (SCOPES), Nice, France, 2007, pp. 41--50.

Digital Library

[12]

B. Egger, J. Lee, and H. Shin, "Scratchpad memory management in a multitasking environment," in Proceedings of the 7th ACM International Conference on Embedded Software (EMSOFT), Atlanta, USA, Dec. 2008, pp. 265--274.

Digital Library

[13]

H. Takase, H. Tomiyama, and H. Takada, "Partitioning and allocation of scratch-pad memory in priority-based multi-task systems," IPSJ Transactions on System LSI Design Methodology, vol. 2 (2009), pp. 180--188, Aug 2009.

[14]

C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," Journal of ACM, vol. 20, no. 1, pp. 46--61, 1973.

Digital Library

[15]

SkyEye - Open Source Simulator. {Online}. Available: http://www.skyeye.org/

[16]

ARM920T - ARM Processor. {Online}. Available: http://www.arm.com/products/CPUs/ARM920T.html

[17]

GLPK (GNU Linear Programming Kit). {Online}. Available: http://www.gnu.org/software/glpk/

[18]

GCC, the GNU Compiler Collection. {Online}. Available: http://gcc.gnu.org/

[19]

TOPPERS Project. {Online}. Available: http://toppers.jp/en/

[20]

μITRON4.0 Specification. {Online}. Available: http://www.ertl.jp/ITRON/SPEC/mitron4-e.html

[21]

EEMBC -- The Embedded Microprocessor Benchmark Consortium. {Online}. Available: http://www.eembc.org/

[22]

S. Thoziyoor, N. Muralimanohar, and N. P. Jouppi, "CACTI 5.0," HP Laboratories, Tech. Rep., 2006.

Cited By

Li YZhan JJiang WLi YMitra TKumar A(2018)Writing-aware data variable allocation on hybrid SRAM+NVM SPMProceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems10.5555/3283552.3283563(1-2)Online publication date: 30-Sep-2018
https://dl.acm.org/doi/10.5555/3283552.3283563
Chang DLin IYong L(2017)ROHOMIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.258404836:3(357-369)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2584048
Tajik HDonyanavard BDutt NJahn JHenkel J(2016)SPMPoolACM Transactions on Embedded Computing Systems10.1145/296844716:1(1-27)Online publication date: 23-Oct-2016
https://dl.acm.org/doi/10.1145/2968447
Show More Cited By

Recommendations

Efficient dynamic heap allocation of scratch-pad memory
ISMM '08: Proceedings of the 7th international symposium on Memory management

An increasing number of processor architectures support scratch-pad memory - software managed on-chip memory. Scratch-pad memory provides low latency data storage, like on-chip caches, but under explicit software control. The simple design and ...
Compiler-assisted dynamic scratch-pad memory management with space overlapping for embedded systems

Scratch-pad memory (SPM), a small, fast, software-managed on-chip SRAM (Static Random Access Memory) is widely used in embedded systems. With the ever-widening performance gap between processors and main memory, it is very important to reduce the ...
Recursive function data allocation to scratch-pad memory
CASES '07: Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems

This paper presents the first automatic scheme to allocate local (stack) data in recursive functions to scratch-pad memory (SPM) in embedded systems. A scratch-pad is a fast directly addressed compiler-managed SRAM memory that replaces the hardware-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DATE '10: Proceedings of the Conference on Design, Automation and Test in Europe

March 2010

1868 pages

ISBN:9783981080162

General Chairs:
Giovanni De Micheli
EPF Lausanne, CH
,
Bashir Al-Hashimi
University of Southampton, UK
,
Program Chairs:
Wolfgang Mueller
University of Paderborn, SE
,
Enrico Macii
Politecnico di Torino, IT

Sponsors

EDAA: European Design Automation Association
ECSI
EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
The IEEE Computer Society TTTC
The IEEE Computer Society DATC
The Russian Academy of Sciences: The Russian Academy of Sciences

Publisher

European Design and Automation Association

Leuven, Belgium

Publication History

Published: 08 March 2010

Check for updates

Qualifiers

Research-article

Conference

DATE '10

Sponsor:

EDAA
EDAC
SIGDA
The Russian Academy of Sciences

DATE '10: Design, Automation and Test in Europe

March 8 - 12, 2010

Germany, Dresden

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
141
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li YZhan JJiang WLi YMitra TKumar A(2018)Writing-aware data variable allocation on hybrid SRAM+NVM SPMProceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems10.5555/3283552.3283563(1-2)Online publication date: 30-Sep-2018
https://dl.acm.org/doi/10.5555/3283552.3283563
Chang DLin IYong L(2017)ROHOMIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.258404836:3(357-369)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2584048
Tajik HDonyanavard BDutt NJahn JHenkel J(2016)SPMPoolACM Transactions on Embedded Computing Systems10.1145/296844716:1(1-27)Online publication date: 23-Oct-2016
https://dl.acm.org/doi/10.1145/2968447
Pan CXie MHu JChen YYang CMarculescu RNicolescu G(2014)3M-PCMProceedings of the 2014 International Conference on Hardware/Software Codesign and System Synthesis10.1145/2656075.2656076(1-10)Online publication date: 12-Oct-2014
https://dl.acm.org/doi/10.1145/2656075.2656076
Bathen LDutt N(2014)SPMCloudACM Transactions on Design Automation of Electronic Systems10.1145/261175519:3(1-45)Online publication date: 23-Jun-2014
https://dl.acm.org/doi/10.1145/2611755
Bathen LDutt N(2014)Embedded RAIDs-on-chip for bus-based chip-multiprocessorsACM Transactions on Embedded Computing Systems10.1145/253331613:4(1-36)Online publication date: 10-Mar-2014
https://dl.acm.org/doi/10.1145/2533316
Bathen LDutt NNicolau AGupta PRosenstiel WMacii E(2012)VaMVProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2492779(284-287)Online publication date: 12-Mar-2012
https://dl.acm.org/doi/10.5555/2492708.2492779
Chang CChen JMunawar WKuo TFalk HJerraya ACarloni LMaraninchi FRegehr J(2012)Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared sramsProceedings of the tenth ACM international conference on Embedded software10.1145/2380356.2380384(153-162)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380356.2380384
Bathen LDutt NGroeneveld PSciuto DHassoun S(2012)HaVOCProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228438(447-452)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228438
Deng NJi WLi JZuo Q(2011)A semi-automatic scratchpad memory management framework for CMPProceedings of the 9th international conference on Advanced parallel processing technologies10.5555/2042522.2042528(73-87)Online publication date: 26-Sep-2011
https://dl.acm.org/doi/10.5555/2042522.2042528
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents