On the Optimality of Allen and Kennedy's Algorithm for Parallel Extraction in Nested Loops
作者： Alain Darte , Frédéric Vivien
关键词: Parallelism (grammar) 、 Parallel computing 、 Nested loop join 、 Algorithm 、 Cycles per instruction 、 Computer science 、 Link (geometry)
摘要: We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each abstraction, minimal transformations needed extraction. The result of this paper that Allen Kennedy's algorithm optimal when dependences are approximated by levels. This means even most sophisticated cannot detect more than found algorithm, as long level only information available.
springer.com
core.ac.uk 
sci-hub.st 参考文章(25)
Xiangyun Kong, David Klappholz, Kleanthis Psarris, The I Test: A New Test for Subscript Data Dependence. international conference on parallel processing. pp. 204- 211 ,(1990)
Callahan, A global approach to detection of parallelism Rice University. ,(1987)
Yi Qing Yang, Tests des dependances et transformations de programme Paris 6. ,(1993)
Utpal K. Banerjee, Dependence analysis for supercomputing ,(1988)
Yoichi Muraoka, Parallelism exposure and exploitation in programs University of Illinois at Urbana-Champaign. ,(1971)
Michael Wolfe, Optimizing Supercompilers for Supercomputers ,(1989)
Yi-Qing Yang, Corinne Ancourt, François Irigoin, Minimal Data Dependence Abstractions for Loop Transformations languages and compilers for parallel computing. pp. 201- 216 ,(1994) , 10.1007/BFB0025880
A. Darte, F. Vivien, A classification of nested loops parallelization algorithms emerging technologies and factory automation. ,vol. 1, pp. 217- 234 ,(1995) , 10.1109/ETFA.1995.496776
Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time International Journal of Parallel Programming. ,vol. 21, pp. 313- 348 ,(1992) , 10.1007/BF01407835
Yi-Qing Yang, Corinne Ancourt, François Irigoin, Minimal data dependence abstractions for loop transformations: extended version International Journal of Parallel Programming. ,vol. 23, pp. 359- 388 ,(1995) , 10.1007/BF02577771