Memory data organization for improved cache performance in embedded processor applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Memory data organization for improved cache performance in embedded processor applications

Full text

Pdf (685 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 2 , Issue 4 (October 1997) table of contents

Pages: 384 - 409

Year of Publication: 1997

ISSN:1084-4309

Authors

Preeti Ranjan Panda	Univ. of California at Irvine, Irvine
Nikil D. Dutt	Univ. of California at Irvine, Irvine
Alexandru Nicolau	Univ. of California at Irvine, Irvine

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 81, Citation Count: 25

Additional Information:

abstract references cited by 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/268424.268464 What is a DOI?

ABSTRACT

Code generation for embedded processors opens up the possibility for several performance optimization techniques that have been ignored by traditional compilers due to compilation time constraints. We present techniques that take into account the parameters of the data caches for organizing scalar and array variables declared in embedded code into memory, with the objective of improving data cache performance. We present techniques for clustering variables to minimize compulsory cache misses, and for solving the memory assignment problem to minimize conflict cache misses. Our experiments with benchmark code kernels from DSP and other domains on the CW4001 embedded processor from LSI Logic indicate significant improvements in data cache performance by the application of our memory organization technique.

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	Santosh G. Abraham , Rabin A. Sugumar , Daniel Windheiser , B. R. Rau , Rajiv Gupta, Predictability of load/store instruction latencies, Proceedings of the 26th annual international symposium on Microarchitecture, p.139-152, December 01-03, 1993, Austin, Texas, United States
	2	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	3	Randy Allen , Ken Kennedy, Vector Register Allocation, IEEE Transactions on Computers, v.41 n.10, p.1290-1317, October 1992 [doi>10.1109/12.166606]
	4	ARAUJO, G., DEVADAS, S., KEUTZER, K., LIAO, S., MALIK, S., SUDARSANAM, A., TJIANG, S., AND WANG, A. 1995. Challenges in code generation for embedded systems. In Code Generation for Embedded Processors, P. Marwedel and G. Goosens, Eds., Kluwer Academic, 48-64.
	5	Todd Michael Austin, Hardware and software mechanisms for reducing load latency, University of Wisconsin at Madison, Madison, WI, 1996
	6	David Callahan , Ken Kennedy , Allan Porterfield, Software prefetching, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.40-52, April 08-11, 1991, Santa Clara, California, United States
	7	S. Carr , K. Kennedy, Compiler blockability of numerical algorithms, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.114-124, November 16-20, 1992, Minneapolis, Minnesota, United States
	8	Jean-Loup Baer , Tien-Fu Chen, Effective Hardware-Based Data Prefetching for High-Performance Processors, IEEE Transactions on Computers, v.44 n.5, p.609-623, May 1995 [doi>10.1109/12.381947]
	9	Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States
	10	Eddy de Greef , Francky Catthoor , Hugo De Man, Memory organization for video algorithms on programmable signal processors, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.552-557, October 02-04, 1995
	11	Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
	12	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	13	GOOSENS, G., RABAEY, J., VANDEWALLE, J., AND MAN, H. D. 1990. An efficient microcode compiler for application specific DSP processors. IEEE Trans. CAD/ICAS 9, 9 (Sept.), 925-937.
	14	Mark D. Hill, A Case for Direct-Mapped Caches, Computer, v.21 n.12, p.25-40, December 1988 [doi>10.1109/2.16187]
	15	Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
	16	Norman P. Jouppi, Cache write policies and performance, Proceedings of the 20th annual international symposium on Computer architecture, p.191-201, May 16-19, 1993, San Diego, California, United States
	17	Y.-L. Ju , Henry G. Dietz, Reduction of Cache Coherence Overhead by Compiler Data Layout and Loop Transformation, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.344-358, August 07-09, 1991
	18	LANNEER, D., PRAET,J.V.,KIFLI, A., SCHOOFS, K., GEURTS, W., THOEN, F., AND GOOSENS,G. 1995. Chess: Retargetable code generation for embedded DSP processors. In Code Generation for Embedded Processors, P. Marwedel and G. Goosens, Eds., Kluwer Academic, 65-84.
	19	Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
	20	Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Storage assignment to decrease code size, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.186-195, June 18-21, 1995, La Jolla, California, United States
	21	LIEM, C., MAY, T., AND PAULIN, P. 1994. Instruction-set matching and selection for DSP and ASIP code generation. In Proceedings of the European Design and Test Conference (March), 31-37.
	22	Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
	23	S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
	24	Preeti R. Panda , Nikil D. Dutt, 1995 high level synthesis design repository, Proceedings of the 8th international symposium on System synthesis, p.170-174, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224537]
	25	Preeti R. Panda , Nikil D. Dutt, Reducing Address Bus Transitions for Low Power Memory Mapping, Proceedings of the 1996 European conference on Design and Test, p.63, March 11-14, 1996
	26	David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	27	PAULIN, P., LIEM, C., MAY, T., AND SUTARWALA, S. 1995. Flexware: A flexible firmware development environment for embedded systems. In Code Generation for Embedded Processors, P. Marwedel and G. Goosens, Eds., Kluwer Academic, 65-84.
	28	RAWAT, J. 1993. Static analysis of cache performance for real-time programming. Tech. Rep., Iowa State University.
	29	SCHENK, W. 1995. Retargetable code generation for parallel, pipelined processor structures. In Code Generation for Embedded Processors, P. Marwedel and G. Goosens, Eds., Kluwer Academic, 119-135.
	30	Ashok Sudarsanam , Sharad Malik, Memory bank and register allocation in software synthesis for ASIPs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.388-392, November 05-09, 1995, San Jose, California, United States
	31	Hiroyuki Tomiyama , Hiroto Yasuura, Optimal Code Placement of Embedded Software for Instruction Caches, Proceedings of the 1996 European conference on Design and Test, p.96, March 11-14, 1996
	32	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
	33	YAMADA, Y., JOHNSON,T.L.,HAAB, G., GYLLENHAAL,J.C.,AND HWU, W. W. 1995. Reducing cache misses in numerical applications using data relocation and prefetching. Tech. Rep. CRHC-95-04, University of Illinois, Urbana.

CITED BY 25

	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
	P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001
	Mahmut Kandemir , J. Ramanujam , Ugur Sezer, Compiler support for block buffering, Proceedings of the 2001 international symposium on Low power electronics and design, p.76-79, August 2001, Huntington Beach, California, United States
	Data memory design and exploration for low-power embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.553-568, October 2001
	Timothy Sherwood , Brad Calder , Joel Emer, Reducing cache misses using hardware and software page placement, Proceedings of the 13th international conference on Supercomputing, p.155-164, June 20-25, 1999, Rhodes, Greece
	P. R. Panda , N. D. Dutt , A. Nicolau, Data cache sizing for embedded processor applications, Proceedings of the conference on Design, automation and test in Europe, p.925-926, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Exploiting off-chip memory access modes in high-level synthesis, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.333-340, November 09-13, 1997, San Jose, California, United States
	Rodric M. Rabbah , Krishna V. Palem, Data remapping for design space optimization of embedded memory systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.186-218, May 2003
	V. Krishna Nandivada , Jens Palsberg, Efficient spill code for SDRAM, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA
	Sri Parameswaran , Jörg Henkel, I-CoPES: fast instruction code placement for embedded systems to improve performance and energy efficiency, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Preeti Ranjan Panda , Luc Semeria , Giovanni de Micheli, Cache-efficient memory layout of aggregate data structures, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada
	Sri Parameswaran , Jörg Henkel, Instruction code mapping for performance increase and energy reduction in embedded computer systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.13 n.4, p.498-502, April 2005
	Tom Vander Aa , Murali Jayapala , Francisco Barat , Geert Deconinck , Rudy Lauwereins , Francky Catthoor , Henk Corporaal, Instruction buffering exploration for low energy VLIWs with instruction clusters, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.824-829, January 27-30, 2004, Yokohama, Japan
	Krishna V. Palem , Rodric M. Rabbah , Vincent J. Mooney, III , Pinar Korkmaz , Kiran Puttaswamy, Design space optimization of embedded memory systems via data remapping, ACM SIGPLAN Notices, v.37 n.7, July 2002
	Mohamed Shalan , Vincent J. Mooney, III, Hardware support for real-time embedded multiprocessor system-on-a-chip memory management, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado
	Yoonseo Choi , Taewhan Kim, Memory access driven storage assignment for variables in embedded system design, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.478-481, January 27-30, 2004, Yokohama, Japan
	Joon-Sang Park , Michael Penner , Viktor K. Prasanna, Optimizing Graph Algorithms for Improved Cache Performance, IEEE Transactions on Parallel and Distributed Systems, v.15 n.9, p.769-782, September 2004
	Yoonseo Choi , Taewhan Kim, Memory layout techniques for variables utilizing efficient DRAM access modes in embedded system design, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Qin Zhao , Rodric Rabbah , Weng-Fai Wong, Dynamic memory optimization using pool allocation and prefetching, ACM SIGARCH Computer Architecture News, v.33 n.5, December 2005
	M. Kandemir , J. Ramanujam , U. Sezer, Improving the energy behavior of block buffering using compiler optimizations, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.1, p.228-250, January 2006
	Tom Vander Aa , Murali Jayapala , Francisco Barat , Geert Deconinck , Rudy Lauwereins , Henk Corporaal , Francky Catthoor, Instruction buffering exploration for low energy embedded processors, Journal of Embedded Computing, v.1 n.3, p.341-351, August 2005
	Wen-Tsong Shiue , Chaitali Chakrabarti, Memory Design and Exploration for Low Power, Embedded Systems, Journal of VLSI Signal Processing Systems, v.29 n.3, p.167-178, November 2001
	Sambuddhi Hettiaratchi , Peter Y. K. Cheung, Mesh Partitioning Approach to Energy Efficient Data Layout, Proceedings of the conference on Design, Automation and Test in Europe, p.11076, March 03-07, 2003
	J. Ramanujam , Satish Krishnamurthy , Jinpyo Hong , Mahmut Kandemir, Address Code and Arithmetic Optimizations for Embedded Systems, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.619, January 07-11, 2002
	Yun Liang , Lei Ju , Samarjit Chakraborty , Tulika Mitra , Abhik Roychoudhury, Cache-aware optimization of BAN applications, Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis, October 19-24, 2008, Atlanta, GA, USA