멀티코어 컴퓨팅 - Create a Parallel Program

 멀티코어 컴퓨팅의 궁극적 목표는 결국 Better Perfomence 를 내는 것이다. 이름과 마찬가지로

a + b

c + e 

위 코드를 병렬 컴퓨팅 처리해서 한번에 계산하면 연산 속도는 2배 빠를 것이다.

 

1. Decomposition 

 처리할 작업을 분류한다. A라는 거대한 작업이 있다면 이를 a b c d로 분류하는 것이다. 이 때 a b c d중 어떤 작업을 병렬처리할 수 있는지도 분류하는데 이때 병렬처리 가능한 부분이 클 수록 성능개선치가 높아진다.

- Amdahl's Law

성능 개선치 예상 공식

 이때, 프로세서가 2억개 있어도 순차처리가능 부분은 무조건 25초가 걸린다. 그러나 병렬처리가 가능한 부분은 거의 0초로 줄일 수 있다.

Speed Up = old running time / new running time

ex) 프로세서가 10개이면 50초 -> 5초 이므로

Speed Up = 100 / 55 = 1.818

 

 

1-1 Domain Decomposition (영역 분해법)

 위 그림처럼 BLOCK 형태로 넓직하게 쪼갠다면 어떨까, 한눈에 보기도 편하고 병렬처리하기 쉬운 것 처럼 보인다. 그러나 이는 단점이 있는데, 4개로 쪼갰을 때 1번 BLOCK은 1~10까지 더하는 연산, 2번은 10~10000까지 더하는 연산으로 쪼개졌다고 하자, 그렇다면 1번 블락을 맡게된 쓰레드는 2번이 모두 처리될 때 까지 (comunication)할 때 까지 놀고 있을 것이다. 이는 비효율적 병렬 컴퓨팅이다. 

그렇다면 아래 CYCLIC으로 쪼갠다면 1번에서 1~5더하고 끝나면 15~20더하고 2번은 6번부터... 이런식으로 매우 균등하게 분배될 것이다. 

즉, BLOCK형태로 쪼개면 I/O가 적지만 Load Balencing 이 좋지않고, CYCLIC 형태는 I/O가 많아 오버헤드가 많이 발생하지만 Load Balencing 이 좋다. 두 경우 모두 상황에 따라 다르지만 CYCLIC 방법이 더 좋다고 한다.

 

영역 분해법의 예시

x축과 cosx의 사이 넓이를 구한다고 가정했을 때 BLOCK 방법시는 인테그랄로 CYCLIC 방법시 시그마 형태로 나타낼 수 있다. 결과는 같다. 

 

1-2 Fuctional Decomposition

 영역 분해법 처럼 영역으로 나누는 것이 아니라 계산의 형태에 초점을 맞춘다(?) 해야할 일에 따라 초점을 맞춘다는 건데 비슷한 연산끼리 묶는다는 것 같다. 즉 더하기는 더하기기리 뺼셈은 뺄셈끼리 정렬은 정렬끼리 이렇게 한다. 단, 이러면 가장 느린 프로세싱에 맞춰질 수 밖에 없다. 

 

2. Assignment 

 작업을 1번의 두가지 방법 중 하나로 쪼갰다면 이제 할당해야한다. 이때 static 방법과 dynamic 방법이 있는데 static은 compile time 즉, 프로그래머가 코드로 정해주는 방식이고 dynamic은 runtime에 알고리즘에 의해 정해진다.

할당의 목적 -

1. Balanced workload

2. Reduced communication costs

 

3. Orchestation

 communication과 synchroization을 구조화.

 

4. Mapping

 실제 작업을 위해 쓰레드에 매핑, 보통 OS가 한다고하네,,,