Dependency의 종류

• RAW(Read-After-Write) : 우리가 관심 가질것...
• WAR(Write-After-Read) : ?
• WAR(Write-After-Write) : linearly independent 할 시 파이프라이닝 가능
• RAR(Read-After-Read) : Data Reuse에 활용

Example

두개의 인스턴스(S1, S2)가 존재하는 코드

for(i = 1; i <= 10; i++)
  s[i] = ...; //S1
  for(j = 0; j < 3; j++)
    a[i][j] = s[i]; //S2

S1.write -> S2.read
본 코드에서는 RAW 디펜던시가 존재함

수학적 표현

Equation 1

$∀<s, t> \in P_e,\space (s \in D^{Si}, t \in D^{Sj}),\space T_{Si}(s) \prec T_{Sj}(t)$

원본 프로그램에서 "source" 인스턴스가 "target" 인스턴스보다 먼저 실행해야 하는 경우, 변환된 프로그램은 위 속성을 유지해야 함(의존성을 충족해야 함).

Lexicographic Order

original

S1(0, i, 0, 0, 0) >> S2(0, i, 1, j, 0)

illegal transform

S1(0, i, 1, 0, 0) >> S2(0, i, 0, j, 0)

Dependence Relation

Dependence relation은 세가지의 종류로 분류 가능함

Uniform dependences
두 dependent iteration이 상수일 경우

• (i) -> (i + 1)
• (i, j) -> (i + 1, j + 1)

Non-uniform dependences

• (i) -> (i + j)
• (i) -> (2i)

Parametric dependences

• (i) -> (i + N)
• (i + N) -> (j + M)

Dependence Polyhedron

Objective: compute the set of statement instances which are dependent

Some of the several possible approaches:

• Distance vector: compute an indicator of the distance between two dependent iteration
  • Problems: approximative for non-uniform dependences
• Best solution: Dependence polyhedron, list of sets of dependent instances, with a set of dependence polyhedra for each pair of statements

Principle: model all pairs of instances in dependence

Definition (Dependence of statement instances)
A statement R depends on a statement $S$ (written $S → R$) if there exists an operation $S(\vec x_S )$ and $R(\vec x_R )$ and a memory location m such that:

• $S(\vec x_S )$ and $R(\vec x_R )$ refer to the same memory location m, and at least one of them writes to that location,
• $x_S$ and $x_R$ belongs to the iteration domain of $R$ and $S$,
• in the original sequential order, $S(\vec x_S )$ is executed before $R(\vec x_R )$.

Data Dependent Graph

구문이 종속적인 경우 구문 사이에는 에지가 있습니다. 그리고 각 에지에 대해 주어진 레벨 l에서 $S → R$에 대한 dependence polyhedron를 정의하고 주어진 참조 쌍 $f_R$ , $f_S$에 대해 정의합니다.

• 주어진 아핀 배열 액세스 쌍에 대해 항상 dependence polyhedron를 구축할 수 있음
• 반복 영역과 액세스 함수도 정확하다면 정확합니다.
• 정의하는 모든 제약 조건이 아핀이므로 행렬로 표현할 수 있습니다.

합법적인 프로그램 변환

• 종속성이 하이퍼플레인을 거꾸로 가로지르는 경우 변환은 불법
• 두 하이퍼플레인 사이에서 정방향으로 가는 종속성은 순차성을 나타냄
• 하이퍼플레인의 어떤 지점 사이에도 종속성이 없으면 병렬성을 나타냄

Definition (Precedence condition)
Given $Θ^T$ a schedule for the instance of $T$, $Θ^S$ a schedule for the instance of $S$. $Θ^T$ and $Θ^S$ are legal schedules if $∀ < \vec x_S$ , $\vec x_T > ∈ D_{S,T}$ : $Θ^S << Θ^T$
Equivalently: $∆_{T,S} = Θ^T − Θ^S \geq 1$

Pluto 알고리즘

legality condition

non-uniform dependences의 경우 j에 대한 함수로 변환

Step-by-Step Example

for (i = 0; i < N; i++){
  for (j = 1; j < N; j++){
    a[i][j] = a[j][i] + a[i][j-1]; //S1
  }
}

• a[i][j].write => a[i][j-1].read : RAW1
• a[i][j].write => a[j][i].read : RAW2

Example for Dependency Polyhedron

Eample Loopnest

for (i=0; i<=N; i++){
  for (j=0; j<=N; j++){
    A[i][k] = A[i + 1][j + 1];  //(S1)
  }
}

Iteration Domain

Array Reference Function:
a.k.a: access function

Precedence Order