Vectorizing for a SIMdD DSP architecture

ABSTRACT

The Single Instruction Multiple Data (SIMD) model for finegrained parallelism was recently extended to support SIMD operations on disjoint vector elements. In this paper we demonstrate how SIMdD (SIMD on disjoint data) supports e#ective vectorization of digital signal processing (DSP) benchmarks, by facilitating data reorganization and reuse. In particular we show that this model can be adopted by a compiler to achieve nearoptimal performance for important classes of kernels.

REFERENCES

• 1: Krste Asanovic , David Johnson, Torrent Architecture Manual, University of California at Berkeley, Berkeley, CA, 1997
• 2: A. J. C. Bik, M. Girkar, P. M. Grey, and X. Tian. Efficient exploitation of parallelism on Pentium III and Pentium 4 processor-based systems. Intel Technology J., February 2001.
• 3: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 4: William Y. Chen , Roger A. Bringmann , Scott A. Mahlke , Richard E. Hank , James E. Sicolo, An efficient architecture for loop based data preloading, Proceedings of the 25th annual international symposium on Microarchitecture, p.92-101, December 01-04, 1992, Portland, Oregon, United States
• 5: Keith D. Cooper , Ken Kennedy , Nathaniel McIntosh, Cross-Loop Reuse Analysis and Its Application to Cache Optimizations, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.1-19, August 08-10, 1996
• 6: Jesus Corbal , Mateo Valero , Roger Espasa, Exploiting a new level of DLP in multimedia applications, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.72-79, November 16-18, 1999, Haifa, Israel
• 7: Paul D'Arcy and Scott Beach. StarCore SC140: A new DSP architecture for portable devices. In Wireless Symposium. Motorola, September 1999.
• 8: Keith Diefendorff , Pradeep K. Dubey , Ron Hochsprung , Hunter Scales, AltiVec Extension to PowerPC Accelerates Media Processing, IEEE Micro, v.20 n.2, p.85-95, March 2000 [doi>10.1109/40.848475]
• 9: Gautam Doshi , Rakesh Krishnaiyer , Kalyan Muthukumar, Optimizing Software Data Prefetches with Rotating Registers, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.257-267, September 08-12, 2001
• 10: Texas Instruments. www.ti.com/sc/c6x, 2000.
• 11: M. Kandemir, I. Kadayif, A. Choudhary, and J. A. Zambreno. Optimizing internest data locality. In PACT, pages 127--135, 2002.
• 12: Andreas Krall , Sylvain Lelait, Compilation Techniques for Multimedia Processors, International Journal of Parallel Programming, v.28 n.4, p.347-361, August 2000 [doi>10.1023/A:1007507005174]
• 13: Samuel Larsen, Emmett Witchel, and Saman Amarasinghe. Techniques for increasing and detecting memory alignment. Technical Memo 621, MIT LCS, November 2001.
• 14: J. H. Moreno , M. Moudgill , K. Ebcioğlu , E. Altman , C. B. Hall , R. Miranda , S.-K. Chen , A. Polyak, Simulation/evaluation environment for a VLIW processor architecture, IBM Journal of Research and Development, v.41 n.3, p.287-302, May 1997
• 15: J. H. Moreno , V. Zyuban , U. Shvadron , F. D. Neeser , J. H. Derby , M. S. Ware , K. Kailas , A. Zaks , A. Geva , S. Ben-David , S. W. Asaad , T. W. Fox , D. Littrell , M. Biberstein , D. Naishlos , H. Hunter, An innovative low-power high-performance programmable signal processor for digital communications, IBM Journal of Research and Development, v.47 n.2-3, p.299-326, March 2003
• 16: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 17: Huy Nguyen , Lizy Kurian John, Exploiting SIMD parallelism in DSP and multimedia algorithms using the AltiVec technology, Proceedings of the 13th international conference on Supercomputing, p.11-20, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305150]
• 18: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Efficient Utilization of Scratch-Pad Memory in Embedded Processor Applications, Proceedings of the 1997 European conference on Design and Test, p.7, March 17-20, 1997
• 19: Alex Peleg , Uri Weiser, MMX Technology Extension to the Intel Architecture, IEEE Micro, v.16 n.4, p.42-50, August 1996 [doi>10.1109/40.526924]
• 20: Keshav Pingali , Micah Beck , Richard Johnson , Mayan Moudgill , Paul Stodghill, Dependence flow graphs: an algebraic approach to program dependencies, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-78, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99595]
• 21: Matthew Allan Postiff , Trevor Mudge, Compiler and microarchitecture mechanisms for exploiting registers to improve memory performance, 2001
• 22: Jaewook Shin , Jacqueline Chame , Mary W. Hall, Compiler-Controlled Caching in Superword Register Files for Multimedia Extension Architectures, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.45-55, September 22-25, 2002
• 23: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: RISC/CISC, VLIW architectures
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

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

General Terms:
Algorithms, Performance

Keywords:
SIMD, compiler controlled cache, data reuse, rotating register file, subword parallelism, vectorization, viterbi