Data Dependence Analysis for Parallelization

병렬화를 위한 자료 종속성 분석 기법

$ATA $EPENDENCE !NALYSIS FOR 0ARALLELIZATION

김진미* - +IM 병렬프로그래밍연구실 선임연구원 민옥기/ ' -IN 병렬프로그래밍연구실 선임연구원 우영춘9 # 7OO 병렬프로그래밍연구실 선임연구원 변석우3 7 "YUN 병렬프로그래밍연구실 선임연구원

최적화 컴파일러 및 병렬 컴파일러는 종속성 분석을 통하여 프로그램의 문장 사이동작들 간에 가해지 는 실행 순서 상의 제약 조건을 추출한다이러한 제약 조건은 계산의 의미를 보존하기 위한 필요 조건들 이며컴파일러의 성능을 향상시키기 위한 프로그램의 변환은 이 제약 조건을 만족하는 범위에서 수행되 어야 한다본 고에서는 컴파일러에서 최적화 및 병렬화할 프로그램의 부분과 적용될 변형 기법 등을 결 정하기 위해 필요한 종속성 분석에 대한 내용을 다룬다

)

최적화 컴파일러 및 병렬 컴파일러는 종속성 분석을 통하여 프로그램의 문장 사이에 가해지는 실행 순서 상의 제약 조건을 추출한다 이러한 제 약 조건은 계산의 의미를 보존하기 위한 필요 조 건들이며 모든 프로그램 변환은 이 제약 조건을 만족하는 범위에서 수행되어야 한다;=

병렬 컴퓨터에서 수행되는 프로그램들은 내부 에 존재하는 병렬성에 따라 병렬로 수행되더라도 결과의 정확성이 보장되어야 한다 즉 순차적으 로 수행되는 경우의 결과가 병렬로 수행되는 경우 에도 보장되어야만 하며 순차 프로그램의 루프를 병렬 수행시키기 위해서는 자료 종속성을 정확하 게 파악하는 일이 매우 중요하다

본 고에서는 컴파일러에서 최적화 및 병렬화

할 프로그램의 부분과 적용될 변형 기법 등을 결 정하기 위해 필요한 종속성 분석에 대한 내용을 다룬다 ))장에서는 루프에서의 자료 종속성 관계 조건문에서의 자료 종속성 그리고 병렬 루프에서 의 자료 종속성에 관련한 기본적인 사항들에 대 해 설명하고 )))장에서는 루프 단위의 종속성 분 석에 필요한 배열 원소들에 대한 종속성 분석에 대 해 설명하고 기본적인 종속성 검사법에 대해 알아 본다 )6장에서는 기술된 내용의 요약으로 맺음한 다

))

컴파일러는 프로그램 내에 표현된 자료 종속 성 관계들을 분석하여 문장 사이에 가해지는 순



전 전 전

전자자자자통통통통신신신동신동동동향향향분향분분분석석석석 제 권 제 호 년 월

서 두개 이상의 연산에 가해지는 순서 혹은 루프 의 반복 사이에 가해지는 순서를 재배열함으로서 효율성을 증진시킬 수가 있다 종속성 분석은 실 행 순서상의 제약 조건을 추출하므로 재배열된 프 로그램이 수행되는 결과는 변환 전의 프로그램이 수행되는 결과와 같아야 한다 따라서 자료 종속 성을 정확히 파악하는 일은 매우 중요한 일이다

종속성은 제어 종속성CONTROL DEPENDENCE 과 자료 종속성DATA DEPENDENCE 으로 나누어진다

문장 #3의 실행 결과가 문장 #3의 실행 여부를 결정할 때 #3는 #3에 제어 종속 관계에 있다고 한다 자료 종속성이란 같은 메모리 장소를 접근 하는 두 문장 사이에 발생하는 실행 순서 상의 제 약 조건을 말한다 자료 종속성은 다시 흐름 종속 성aOW DEPENDENCE  반 종속성ANTI DEPENDENCE  출력 종속성OUTPUT DEPENDENCE 의 세 유형으로 분류할 수 있다 아래의 예에서 문장 3의 변수

!에 값이 기록된 후에 3에서 변수 !의 읽기가 발생할 때 3는 3에 흐름 종속성이 있다고 하며 3에서 변수 $를 읽은 후에 3에서 새로운 값이 기록될 때 3은 3에 반 종속적이라고 하고 3과 3에서 처럼 두 문장에서 동시에 동일한 변수에 값이 기록될 때 출력 종속 관계에 있다고 한다

캐쉬 등의 메모리 위계를 효율적으로 하기 위한 최적화 컴파일러의 경우에는 입력INPUT 종속성 도 고려된다 3에서 변수 !를 읽고 3에서 변수

!를 읽을 때 이를 입력 종속성 관계에 있다고 한 다; =

3  !   3  "  ! 3  #  ! $ 3  $   3  !  

컴파일러는 종속성 정보를 나타내기 위하여 자 료 종속성 그래프DATA DEPENDENCE GRAPH 를 생성 한다 그래프 내에서 노드NODE 는 한 문장을 표 현하고 두 노드 사이의 호ARC 는 종속성을 나타 낸다

 루프에서의 자료 종속성

루프에서는 루프 내의 문장들이 여러 번 반복 수행하므로 프로그램 수행 시간의 대부분을 차지 하게 된다 이러한 루프를 최적화하거나 병렬화 시키기 위해서는 종속성 분석을 통하여 적절하 게 루프를 변형한다 다음의 예와 같이 두 문장 3와 3가 루프의 같은 회전에서는 종속성이 없 으나 두 연속적인 회전 사이에서 종속성을 갖고 있을 때 3와 3는 루프 전이 종속성LOOP CARRIED DEPENDENCE 을 갖고 있다고 한다 )  K일 때 3는 K p의 회전시에 3에 의해 기록된 8K p 의 값 을 읽음을 알 수 있다

3 FOR )   TO  DO 3 8;)=  9 ;)=  :;)=

3 !;)=  8;) p=  3 ENDFOR

이를 루프를 펼쳐 살펴보면 루프의 각 회전 시에 3의 8에 할당된 값은 루프의 다음 회전시 3의 8값에서 참조됨을 알 수 있다



병렬화를 위한 자료 종속성 분석 기법

)   3 8;=  9 ;= :;=

3 !;=  8;=   )   3  8;=  9 ;=  :;=

3  !;=  8;=   )   3  8;=  9 ;=  :;=

3  !;=  8;=  

루프가 실행될 때에는 일정한 크기로 증가 혹 은 감소하는 루프 제어 변수를 매개로 배열 변수 를 일정한 패턴으로 접근하는 일이 매우 빈번하 게 발생된다 따라서 루프를 구성하는 문장들 사 이의 종속성 분석은 배열 변수 첨자식SUBSCRIPT EXPRESSION 분석을 중심으로 진행된다 종속성 분 석에 의하여 일단 종속성이 있다고 결론이 나면 그 종속성에 대하여 기술을 하여야 한다 일반적 으로 가능한 해집합을 모두 저장하기보다는 이에 대한 방향 정보나 거리 정보를 저장하는 게 보통 이다 이 정보를 거리 벡터DISTANCE VECTOR 나 방 향 벡터DIRECTION VECTOR 라고 한다

FOR )   TO N FOR *   TO N p

!;) *=  !;) *= !;) p * = 

ENDFOR ENDFOR

루프의 특정 회전은 루프 제어 변수의 벡터로 나타낼 수 있다 위의 프로그램에서 회전 I J 

  과 I J    일 때를 살펴 보면   회 전이 먼저 진행되어 배열 원소 !; =에 값을 기 록하게 된다 이 값을   회전에서 읽게 되므 로   회전에서   회전으로 흐름 종속성

이 있음을 알 수 있다 이 때 종속성 거리는 

 p     p 이 된다 이 예에서의 종속 성 거리는 모든 종속 관계를 갖는 모든 루프 회 전 쌍에 대하여 성립한다 이러한 종속성 거리를 거리 벡터라고 한다 적법한 거리 벡터는 사전적 으로LEXICOGRAPHICALLY  벡터보다 크다 즉 거리 벡터의 원소 중 첫 번째 이 아닌 원소는 양수이 어야 한다 거리 벡터가  보다 작다는 것은 시간 적으로 먼저 진행되는 루프 회전에서 실행되는 문 장이 나중에 진행되는 회전에서 실행되는 문장에 종속됨을 의미한다

거리 벡터 각 원소의 극성만 알아도 최적화를 수행할 수 있는 경우에는 방향 벡터를 사용한다

거리 벡터  p 은 방향 벡터   로 나타낼 수 있다 방향 벡터는 거리 벡터가  이상의 종속 성 거리로 표현될 때 이를 요약하여 나타낼 때에 도 사용할 수 있다 예를 들어 거리 벡터 F p 

  G은  g 로 거리벡터 F p     

 G는  s 로 나타낼 수 있다 방향 벡터에서 는 양의 값을 는 음의 값을 는 을 나타내며 이 들의 조합도 가능한데 양수 음수 모두를 나타내 는 경우에는 s를 사용한다

종속성 검사는 병렬화 및 최적화를 위한 가장 중요한 분석 작업의 하나로써 다양한 검사법이 연 구되어 사용되고 있다 그러나 검사 방법들간의 정확도에 대하여 규명된 연구 결과는 거의 없으 며 일부 검사 방법들 간에 우수성에 관한 증명이 이루어졌거나 실험적인 연구가 이루어졌다 배열 첨자식들이 같은 값을 가질 수 있는지를 확인하 는 문제는 수학적으로 정수 프로그래밍 문제로서 .0 #OMPLETE 문제이다 종속성 분석 방법 중 가



/*거리벡터 {(2, –1)} */

전 전 전

전자자자자통통통통신신신동신동동동향향향분향분분분석석석석 제 권 제 호 년 월

장 널리 쓰이는 방법에는 '#$ 검사 "ANERJEE 검 사 등이 있으며 이러한 검사 방법들은 다음 장에 서 설명하였다

 조건문에서의 자료 종속성

프로그램에서 조건문이 쓰여질 경우 컴파일러 는 컴파일 시간에 어느 문으로 분기가 이동할지 예측할 수 없다 이 경우 자료 종속성 관계는 예 측할 수 있는 조건들 각각에 대해 조사하여야 한 다 조건문에서의 자료 종속성은 조건문 간의 다 른 경로에 있는 문장들 간에는 발생하지 않는다

3 8   3 9   3 IF 9  4 THEN 3 8   3 ELSE 3 9  8 3 ENDIF 3 :  8  9

위의 예에서는 3과 3에서 8가 정의되고 3과 3에서 사용됨을 알 수 있다 조건문에서 3이 수행될 경우 3과 3에서는 흐름 종속성이 있다 3가 3전에 나오고 있지만 이 두 문장은 서 로 같이 수행될 경우가 없으므로 이 문장들 간에 는 종속성이 있을 수 없다 3에 사용되는 8에서 는 3 및 3에서의 두 흐름 종속성이 있다 그리고 3과 3에서 출력 종속성이 있음을 알 수 있다

루프의 경우에는 동일한 회전에서 동시에 수행 될 수 없는 문장들 간에는 루프 독립 종속성LOOP INDEPENDENT DEPENDENCE 을 가지지 않는다

3 FOR )   TO  DO 3 IF !;)=   THEN 3 !;)=  ";) p=   3 ELSE

3 ";)=  !;)= r  3 ENDIF

3 ENDFOR

3와 3에서의 !;)=는 반 종속성 관계가 있다

그리고 3와 3에서의 !;)=는 같은 회전에서 사용 할 수 없으므로 루프 독립 종속성을 가지지 않는 다 그러나 3에 할당된 ";)=는 다음 회전시 3에 서 사용될 수 있다 이 경우 3에서 3까지는 루프 전이 종속성이 존재한다

 병렬 루프에서의 자료 종속성

일반적으로 컴파일러는 두 문장이나 두 루프 회전간에 변수들이 같은 메모리 저장 위치를 참 조하는지 또는 같은 값에 대한 참조인지를 분석 하여 자료 종속성 관계를 결정하게 된다 결정된 자료 종속 관계를 참조하여 루프를 병렬화시키며 병렬 루프는 일반적으로 다음과 같이 세 유형으로 표현한다

{ FORALL 루프

FORALL 루프는 루프 내에 하나 이상의 문장을 포 함한다 각 문장은 저장되기 전에 인덱스 집합 의 모든 값에 대해 표현식의 오른쪽 부분이 순 서적으로 먼저 수행된 값에 의해 계산되어 수 행된다

FORALL )   TO  DO 8;)=  8;) p= 8;) =

ENDFORALL



병렬화를 위한 자료 종속성 분석 기법

각각의 회전 I에서 바운드 내에 있는 I  과 Ip 의 회전이 사용되어 8;)=를 정의한다 순 차 루프라면 8;)=에서 8;) p=간에는 흐름 종 속성을 갖고 8;) =에서 8;)=간에는 반 종속 성의 관계를 갖는다

{ DOPAR 루프

DOPAR 루프는 각 회전이 루프의 시작 전 값들 에 대한 모든 변수들의 복사본을 갖고 계산된다

DOPAR )   TO  DO 8;)=  9 ;)=  

:;)=  8;) p=  8;)= 8;)  =

ENDDOPAR

종속성 관계는 다음과 같다

정의 사용 종속성 거리

8;)= 8;) p= 반 종속성 p

8;)= 8;)= 흐름 종속성 

8;)= 8;)  = 반 종속성 

{ DOSINGLE 루프

DOSINGLE 루프에서는 출력 종속성 관계를 배제 하는 단일 할당 규칙이 적용된다 즉 한번 할 당된 값의 재정의를 할 수 없게 된다

DOSINGLE )   TO  DO 8;)=  9 ;)=  

:;)=  8;) p=  8;)= 8;)  =

ENDDOSINGLE

종속성 관계는 다음과 같다

정의 사용 종속성 거리

8;)= 8;) p= 흐름 종속성 

8;)= 8;)= 흐름 종속성 

8;)= 8;) = 흐름 종속성 p

다음 예는 앞서 설명한 각 병렬 루프의 수행 결 과 들이 다름을 보여준다

3 LOOP )  

3 A)  A) p   3 B)  B)  A) p

3 ENDLOOP

이 예에서 표현식의 오른쪽 부분이 각 루프의 유형에 따라 예전 값을 참조하는지 새로운 값을 참조하는지에 따른 표를 작성하면 다음과 같다

3 A) p 3 A) p 3 B) 

FOR NEW NEW OLD

FORALL OLD NEW OLD

DOPAR OLD OLD OLD

DOSINGLE NEW NEW NEW

변수의 초기값들을 다음과 같이 가정하면

     

A      

B      

각 루프의 유형에 따른 A와 B배열의 값들은 다 음과 같다 여기서 p는 먼저 가지고 있던 값이 변 경되지 않음을 나타낸다



전 전 전

전자자자자통통통통신신신동신동동동향향향분향분분분석석석석 제 권 제 호 년 월

FOR      

A    

B    

FORALL      

A    

B    

DOPAR      

A    

B    

DOSINGLE      

A    

B    

)))

스칼라 변수의 경우에는 자료 흐름 분석DATA aOW ANALYSIS 이나 &5$FACTORED USE DEF CHAINS 분 석 등을 이용하여 거리나 방향 정보를 갖는 확실 한 자료 종속성 관계를 찾을 수가 있다 배열의 경 우에 컴파일러는 첨자식들을 처리해야 하는데 이 는 수학적으로 선형 등식 및 부등식의 문제이다

종속성 검사는 병렬화를 위한 가장 중요한 분석 작업의 하나로써 다양한 검사법이 연구되었으며

종속성 분석 방법 중 가장 널리 쓰이는 방법에는 3EPARABILITY 검사 '#$ 검사 "ANERJEE 검사 등이 있으며 이러한 검사 방법 들을 설명하였다; =

 종속성 검사법

가 종속성 검사에 필요한 제약 조건들

V와 V^를 같은 배열에 해당하는 변수들이라고 하자

V  !F)      FD)  $%&3 V^  !F_^)^      F_D^)^  $%&3



$%&3  FV  6!28 3 IS A DE`NITION OF VG

53%3  FV  6!28 3 IS A USE OF VG

여기에서 )  )_     )N 이고 )^ )^    )^N 이며 D g  모든 R  ;  D=에 대해 FR;3=
:

이고 F^_R;3=
:이다 이러한 조건에서 종속성 문 제는 다음의 제약 조건들을 갖는다

① DO 루프의 변수에 있어서 첨자 수식들은 선형 함수로 한정시킨다

② D  이라 가정한다

③ 수식에 대한 해의 존재 여부는 한정된 루프의 범위 내에서 계산하여 방향 벡터 d를 설정할 수 있는지에 달려있다

V c !F ) 이고 V^c !F^)^ 라고 하자 함수 F 와 F^는 아래와 같은 선형 조건,). 을 만족한 다

,).





F )  A 8

fJfN

AJ)J

F^)^  B_ 8

fJfN^

B_J)^_J

여기서 모든 A_J f J f N 와 모든 BJ f J f N^ 는 정수 상수들이다 3 3^ V V^와 방향 벡터



병렬화를 위한 자료 종속성 분석 기법

d  DIR;3= r ;3^= 에 대한 종속 시스템은 종속 등식DEPENDENCE EQUATION $%1  영역REGION

2%'  그리고 제한 조건CONSTRAINT #34 들로 다음과 같이 구성된다

$%1 A

8

fJfN

AJIJp



B 8

fJfN^

BJI^J



!  

2%' I_J ;4_J 5_J=  f J f N I^J ;4^J 5^J=  f J f N^

#34 I_Jd_JI^_J  f J f M

자료 종속성 문제들은 $%1 2%' #34를 만 족하는 I_J f J f N 와 I^_J f J f N^ 가 존재하는 지 즉 $%1를 만족하는 해가 존재하는지를 검사 하여 해가 존재한다면 종속관계가 성립된다고 할 수 있다

나 3EPARABILITY 검사

3EPARABILITY 검사는 정확하게 종속성의 존재 여부를 가려주는 검사로서 종속 등식의 DO 변수 가 오직 하나 이하일 때에만 적용될 수 있다 예를 든다면 F) *   r* p와 F^) *   r * p  혹은 F) *  )  과 F^) *   r )  와 같 은 경우에 적용이 가능하며 F) *  )  과 F^) *  * p 과 같은 경우에는 적용이 되지 않 는다 이 검사는 종속 존재에 대한 필요 충분 조 건을 제공함과 동시에 만약 종속이 있다면 종속 변수간 거리의 최대 최소치도 계산하여 준다 적 용할 제약 조건이 너무 한정되어 보이지만 실제 프로그램들은 대부분이 이런 제약을 넘지 않으므 로 실용성은 매우 높다 3EPARABILITY 검사는 아래

와 같이 정의되는 제약 조건을 만족할 때에만 적 용될 수 있다

3%0 K  ;  M=  J  ;  N=  J  K A_J  >

J  ;  N^=  J  K B_J 

3%0 이 만족된다고 가정하자 그러면

F )  AAK)K 그리고 F^)^  BB_K)^_K이다

만약 A  A_K B  B_K 4_K 4 그리고 5_K 5라 한다면 아래와 같은 종속 시스템을 풀 수 있다

3%0 393





3%0 $%1 AX pBY  BpA

3%0 2%' X Y  ;4  5=

3%0 #34 X d Y

여기에서 d는 d  F   sG과 같은 방향 벡터 의 원소이다

;정리  3EPARABILITY 검사=

3EPARABILITY 검사 제약 조건인 3%0 이 만족되 고 4  54  5 를 상수로 가정하면 아래와 같이 서술되는 $%0 %.$%.#% 변수값이 참일 때만 3와 3^는 종속적이다 만약 3와 3^가 종속적이라 면 3/,54 )/. 3%4  FX Y J X Y 는 3%0 393 를 만족한다G 또한 종속 최소 거리와 최대 거리를 나타내는 -). $)34 와 -!8 $)34 는 아래와 같이 주어진다

 만약 A  B이거나 A  이거나 B  이라면 이 경우에 STRONG SEPARABILITY라고 부른다 H표



전 전 전

전자자자자통통통통신신신동신동동동향향향분향분분분석석석석 제 권 제 호 년 월

H표 I STRONG SEPARABILITY검사를 위한 표

!SSERTION $EPENDENCE 3OLUTION

PA B d #ONDITION #ONDITION -). $)34 -!8 $)34

P_A B P_A B

)  A B TRUE  5 p4

A  B    A B TRUE  

 A_ B_ TRUE  5 p4

s A B TRUE  5 p4

))   f W f 5 p4 Y pX  W W W

A  B  >  A B Y pX  W  

A J BpA   f pW f 5 p4 Y pX  W pW pW

s  f JWJ f 5 p4 Y pX  W JWJ JWJ

)))  4 f pW f 5 p X  pW  5  W

A   B  >  4 f pW f 5 X  pW  

A J BpA  4   f pW f 5 X  pW  pW p4

s 4 f pW f 5 X  pW  MAX5  W pW p4

)6  4   f S f 5 Y  S  S p4

A   B  >  4 f S f 5 Y  S  

B J BpA  4 f S f 5 p Y  S  5 pS

s 4 f S f 5 Y  S  MAXS p4 5 pS

용어  W  pB_pA_ A A    S  pBpA_ B B  

I은 아래와 같은 관련 정보들을 종합한 것이 다

I 종속성의 존재

A B와 d가 H표 I에서 수식 P_A B 와 PA B 중 어느 한 쌍을 만족할 때만

$%0 %.$%.#% 값은 참이다

II 종속성의 특성

3와 3^를 종속 관계에 있다고 가정한다

그러면

3/,54 )/. 3%4  FX Y J 4 f X Y f 5 > PX Y G

 A  B A   B  라고 가정하자 이 경우 를 WEEK SEPARABILITY라고 하며 3와 3^는 GCD A B J B_p A 이고 알고리즘이

$%0 %. $%.#%  참의 값을 가질 때 에만 종속 관계를 갖는다 만약 종속이 존 재한다면 3/,54 )/. 3%4  -). $)34 와 -!8 $)34 가 WEEK SEPARABILITY 검사 알고리 즘에 의해 결정되며 여기에서는 생략한다

다 '#$ 검사

루프의 첨자가 정수임을 이용하여 최대공 약수의 정리를 사용하는 검사 방법이다 즉 8N

I

A_I8_I C_I가 정수해를 가질 필요 충분 조건은

GCDA A     AN MOD C   임을 이용하여 종 속성의 존재 여부를 검사한다

'#$ 검사는 종속성을 검출해 내기 위한 필 요 조건만을 판별할 수 있다 따라서 정확한 종속 검사법을 실시할 수 없는 경우에 한하여 '#$ 검 사를 적용시키는 것이 바람직하다 '#$ 검사는 주어진 영역 내에서 LINEAR DIOPHANTINE EQUATION을 만족시키는 해가 존재하는지를 판단해 준다 이를 정리하면 다음과 같다

C A A     AN을 모든 A에 대해 값이 아닌 정 수들이라 가정하면 LINEAR DIOPHANTINE EQUATION인 A_X_ A_X_ q q q  A_NX_N C는 아래 조건을 만족할 때 2  :^N의 영역 내에서 해를 가진다



병렬화를 위한 자료 종속성 분석 기법

① GCDA A     AN 은 C를 나눈다

② 4_LOWF 2 f C f 5UPF 2 을 만족하는데 여 기에서 F는 FX  A_X_A_X_q q q A_NX_N으로 정리되는 함수이며 4_LOW 5_UP은 각각 제한 영 역의 하한치와 상한치를 나타낸다

위의 조건에 따라 GCDA_ A_ q q q  A_N 를 구한 다 만약 이 때 GCDA_ A q q q  AN 가 C를 나누 지 못한다면 방정식의 해가 존재하지 않는 것이 므로 종속성은 존재하지 않는다 그러나 실제 프 로그램의 활용도를 생각해 볼 때 '#$ 검사는 크 게 도움이 되지 못하는 경우가 많다 예를 들어 B A인 경우 Bp A의 DIVISOR에 모든 경우의 수 가 해당되고 또 가지 이상의 수에서 GCD를 찾 을 때 의 값이 나와도 결과가 참이 되기 때문이 다 예를 들면 GCDA B  일 경우 GCDA B C  GCDGCDA B  C  이 된다 따라서 '#$의 실용 적인 적용성은 제한되어 있다

라 "ANERJEE 검사

'#$ 검사는 제한 영역을 고려하지 않고 종속 등식을 만족하는 정수해의 존재 여부만을 알려주 는 반면 "ANERJEE 검사를 통해서는 루프의 제한 영 역 안에서 종속 등식이 실수해를 가지는지를 판단 할 수 있다 따라서 '#$ 검사를 실행하여 해가 존재한다고 판명되는 경우 "ANERJEE 검사의 실행 에도 해가 존재한다고 판명되면 정확하게 종속성 이 존재하는 것이다 프로그램내의 할당문 개에 대해 각각 !와 "라 하고 다음과 같이 가정한다

!와 "를 기준으로 루프 내의 문장들을 개의 분 리된 그룹으로 분류할 수 있다 루프의 ,#부분은

!와 "를 모두 포함하는 부분이고 "를 제외하고

!만 포함하는 부분을 ,!라 한다면 반대로 !를 제 외한 "를 포함하는 부분을 ,"라 한다 ,#부분에 는 M개의 루프 문장들이 있고 ,#를 더해서 ,!까 지는 N개의 문장들이 있으며 ,# ,!까지 더해서 ,"까지는 N^개의 문장이 있다 즉

,#  ,_ ,_     ,_M ,!  ,M ,M     ,N ,"  ,N ,N     ,N^ 이다

임의의 루프 문장 ,+에 대해 루프 변수를 )_K 하 한치를 4_J 상한치를 5_J J       N^ 로 표현 한다 !문장의 변수를 X라 하고 "문장의 변수를 Y라 하자 그리고 이들 중 적어도 하나를 출력 변 수로 가정하면 아래와 같은 선형식을 갖는다

X  !AA)    AM)MAM)M    AN)N Y  !BB)    BM)M BN)N    BN^)N^

따라서 !와 "문장이 아래와 같은 DIOPHANTINE EQUATION의 해를 가진다면 X Y로 인해 "는 !에 대 해 종속 관계에 있게 된다

A_I_pB_J_     A_MI_MpB_MJ_M  A_MI_M ANINpBNJNp   pBN^JN^ BpA

위 식은 다음의 조건을 만족한다

4Kf I_Kf 5_K  f K f N 

4_Kf J_Kf 5_K  f K f M이고 N  f K f N^ 

그리고 I_KpJ_K 





  IF !K 

  IF !_K   f K f M

  IF !K p



전 전 전

전자자자자통통통통신신신동신동동동향향향분향분분분석석석석 제 권 제 호 년 월

위의 경우를 거리 벡터를 이용하여 표현할 수 있다

LT  FJ  J  ;  M= >dJ @  G EQ  FJ  J  ;  M= >dJ @  G GT  FJ  J  ;  M= >dJ @  G ST  FJ  J  ;  M= >d_J @ s G

J  ;  M=의 각 원소들은 위 네가지 집합 중 반 드시 어느 한가지에만 포함된다 즉 LT;EQ;GT;ST 

; M=이다 이러한 사항을 이용하여 "ANERJEE 검 사의 식을 좀 더 다루기 쉽도록 아래와 같이 분류 하여 표현할 수 있다

제한 영역이 4_J 5J 4 J^와 5J^의 상수인 종속 시스템을 생각하면 3bd3^혹은 3^bd^p3는 다음을 수반한다

8

fJfM

,#_J 8

MJfN

,!_J 8

MJfN^

,"_Jf B_pA_ f

8

fJfM

5#Jp 8

MJfN

5!J 8

MJfN^

5"J

여기에서

① ,#_J





pA_J^pB_J 5_Jp4_Jp A_JpB_J 4_JpB_J FOR J  LT

pA_JpB_J ^p5_Jp4_J A_JpB_J 4_J FOR J  EQ

pB_JpA_J 5_Jp4_Jp A_JpB_J 4_JA_J FOR J  GT

pA_J^pB_J 5_Jp4_J A_JpB_J 4_J FOR J  ST

② ,!_J pAJp5Jp4J  AJ4J FOR M  J f N

③ ,"J pBJ

5Jp4J pBJ4J FOR M  J f N^

④ 5#J 





A_JpB_J 5_Jp4_Jp A_JpB_J 4_JpB_J FOR J  LT

A_JpB_J 5_Jp4_J  A_JpB_J 4_J FOR J  EQ

B_J^pA_J 5_Jp4_Jp  A_JpB_J 4_JA_J FOR J  GT

A_J B_J^p 5_Jp4_J  A_JpB_J 4_J FOR J  ST

⑤ 5!_J AJ5Jp4J AJ4J FOR M  J f N

⑥ 5"_J B_J^p5_J^p4_J^ pB_J4_J^ FOR M  J f N^ 위와 같이 "ANERJEE 검사를 통해서는 루프의 제 한 영역 안에서 종속 등식이 실수해를 가지는지를 판단할 수 있다

)6

지금까지 루프에서의 자료 종속성 관계 조건 문에서의 자료 종속성 관계 그리고 병렬 루프에 서의 자료 종속성 관계에 관한 기본적인 사항들 에 대해서 알아보았다 또한 종속성 검사는 병렬 화를 위한 가장 중요한 분석 작업의 하나로서 다 양한 검사법이 연구되었으며 배열 원소들에 대한 기본적인 종속성 검사법에 대해서도 알아보았다

본문에서 설명하였듯이 자료 종속성이란 같은 메모리 장소를 사용하는 두 문장 사이의 수행 순 서가 유지되어야 하는 성질이며 이러한 종속성이 없을 경우에 두 문장은 병렬로 수행이 가능하다는 뜻이 된다 프로그램에서 루프문에서의 계산 내용 을 보면 배열 원소들에 대한 동일한 연산을 수행 하는 경우가 대부분이므로 배열로 인한 종속성을



병렬화를 위한 자료 종속성 분석 기법

분석하는 것이 중요한 일이라 할 수 있다 이러한 종속성 분석은 특히 루프문의 병렬화 성능에 매우 큰 영향을 주는 것으로 간주되어 많은 연구가 진 행되고 있다

참 고 문 헌

;= "ACON 3 , 'RAHAM AND / * 3HARP <#OMPILER TRANS FORMATIONS FOR HIGH PERFORMANCE COMPUTING !#- #OM PUTING 3ERVEY VOL  NO  PP   

;= - 7OLFE <$ATA DEPENDENCE AND PROGRAM RESTRUCTURING 4HE *OURNAL OF 3UPERCOMPUTING VOL  NO  PP  



;= - 7OLFE (IGH 0ERFORMANCE #OMPILERS AND 0ARALLEL #OM PUTING #! !DDISON 7EESLY 0UBLISHING #OMPANY )NC



;= 5 "ANERJEE $EPENDENCE !NALYSIS FOR 3UPERCOMPUTING

+LUWER !CADEMIC 0UBLISHERS 

;= ! 6 !HO 2 3ETHI AND * $ 5LLMAN #OMPILERS 0RIN CIPLES 4ECHNIQUES AND 4OOLS !DDISON 7ESLEY 

;= ( :IMA AND " #HAPMAN 3UPERCOMPILERS FOR 0ARALLEL AND 6ECTOR #OMPUTERS !#- 0RESS