[Parallel Computing] (8) Loop Carried Dependence

앞 글에서 Dependences의 종류에 대해서 살펴보았다. 이때, 실제 True dependence(WAR)를 제외하고 Anti dependence(RAW), Output dependence(WAW)은 False dependence로 실제 연산의 실행 순서와 관련되어 있는 것이 아니라 메모리 위치의 재사용에 의해 발생한다. 이는 Register Renaming으로 제거 가능한다. 

 

Loop-Independent/Carried dependence는 Loop-Independent는 loop와 관계없이 발생하는 dependence이며, Loop-Carried는 loop의 iteration에 따라 진행되는 흐름에서 발생하는 dependence이다. 

 

Loop-Independent/Carried dependence[1]

아래 그림 처럼 몇 개의 Loop를 나열해 보면 더 쉽게 알 수 있다. i=0와 i=1 iteration에서 보면 B [1]이 서로 존재하고, RAW인 Anti dependence가 생성된 것을 알 수 있다. 

Loop unrolling & Loop-carried dependence[1]

 

Loop Fusion은 여러 인접한 두 개의 Loop를 하나의 Loop에서 수행할 수 있도록 합치는 것을 의미한다. 이 때, 주의해야 할 점은 Loop Fusion으로 인하여 기존에 없었던 dependence가 생성되면 안 되는 것이다. 아래의 그림은 Loop Fusion이 illegal 한 경우를 보여준다. s3->s2로의 새로운 Anti dependece(WAR)가 생성되었으므로 loop fusiton은 수행할 수 없다. 

Loop Fusion illegal Case[2]

Loop fusion을 수행하는 이유는 하나의 Loop문 안에서 비슷한 메모리 접근이 발생하므로 Cache의 효율이 좋고, Loop 문에 따른 branch instruction의 수가 적어지며, loop iteration 수를 계산하기 위해 필요한 양이 줄어든다. 

 

Loop Distribution은 Loop Fusion과 반대로 Loop를 분리하는 것을 의미한다. 이 경우, Loop-Carried dependences가 loop-independent dependences로의 변환이 수행된다. Loop Fusion과 마찬가지로 기본의 dependences를 제거하거나 추가되는 형태로 변경되지 않아야 한다. 아래 예시와 같이 기존에 가지고 있던 dependences가 모두 동일하게 유지되는 것을 살펴볼 수 있다. 

Loop Distribution legal Case[2]

 

Reduction은 어떤 연산을 이용해 여러 개의 값을 모아서 하나의 값을 생성하는 과정이다. 예을 들어 아래와 같이 arr의 값을 모두 더하는 코드가 있다고 하면, 이 loop은 loop-carried dependence 때문에 순차적으로 수행되어야 한다. 즉 arr의 크기(N)만큼의 순차적인 덧셈이 필요하다. 

sum of array example [4]

아래 그림과 같이 서로 두 개씩 더 하고 그 다음 레벨에서 또 두 개씩 더하는 형태로 수행하는 Parallel reduction을 적용하면 logN 번의 덧셈 스텝만 필요하다. 

Parallel reduction [5]

Scan은 주어진 연산의 결과로 얻는 열의 위치 i에 있는 원소는, 원래 열의 위치 0부터 위치 i까지 위치한 원소들에 주어진 연산을 적용하여 얻을 수 있다. 아래와 같이 prefix sum을 수행하는 것이 하나의 예제가 될 수 있다. 

scan example[6]

아래 그림 처럼 parallel scan을 적용하면 log N번의 덧셈 스텝만 필요하다. 

parallel scan [6]

 

 

[1] : https://www.cs.cmu.edu/afs/cs/academic/class/15828-s98/lectures/0318/sld006.htm

Data Dependence in Loops

[2] : https://images.app.goo.gl/1P7rAhcUiWEScT2V9

Dependence Analysis and Loops CS 3220 Spring ppt download

[3] : https://slideplayer.com/slide/10573300/

Dependence Analysis and Loops CS 3220 Spring ppt download

[4]: https://images.app.goo.gl/xeFdW766yMkip4Zn6

How to write a Python program to sum the elements of an array - Quora

[5]: https://images.app.goo.gl/EMrHjzSaRshfmRJv7

The binary tree of Parallel Reduction Algorithm | Download ...

[6]: http://lumetta.web.engr.illinois.edu/408-S20/slide-copies/ece408-lecture16-S20.pdf