Browse Prior Art Database

Balancing data locality and coarse-grained parallelism in loop permutation

IP.com Disclosure Number: IPCOM000127531D
Original Publication Date: 2005-Aug-31
Included in the Prior Art Database: 2005-Aug-31
Document File: 2 page(s) / 142K

Publishing Venue

IBM

Abstract

In this note, we present some principles for loop selection algorithm for permuting nested loops in an auto -parallelizing compiler. It will help us to further develop algorithms considering both data locality and coarse-grained parallelism.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Balancing data locality and coarse -grained parallelism in loop permutation

Abstract. In this note, we present some principles for loop selection algorithm for permuting nested loops in an auto -parallelizing compiler. It will help us to further develop algorithms considering both data locality and coarse-grained par-allelism.

Keywords: parallelizing compiler, data dependence, loop permutation, data locality, parallel do

1 Description

Before we present our discussion in details, we need to introduce the underlining model to analyze the problem.

1.1 Analyzing model

The data dependence vectors[1] are still our principle tools to analyze and verify the transformation that we are going to apply on a loop nest. Suppose δ = {δ 1... δ n} is a hybrid distance/direction vector with the most precise information derivable. It represents a data dependence between two array references, corresponding left to right from the outermost loop to innermost loop enclosing the references. Data dependences are loop-independent if the accesses to the same memory location occur in the same loop iteration; they are loop-carried if the accesses occur on different loop iterations. For example, if we have

  as a loop nest from L1 to Ln, we may have two dependences SA and SB characterizing the nested loops, which were caused by S1/S2 and T1/T2. For simplicity, we assume that f, g, u, v are linear functions of the loop induction variables in this note. Furthermore,

  is a 2 by n dependence matrix, denoted as D. More generally, the number of rows in a dependence matrix may be from one to any positive number, depending on how many references in the loop body.

1

[This page contains 2 pictures or other non-text objects]

Page 2 of 2

We introduce two theorems.

  Theorem 1 (C-level interchangeable). Loop Lc and Lc-1 are interchangeable if and only if for any δ in D, δ ≠ (=(c-2)<> ... ), where, =(c-2) means there are (c - 2) directions as "=" before the first "<".

  Theorem 1 and its variant forms can be fou...