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

• Creating a Parallel Program

1. Decomposition

 

- Decomposition 이란 작업물을 분할하는 것이다. 1~ 100 까지 숫자를 연산해야한다고 하면 1~ 10까지 11~20까지 등으로 작업물을 나누는 것이다. 

이러한 작업물을 나누는 대는 두가지 방법이 있다.

BLOCK : 쓰레드의 개수만큼 크게크게 나눈다.

CYCLIC : 잘개 나누고 쓰레드에 할당한다.

 

BLOCK을 사용하면 크게 나누지 않아 오버헤드가 적지만 로드밸런싱이 좋지 않고 CYCLIC은 로드밸런싱은 좋지만 오버헤드가 많다. 상황에 따라 다르지만 CYCLIC이 효과가 좋을 때가 많다. 이를 Domain Decomposition 이라한다.

 

Functional Decomposition은 작업 유형에 따라 나누는 것이다, 정렬문제, 서치문제 등으로 나누게된다. 

 

- Assignment

Decomposition에서 나눈 작업물들을 할당하는 작업이다. 여기서 Static 과 Dynamic 으로 나눌 수 있는데 Static 은 컴파일타임에 작업물이 할당되기 때문에 프로그래머가 결정하는 것이고 Dynamic 은 런타임에 유동적으로 할당되는 방식이다.

 

-Orchestration

구조적으로 커뮤니케이션과 동기화를 의미한다.

프로세서가 동기화와 통신에서 비용을 줄이도록 하는 과정이다. 

 

- Mapping 

쓰레드에 execution units 으로 실행하는 과정. 보통 OS가 실행한다.

 

각 단계에서 Performance of Parallel Programs 를 살펴보자.

Decomposition - Coverage of Parallel in algorithm : 병렬알고리즘에 의해

Assignment - Granularity of Partitioning among processor : 어떻게 쪼개느냐에 달려있다.

Orchestration/Mapping - Locality of computation and communication : 소통을 얼마나 빨리하고 계산하느냐에 따라 달려있다.

 

암달의 법칙 : 병렬 컴퓨팅을 한다고 해서 다 성능이 향상되지 않는다. 병렬컴퓨팅이 가능한 부분이 있어야 그 부분을 개선하는건데 반드시 시퀀셜한 부분이라면 성능은 좋아지지 않는다.

 

speed up = old running time / new running time

 

1 / {(1 - p) + p / n} 

 

여기서 p는 병렬이 가능한 수 n은 전체수이다.

 

•  Performance Scalability 

확장성 : 확장성이란 시스템이 커져서 쓰레드가 많아지거나 자원이 많아져도 성능이 비슷하게 좋아지는 정도를 뜻한다. 

 

• Granualrity

qualitative measure of the ratio of computation to communication

Coarse : relatively large amounts of computational work are done between communication events

Fine : relatively small amounts of computational work are done between communication events

 

 파인의 경우 잘게 나누고 작은 계산 후 커뮤니케이션을 한다. 그러므로 계산은 줄지만 커뮤니케이션을 많이하기 때문에 오버헤드가 자주 발생한다. 오버헤드가 높기 떄문에 성능향상이 어렵고 로드밸런싱은 잘 될 수 있다. 스레드 수가 많을 때 유리 block , cyclic 모두 파인에 속함

 

코어스는 큰 계산 후 커뮤니케이션을 한다. 그러므로 계산은 어렵지만 커뮤니케이션을 자주하지 않는다. 오버헤드가 낮고 로드밸런싱이 어렵다. 쓰레드 수가 적을 때 유리

 

대부분 granularity의 효율은 알고리즘과 하드웨어에 달려있다. 대부분의 케이스에서 오버헤드는 커뮤니케이션과 동기화에 달려있다. 파인 은 오버헤드를 둘이는데 도움을 줄 수 있다. 로드밸런싱이 안좋은대신에

 

로드밸런싱은 각 작업을 얼마나 고르게 분배하느냐이다. 

The whole work should be completed as fast as possible 

 

As workers are very expensive, they should be kept busy.

 

They work should be distributed fairly. About the same amount of work should be assigned to every worker.

 

There are precedence constraints between different tasks (we can start building the roof only after finishing the walls). Thus we also have to find a clever processing order of the different jobs.

: 올바른 작업 처리 순서도 찾아내야한다.

 

•  Load Balancing Problem 

Processors that finish early have to wait for the processor with the largest amount of work to complete

: 일찍 완료된 프로세서는 가장 많은 일을 처리하는 프로세서가 완료될 때 까지 기다려야함. -> 동기화/커뮤니케이션

 

1. Static Load balancing

nProgrammer make decisions and assigns a fixed amount of work to each processing core a priori

nLow run time overhead

nWorks well for homogeneous multicores

nAll core are the same

nEach core has an equal amount of work

nNot so well for heterogeneous multicores

nSome cores may be faster than others

nWork distribution is uneven

 

오버헤드가 낮고 호모지니어스한 멀티코어에서는 잘 작동하지만 헤테로이지니어스한 멀티코어에서는 잘 작동하지 않을 수 있음. -> 로드밸런싱이 안좋을 수 있음

 

2. Dynamic Load balancing

런타임에 로드밸런싱을 맞추는 방식, 기본적으로 높은 런타임 오버헤드를 갖고 있음.

만약 쓰레드가 많으면 같은 엑세스가 자주 일어날 수 있음. 즉, 확장성에 문제가 있음. 헤테로지니어스 한 멀티코어에서 좋음 

 

로드밸런싱 - 어떻게 하면 잘 나눌 수있을까?

동기화/커뮤니케이션 - 어떻게 해야 오버헤드가 덜 일어날까?

 

커뮤니케이션 vs 동기화

커뮤니케이션 : 두개이상의 프로세스나 시스템 사이에서 상호작용하는 일, 정보 교환의 개념

동기화 : 다수의 프로세스나 스레드들이 공유자원에서 동시에 접근하면서 생길 수 있는 일

 

커뮤니케이션의 종류

1. Point to Point

2. All to All

3. Broadcast(one to all) and Reduce (all to one)

4. Sactter (one to several) and Gather (several to one)

 

커뮤니케이션의 비용

1. 오버헤드 언제나 오버헤드가 일어남 

2. 대기비용 종종 작업간의 동기화가 필요한데 이 때 대기시간으로 대기비용이 듦

process 나 task 간의 통신은 시스템 성능에 부정적인 영향을 줄 수 있음

 

Latency vs Bandwidth 지연시간 vs 대역폭

 

레이턴시 : 최소단위 메세지를 보내는데 걸리는 시간

대역폭 : 시간단위당 전송할 수 있는 데이터의 량

많은 작은 메세지를 보내면 지연시간이 커뮤니케이션 오버헤드를 지배할 수 있음. 그러므로 작은 메세지를 패키지로 보내는 것이 효율적일 수 있음

 

MPI

Message Passing Library

- SPMD 모델

 

병렬컴퓨팅, 클러스터, 이질적인 네트워크, 멀티코어

 

Reduction

- 프로세서들이 협업하여 하나의 대규모 연산을 처리하는 방법. 

프로세서는 리덕션을 각 프로세서들이 모두 기여할 때 까지 각 프로세서들이 완료되지 않아야함.

 

동기화

 

동기화의 타입

1. 배리어

- Any thread/process must stop at this point(barrier) and cannot porceed until all other threads/processes reach this barrier

2. 락/ 세마포어

- The first task acquires the lock. This task can then safely (serially) access the protected data or code.

- Other tasks can attempt to acquire the lock but must wait until the task that owns the lock releases it.

 

지역성

병렬 프로세서는 빠르고 큰 메모리를 가지고 있다. 알고리즘은 로컬데이터에서 하는게 좋다.

 

 UMA.

중앙에 위치한 메모리를 사용하여 모든 프로세서들이 균등한 거리에 있기 때문에 엑세스타임이 동일함

 

NUMA

 물리적으로 분할되어있지만 모든 프로세서가 엑세스할 수 있는데 메모리를 사용함. CC-NUMA는 캐시 일관성을 유지하면서 NUMA를 구현하는 방법임.

 

캐시 일관성

- 캐시를 공유하면 데이터의 변화를 다른 메모리는 이상한 값을 갖고 있을 수 있다. 이것에 대한 조치를 해주어야한다.

 

스누핑 : 데이터 요청을 모든 프로세서에게 보내는 방식으로 모든 프로세서에 대한 데이터 요청을 처리

 

디렉토리-베이스 : 공유되는 데이터를 디렉터리에서 추적하여 각 프로세서에 대한 직접적인 요청을 보냄

 

Share Memory Architecture

모든 프로세서는 전역 주소공간으로 모든 메모리에 엑세스 가능 우마, 누마

장점

: 전역 주소 공간은 메모리에 대한 사용자 친화적인 프로그래밍 관점을 제시함. 메모리와 CPU의 근접성으로 데이터 공유가 빠르고 균일함

 

단점

: CPU간의 확장성 부족. 동기화를 위한 프로그래머가 책임을 져야함. 

또한 점 점 더 많은 프로세서를 가진 공유 메모리 기계를 설계하고 제작하는 것이 비싸고 어려워짐

 

Distributed Memory Architecture

- 오직 자신만의 로컬 메모리만을 가짐

- 독립적임

- 커뮤니케이션 네트워크를 요구함 

 

장점

- 확장성

- 비용이 효율적

 

단점

- 데이터 통신의 프로그래머 책임

- 전역메모리없음

- 비균일 메모리 엑세스 타임

 

Hybrid Architectr\ure

두개 짬뽕

확장성좋음

만들기 ㅈㄴ어려움