A SIMD optimization framework for retargetable compilers

ABSTRACT

Retargetable C compilers are currently widely used to quickly obtain compiler support for new embedded processors and to perform early processor architecture exploration. A partially inherent problem of the retargetable compilation approach, though, is the limited code quality as compared to hand-written compilers or assembly code due to the lack of dedicated optimizations techniques. This problem can be circumvented by designing flexible, retargetable code optimization techniques that apply to a certain range of target architectures. This article focuses on target machines with SIMD instruction support, a common feature in embedded processors for multimedia applications. However, SIMD optimization is known to be a difficult task since SIMD architectures are largely nonuniform, support only a limited set of data types and impose several memory alignment constraints. Additionally, such techniques require complicated loop transformations, which are tailored to the SIMD architecture in order to exhibit the necessary amount of parallelism in the code. Thus, integrating the SIMD optimization and the required loop transformations together in a single retargeting formalism is an ambitious challenge. In this article, we present an efficient and quickly retargetable SIMD code optimization framework that is integrated into an industrial retargetable C compiler. Experimental results for different processors demonstrate that the proposed technique applies to real-life target machines and that it produces code quality improvements close to the theoretical limit.

REFERENCES

• 1: Associated Computer Experts (ACE). The COSY compiler development system. http://www.ace.nl.
• 2: Advanced RISC Machines Ltd. The ARM11 processor. http://www.arm.com.
• 3: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 4: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 5: Cheong, G. and Lam, M. S. 1997. An optimizer for multimedia instruction sets. In Proceedings of the 2nd SUIF Compiler Workshop. Stanford University, CA.
• 6: Coware Inc. Processor Designer. http://www.coware.com.
• 7: Alexandre E. Eichenberger , Peng Wu , Kevin O'Brien, Vectorization for SIMD architectures with alignment constraints, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 8: Joseph A. Fisher, Customized instruction-sets for embedded processors, Proceedings of the 36th ACM/IEEE conference on Design automation, p.253-257, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309923]
• 9: Franchetti, F., Kral, S., Lorenz, J., and Ueberhuber, C. W. 2005. Efficient utilization of SIMD extensions. Proc. IEEE. 93, 2, 409--425.
• 10: Christopher W. Fraser , David R. Hanson , Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.213-226, Sept. 1992 [doi>10.1145/151640.151642]
• 11: Christopher W. Fraser , Robert R. Henry , Todd A. Proebsting, BURG: fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, v.27 n.4, p.68-76, April 1992 [doi>10.1145/131080.131089]
• 12: Glöckler, T., Bitterlich, S., and Meyr, H. 2000. ICORE: a low-power application specific instruction set processor for DVB-T acquisition and tracking. In Proceedings of the 13th Annual IEEE International ASIC/SOC Conference. IEEE, Los Alamitos, CA.
• 13: GNU Compiler Collection. Auto-vectorization in GCC. http://gcc.gnu.org/projects/tree-ssa/vectorization.html.
• 14: Matthias Gries , Kurt Keutzer, Building ASIPs: The Mescal Methodology, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 15: A. Hoffman , T. Kogel , H. Meyr, A framework for fast hardware-software co-simulation, Proceedings of the conference on Design, automation and test in Europe, p.760-765, March 2001, Munich, Germany
• 16: Andreas Hoffmann , Heinrich Meyr , Rainer Leupers, Architecture Exploration for Embedded Processors with Lisa, Kluwer Academic Publishers, Norwell, MA, 2002
• 17: Manuel Hohenauer , Hanno Scharwaechter , Kingshuk Karuri , Oliver Wahlen , Tim Kogel , Rainer Leupers , Gerd Ascheid , Heinrich Meyr , Gunnar Braun , Hans van Someren, A Methodology and Tool Suite for C Compiler Generation from ADL Processor Models, Proceedings of the conference on Design, automation and test in Europe, p.21276, February 16-20, 2004
• 18: Manuel Hohenauer , Christoph Schumacher , Rainer Leupers , Gerd Ascheid , Heinrich Meyr , Hans van Someren, Retargetable code optimization with SIMD instructions, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176291]
• 19: Intel Corporation. Intel C compiler. http://www.intel.com.
• 20: Akira Kitajima , Makiko Itoh , Jun Sato , Akichika Shiomi , Yoshinori Takeuchi , Masaharu Imai, Effectiveness of the ASIP design system PEAS-III in design of pipelined processors, Proceedings of the 2001 conference on Asia South Pacific design automation, p.649-654, January 2001, Yokohama, Japan [doi>10.1145/370155.370573]
• 21: Andreas Krall , Sylvain Lelait, Compilation techniques for multimedia processors, International Journal of Parallel Programming, v.28 n.4, p.347-361, Aug. 2000 [doi>10.1023/A:1007507005174]
• 22: Alexei Kudriavtsev , Peter Kogge, Generation of permutations for SIMD processors, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 23: Samuel Larsen , Saman Amarasinghe, Exploiting superword level parallelism with multimedia instruction sets, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.145-156, June 18-21, 2000, Vancouver, British Columbia, Canada
• 24: Samuel Larsen , Emmett Witchel , Saman P. Amarasinghe, Increasing and Detecting Memory Address Congruence, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.18-29, September 22-25, 2002
• 25: Rainer Leupers, Code Optimization Techniques for Embedded Processors: Methods, Algorithms, and Tools, Kluwer Academic Publishers, Norwell, MA, 2000
• 26: Rainer Leupers, Code selection for media processors with SIMD instructions, Proceedings of the conference on Design, automation and test in Europe, p.4-8, March 27-30, 2000, Paris, France [doi>10.1145/343647.343679]
• 27: Rainer Leupers , Peter Marwedel, Retargetable compiler technology for embedded systems: tools and applications, Kluwer Academic Publishers, Norwell, MA, 2001
• 28: Prabhat Mishra , Nikil Dutt , Alex Nicolau, Functional abstraction driven design space exploration of heterogeneous programmable architectures, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500061]
• 29: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 30: Dorit Nuzman , Richard Henderson, Multi-platform Auto-vectorization, Proceedings of the International Symposium on Code Generation and Optimization, p.281-294, March 26-29, 2006 [doi>10.1109/CGO.2006.25]
• 31: Dorit Nuzman , Ira Rosen , Ayal Zaks, Auto-vectorization of interleaved data for SIMD, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 32: NXP Semiconductors. The TriMedia media processor. http://www.nxp.com.
• 33: Oraioglu, A. and Veidenbaum, A. 2003. Application specific microprocessors (Guest Editors' Introduction). IEEE Des.Test Comput. 20.
• 34: Gilles Pokam , Stéphane Bihan , Julien Simonnet , François Bodin, SWARP: a retargetable preprocessor for multimedia instructions: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.2-3, p.303-318, January 2004 [doi>10.1002/cpe.v16:2/3]
• 35: Pryanishnikov, I., Krall, A., and Horspool, N. 2003. Pointer alignment analysis for processors with SIMD instructions. In Proceedings of the 5th Workshop on Media and Streaming Processors. ACM, New York.
• 36: Ren, G., Wu, P., and Padua, D. 2003. A preliminary study on the vectorization of multimedia applications for multimedia extensions. In Proceedings of the 16th International Workshop of Languages and Compilers for Parallel Computing. Springer, Berlin, Germany.
• 37: Gang Ren , Peng Wu , David Padua, Optimizing data permutations for SIMD devices, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 38: Rizzolo, N. and Padua, D. 2005. HiLO: high level optimization of FFTs. In Proccedings of the 18th International Conference on Languages and Compilers for High Performance Computing. Springer, Berlin, Germany, 238--252.
• 39: Tensilica, Inc. Xtensa C compiler. http://www.tensilica.com.
• 40: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 41: Peng Wu , Alexandre E. Eichenberger , Amy Wang, Efficient SIMD Code Generation for Runtime Alignment and Length Conversion, Proceedings of the international symposium on Code generation and optimization, p.153-164, March 20-23, 2005 [doi>10.1109/CGO.2005.18]
• 42: Zivojnovic, V., Velarde, J., Schläger, C., and Meyr, H. 1994. DSPStone—a DSP-oriented benchmarking methodology. In Proceedings of the International Conference on Signal Processing Applications and Technology (ICSPAT). IASTED, Calgary, Alberta.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Algorithms, Performance

Keywords:
ASIP, SIMD, retargetable compilers, subword parallelism, vectorization