Optimizing techniques for saturated arithmetic with first-order linear recurrence

ABSTRACT

Saturated arithmetic is a typical operation in multimedia applications, most multimedia extensions in the instruction set architecture (ISA) of modern processors provide saturation instructions for such operation. Therefore, extensive researches have focused on how to utilize saturation instructions to optimize programs. Previous algorithms mainly focus on purely saturated arithmetic, however saturated arithmetic is often mingled with first-order linear recurrence (FOLR) in real life applications. When FLOR pattern appears in the program, previous algorithms can not identify the saturated arithmetic as well.

In fact, the saturated arithmetic with FOLR (SAWF) is a new and significant pattern, especially, SAWF with one as coefficient is frequently used in multimedia applications. Hence, it is necessary to explore a method with which such pattern can be efficiently vectorized. This paper discusses how to vectorize SAWF, explores the efficient method to vectorize SAWF with one as coefficient and gives its evaluation and implement a library for the optimizing technique. Such an implementation manner can make compilers are able to exploit it more easily. The experimental results shows the optimizing technique can achieve a speedup of 1.19 to 1.46 on Pentium IV processor. At the same time, the optimizing techniques in this paper can also be used to develop a library for SAWF so a programmer can benefit even without changing the compiler.

REFERENCES

• 1: Gang Ren , Peng Wu , David Padua, An Empirical Study On the Vectorization of Multimedia Applications for Multimedia Extensions, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.89.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.94]
• 2: Aart J. C. Bik, Milind Girkae, Paul M. Grey, Xinmin Tian. Automatic Detection of Saturation and Clipping Idioms. Proceedings of the 15th International Workshop on Languages and Compilers for parallel computers, July, 2002
• 3: 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]
• 4: Nathan T. Slingerland , Alan Jay Smith, Design and characterization of the Berkeley multimedia workload, Multimedia Systems, v.8 n.4, p.315-327, July 2002 [doi>10.1007/s005300200052]
• 5: Ren G, Wu P, Padua D. A Preliminary Study On the Vectorization of Multimedia Applications for Multimedia Extensions. Proc. Of the 16th Int'l WorkShop on Languages and Compilers for Parallel Computing. 2003
• 6: Weihua Jiang, Chao Mei, BoHuang, Jianhui Li, Jiahua Zhu, Binyu Zang, Chuanqi Zhu. Boosting the Performance of Multimedia Applications Using SIMD Instructions. Compiler Constructions. 2005
• 7: Jiahua Zhu, HongJiang Zhang, Hui Shi, Binyu Zang, Chuanqi Zhu "Overflow Controlled SIMD Arithmetic". The 17th International Workshop on Languages and Compilers for Parallel Computing (LCPC 04)
• 8: Hong-soog Kim , Young-ha Yoon , Dong-soo Han, Parallel Processing of First Order Linear Recurrence on SMP Machines, The Journal of Supercomputing, v.27 n.3, p.295-310, March 2004 [doi>10.1023/B:SUPE.0000011389.69863.dc]
• 9: M. Nakamura, Y. Okabe, and T. Tsuda. New fast algorithms for first-order linear recurrences on vector computers. In 5th Workshop on Compilers for Parallel Computers, pp. 167C174, June 1995.
• 10: Haigeng Wang , Alexandru Nicolau , Stephen Keung , Kai-Yeung Sunny Siu, Computing Programs Containing Band Linear Recurrences on Vector Supercomputers, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.769-782, August 1996 [doi>10.1109/71.532109]
• 11: Y. Tanaka , K. Iwasawa , S. Gotoo , Y. Umetani, Compiling techniques for first-order liner recurrences on a Vector computer, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.174-181, November 12-17, 1988, Orlando, Florida, United States
• 12: Haigeng Wang , Alexandru Nicolau , Stephen Keung , Kai-Yeung Siu, Scalable Techniques for Computing Band Linear Recurrences on Massively Parallel and Vector Supercomputers, Proceedings of the 8th International Symposium on Parallel Processing, p.502-508, April 01, 1994
• 13: 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]
• 14: Bess Zheng , Jenn-Yuan Tsai , B. Y. Zhang , T. Chen , B. Huang , J. H. Li , Y. H. Ding , J. Liang , Y. Zhen , Pen-Chung Yew , Chuan-Qi Zhu, Designing the Agassiz Compiler for Concurrent Multithreaded Architectures, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.380-398, August 04-06, 1999

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
FOLR, SAWF, SIMD, optimization