20160310

동시성 프로그램의 이해
– n-body simulation은 물리 시뮬레이션에서 많이 쓰임. 여러 개의 상호 작용을 동시에 계산해야 하므로, 병렬성을 사용해야 함. Data parallelism을 사용해야 함. Data level parallelism도 있지만, function level parallelism도 있다. Data level parallelism과 function level parallelism은 다르다.

– 병렬 프로그램을 만드는 단계는 decomposition, assignment, orchestration, mapping으로 나뉜다. 전체 작업을 나누는 것이 decomposition, 이를 프로세스에 할당하는 것이 assignment, 프로세스끼리 상호작용하도록 하는 것이 orchestration, 프로세서에 매핑하는 것이 mapping이다.

1) Decomposition은 병렬성을 활용하기 위해 작업을 나누는 것.
2) Assignment 단계에서는 전체 작업을 일정 단위로 나눈다. 각 프로세스가 하는 작업량이 비슷하도록 할당하는 것이 필요하다. 한쪽에만 너무 많이 할당하면 일부 프로세스가 기다려야 해, 전체 시간이 늦어짐. 바다 시뮬레이션과 같은 경우에는 일정하게 구역을 나누면 작업량이 비슷함. 하지만 물리 시뮬레이션과 같은 경우에는 잘 나누어지지 않을 수 있음. 작업량을 잘 나누는 load balancing이 필요하다.
3) Orchestration에서는 프로세스끼리 통신을 효율적으로 하도록 하는 것. Naming data의 문제. 공유 메모리 환경에서는 어차피 보이는 데이터가 같으므로 문제 없음. MPI에서는 문제가 됨. MPI에서도 정적으로 데이터를 나누어 처리한다면 문제가 없음. 하지만 동적으로 데이터가 프로세스를 옮겨다닌다면, 어디에 해당 데이터 정보를 요청할지 모른다는 문제가 있음. Synchronization 문제는 공유 메모리에서 더 큰 문제이다. “시간적인” 구조화도 중요한 문제이다. 여러 개의 프로세스가 어떻게 스케쥴되도록 할 것인가의 문제.
4) Mapping은 프로세스를 실제 코어에 매핑하는 것. 많은 경우에 운영체제가 이러한 매핑을 대신하게 됨. NUMA 시스템에는 local memory 접근이 remote memory 접근보다 빠르다는 특징이 있음. 그리고 remote memory 접근은 인터커넥트 트래픽을 유발한다는 문제가 있음. MPI에서는 이러한 문제가 더 커진다. 네트워크를 통해 연결되어 있기 때문에, 프로세스 그룹에 따라 처리 속도가 많이 달라질 수 있음.

무엇이 병렬성을 저하시키는가? 병렬성을 활용하고자 하는 경우가 많지만, 병렬성에도 한계가 있음.

what hurts parallelism.PNG

1) Amdahl’s Law에 의해 제약됨. Amdahl’s Law는 최적화로 인한 성능 개선은 최적화 가능한 부분의 비율에 제약된다는 것. 100개의 코어를 사용해 80% 가속하려면, 전체의 99.75%가 병렬화 가능해야 한다. nxn 행렬에 대해 2-phase calculation을 한다고 하자. 직렬화된 연산이 n^2, 병렬화된 연산이 n^2, 프로세서의 수가 p일 때, speedup은 (2n^2 / ((n^2/p) + n^2) ) 에 제약된다.

2) 병렬성 저하의 원인으로 imbalanced load의 문제가 있다. 프로세스간 동기화를 위해 barrier, global synchronization을 사용할 수 있다. 데이터가 동일하게 분할되지 않았을 수도 있고, 동일하게 분할되었다 하더라도 연산 요구량이 다를 수 있다. 랜덤화를 통해 해결할 수 있다.

– Barnes-Hut은 multi body simulation에 사용할 수 있음. Quad tree를 유지하면서 특정 부분을 특정 thread가 처리하도록 하는 기법. Semi-dynamic 기법들이다. 객체들이 느린 속도로 움직이기 때문이다.

– 작업 분할을 위해 task queues를 사용할 수 있다. Centralized task queue를 사용할 수도 있고, distributed task queues를 사용할 수 있다. Hadoop은 centralized task queue를 사용하는데, synchronization의 문제가 있을 수 있다(여러 개의 worker가 동시에 접근하는 경우). Linux scheduler가 distributed task queues를 갖고 있다. 코어마다 queue를 갖고 있으며, 자기 queue에 작업이 없으면 다른 queue의 job steal을 시도한다. Load balancing의 측면에서는 centralized queue가 항상 좋다. 하지만 worker가 많아지는 상황에서는 distributed task queue를 사용하는 것이 synchronization의 문제 해결 가능. 수천개의 worker가 있다면 centralized queue는 비효율적이다.

3) 병렬성 저하의 문제로 lock contention의 문제가 있다. Lock은 무엇인가? 공유 데이터에 접근 제어를 위해 사용하는 것이 lock. 여러 개의 프로세스가 공유 데이터에 동시에 접근하는데, 적어도 한 개의 연산이 쓰기 연산인 것이 data race. Lock의 사용을 통해 해결할 수 있다. 하지만 lock의 사용은 병렬성을 떨어뜨린다. 강의 슬라이드의 예제에서 lock이 전체 배열에 대한 접근을 제어한다는 문제가 있음. 계좌 단위로 lock을 거는 것이 더 좋음. 하지만 fine-grained lock은 deadlock을 유발할 수 있음. 송금에서 A가 B의 lock을, B가 A의 lock을 요구하는 경우.

– 공유 메모리 환경에서는 일정 메모리에 데이터를 쓰고 읽음으로써 통신한다. 캐시를 사용해 메모리까지 접근하지 않고 데이터를 가져올 수 있다. 하지만 캐시끼리의 데이터가 일관성이 없을 수 있다. 한 코어에서의 데이터 변경이 다른 코어에까지 반영되어야 한다. 이것이 coherence problem이다. 이를 해결하기 위한 방법에 두 가지가 있음. Update-based protocolinvalidation-based protocol.

Update-based protocol은 캐시 라인의 변경이 발생할 때 다른 캐시의 캐시 라인도 업데이트한다. Invalidation-based protocol은 캐시 라인의 변경이 발생할 때 다른 캐시 라인을 invalidate만 한다. 네트워크 대역폭을 줄일 수 있으나, producer-consumer 통신에서는 문제가 있을 수 있음. 실제 컴퓨터에서는 invalidation-based protocol이 많이 쓰인다. 왜 invalidation을 더 많이 쓰는가, 실제로는 데이터를 공유하는 경우가 많이 없기 때문이다(locality). 한편, update-based protocol에서 update가 도착하기 전에 해당 캐시 라인을 읽게 된다면 어떻게 하나? 그것에 대해서는 coherence protocol이 보장하는 것이 없음. 이 문제는 consistency 문제이고, 나중에 이야기할 것.

4) Coherence를 제공하게 되면서 false sharing이 발생한다(Invalidation-based protocol).  False sharing은 프로세서 A와 프로세서 B가 서로 다른 데이터를 사용함에도 불구하고,  두 데이터가 같은 캐시 블록에 포함되어 있음으로 인해 불필요한 invalidation이 발생하는 것. False sharing은 cache coherence 단위가 캐시 블록이기 때문이다. 워드, 바이트, 비트 단위가 아닌 캐시 블록 단위로 공유한다는 것이 false sharing을 유발한다. 한 캐시 블록에는 8개의 float, 16개의 int가 들어감. 따라서 한 개만 변경되어도 캐시 블록을 업데이트해야 하므로 문제가 있음.

– Optical interconnect에서는 coherence bandwidth가 많이 늘어남. 그렇다면 update-based protocol을 사용하고, word 단위로 공유하면 어떨까? 프로세서 사이에는 locality가 떨어지는 것이 사실이지만, 그래도 성능을 높일 수 있지 않을까?

5) Locality에 대한 고려가 중요하다. Temporal locality를 높이기 위해 데이터를 적절히 나누는 것은 좋다. Temporal locality가 있는 경우에 blocking을 사용한다. N^2 데이터에 N^2 연산을 하는 것은 blocking이 무의미. N^2 데이터에 N^3 연산을 하면 blocking으로 성능 개선 가능. 행렬 곱이 이같은 사례. Simulating ocean currents에는 N^2 데이터에 N^2 연산을 하므로, blocking이 무의미. Spatial locality도 고려해야 한다. 한 번에 처리하는 데이터 양과 특성을 고려해 연산하는 것이 중요. Column-wise 접근하는데 row-wise 연산하면 손해. 행렬 곱연산에서는 row-wise, column-wise 연산 모두 필요하므로 문제가 생김. Blocking으로 해결 가능함.

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

누적 방문자 수
  • 101,726 hits
%d bloggers like this: