ON THE OPTIMALITY OF ALLEN AND KENNEDY'S ALGORITHM FOR PARALLELISM EXTRACTION IN NESTED LOOPS
作者： ALAIN DARTE , FRÉDÉRIC VIVIEN*†
DOI: 10.1080/01495739708941417
关键词:
摘要: 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. In other words, loop distribution sufficient detecting graphs with
sci-hub.se 参考文章(28)
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)
Thomas Kailath, Vwani Prasad Roychowdhury, Derivation, extensions and parallel implementation of regular iterative algorithms Stanford University. ,(1989)
Dirk Grunwald, Data Dependence Analysis: The Lambda Test Revisited. international conference on parallel processing. pp. 220- 223 ,(1990)
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