Pack instruction generation for media pUsing multi-valued decision diagram

ABSTRACT

SIMD instructions are often implemented in modern multimedia oriented processors. Although SIMD instructions are useful for many digital signal processing applications, most compilers do not exploit SIMD instructions. The difficulty in the utilization of SIMD instructions stems from data parallelism in registers. In assembly code generation, the positions of data in registers must be noted. A technique of generating pack instructions which pack or reorder data in registers is essential for exploitation of SIMD instructions. This paper presents a code generation technique for SIMD instructions with pack instructions. SIMD instructions are generated by finding and grouping the same operations in programs. After the SIMD instruction generation, pack instructions are generated. In the pack instruction generation, Multi-valued Decision Diagram (MDD) is introduced to represent and to manipulate sets of packed data. Experimental results show that our code generation technique can generate assembly code with SIMD and pack instructions performing complex repacking of 8 packed data in registers for a commercial VLIW processor with 6 pack instructions and achieved speedup ratio of up to 7.7.

REFERENCES

• 1: Media embedded Processor, http://www.mepcore.com. 2005.
• 2: Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
• 3: S. M. Arvind Srinivasan Timothy Kam and R. K. Brayton. Algorithms for discrete function manipulation. In Proceedings of the IEEE International Conference on Computer-Aided Design, pages 92--95, November 1990.
• 4: Aart J. C. Bik , Milind Girkar , Paul M. Grey , Xinmin Tian, Automatic intra-register vectorization for the Intel architecture, International Journal of Parallel Programming, v.30 n.2, p.65-98, April 2002 [doi>10.1023/A:1014230429447]
• 5: 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
• 6: 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
• 7: 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
• 8: Rainer Leupers, Code Optimization Techniques for Embedded Processors: Methods, Algorithms, and Tools, Kluwer Academic Publishers, Norwell, MA, 2000
• 9: T. Miyamori, J. Tanabe, Y. Taniguchi, K. Furukawa, T. Kozakaya, H. Nakai, Y. Miyamoto, K. Maeda, and M. Matsui. Development of image recognition processor based on configurable processor. Journal of Robotics and Mechatronics, 17(4):437--446, 2005.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
SIMD instructions, multi-valued decision diagram