Compiler-directed scratchpad memory management via graph coloring

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Compiler-directed scratchpad memory management via graph coloring

Full text

Pdf (488 KB)

Source

ACM Transactions on Architecture and Code Optimization (TACO) archive
Volume 6 , Issue 3 (September 2009) table of contents

Article No. 9

Year of Publication: 2009

ISSN:1544-3566

Authors

Lian Li	University of New South Wales, Sydney, Australia
Hui Feng	University of New South Wales, Sydney, Australia
Jingling Xue	University of New South Wales, Sydney, Australia

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references index terms

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/1582710.1582711 What is a DOI?

ABSTRACT

Scratchpad memory (SPM), a fast on-chip SRAM managed by software, is widely used in embedded systems. This article introduces a general-purpose compiler approach, called memory coloring, to assign static data aggregates, such as arrays and structs, in a program to an SPM. The novelty of this approach lies in partitioning the SPM into a pseudo--register file (with interchangeable and aliased registers), splitting the live ranges of data aggregates to create potential data transfer statements between SPM and off-chip memory, and finally, adapting an existing graph coloring algorithm for register allocation to assign the data aggregates to the pseudo--register file. Our experimental results using a set of 10 C benchmarks from MediaBench and MiBench show that our methodology is capable of managing SPMs efficiently and effectively for large embedded applications. In addition, our SPM allocator can obtain close to optimal solutions when evaluated and compared against an existing heuristics-based SPM allocator and an ILP-based SPM allocator.

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	Appel, A. W. and George, L. 2001. Optimal spilling for CISC machines with few registers. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01). ACM, New York, 243--253.
	2	Avissar, O., Barua, R., and Stewart, D. 2002. An optimal memory allocation scheme for scratch-pad-based embedded systems. Trans. Embed. Comput. Syst. 1, 1, 6--26.
	3	Briggs, P., Cooper, K. D., and Torczon, L. 1994. Improvements to graph coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3, 428--455.
	4	Chaitin, G. J. 1982. Register allocation & spilling via graph coloring. In Proceedings of the SIGPLAN Symposium on Compiler Construction (SIGPLAN'82). ACM, New York, 98--101.
	5	Chow, F. C. and Hennessy, J. L. 1990. The priority-based coloring approach to register allocation. ACM Trans. Program. Lang. Syst. 12, 4, 501--536.
	6	Cooper, K. D. and Harvey, T. J. 1998. Compiler-controlled memory. In Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS VIII). ACM, New York, 2--11.
	7	Genius, D. 1998. Handling cross interferences by cyclic cache line coloring. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT'98). IEEE, Los Alamitos, CA, 112.
	8	George, L. and Appel, A. W. 1996. Iterated register coalescing. ACM Trans. Program. Lang. Syst. 18, 3, 300--324.
	9	Hiser, J. D. and Davidson, J. W. 2004. Embarc: An efficient memory bank assignment algorithm for retargetable compilers. In Proceedings of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools (LCTES'04). ACM, New York, 182--191.
	10	Kandemir, M., Ramanujam, J., Irwin, J., Vijaykrishnan, N., Kadayif, I., and Parikh, A. 2001. Dynamic management of scratch-pad memory space. In Proceedings of the 38th Annual Conference on Design Automation (DAC'01). ACM, New York, 690--695.
	11	Kapasi, U., Dally, W. J., Rixner, S., Owens, J. D., and Khailany, B. 2002. The imagine stream processor. In Proceedings IEEE International Conference on Computer Design. IEEE, Los Alamitos, CA, 282--288.
	12	Li, L., Gao, L., and Xue, J. 2005. Memory coloring: A compiler approach for scratch-pad memory management. In Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques (PACT'05). IEEE, Los Alamitos, CA, 329--338.
	13	Lueh, G.-Y., Gross, T., and Adl-Tabatabai, A.-R. 2000. Fusion-based register allocation. ACM Trans. Program. Lang. Syst. 22, 3, 431--470.
	14	Panda, P. R., Dutt, N. D., and Nicolau, A. 1997a. Architectural exploration and optimization of local memory in embedded systems. In Proceedings of the 10th International Symposium on System Synthesis (ISSS'97). IEEE, Los Alamitos, CA, 90--97.
	15	Panda, P. R., Dutt, N. D., and Nicolau, A. 1997b. Efficient utilization of scratch-pad memory in embedded processor applications. In Proceedings of the European Conference on Design and Test. IEEE, Los Alamitos, CA, 7.
	16	Panda, P. R., Dutt, N. D., and Nicolau, A. 2000. On-chip vs. off-chip memory: The data partitioning problem in embedded processor-based systems. ACM Trans. Design Autom. Electr. Syst. 5, 3, 682--704.
	17	Park, J. and Moon, S.-M. 2004. Optimistic register coalescing. ACM Trans. Program. Lang. Syst. 26, 4, 735--765.
	18	Ravindran, R. A., Nagarkar, P. D., Dasika, G. S., Marsman, E. D., Senger, R. M., Mahlke, S. A., and Brown, R. B. 2005. Compiler managed dynamic instruction placement in a low-power code cache. In Proceedings of the 3rd IEEE/ACM International Symposium on Code Generation and Optimization (CGO'03). IEEE, Los Alamitos, CA, 179--190.
	19	Sjödin, J. and von Platen, C. 2001. Storage allocation for embedded processors. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES'01). ACM, New York, 15--23.
	20	Smith, M. D., Ramsey, N., and Holloway, G. 2004. A generalized algorithm for graph coloring register allocation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'04). ACM, New York, 277--288.
	21	Steinke, S., Wehmeyer, L., Lee, B., and Marwedel, P. 2002. Assigning program and data objects to scratchpad for energy reduction. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'02). IEEE, Los Alamitos, CA, 409.
	22	Udayakumaran, S., Dominguez, A., and Barua, R. 2006. Dynamic allocation for scratch-pad memory using compile-time decisions. Trans. Embed. Comput. Syst. 5, 2, 472--511.
	23	Verma, M., Wehmeyer, L., and Marwedel, P. 2004a. Cache-aware scratch-pad allocation algorithm. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'04). IEEE, Los Alamitos, CA, 21264.
	24	Verma, M., Wehmeyer, L., and Marwedel, P. 2004b. Dynamic overlay of scratch-pad memory for energy minimization. In Proceedings of the 2nd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'04). ACM, New York, 104--109.
	25	Wolfe, M. 1989. Iteration space tiling for memory hierarchies. In Proceedings of the 3rd SIAM Conference on Parallel Processing for Scientific Computing. Society for Industrial and Applied Mathematics, Philadelphia, 357--361.
	26	Xue, J. 2000. A Loop Tiling Theory for Optimizing Compilers. Kluwer Academic Publishers, The Netherlands.