preprint · OpenGrey (Institut de l'Information Scientifique et Technique) · 1992

Scheduling Uniform Loop Nests

Alain Darte, Yves Robert, Ecole Normale Superieure de Lyon, 69 (France). Lab. de l'Informatique du Parallelisme, Centre National de la Recherche Scientifique (CNRS), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme, Institut Informatique et Mathematiques Appliquees de Grenoble (IMAG), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme

Cited by 3Abstract and details only

Abstract

This paper surveys scheduling techniques for uniform loop nests. First we introduce the hyperplane method and related variants. Then we extend it by using a different affine scheduling for each statement within the nest. In both cases we present a new, constructive and efficient method to determine optimal solutions. 1 Introduction Loop nests lie in the heart of supercompilers-parallelizers for supercomputers. On one hand their importance in terms of applications is evident: in many scientific programs, the time spent in the execution of a couple of loops represents a large fraction of the total execution time, while the potential parallelism of these loops is often very important. On the other hand, the regular and repetitive structure of loop nests greatly facilitates the use of dependence analysis techniques and of scheduling and allocation strategies. The general problem of finding the optimal scheduling for a task system on a parallel machine is NP-hard (due to the communications...

Cite this paper

APA 7

Darte, A., Robert, Y., Ecole Normale Superieure de Lyon, F. L. D. L. D. P., Centre National de la Recherche Scientifique (CNRS), L. F. L. D. L. D. P., & Institut Informatique et Mathematiques Appliquees de Grenoble (IMAG), L. F. L. D. L. D. P. (1992). Scheduling Uniform Loop Nests. OpenGrey (Institut de l'Information Scientifique et Technique).

MLA 9

Darte, Alain, et al. “Scheduling Uniform Loop Nests.” OpenGrey (Institut de l'Information Scientifique et Technique), 1992.

Chicago

Darte, Alain, Yves Robert, 69 (France). Lab. de l'Informatique du Parallelisme Ecole Normale Superieure de Lyon, 69 - Lyon (France). Lab. de l'Informatique du Parallelisme Centre National de la Recherche Scientifique (CNRS), and 69 - Lyon (France). Lab. de l'Informatique du Parallelisme Institut Informatique et Mathematiques Appliquees de Grenoble (IMAG). 1992. “Scheduling Uniform Loop Nests.” OpenGrey (Institut de l'Information Scientifique et Technique).

Harvard

Darte, A. et al. (1992) ‘Scheduling Uniform Loop Nests’, OpenGrey (Institut de l'Information Scientifique et Technique).

BibTeX

@misc{darte1992scheduling,
  title = {{Scheduling Uniform Loop Nests}},
  author = {Darte, Alain and Robert, Yves and Ecole Normale Superieure de Lyon, 69 (France). Lab. de l'Informatique du Parallelisme and Centre National de la Recherche Scientifique (CNRS), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme and Institut Informatique et Mathematiques Appliquees de Grenoble (IMAG), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme},
  journal = {OpenGrey (Institut de l'Information Scientifique et Technique)},
  year = {1992}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.