Versatility of extended subwords and the matrix register file

ABSTRACT

Extended subwords and the matrix register file (MRF) are two micro architectural techniques that address some of the limitations of existing SIMD architectures. Extended subwords are wider than the data stored in memory. Specifically, for every byte of data stored in memory, there are four extra bits in the media register file. This avoids the need for data-type conversion instructions. The MRF is a register file organization that provides both conventional row-wise, as well as column-wise, access to the register file. In other words, it allows to view the register file as a matrix in which corresponding subwords in different registers corresponds to a column of the matrix. It was introduced to accelerate matrix transposition which is a very common operation in multimedia applications. In this paper, we show that the MRF is very versatile, since it can also be used for other permutations than matrix transposition. Specifically, it is shown how it can be used to provide efficient access to strided data, as is needed in, e.g., color space conversion. Furthermore, it is shown that special-purpose instructions (SPIs), such as the sum-of-absolute differences (SAD) instruction, have limited usefulness when extended subwords and a few general SIMD instructions that we propose are supported, for the following reasons. First, when extended subwords are supported, the SAD instruction provides only a relatively small performance improvement. Second, the SAD instruction processes 8-bit subwords only, which is not sufficient for quarter-pixel resolution nor for cost functions used in image and video retrieval. Results obtained by extending the SimpleScalar toolset show that the proposed techniques provide a speedup of up to 3.00 over the MMX architecture. The results also show that using, at most, 13 extra media registers yields an additional performance improvement ranging from 1.38 to 1.57.

REFERENCES

• 1: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 2: Baron, M. 2005. Cortex-A8: High speed, low power. Microprocessor Rep. 11, 14, 1--6.
• 3: Bartkowiak, M. 2001. Optimizations of color transformation for real time video decoding. In Proceedings of the EURASIP Conference on Digital Signal Processing for Multimedia Communications and Services.
• 4: Bensaali, F. and Amira, A. 2005. Accelerating colour space conversion on reconfigurable hardware. Image Vision Comput. 23, 935--942.
• 5: Sourav Chatterji , Manikandan Narayanan , Jason Duell , Leonid Oliker, Performance Evaluation of Two Emerging Media Processors: VIRAM and Imagine, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.229.1, April 22-26, 2003
• 6: Sagarmay Deb, Video Data Management and Information Retrieval, IRM Press, 2005
• 7: 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]
• 8: Flachs, B., Asano, S., Dhong, S. H., Hofstee, H. P., Gervais, G., Kim, R., Le, T., Liu, P., Leenstra, J., Michael, J. L. B., Oh, H. J., Mueller, S. M., Takahashi, O., Hatakeyama, A., Watanabe, Y., Yano, N., Brokenshire, D. A., Peyravian, M., Vandung, T., and Iwata, E. 2006. The microarchitecture of the synergistic processor for a cell processor. IEEE J. Solid-State Circuits 41, 63--70.
• 9: John Goodacre , Andrew N. Sloss, Parallelism and the ARM Instruction Set Architecture, Computer, v.38 n.7, p.42-50, July 2005 [doi>10.1109/MC.2005.239]
• 10: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 11: Gwennap, L. 1996. Digital, MIPS add multimedia extensions. Microprocessor Rep. 10, 15, 24--28.
• 12: Libo Huang , Mingche Lai , Kui Dai , Hong Yue , Li Shen, Hardware Support for Arithmetic Units of Processor with Multimedia Extension, Proceedings of the 2007 International Conference on Multimedia and Ubiquitous Engineering, p.633-637, April 26-28, 2007 [doi>10.1109/MUE.2007.134]
• 13: IBM 2007. Synergistic Processor Unit Instruction Set Architecture. IBM. Version 1.2.
• 14: Matthew D. Jennings , Thomas M. Conte, Subword Extensions for Video Processing on Mobile Systems, IEEE Concurrency, v.6 n.3, p.13-16, July 1998 [doi>10.1109/4434.708250]
• 15: Juurlink, B., Borodin, D., Meeuws, R. J., Aalbers, G. T., and Leisink, H. 2007. The SimpleScalar Instruction Tool (SSIT) and the SimpleScalar Architecture Tool (SSAT). Available via http://ce.et.tudelft.nl/~shahbahrami
• 16: Kozyrakis, C., Gebis, J., Martin, D., Williams, S., Mavroidis, I., Pope, S., Jones, D., Patterson, D., and Yelick, K. 2000. Vector IRAM: A media-oriented vector processor with embedded DRAM. In Proceedings of the 12th International Conference on Hot Chips.
• 17: Peter M. Kuhn , Kuhn Peter M., Algorithms, Complexity Analysis and VLSI Architectures for MPEG-4 Motion Estimation, Kluwer Academic Publishers, Norwell, MA, 1999
• 18: 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
• 19: Lee, A. J. T., Hong, R. W., and Chang, M. F. 2004. An approach to content-based video retrieval. In Proceedings of the IEEE International Conference on Multimedia and Expo. Vol. 1. 273--276.
• 20: J. Lee , N. Vijaykrishnan , M. J. Irwin , W. Wolf, An Architecture for Motion Estimation in the Transform Domain, Proceedings of the 17th International Conference on VLSI Design, p.1077, January 05-09, 2004
• 21: Ruby B. Lee , Michael D. Smith, Guest Editors' Introduction: Media Processing: A New Design Target, IEEE Micro, v.16 n.4, p.6-9, August 1996 [doi>10.1109/MM.1996.526920]
• 22: 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
• 23: Motorola Inc. 1998. AltiVec Technology Programming Environments Manual. Motorola Inc. Rev.0.1.
• 24: Dorit Naishlos , Marina Biberstein , Shay Ben-David , Ayal Zaks, Vectorizing for a SIMdD DSP architecture, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951714]
• 25: Alex Peleg , Sam Wilkie , Uri Weiser, Intel MMX for multimedia PCs, Communications of the ACM, v.40 n.1, p.24-38, Jan. 1997 [doi>10.1145/242857.242865]
• 26: Charles A. Poynton, A technical introduction to digital video, John Wiley & Sons, Inc., New York, NY, 1996
• 27: Majid Rabbani , Paul W. Jones, Digital Image Compression Techniques, Society of Photo-Optical Instrumentation Engineers (SPIE), Bellingham, WA, 1991
• 28: Srinivas K. Raman , Vladimir Pentkovski , Jagannath Keshava, Implementing Streaming SIMD Extensions on the Pentium III Processor, IEEE Micro, v.20 n.4, p.47-57, July 2000 [doi>10.1109/40.865866]
• 29: Seshan, N. 1998. High VelociTI Processing. IEEE Signal Processing Mag. 15, 2, 86--101.
• 30: Asadollah Shahbahrami , Ben Juurlink , Demid Borodin , Stamatis Vassiliadis, Avoiding conversion and rearrangement overhead in SIMD architectures, International Journal of Parallel Programming, v.34 n.3, p.237-260, June 2006 [doi>10.1007/s10766-006-0015-0]
• 31: Asadollah Shahbahrami , Ben Juurlink , Stamatis Vassiliadis, Accelerating Color Space Conversion Using Extended Subwords and the Matrix Register File, Proceedings of the Eighth IEEE International Symposium on Multimedia, p.37-46, December 11-13, 2006 [doi>10.1109/ISM.2006.16]
• 32: Asadollah Shahbahrami , Ben Juurlink , Stamatis Vassiliadis, Limitations of special-purpose instructions for similarity measurements in media SIMD extensions, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176796]
• 33: Shanableh, T. and Ghanbari, M. 2000. Heterogeneous video transcoding to lower spatio-temporal resolutions and different encoding formats. IEEE Trans. Multimedia 2, 2, 101--110.
• 34: Nathan Slingerland , Alan Jay Smith, Measuring the Performance of Multimedia Instruction Sets, IEEE Transactions on Computers, v.51 n.11, p.1317-1332, November 2002 [doi>10.1109/TC.2002.1047756]
• 35: Tamhankar, A. and Rao, K. R. 2003. An overview of H.264/MPEG-4 Part 10. In Proceedings of the 4th International Conference on Video and Image Processing and Multimedia Communications. 1--51.
• 36: Texas Instruments 2007. TMS320C64x/C64x+ DSP CPU and Instruction Set Reference Guide. Texas Instruments. Literature Number: SPRU732D.
• 37: Marc Tremblay , J. Michael O'Connor , Venkatesh Narayanan , Liang He, VIS Speeds New Media Processing, IEEE Micro, v.16 n.4, p.10-20, August 1996 [doi>10.1109/40.526921]
• 38: Liwei Wang , Yan Zhang , Jufu Feng, On the Euclidean Distance of Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.8, p.1334-1339, August 2005 [doi>10.1109/TPAMI.2005.165]
• 39: Zhang, D. and Lu, G. 2003. Evaluation of similarity measurement for image rretrieval. In Proceedings of the IEEE International Conference on Neural Networks and Signal Processing. Vol. 2. 928--931.

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
SIMD architectures, SIMD programming, multimedia standards