멀티코어컴퓨팅 - 2. Performance of Parallel Programs

Flynn's Taxanomy

 

Instruction stream, Data stream 에 따라서 병렬성을 고려해 컴퓨터의 종류를 분류한다.

 

SISD (single instruction, sigle data)

병렬성이 없는 컴퓨터이다.

 

SIMD (single instruction, multiple data)

gpu가 여기 해당한다.

모든 프로세스 유닛이 clock cycle동안 (다른 데이터에 대해서) 동일한 instruction을 수행한다.

parallel processing이라고 할수있다.

 

MISD(Multiple Instruction, Single Data)

독립된 여러 프로세서들이 동일한 데이터에 대해서 서로다른 병렬 작업을 수행한다.

 

MIMD (Multiple Instruction, Multiple Data)

각 코어가 여러 데이터에 대해서 여러 작업을 수행한다. 코어는 독립적으로 행동한다.

요즘 대부분의 CPU가 여기에 해당한다.

 

Creating parallel program

decomposition

entire task를 작은 small tasks로 쪼갠다.

do_payroll()이라는 작업을 sequential하게 수행하면 좌측 그림과 같다.

그런데 do_payroll()을 작은 네개의 sub task들로 분해해서 네개의 프로세서가 병렬 처리 가능하도록 쪼개는 단계를 말한다.

사용하는 데이터를 기준으로 sub task들로 분해(domain decomposition)

각 프로세서들은 data의 특정 portion에서만 작업을 하게 된다.

ex) 100명의 시험지를 두명이서 채점한다고 하면 A는 1~50 시험지만 채점하고 B는 51~100 시험지만 채점하는 것과 같다. 

ex) Matrix, Image에 대한 작업이 특히 이렇다.

data set의 portion 기준으로 다양하게 sub task들로 쪼갤 수 있다.

cyclic : 작은 chunk들을 반복적으로 프로세서들에게 할당. load balancing, 지역성에 관점에서는 더 좋은 방법이다

block : 큰 chunk를 할당, work유닛 수가 적기 때문에 communication, syncronization 오버헤드는 비교적 더 적을 수 있다.

수행할 기능들을 기준으로 sub task로 분해(Functional decomposition)

ex) 100명의 시험지를 두명이서 채점한다고 하면 A는 모든 시험지의 객관식만 채점하고 B는 주관식만 채점하는 것과 같다. 

 

Assignment

small tasks를 각 프로세서에게 할당한다.

communication cost를 최소화하면서 load가 균일하게 분배되도록 한다.

Orchestration

communication, synchronization을 수행하는 단계.

최대한 communication cost를 최소화하고 지역성을 보존하도록 한다.

Mapping

각 프로세서에게 thread를 할당하는 단계

최대한 locality를 보존하고 communication, syncronization을 최소화 하는 방향으로 OS가 수행하는 작업이다.

 

Amdahl’s Law

amdahl의 법칙에 의하면 병렬처리 가능한 부분에 대해서만 성능향상이 가능하다. 즉 코어가 무한대라도 50초보다 더 단축할 수 없다. (1/(1-p)보다 작거나 같다.)

사실상 speed up에서 중요한건 sequential한 부분의 비율이다.

Scalability

scalability는 extension과는 다르다. parallel computing에서 가장 중요한 두가지를 꼽으라면 scalability와 load balancing이다.

resource가 추가될때마다 speedup의 정도를 말한다. 이상적으로 linear line을 그린다. 실제로는 Linear speedup보다 기울기가 낮은 그래프로 나타난다.

cache utilization, cpu scheduling등이 받쳐주면 ideal한 그래프보다 더 높은 scalability도 가능하다.

 

Granularity

work unit의 크기를 나타낸다. (좌)fine level granularity (우)coarse level granularity 라고 한다. 너무 fine해도 coarse해도 좋지 않기 때문에 중간을 선택한다.

do payroll하나의 크기가 granularity이다. work unit이 클수록 한 한 unit에 더 많은 computational work가 있다.

보통 computation work 이후 communication(synchronization) work가 이루어진다. 노란색 작업이 동기화 작업에 해당한다.

fine grain

computation/communication 이 작다. (communication overhead크다)

대신 load balancing에 용이하다.

coarse grain

computation/communication 이 크다 (communication overhead가 낮다).

대신 load balancing에 불리하다. 하지만 얼마든지 개선 방법을 찾을 수 있다.

 

Load balancing

모든 프로세서들이 항상 busy하도록 작업을 공평하게 잘 분배해야 한다.(프로세서의 idle time을 최소화 한다)

load balancing이 잘 되지 않으면 먼저 일이 끝난 프로세서가 synchronozation을 위해 아직 작업중인 프로세스를 기다리는 경우가 생길수도 있다.

static load balancing

load balancing이 compile time에 이루어지는 것, 프로그래머가 미리 core들에게 작업량을 assign한다.

따라서 load balancing을 위한 runtime overhead가 낮다.

core들이 동일하다면 이렇게 동일한 양의 작업을 미리 나누어주는 방법이 잘 될수있다.

반대로 core들이 heterogeneous하다면 (어떤 코어가 조금 더 빠름) static하게 작업량을 distribute하기 쉽지 않다.

dynamic load balancing

load balancing이 실행시간에 이루어지는 것, 실행시간 전에 누가 어떤 task를 할당받을지 모른다.

특히 heterogeneous한 코어들 사이에서 computing power가 unpredictable하다면 이상적인 방법이다.

코어,쓰레드들이 각자 task queue로 부터 일을 가져가서 수행한다. work queue가 다 빌때까지 동적으로 load balancing이 수행된다.

load balancing을 위한 runtime overhead가 크다.

communication

processor, thread간의 communication을 말한다.

communication은 비용이 굉장히 큰 작업이다. 

synchronous동기 : 요청을 했으면 즉시 이어서 응답이 온다. 응답을 기다리며 멈춰있는다.

asynchronous비동기 : 요청을 했는데 언제 응답이 올지 모른다. 그동안 다른 일을 하고 있는다.

*reduction : 작은 semi 결과들에 대해 add, or, and, min, max등을 통해 최종 결과를 만드는 것. 모든 프로세서의 data를 모아서 한 결과를 반환하는 것

blocking(synchronous) : ex)sender는 메시지의 응답이 올때까지 기다린다. 즉 communication이 끝날때까지 block된다.

non-blocking(asynchronous) : ex)sender는 자기 할일 하고 있다가 응답이 오면 그때 가서 확인한다. block되지 않는다.

 

MPI : Message Passing Library

다른 컴퓨터에게 메시지를 보내고 받는데 사용하는 라이브러리이다.

clusters에서는 MPI사용이 아주 일반적이다.

이렇게 한 프로세서에서 다른 프로세서로의 통신을 Point-to-point라고 한다.

파란 사각형들의 면적을 구하는 경우 reduction을 수행하면 된다. 프로세서끼리 구역을 나눠서 처리한 다음 MPI로 통신하여 하나의 결과를 내는 것이다.

 

synchronization

race condition을 피하고 올바른 runtime 순서를 얻기 위해 동시에 일어나는 이벤트들을 coorinate하는 것을 말한다.

barrier : 쓰레드, 프로세스가 반드시 어떤 지점 안에 끝나야 할때 그 지점을 말한다.

lock/semaphore : 한 쓰레드가 자원을 소유하는동안 다른 쓰레드는 대기한다. (동기화 문제를 해결하기 위해 사용하는 방법)

 

Shared Memeory Architecture

프로세서를 100개가지 등 확장이 어려움

하나의 global address memory를 서로 공유한다. (어떤 cpu든지 메모리의 어느공간이든 접근이 가능)

따라서 synchronization이 반드시 필요하다

프로세서 수가 많아질수록 설계하기가 어렵고 비싸다

Uniform memory Acess (UMA)

모든 코어들이 중심에 메모리 하나를 공유

Non uniform memory access (NUMA)

물리적으로 서로 분리되어 있지만 서로 접근 가능

하지만 논리적으로 하나의 메모리를 공유하고 있다고 느낀다.

large scale의 서버레벨의 컴퓨터의 경우 흔한 architecture이다.

 

Distributed memeory architecture

각각 독립된 메모리를 갖는다.

서로의 메모리에 접근하기가 쉽지 않다. global memory access가 불가능

가격이 저렴하고 규모를 키우기가 쉽다

상대적으로 느린 data communication이 수행되어야 한다.

 

 

cache coherence

공유 메모리 시스템에서 각 클라이언트(혹은 프로세서)가 가진 로컬 캐시 간의 일관성을 의미한다.

각 클라이언트가 자신 만의 로컬 캐시를 가지고 다른 여러 클라이언트와 메모리를 공유하고 있을 때, 캐시의 갱신으로 인한 데이터 불일치 문제가 발생한다.

예를 들어 변수 X에 대해서 두 클라이언트가 변수 X를 공유하고 있고 그 값이 0이라고 하자. 이때 클라이언트 1이 X에 1을 대입하였고 클라이언트 2가 변수 X를 읽어들이게 되면 클라이언트 2는 클라이언트 1에 의해 수정된 값인 1을 받아들이는 것이 아니라 현재 자신의 로컬 캐시에 있는 0을 읽어들이게 된다. 따라서 캐시 1, 2는 같은 X라는 변수에 대해 다른 값을 가지게 되므로 데이터 불일치 문제가 발생한다. 캐시 일관성을 유지한다고 하는 것은 이러한 데이터 불일치 현상을 없애는 것을 의미한다.