Abstract
Loop skewing is a new procedure to derive the wavefront method of execution of nested loops. The wavefront method is used to execute nested loops on parallel and vector computers when none of the loops can be done in vector mode. Loop skewing is a simple transformation of loop bounds and is combined with loop interchanging to generate the wavefront. This derivation is particularly suitable for implementation in compilers that already perform automatic detection of parallelism and generation of vector and parallel code, such as are available today. Loop normalization, a loop transformation used by several vectorizing translators, is related to loop skewing, and we show how loop normalization, applied blindly, can adversely affect the parallelism detected by these translators.
Similar content being viewed by others
References
M. Wolfe, Optimizing Supercompilers for Supercomputers, Ph. D. Thesis, Dept. of Comp. Sci. Rpt. No. 82-1105, Univ. of Illinois, Urbana, Illinois, (October, 1982).
J. R. Allen and K. Kennedy, Automatic Loop Interchange,Proc. of the ACM SIGPLAN '84 Symposium on Compiler Construction, Montreal, Canada, SIGPLAN Notices19, (6):233–246, (June 1984).
J. R. Allen and K. Kennedy, Automatic Translation of Fortran Programs to Vector Form,Supercomputers: Design and Applications, Kai Hwang, (ed.), IEEE Computer Society Press, Silver Spring, Maryland, pp. 186–203, (1982).
J. R. Allen and K. Kennedy, Automatic Translation of Fortran Programs to Vector Form, Tech. Rpt. COMP TR84-9, Rice Univ., Houston, Texas, (July 1984).
D. Kuck, R. Kuhn, B. Leasure, and M. Wolfe, The Structure of an Advanced Vectorizer for Pipelined Processors,Proc. of COMPSAC 80, The 4th Int'l Computer Software and Applications Conf., Chicaga, Illinois, pp. 709–715 (October 1980).
D. Kuck, R. Kuhn, B. Leasure, and M. Wolfe, The Structure of an Advanced Retargetable Vectorizer,Supercomputers: Design and Applications, Kai Hwang (ed.), IEEE Computer Society Press, Silver Spring, Maryland, pp. 163–178 (1982).
Y. Muraoka,Parallelism Exposure and Exploitation in Programs, Ph. D. Thesis Dept. of Comp. Sci. Rpt. No. 71-424, University of Illinois, Urbana, Illinois, (February 1971).
U. Banerjee, S. C. Chen, D. Kuck, and R. Towle, Time and Parallel Processor Bounds for Fortran-Like Loops,IEEE Trans. on Computers,C 28 (9): 660–670 (September 1979).
R. H. Kuhn, Optimization and Interconnection Complexity for: Parallel Processors, Single-Stage Networks, and Decision Trees, Ph. D. Thesis, Dept. of Comp. Sci. Rpt. No. 80-1009, University of Illinois, Urbana, Illinois, (February 1980).
L. Lamport, The Parallel Execution of DO Loops,Comm. of the ACM,17(2):83–93 (February 1974).
U. Banerjee, Data Dependence in Ordinary Programs, M. S. Thesis, Dept. of Comp. Sci. Rpt. No. 76-837, Univ. of Illinois, Urbana, IL, (November 1976).
U. Banerjee, Speedup of Ordinary Programs, Ph. D. Thesis, Dept. of Comp. Sci. Rpt. No. 79-989, University of Illinois, Urbana Illinois, (October 1979).
D. Kuck,The Structure of Computers and Computations, Vol. I, John Wiley and Sons, Inc., New York, (1978).
C. Huson et al., The KAP/205: An Advanced Source-to-Source Vectorizer for the Cyber 205 Supercomputer,Proc. of the 1986 Int'l Conf. on Parallel Processing St. Charles, IL, IEEE Computer Society Press, Washington, DC, pp. 827–832 (August 1986).
J. Davies et al., The KAP/S-1: An Advanced Source-to-Source Vectorizer for the S-1 Mark IIa Supercomputer,Proc. of the 1986 Int'l Conf. on Parallel Processing, St. Charles, Illinois, IEEE Computer Society Press, Washington, DC, pp. 833–835 (August 1986).
T. Macke et al., The KAP/ST-100: An Advanced Source-to-Source Vectorizer for the ST-100 Attached Processor,Proc. of the 1986 Int'l Conf. on Parallel Processing, St. Charles, Illinois, IEEE Computer Society Press, Washington, DC, pp. 171–175 (August 1986).
M. Wolfe, Advanced Loop Interchanging,Proc. of the 1986 Int'l Conf. on Parallel Processing, St. Charles, Illinois, IEEE Computer Society Press, Washington, DC, pp. 536–543 (August 1986).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wolfe, M. Loops skewing: The wavefront method revisited. Int J Parallel Prog 15, 279–293 (1986). https://doi.org/10.1007/BF01407876
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01407876