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 constraints; automatic parallelization; automatic systolic array design; closed form schedules; parametric linear program; systems of recurrence equations

Mathematics Subject Classification ID

90C31: Sensitivity, stability, parametric optimization

90C05: Linear programming

90B35: Deterministic scheduling theory in operations research

65Y05: Parallel numerical computation

68W15: Distributed algorithms

Related Items

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

Uses Software

• Lucid
• PipLib

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item