New Loop Transformation Techniques for Massive Parallelism

Abstract

This paper presents new loop transformation techniques that can extract more parallelism from a class of programs than existing techniques. A formal mathematical framework which unifies the existing loop transformation techniques is given. We classify schedules of a loop transformation into three classes: uniform, subdomain-variant, and statement-variant. New algorithms for generating these schedules are given. Viewing from the degree of parallelism to be gained by loop transformation, the schedules can also be classified as single-sequential level, multiple-sequential level, and mixed schedule. We described iterative and recursive algorithms to obtain multiple-sequential level and mixed schedules respectively based on the algorithms for single-sequential level schedules.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1990
Accession Number
ADA249325

Entities

People

  • Lee-chung Lu
  • Marina Chen

Organizations

  • Yale University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Decomposition
  • Dynamic Programming
  • Equations
  • Inequalities
  • Intervals
  • Iterations
  • Linear Programming
  • Lisp Programming Language
  • Nonlinear Programming
  • Nonlinear Systems
  • Two Dimensional
  • Vector Spaces

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Computational Linguistics
  • Systems Analysis and Design