Parallel Programming on Shard Memory Systems

강의: 한승수교수(KAIST)

 

Parallel Programming on Shard Memory Systems

1. Parallel 방식은 크게 세가지 Level로 분류해 볼 수 있다.

- Task level (ex. thread function)

- Data : 서로 다른 data set에 대해서 동일한 logic를 적용하는 경우

- Instruction level : CPU가 처리하는 instruction 단위를 pararrel하게 진행. 보통 2~3개정도의 instruction을 동시에 진행, H/W layer에서의 접근 방안

 

2. Ideal Pararrel progamming

programmer는 serial하게 code를 짜면 compiler가 알아서 자동적으로 pararrel 적용 구간을 판단하여 적용

 

3. Real pararrel programming

programmer는 parallel algorithm을 적용하여 구현

 

4. Shared memory system: memory address를 공유하게 되며 thread기반 progamming이 가능

 

5. Distrubuted memory system: each memory space가 존재함. process간 memory공유가 가능하겠으나 별도의 방안이 필요

 

6. Thread library 사용 방식: developer는 처음부터 전체 동기, 비동기 logic을 구상하게 됨 

 

7. Open MP 방식 : developer는 serial 하게 code를 구현하고 이후 directives(?)를 삽입하여 pararrel 구간을 지정, developer의 동기/비동기 구분에 따른 실수를 방지

 

8. Open MP model : fork/join model. 즉, single thread가 동작하다가 directive가 설정된 구간에서 teams of thread가 fork되어 동작, 그리고 다시 join되면 single thread로 변환. 실제로는 fork방식보다는 thread pool을 만들어 사용. 동기화가 필요한 변수들에 대해서는 별도의 annotation이 필요

ex)

#progma cmp task

routine_a

 

#progma cmp task

reoutine_b

 

#program omp taskwait

process(p);

 

* 위의 코드에서 #program cmp task는 Open MP에서 spec.기반 library에 제공하는 directive이다. routine_a, routine_b는 thread로 수행이 되고 process(p)는 두 thread가 종료되면 수행된다.

 

9. Synchronization

- mutual exclusion

- event sync. ex) 특정 event가 발생할 때에만 수행

 

* Open MP는 lock/unlock에 대한 자유도를 없앴다.(실수방지를 위해서)

* Tread API에서는 두 개의 thread가 상호 wait/signal 구조를 가진다.

 

10. major computer h/w and s/w vendors jointly defines Open MP.org

(http://en.wikipedia.org/wiki/Open_MP)

 

11. Open MP는 distributed memory system은 지원하지 않는다. high level abstract방식이기 때문에 speed efficiency가 떨어질 수도 있다.

 

Pararrel Program Performance

1. automatic pararrelization은 두가지 의미를 가짐

- Fully automatic pararrelization(compiler가 자동으로 parallel loop를 찾음)

- developer dedicated pararrelization(개발자가 Open MP제공 directive에 의해서 구간 지정)

 

2. Task decomposition 에 의한 Performance 향상

 

3. Tool 에 의해서 hot spot 발견 가능

 

4. multi-core는 각각의 core가 가지는 cache를 활용하게 됨에 따라 single core방식에 비해서 speed efficiency를 꾀할 수 있다.

 

5. Performance Optimization

- Load imbalance (특정 구간이 느려지면 이로 인해서 전체 수행 시간이 느려진다. imbalance 구간을 찾는다.)

- Data communication(cache에 data hit rate를 높힌다.)

- Redundant synchronization(세부적으로 asynchronization 구간을 찾아 분리한다.)

- Pararrelization Overhead(thread pooling방식 적용, thread구간을 넓히어서 pararrelization회수를 줄인다.)

 

6. Intel Thread profiler

- pararrel portion, sequential portion확인

- load imbalance 분석

- locks 오류검증

- synchronization 오류검증

- parerralization overhead 계산

 

7. Supporting Tool

- 동시동작 thread 개수 조사

- thread 수행시간 계산

 

8. Parallelization bugs

- Missing synchronizations (e.g. mutual exclusion, barrier)

- Improper locking order

- improper message passing order (in MPI programs)