New directions in compiler technology for embedded systems (embedded tutorial)

ABSTRACT

Traditionally, compiler technology has focused on the generation of code with the goal of improving performance for a variety of applications running on general-purpose processor architectures. In the embedded system space, compiler technology is faced with many new challenges, including: code generation for specialized architectural features, requireing a highly flexible degree of retargetability; memory-aware code generation that exploits the timing and structure of the embedded system's memory organization; optimizing software to meet both real-time and performance constraints; energy- and power-aware software generation, both from the context of energy minimization, as well as power modulation; code size minimization for memory-constrained embedded systems; coarse-grain transformations for tightly-coupled, memory-constrained multi-processor architectures; and interaction with the operating system for active management of embedded system resources. This paper discusses new directions for compiler technology, surveys some of the current research efforts and illustrates proposed solutions to selected issues.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 3: R. M. Stallman, Using and Porting GNU CC (for version 2.g5), Free Software Foundation, Inc, 1999.
• 4: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 5: Texas Instruments, TMS320C62z/C67z CPU and Instruction Set Reference Guide, 1998.
• 6: S. Bashford, U. Bieker, B. Harking, R. Leupers, P. Marwedel, A. Neumann, and D. Voggenauer, The MIMOLA Language Version 4.1, University of Dortmund, 1994.
• 7: D. Lanneer, J. Van Praet, A. Kifli, K. Schoofs, W. Geurts, F. Thoen, and G. Goossens, "CHESS: Retargetable code generation for embedded DSP processors," Code Generation for Erabedded Processors (P. Marwedel and G. Goossens, ed.), Kluwer Academic Publishers, 1995.
• 8: M. Freericks, The nML Machine Description Formalism, Fachbereich Informatik, TU Berlin, 1991.
• 9: Rainer Leupers, Code Optimization Techniques for Embedded Processors: Methods, Algorithms, and Tools, Kluwer Academic Publishers, Norwell, MA, 2000
• 10: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steven Tjiang , Albert Wang, Storage assignment to decrease code size, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.235-253, May 1996 [doi>10.1145/229542.229543]
• 11: Trimaran Release, "The MDES user manual," SIA NTRS lgg7 Edition, http://www.trimaran.org, 1997.
• 12: Ashok Halambi , Peter Grun , Vijay Ganesh , Asheesh Khare , Nikil Dutt , Alex Nicolau, EXPRESSION: a language for architecture exploration through compiler/simulator retargetability, Proceedings of the conference on Design, automation and test in Europe, p.100-es, January 1999, Munich, Germany [doi>10.1145/307418.307549]
• 13: Alexandru Nicolau , Roni Potasman , Haigeng Wang, Register Allocation, Renaming and Their Impact on Fine-Grain Parallelism, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.218-235, August 07-09, 1991
• 14: David A. Berson , Rajiv Gupta , Mary Lou Soffa, Resource Spackling: A Framework for Integrating Register Allocation in Local and Global Schedulers, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.135-146, August 24-26, 1994
• 15: Steven Novack , Alexandru Nicolau, Mutation Scheduling: A Unified Approach to Compiling for Fine-Grain Parallelism, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.16-30, August 08-10, 1994
• 16: A. Halambi, P. Grtm, H. Tomiyama, N. Dutt, and A. Nicolau, "Automatic software toolkit generation for embedded systemson-chip," In Proc. of ICVC, 1999.
• 17: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 18: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 19: 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
• 20: Scott McFarling, Procedure merging with instruction caches, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.71-79, June 24-28, 1991, Toronto, Ontario, Canada
• 21: Hiroyuki Tomiyama , Hiroto Yasuura, Code placement techniques for cache miss rate reduction, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.4, p.410-429, Oct. 1997 [doi>10.1145/268424.268469]
• 22: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 23: Peter Grun , Nikil Dutt , Alex Nicolau, MIST: an algorithm for memory miss traffic management, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 24: Peter Grun , Nikil Dutt , Alex Nicolau, Memory aware compilation through accurate timing extraction, Proceedings of the 37th conference on Design automation, p.316-321, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337428]
• 25: Yau-Tsun Steven Li , Sharad Malik , Benjamin Ehrenberg, Performance Analysis of Real-Time Embeded Software, Kluwer Academic Publishers, Norwell, MA, 1998
• 26: Christian Ferdinand , Reinhard Wilhelm, Efficient and Precise Cache Behavior Prediction for Real-TimeSystems, Real-Time Systems, v.17 n.2-3, p.131-181, Nov. 1999 [doi>10.1023/A:1008186323068]
• 27: Ali Dasdan , Rajesh K. Gupta, Timing analysis of embedded real-time systems, 1999
• 28: Chang-Gun Lee , Joosun Hahn , Yang-Min Seo , Sang Lyul Min , Rhan Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Analysis of Cache-Related Preemption Delay in Fixed-Priority Preemptive Scheduling, IEEE Transactions on Computers, v.47 n.6, p.700-713, June 1998 [doi>10.1109/12.689649]
• 29: Hiroyuki Tomiyama , Nikil D. Dutt, Program path analysis to bound cache-related preemption delay in preemptive real-time systems, Proceedings of the eighth international workshop on Hardware/software codesign, p.67-71, May 2000, San Diego, California, United States [doi>10.1145/334012.334025]
• 30: A. Datta, S. Choudhury, A. Basu, H. Tomiyama, and N. Dutt, "Task layout generation to minimize cache miss penalty for preemptive real time tasks: An ILP approach," In Prec. of 9th SASIMI, 2000.
• 31: Peter Grun , Florin Balasa , Nikil Dutt, Memory size estimation for multimedia applications, Proceedings of the 6th international workshop on Hardware/software codesign, p.145-149, March 15-18, 1998, Seattle, Washington, United States
• 32: E. De Greef, F. Catthoor, and H. De Man, "Memory size reduction through storage order optimization for embedded parallel multimedia applications," In Prec. of Workshop on Par. Prec. and Multimedia, Int'l. Par. Prec. Symp (IPPS), 1997.
• 33: R. van de Wiel, Code Compaction Bibliography, ht t p://www.win.t ue.nl/rikvdw/bibl.ht ml, 2000.
• 34: Ireneusz Karkowski , Henk Corporaal, Exploiting Fine- and Coarse-grain Parallelism in Embedded Programs, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.60, October 12-18, 1998
• 35: Koen Danckaert , Kostas Masselos , Francky Catthoor , Hugo De Man, Strategy for power efficient combined task and data parallelism exploration illustrated on a QSDPCM video codec, Journal of Systems Architecture: the EUROMICRO Journal, v.45 n.10, p.791-808, April 1999 [doi>10.1016/S1383-7621(98)00039-3]
• 36: Vivek Tiwari , Sharad Malik , Andrew Wolfe , Mike Tien-Chien Lee, Instruction level power analysis and optimization of software, Journal of VLSI Signal Processing Systems, v.13 n.2-3, p.223-238, Aug./Sept. 1996 [doi>10.1007/BF01130407]
• 37: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 38: Wen-Tsong Shiue , Chaitali Chakrabarti, Memory exploration for low power, embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.140-145, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309902]
• 39: Chidamber Kulkarni , Francky Catthoor , Hugo De Man, Advanced Data Layout Optimization for Multimedia Applications, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.186-193, May 01-05, 2000
• 40: H. Tomiyama , T. Ishihara , A. Inoue , H. Yasuura, Instruction scheduling for power reduction in processor-based system design, Proceedings of the conference on Design, automation and test in Europe, p.855-860, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 41: Scott Rixner , William J. Dally , Ujval J. Kapasi , Peter Mattson , John D. Owens, Memory access scheduling, Proceedings of the 27th annual international symposium on Computer architecture, p.128-138, June 2000, Vancouver, British Columbia, Canada
• 42: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 43: N. Vijaykrishnan , M. Kandemir , M. J. Irwin , H. S. Kim , W. Ye, Energy-driven integrated hardware-software optimizations using SimplePower, Proceedings of the 27th annual international symposium on Computer architecture, p.95-106, June 2000, Vancouver, British Columbia, Canada
• 44: M. Kandemir , N. Vijaykrishnan , M. J. Irwin , W. Ye, Influence of compiler optimizations on system power, Proceedings of the 37th conference on Design automation, p.304-307, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337425]
• 45: Diana Marculescu, Profile-driven code execution for low power dissipation (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.253-255, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344619]
• 46: The COPPER Project: Compiler-Controlled Continuous Power- Performance Management, The Center for Embedded Computer Systems, University of California, Irvine, http://www.cecs.uci.edu/~copper.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers

  C. Computer Systems Organization

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Languages, Performance, Theory