An efficient way to filter out data dependences with a sufficiently large distance between memory references
Abstract
There are a number of data dependence tests that have been proposed in the literature. The most widely used approximate data dependence tests are the Banerjee inequality and the GCD test. In this paper we consider parallelization for microprocessors with the multimedia extensions. For the short SIMD parallelism extraction it is essential that, if dependency exists, then the distance between memory references is greater than or equal to the number of data processed in the SIMD register. This implies that some loops that could not be vectorized on traditional vector processors can still be parallelized for the short SIMD execution. In this paper we present an accurate and simple method that can filter out data dependences with a sufficiently large distance between memory references for linear array references within a nested loop. The presented method is suitable for use in a dependence analyzer that is organized as a series of tests, progressively increasing in accuracy, as a replacement for the GCD or Banerjee tests.
References
[1]
Banerjee U., Eigenman R., Nicolau A., Padua D. A., 1993. Automatic Program Parallelization. Proceedings of the IEEE. 81 (2), 211--243.
[2]
Banerjee U., 1997. Dependence Analysis: A Book Series on Loop Transformations for Restructuring Compilers. Kluwer Academic Publishers, Dordrecht.
[3]
Bik A. J. C., Girkar M., Grey P. M., Tian X. M., 2002. Automatic Intra-Register Vectorization for the Intel (R) Architecture. International Journal of Parallel Programming. 30 (2), 65--98.
[4]
Bulić P., Guštin V., 2003. An Extended ANSI C for Processors with a Multimedia Extension. International Journal of Parallel Programming. 31 (2), 107--136.
[5]
Chang W. L., Chu C. P., 2001. The Generalized Direction Vector I Test. Parallel Computing. 27 (8), 1117--1144.
[6]
Chen Z. Q., Xu B. W., Zhao J. J., 2002. An overview of methods for dependence analysis of concurrent programs. ACM SIGPLAN Notices. 37 (8), 45--52.
[7]
Cockshott P., 2002. Vector pasal reference manual. ACM SIGPLAN Notices. 37 (6), 59--81.
[8]
Eichenberger A. E., Wu P., O'Brien K., 2004. Vectorization for SIMD Architectures with alignment constraints. ACM SIGPLAN Notices. 39 (6), 82--93.
[9]
Kong X., Klappholz D., Psarris K., 1991. The I Test: An Improved Dependence Test for Automatic Parallelization and Vectorization. IEEE Transactions on Parallel and Distributed Systems. 2 (3), 342--349.
[10]
Kral S., Franchetti F., Lorenz J., Ueberhuber C. W., 2003. SIMD vectorization of straight line FFT code. Lecture Notes in Computer Science. 2790, 251--260.
[11]
Kral S., Franchetti F., Lorenz J., et al., 2004. FFT compiler techniques. Lecture Notes in Computer Science. 2985, 217--231.
[12]
Krall A., Lelait S., 2000. Compilation Techniques for Multimedia Processors. International Journal of Parallel Programming. 28 (4), 347--361.
[13]
Larsen S., Amarasinghe S., 2000. Exploiting superword level parallelism with multimedia instruction sets. ACM SIGPLAN Notices. 35 (5), 145--156.
[14]
Lee R., 1995. Accelerating Multimedia with Enhanced Processors. IEEE Micro. 15 (2), 22--32.
[15]
Lee R., Smith M. D., 1996. Media Processing: A New Design Target. IEEE Micro. 16 (4), 6--9.
[16]
Oberman S., Favor G., Weber F., 1999. AMD 3DNow! Technology: Architecture and Implementation. IEEE Micro. 19 (2), 37--48.
[17]
Peleg A., Weiser U., 1996. MMX Technology Extension to the Intel Architecture. IEEE Micro. 16 (4), 42--50.
[18]
Pokam G., Bihan S., Simonnet J., Bodin F., 2004. SWARP: a retargetable preprocessor for multimedia instructions. Concurrency And Computation-Practice & Experience. 16 (2--3), 303--318.
[19]
Pough W., 1992. A Practical Algorithm for Exact Array Dependence Analysis. Communications of the ACM. 35 (8), 102--114.
[20]
Psarris K., Klappholz D., Kong X., 1991. On the Accuracy of the Banerjee Test, Shared Memory Multiprocessors (special issue). Journal of Parallel and Distributed Computing. 12(2).
[21]
Psarris K., Klappholz D., Kong X., 1993. The Direction Vector I Test. IEEE Transactions on Parallel and Distributed Systems. 4 (11), 1280--1290.
[22]
Sreraman N., Govindarajan R., 2000. A Vectorizing Compiler for Multimedia Extensions. International Journal of Parallel Programming. 28 (4), 363--400.
[23]
Tanaka H., Kobayashi S., Takeuchi Y., et al., 2003. A code selection method for SIMD processors with PACK instructions. Lecture Notes in Computer Science. 2826, 66--80.
[24]
Wolfe M. J., Banerjee U., 1987. Data Dependence and its Application to Parallel Processing. International Journal of Parallel Programming. 16 (2), 137--178.
[25]
Wolfe M. J., Tseng C. W., 1992. The Power Test for Data Dependence. IEEE Transactions on Parallel and Distributed Systems. 3 (5), 591--601.
[26]
Wolfe M. J., 1996. High Performance Compilers for Parallel Computing. Addison-Wesley Publishing Company.
[27]
Zima H. P., Chapman B. M., 1990. Supercompilers for Parallel and Vector Computers. Addison-Wesley Publishing Company.
Index Terms
- An efficient way to filter out data dependences with a sufficiently large distance between memory references
Recommendations
Exploitation of parallelism to nested loops with dependence cycles
In this paper, we analyze the recurrences from the breakability of the dependence links formed in general multi-statements in a nested loop. The major findings include: (1) A sink variable renaming technique, which can reposition an undesired anti-...
An approximate method for filtering out data dependencies with a sufficiently large distance between memory references
In this paper we present an approximate algorithm for detecting and filtering data dependencies with a sufficiently large distance between memory references. A sequence of the same operations (typically enclosed in a `for' loop) can be replaced with a ...
Communication-Free Alignment for Array References with Linear Subscripts in Three Loop Index Variables or Quadratic Subscripts
Bau et al. proposed an efficient and precise data alignment method to ascertain whether there is communication-free alignment of array reference function with linear subscripts in one loop index variable. Chu et al. presented an efficient and precise ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2005 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 April 2005
Published in SIGPLAN Volume 40, Issue 4
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 192Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in