20160317

동시성 프로그램의 이해
– Message passing으로 grid solver 구현하기. 전체 행렬 A를 공유할 수는 없음. 프로세스별로 나누어 처리하도록 해야 한다. Ghost row는 실제로 해당 프로세스가 갖고 있는 row는 아니지만, 다른 프로세스에서 처리한 것을 임시로 저장하기 위한 버퍼로 사용하는 것. 프로세스별로 데이터를 나누고, 프로세스간 데이터 교환을 위해 ghost row를 추가한다. 그리고 edge를 이웃에 전송한다. ghost row를 받아서 연산한다. MPI 구현에서는 lock, barrier를 사용하지 않음. SEND, RECEIVE가 lock과 barrier처럼 동작한다. 작업 분배는 shared memory model과 유사하지만, 어떻게 함께 동작하는지는 shared memory model과 다르다. 더하는 것을 여러 번 호출하지 않고 REDUCE를 한 번 호출해도 된다.
– send/recv에서 synchronous(blocking), asynchronous가 있다. recv는 메시지가 도착해야 리턴하고, irecv는 즉시 리턴한다. recv는 일종의 barrier처럼 사용될 수 있다. irecv는 커뮤니케이션과 연산을 중첩할 수 있다는 장점이 있다. MPI는 topology에 대한 이해가 있어야 한다는 점에서 어려움. MPI는 구현에 따라 deadlock이 일어날 수도 있다. SEND 함수가 보낸 것을 받아야만 return한다면 deadlock 발생. 실제로는 버퍼에만 넣으면 반환하므로 일반적으로 OK.
– Shared address space와 message passing의 비교
20160317 shared address space message passing.PNG
– 쓰레드를 생성할 때, 쓰레드가 항상 100% utilization을 보이는 것이 아니라면 코어 수보다 더 많은 쓰레드를 만드는 것이 도움이 될 수 있다(웹 서버). 예제 코드에서 hits 배열은 공유 변수이다. master thread가 각 원소를 쓰레드에게 분배한 것. 하지만 slave 쓰레드에서 공유 변수는 아니다. 따라서 개별 쓰레드에서 직접 업데이트해도 괜찮을 것처럼 보인다. 하지만 실제로는 false sharing 문제가 발생할 수 있기 때문에 성능 저하가 발생할 수 있다. False sharing 문제를 해결하기 위해서 모든 계산이 끝난 뒤 hits 배열을 업데이트해도 되고, 아니면 padding을 사용해도 된다 (false sharing 문제를 해결). Padding을 사용하면 메모리를 낭비하게 되지만, false sharing 문제를 해결할 수 있다는 장점이 있다.
– 쓰레드에서 race condition이 문제이다. 타이밍 또는 스케쥴링에 따라 결과가 어떻게 될지 모른다는 문제. 핵심 연산을 atomic하게 만듦으로써 해결할 수 있다. mutual exclusion을 사용하면 해결할 수 있다. Producer-consumer 관계에서도 버퍼 상태 위한 변수에 대해 lock을 걸어야 한다.
Pthread는 normal, recursive, error-check lock을 제공한다. normal lock은 lock을 여러 번 획득할 수 없다. recursive lock은 lock을 여러번 획득하는 것을 허용한다. error-check lock은 오류를 알려주는 기능을 한다.
– 두 쓰레드가 동시에 lock을 획득하려 하면 (lock contention) 어떻게 되는가? 구현에 따라 다름. spinlock이라면 lock을 획득하지 못한 경우에 spinning하게 된다 (자원 낭비). pthread는 어떻게 구현되어 있는가? 최신 버전은 모르겠지만, 이전 버전까지는 sleep하도록 되어 있었다. spinning도 사실 나쁜 것은 아님. sleep과 wake에 시간이 걸리기 때문이다. 일정한 threshold를 갖고 spinning, sleep 사이에 결정할 수도 있을 것이다. Lock contention으로 인한 문제를 어떻게 해결할 것인가? trylock을 사용할 수 있다.
– Producer-consumer model에서 버퍼의 상태를 반복적으로 확인하게 됨 (polling). Polling은 synchronous하지만, 오버헤드가 크다. 이를 해결하기 위해 condition variable을 사용할 수 있다.

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,234 hits
%d bloggers like this: