Affordable Access

Publisher Website

Transformations of nested loops with non-convex iteration spaces

Authors
Journal
Parallel Computing
0167-8191
Publisher
Elsevier
Publication Date
Volume
22
Issue
3
Identifiers
DOI: 10.1016/0167-8191(95)00069-0
Keywords
  • Parallel Processing
  • Loop Transformation
  • Nested Loops
  • Non-Convex Iteration Space
  • Quasi-Convex Polyhedron
  • Maximal Normal Form
  • Minimal Normal Form
  • Spmd
Disciplines
  • Linguistics

Abstract

Abstract When compiling for parallel machines, it is often necessary to generate a loop nest to scan a region of index points in lexicographic order. One well-known application example is the use of loop transformations to restructure loop nests. Previous work shows how to generate code to scan a convex polyhedron (possibly intersected with a lattice), a region derived from an application of a non-singular transformation to a convex iteration space. The driving force behind this work is to investigate how to generate code for non-singular transformations of nested loops with non-convex iteration spaces. The final result is a method that generates code for a union of convex polyhedra, possibly intersected with a lattice. Two other applications that are discussed include generation of data transfer code for machines with a hierarchical memory and construction of SPMD programs for distributed memory parallel machines.

There are no comments yet on this publication. Be the first to share your thoughts.