Memory allocation for embedded systems with a compile-time-unknown scratch-pad size

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Memory allocation for embedded systems with a compile-time-unknown scratch-pad size

Full text

Pdf (1.20 MB)

Source

ACM Transactions on Embedded Computing Systems (TECS) archive
Volume 8 , Issue 3 (April 2009) table of contents

Article No. 21

Year of Publication: 2009

ISSN:1539-9087

Authors

Nghi Nguyen	University of Maryland, College Park, MD
Angel Dominguez	University of Maryland, College Park, MD
Rajeev Barua	University of Maryland, College Park, MD

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 38, Downloads (12 Months): 163, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1509288.1509293 What is a DOI?

ABSTRACT

This article presents the first memory allocation scheme for embedded systems having a scratch-pad memory whose size is unknown at compile time. A scratch-pad memory (SPM) is a fast compiler-managed SRAM that replaces the hardware-managed cache. All existing memory allocation schemes for SPM require the SPM size to be known at compile time. Unfortunately, because of this constraint, the resulting executable is tied to that size of SPM and is not portable to other processor implementations having a different SPM size. Size-portable code is valuable when programs are downloaded during deployment either via a network or portable media. Code downloads are used for fixing bugs or for enhancing functionality. The presence of different SPM sizes in different devices is common because of the evolution in VLSI technology across years. The result is that SPM cannot be used in such situations with downloaded codes.

To overcome this limitation, our work presents a compiler method whose resulting executable is portable across SPMs of any size. Our technique is to employ a customized installer software, which decides the SPM allocation just before the program's first run, since the SPM size can be discovered at that time. The installer then, based on the decided allocation, modifies the program executable accordingly. The resulting executable places frequently used objects in SPM, considering both code and data for placement. To keep the overhead low, much of the preprocessing for the allocation is done at compile time. Results show that our benchmarks average a 41% speedup versus an all-DRAM allocation, while the optimal static allocation scheme, which knows the SPM size at compile time and is thus an unachievable upper-bound and is only slightly faster (45% faster than all-DRAM). Results also show that the overhead from our customized installer averages about 1.5% in code size, 2% in runtime, and 3% in compile time for our benchmarks.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Analog Devices. 1996. ADSP-21xx 16-bit DSP Family. http://www.analog.com/processors/processors/ADSP/index.html.
	2	Analog Devices. 2001. SHARC ADSP-21160M 32-bit Embedded CPU. http://www.analog.com/processors/processors/sharc/index.html.
	3	Analog Devices. 2004. TigerSharc ADSP-TS201S 32-bit DSP. http://www.analog.com/processors/processors/tigersharc/index.html.
	4	Federico Angiolini , Luca Benini , Alberto Caprara, Polynomial-time algorithm for on-chip scratchpad memory partitioning, 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.951751]
	5	Federico Angiolini , Francesco Menichelli , Alberto Ferrero , Luca Benini , Mauro Olivieri, A post-compiler approach to scratchpad mapping of code, 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.1023869]
	6	Arm. 2004. ARM968E-S 32-bit Embedded Core. http://www.arm.com/products/CPUs/ARM968E-S.html.
	7	Atmel. 2004. Atmel AT91C140 16/32-bit Embedded CPU. http://www.atmel.com/dyn/resources/proddocuments/doc6069.pdf.
	8	Oren Avissar , Rajeev Barua , Dave Stewart, Heterogeneous memory management for embedded systems, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502223]
	9	Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
	10	Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
	11	Bohr, M., Doyle, B., Kavalieros, J., Barlage, D., Murthy, A., Doczy, M., Rios, R., Linton, T., Arghavani, R., et al. 2002. Intels 90nm technology: Moores law and more. Document Number: {IR-TR-2002-10}.
	12	Cnetx. Downloadable software. http://www.cnetx.com/slideshow/.
	13	CodeSourcery. http://www.codesourcery.com/.
	14	Angel Dominguez , Sumesh Udayakumaran , Rajeev Barua, Heap data allocation to scratch-pad memory in embedded systems, Journal of Embedded Computing, v.1 n.4, p.521-540, December 2005
	15	Edler, J. and Hill, M. 2004. Dineroiv cache simulator. http://www.cs.wisc.edu/markhill/DineroIV/.
	16	Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
	17	Handango. Downloadable software. http://www.handango.com/.
	18	John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	19	Jason D. Hiser , Jack W. Davidson, EMBARC: an efficient memory bank assignment algorithm for retargetable compilers, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
	20	Hitachi/Renesas. 2004. M32R-32192 32-bit Embedded CPU. http://documentation.renesas.com/eng/products/mpumcu/rej03b0019 32192ds.pdf.
	21	Hitachi/Renesas. 1999. SH7050 32-bit CPU. http://documentation.renesas.com/eng/products/mpumcu/e602121 sh7050.pdf.
	22	Infineon. 2001. XC-166 16-bit Embedded Family. http://www.infineon.com/cmc_upload/documents/036/812/c166sv2um.pdf.
	23	Intel Flash. Intel wireless flash memory (W30). http://www.intel.com/design/flcomp/datashts/290702.htm.
	24	Janzen, J. 2001. Calculating memory system power for DDR SDRAM. DesignLine J. 10, 2.
	25	M. Kandemir , J. Ramanujam , J. Irwin , N. Vijaykrishnan , I. Kadayif , A. Parikh, Dynamic management of scratch-pad memory space, Proceedings of the 38th conference on Design automation, p.690-695, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379049]
	26	LandWare, Inc. 2003. Pocket Quicken PPC20 Manual. http://www.landware.com/downloads/MANUALS/PocketQuickenPPC20Manual.pdf.
	27	Csaba Andras Moritz , Matthew Frank , Saman P. Amarasinghe, FlexCache: A Framework for Flexible Compiler Generated Data Caching, Revised Papers from the Second International Workshop on Intelligent Memory Systems, p.135-146, November 12, 2000
	28	Motorola/Freescale. 2003. Dragonball MC68SZ328 32-bit Embedded CPU. http://www.freescale.com/files/32bit/doc/factsheet/MC68SZ328FS.pdf.
	29	Motorola/Freescale. 2002. MPC500 32-bit MCU Family. http://www.freescale.com/files/microcontrollers/doc/factsheet/MPC500FACT.pdf.
	30	Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, On-chip vs. off-chip memory: the data partitioning problem in embedded processor-based systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.682-704, July 2000 [doi>10.1145/348019.348570]
	31	Panel, L. 2003. Compilation challenges for network processors. In Proceedings of the ACM Conference on Languages, Compilers and Tools for Embedded Systems (LCTES'03). ACM, New York.
	32	Phatware, Corp. Downloadable software. http://www.phatware.com/phatnotes/.
	33	PhatWare, Corp. 2006. PhatNotes Professional Edition Version 4.7 User's Guide. http://www.phatware.com/doc/PhatNotesPro.pdf.
	34	Shivakumar, P. and Jouppi, N. 2004. Cacti 3.2. http://research.compaq.com/wrl/people/jouppi/CACTI.html.
	35	Amit Sinha , Anantha P. Chandrakasan, JouleTrack: a web based tool for software energy profiling, Proceedings of the 38th conference on Design automation, p.220-225, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378467]
	36	Sjodin, J., Froderberg, B., and Lindgren, T. 1998. Allocation of global data objects in on-chip RAM. In Proceedings of the International Workshop on Compiler and Architecture Support for Embedded Computing Systems (CASES'98). ACM, New York.
	37	Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502221]
	38	Softmaker. Downloadable software. http://www.softmaker.de.
	39	SoftMaker Software GmbH. 2004. Plan Maker 2004 Manual. http://www.softmaker.net/down/pm2004manualen.pdf.
	40	Stefan Steinke , Nils Grunwald , Lars Wehmeyer , Rajeshwari Banakar , M. Balakrishnan , Peter Marwedel, Reducing energy consumption by dynamic copying of instructions onto onchip memory, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581247]
	41	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
	42	Vivek Tiwari , Sharad Malik , Andrew Wolfe, Power analysis of embedded software: a first step towards software power minimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.437-445, Dec. 1994 [doi>10.1109/92.335012]
	43	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]
	44	Sumesh Udayakumaran , Angel Dominguez , Rajeev Barua, Dynamic allocation for scratch-pad memory using compile-time decisions, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.2, p.472-511, May 2006 [doi>10.1145/1151074.1151085]
	45	Manish Verma , Lars Wehmeyer , Peter Marwedel, Cache-Aware Scratchpad Allocation Algorithm, Proceedings of the conference on Design, automation and test in Europe, p.21264, February 16-20, 2004
	46	Manish Verma , Lars Wehmeyer , Peter Marwedel, Dynamic overlay of scratchpad memory for energy minimization, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016748]
	47	Lars Wehmeyer , Urs Helmig , Peter Marwedel, Compiler-optimized usage of partitioned memories, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.114-120, June 20-20, 2004, Munich, Germany [doi>10.1145/1054943.1054959]
	48	Wehmeyer, L. and Marwedel, P. 2004. Influence of onchip scratchpad memories on wcet prediction. In Proceedings of the 4th International Workshop on Worst-Case Execution Time (WCET) Analysis. ACM, New York.
	49	Wilton, S. and Jouppi, N. 1996. Cacti: An enhanced cache access and cycle time model. IEEE J. Solid-State Circuits.
	50	Xi-art. Downloadable software. http://www.xi-art.com/.