20160315

동시성 프로그램의 이해
– 프로그램의 병렬화 수준은 프로그램 내에서 활용할 수 있는 병렬성에 제약된다. 그리고 락을 사용할 때에는 최대한 적은 영역만을 락으로 잡아야 한다. 또한 너무 많은 데이터를 락을 잡지 않도록 해야 한다. 블로킹은 O(n^k) 데이터에 O(n^(k+1))연산을 수행할 때 사용한다. 행렬 곱에서는 O(n^2) 데이터에 O(n^3) 연산을 수행한다. CUDA에서의 shared memory를 사용하는데 블로킹을 사용하면 좋다.
– 다섯 개 점의 평균을 내는 연산이 있다고 하자. 이 연산을 계속하다가, 어느 threshold를 넘으면(점들의 차이가 없어지면) 멈춘다. Sequential하게 업데이트한다고 하면, 점들 사이에 dependency가 생긴다. 다음 점의 값이 이전의 값에 의존성을 갖기 때문이다. 따라서 병렬성에 제약이 생기게 된다. 원래 불필요한 의존성이 생기기 때문이다.
– Red-black ordering으로 병렬성을 높일 수 있다. 전체 점들을 red point, black point로 나누고, red와 black을 번갈아가면서 업데이트한다. 최종 결과는 sequential version과 약간 다를 수 있지만, 목표하는 바를 병렬 처리로 가속할 수 있다는 점에서 red-black ordering이 더 우수하다. for 중첩문 내의 문장이 병렬 실행된다면, n^2의 쓰레드를 동시에 실행할 수 있다. 실제로 동시에 실행할 수 있는 쓰레드는 코어의 수에 제약된다.
– 작업 할당에 block assignment, cyclic assignment 기법이 있을 수 있다. Block assignment는 전체 작업을 p row로 나누어 할당하는 것(p는 프로세스의 수). Cyclic assignment는 한 개의 열마다 나누어 프로세스가 가져가는 것. Block assignment가 더 높은 locality를 보일 것이다. 한편, job stealing이 dynamic assignment에 속한다.
– 이 문제에 대해서는 single program multiple data(SPMD)를 사용할 수 있다. 동일한 작업을 여러 개의 데이터에 대해 수행하므로 SPMD가 적합하다. 유사코드 설명. nprocs의 프로세스를 생성할 것이나, 이미 master thread있으므로 nprocs-1 쓰레드만 추가 생성한다. Solve 함수를 실행하도록 하고, 인자값으로 A를 준다. 그리고 master thread도 Solve 함수를 호출하며 A를 인자로 준다. 모든 쓰레드가 같은 위치에 도달했음을 보장하는 것이 barrier이다. 쓰레드의 실행 속도가 다름을 가정하고 있기 때문에, barrier가 필요하다. join과 barrier가 비슷하기는 하지만, join은 barrier가 의미가 다르다. Barrier는 진행 속도를 맞춘 뒤에 프로그램을 계속 실행하기 위해 사용한다면, join 은 실행이 완료된 이후 쓰레드를 파괴하기 위해 사용한다. 유사 코드에서 wait_for_end가 join에 해당한다. 그리고 코드에서 my_diff를 사용하고 있는데, 쓰레드들이 공유 변수인 diff가 아닌 my_diff에 업데이트하게 함으로써 과다하게 lock을 잡는 것을 막을 수 있다.
– diff=diff+mydiff에서 발생하는 단계는 1) tmp <- diff, 2) tmp = tmp + mydiff, 3) diff <- tmp 이다. lock을 해줘야 쓰레드가 동시에 업데이트함으로써 생길 수 있는 문제를 막을 수 있다. 읽기만 하면 lock을 쓸 필요가 없다.
– 이렇게 만든 프로그램은 lockstep으로 실행되는 것은 아니다(코어마다 같은 명령어를 실행하는 것은 아님). pid를 사용해 해당 쓰레드가 처리하는 데이터의 범위를 결정한다. 완료 조건이 불필요하게 여러 번 확인된다는 문제점은 있다. 이렇게 실행하는 값은 non-deterministic하다. 쓰레드가 같은 순서로 동시에 진행된다는 보장이 없기 때문이다. 쓰레드 사이의 스케쥴링이 어떻게 될지 알 수 없다는 것을 항상 생각해야 한다. 이 코드에서는 diff에 mydiff를 더하는 것이 reduction 과정이다. O(n)의 시간이 걸릴 것. sum, mean을 구하는 것이 reduction 연산이다.
여러 개의 쓰레드가 동시에 공유 변수를 업데이트할 때 mutual exclusion을 해주어야 한다. critical section에 대한 접근을 serialize하고자 할 때 locking mechanism을 사용한다. 여러 개의 쓰레드가 같은 lock을 얻으려고 할 때 lock contention이 발생한다.
20160315 consistency problem.PNG
Barrier를 사용하면 모든 쓰레드가 같은 진행 속도로 실행되도록 할 수 있다. point-to-point event synchronization 기법을 통해 쓰레드 사이의 순서를 만들 수 있다. 유사 코드에서 P1은 항상 1을 출력하게 된다. 하지만 이 코드가 작동하지 않을 수 있다. Consistency 문제가 발생할 수 있기 때문이다. A에 쓰기 명령과 flag에 쓰기 명령의 순서가 차례대로 진행되는 것처럼 보이지 않을 수 있다. 읽기 순서가 reorder되기 때문이다. 이를 consistency 문제라고 한다. 나중에 자세히 설명할 것.

Advertisements
Tagged with: , , , , , , , , , , , , , , , ,
Posted in 1) Memo

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

누적 방문자 수
  • 88,328 hits
%d bloggers like this: