Some efficient solutions to the affine scheduling problem. I: One- dimensional time

DOI10.1007/BF01407835zbMath0783.90050MaRDI QIDQ687632

Paul Feautrier

Publication date: 20 December 1993

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

zbMATH Keywords

precedence constraintsautomatic parallelizationautomatic systolic array designclosed form schedulesparametric linear programsystems of recurrence equations

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Parallel numerical computation (65Y05) Distributed algorithms (68W15)

Related Items

Heterogeneous LBM Simulation Code with LRnLA Algorithms ⋮ Generation of parallel synchronization-free tiled code ⋮ Scalable and structured scheduling ⋮ Locally recursive non-locally asynchronous algorithms for stencil computation ⋮ Parallelization of sequential programs: distribution of arrays among processors and structurization of communications ⋮ Affine scheduling on bounded convex polyhedric domains is asymptotically optimal ⋮ Maximum flows in parametric graph templates ⋮ A consistent generation of pipeline parallelism and distribution of operations and data among processors ⋮ Incremental closure for systems of two variables per inequality ⋮ Quantifier elimination in automatic loop parallelization ⋮ ON THE OPTIMALITY OF ALLEN AND KENNEDY'S ALGORITHM FOR PARALLELISM EXTRACTION IN NESTED LOOPS ⋮ Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs ⋮ On loop transformations of nested loops with affine dependencies ⋮ Synthesizing ranking functions for loop programs via SVM ⋮ Ranking Functions for Linear-Constraint Loops ⋮ Automatic array partitioning based on the Smith normal form ⋮ Some efficient solutions to the affine scheduling problem. II: Multidimensional time

Uses Software

• Lucid
• PipLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computability of recurrence equations
• Synthesizing systolic arrays from recurrence equations
• Optimal code parallelization using unimodular transformations
• Dataflow analysis of array and scalar references
• Mapping uniform loop nests onto distributed memory architectures
• The parallel execution of DO loops
• The Organization of Computations for Uniform Recurrence Equations