Loop skewing: the wavefront method revisited

DOI10.1007/BF01407876MaRDI QIDQ1822225zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1986

Published in International Journal of Parallel Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01407876

zbMATH Keywords

compiler optimizationexecution of nested loopsloop interchangingLoop normalizationparallel and vector computersparallelismtransformation of loop boundsvector and parallel code

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Theory of operating systems (68N25)

Review text

Loop skewing is a new procedure to derive the wavefront method of execution of nested loops. The wavefront method is used to 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. The 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.

Recommendations

• Revisiting cycle shrinking
• scientific article; zbMATH DE number 618313
• scientific article; zbMATH DE number 1487613
• Scheduling Sequential Loops on Parallel Processors
• On loop transformations of nested loops with affine dependencies

Cites work

• Automatic translation of FORTRAN programs to vector form
• scientific article; zbMATH DE number 194119 (Why is no real title available?)
• The parallel execution of DO loops
• Time and Parallel Processor Bounds for Fortran-Like Loops

Cited in

(4)

• Parallel versions of Stone's strongly implicit algorithm
• On Linear Skewing Schemes and d-Ordered Vectors
• scientific article; zbMATH DE number 1863549 (Why is no real title available?)
• Heterogeneous LBM Simulation Code with LRnLA Algorithms

This page was built for publication: Loop skewing: the wavefront method revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822225)