caa a22 4500 445852054 CHVBK 20180317145416.0 cr unu---uuuuu 170323e20110501xx s 000 0 eng 10.1007/s11227-009-0364-8 doi (NATIONALLICENCE)springer-10.1007/s11227-009-0364-8 An approximate method for filtering out data dependencies with a sufficiently large distance betweenmemoryreferences [Elektronische Daten] [Patricio Bulić, Tomaž Dobravec] 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 single SIMD operation if the distance between memory references is greater than or equal to the number of data processed in the SIMD register. Some loops that could not be vectorized on traditional vector processors, can still be parallelized for short SIMD execution. There are a number of approximate data-dependence tests that have been proposed in the literature but in all of them data dependency will be assumed when actually there is no such a dependence that could restrict parallelization related to the short SIMD execution model. By examining the properties of linear subscript expressions of possibly conflicting data references, our algorithm gives the green light to the parallelization process if some sufficient conditions regarding the dependence distance are met. Our method is based on the Banerjee test and checks the minimum and maximum distances between memory references within the iteration space rather than searching for the existence of an integer solution to the dependence equation. The proposed method extends the accuracy and applicability of the classical Banerjee test. Springer Science+Business Media, LLC, 2009 Data dependency nationallicence Multimedia extensions nationallicence SIMD instructions nationallicence Vectorizing compilers nationallicence Bulić Patricio Faculty of Computer and Information Science, University of Ljubljana, Tržaška c. 25, 1000, Ljubljana, Slovenia aut Dobravec Tomaž Faculty of Computer and Information Science, University of Ljubljana, Tržaška c. 25, 1000, Ljubljana, Slovenia aut The Journal of Supercomputing Springer US; http://www.springer-ny.com 56/2(2011-05-01), 226-244 0920-8542 56:2<226 2011 56 11227 https://doi.org/10.1007/s11227-009-0364-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11227-009-0364-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bulić Patricio Faculty of Computer and Information Science, University of Ljubljana, Tržaška c. 25, 1000, Ljubljana, Slovenia aut NATIONALLICENCE 700 1- Dobravec Tomaž Faculty of Computer and Information Science, University of Ljubljana, Tržaška c. 25, 1000, Ljubljana, Slovenia aut NATIONALLICENCE 773 0- The Journal of Supercomputing Springer US; http://www.springer-ny.com 56/2(2011-05-01), 226-244 0920-8542 56:2<226 2011 56 11227 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer