Probabilistic source-level optimisation of embedded programs

ABSTRACT

Efficient implementation of DSP applications is critical for many embedded systems. Optimising C compilers for embedded processors largely focus on code generation and instruction scheduling which, with their growing maturity, are providing diminishing returns. This paper empirically evaluates another approach, namely source-level transformations and the probabilistic feedback-driven search for "good" transformation sequences within a large optimisation space. This novel approach combines two selection methods: one based on exploring the optimisation space, the other focused on localised search of good areas. This technique was applied to the UTDSP benchmark suite on two digital signal and multimedia processors (Analog Devices TigerSHARC TS-101, Philips TriMedia TM-1100) and an embedded processor derived from a popular general-purpose processor architecture (Intel Celeron 400). On average, our approach gave a factor of 1.71 times improvement across all platforms equivalent to an average 41% reduction in execution time, outperforming existing approaches. In certain cases a speedup of up to ͠ 7 was found for individual benchmarks.

REFERENCES

• 1: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 2: F. Bodin, T. Kisuki, P.M.W. Knijnenburg, M.F.P. O'Boyle and E. Rohou. Iterative Compilation in a Non-linear Optimisation Space. In Proceedings of the 1998 Workshop on Profile and Feedback Directed Compilation, Organised in conjunction with PACT'98, 1998.
• 3: C. Brandolese , W. Fornaciari , F. Salice , D. Sciuto, Source-level execution time estimation of C programs, Proceedings of the ninth international symposium on Hardware/software codesign, p.98-103, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371694]
• 4: K. Chow and Y. Wu. Feedback-directed selection and characterization of compiler optimizations. In Proceedings of the 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4), December 2001.
• 5: K. D. Cooper, D. Subramanian, and L. Torczon. Adaptive Optimizing Compilers for the 21st Century. In Proceedings of the 2001 LACSI Symposium, Los Alamos Computer Science Institute, October 2001.
• 6: K. D. Cooper, A. Grosul, T.J. Harvey, S. Reeves, D. Subramanian, L. Torzon, and T. Waterman Exploring the Structure of the Space of Compilation Sequences Using Randomized Search Algorithms In Proceedings of the 2004 LACSI Symposium, Santa Fe, NM, October 2004.
• 7: H. Falk. An approach for automated application of platform-dependent source code transformations. http://ls12-www.cs.uni-dortmund.de/~falk/, 2001.
• 8: Björn Franke , Michael O'boyle, Array recovery and high-level transformations for DSP applications, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.132-162, May 2003 [doi>10.1145/643470.643472]
• 9: G. Fursin, M. O'Boyle, and P. Knijnenburg. Evaluating iterative compilation. In Proceedings of Languages and Compilers for Parallel Computers (LCPC'02), College Park, MD, USA, 2002.
• 10: E.F. Granston and A. Holler. Automatic recommendation of compiler options. In Proceedings of the 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4), December 2001.
• 11: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 12: Mahmut T. Kandemir , Narayanan Vijaykrishnan , Mary Jane Irwin , Hyun Suk Kim, Experimental Evaluation of Energy Behavior of Iteration Space Tiling, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.142-157, August 10-12, 2000
• 13: T. Kisuki , P. M. W. Knijnenburg , M. F. P. O'Boyle, Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.237, October 15-19, 2000
• 14: Prasad Kulkarni , Wankang Zhao , Hwashin Moon , Kyunghwan Cho , David Whalley , Jack Davidson , Mark Bailey , Yunheung Paek , Kyle Gallivan, Finding effective optimization phase sequences, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 15: C. Lee. UTDSP benchmark suite. http://www.eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.html, 1998.
• 16: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Code optimization techniques for embedded DSP microprocessors, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.599-604, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217596]
• 17: Clifford Liem , Pierre Paulin , Ahmed Jerraya, Address calculation for retargetable compilation and exploration of instruction-set architectures, Proceedings of the 33rd annual conference on Design automation, p.597-600, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240631]
• 18: R. P. J. Pinkers , P. M. W. Knijnenburg , M. Haneda , H. A. G. Wijshoff, Statistical Selection of Compiler Options, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'04), p.494-501, October 04-08, 2004
• 19: M. Saghir, P. Chow, and C. Lee. A comparison of traditional and VLIW DSP architecture for compiled DSP applications. In International Workshop on Compiler and Architecture Support for Embedded Systems (CASES '98), Washington, DC, USA, 1998.
• 20: B. Su, J. Wang, and A. Esguerra. Source-level loop optimization for DSP code generation. In Proceedings of 1999 IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP '99), volume 4, pages 2155--2158, Phoenix, AZ, 1999.
• 21: S. Triantafyllis, M. Vachharajani, and D.I. August. Compiler Optimization-Space Exploration. The Journal of Instruction-Level Parallelism, volume 7, January 2005.
• 22: Michael J. Voss , Rudolf Eigemann, High-level adaptive program optimization with ADAPT, ACM SIGPLAN Notices, v.36 n.7, p.93-102, July 2001
• 23: V. Zivojnovic, J. Velarde, C. Schlager, and H. Meyr. DSPstone: A DSP-oriented benchmarking methodology. In Proceedings of the International Conference on Signal Processing Applications & Technology (ICSPAT '94), pages 715--720, Dallas, TX, USA, 1994.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization; Retargetable compilers

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Experimentation, Performance

Keywords:
adaptive compilation, digital signal processing, feedback-directed optimization, iterative compilation, source-level optimization