멀코 8장. 병렬 라이브러리

프로그래밍이 편리하다. 디버깅이 어렵다.

블럭킹으로 구현하면 안된다. 운영체제 호출하면 안된다.

컨텍스트 스위치 오버헤드와 스레드 생성 오버헤드가 없다. 생성한 코어에서만 사용이 가능해서 멀티 코어에서 사용하지 못한다.

O

컴파일러 레벨에서 구현되어야 한다.

X

A: Multi-Thread B: 공유메모리

A: 컴파일러 디렉티브, B: 함수, C: 변수

분산 메모리에서는 사용할 수 없다. 최상의 공유메모리 사용 패턴을 보장하지 않는다. Data Dependency, Data Race, Deadlock 검사는 프로그래머가 해야 한다. 어느 부분을 어떻게 병렬화 할지를 프로그래머가 지정해 주어야 한다.

Fork-join

X

X

call by value

call by reference

O

X

data dependency

O

X

쓰레드 사용에 편리한 여러 API를 가진다. Task 관리 기능을 포함한다. Intel CPU에서 동작한다.

Loop Parallelizer: loop를 병렬로 사용하고 싶을 때 사용 Containers: vector, set, queue에서 사용하는 contains를 최적화해서 non-blocking으로 구현해 놨다. Mutual Exlusion: 여기서도 뮤텍스를 제공하지만 기존 C++11에 있는 것과 비슷하다. 메모리 할당자: 멀티스레드 상에서의 효율적인 메모리 할당자 Task 스케쥴링

O

parallel_for(first, last, step, f);

모든 메소드가 다 안전한 것이 아니다. insert(), find(), count(), size(), at()만 안전하다. erase()가 안전하지 않아서 지울 수가 없다.

X

size_t(0), N, [&table](int i)

concurrent_hash_map

동시성 문제가 있기 때문이다.

clear() 메소드는 병렬수행이 불가능하니 꼭 다른 메소드와 동시에 호출되지 않도록 해야 한다. 원소들이 연속된 주소에 있지 않으므로 일반적인 pointer 연산은 불가능하다. 크기 감소가 안된다. 원소를 읽을 때 원소가 생성 중일 수 있으므로 읽기 전에 생성완료를 확인하도록 프로그래밍해야 한다.

empty() 호출이 pop()의 성공을 보장하지 않기 때문이다. empty()를 할때는 empty가 아니었지만 pop()할 때는 empty일 수 있기 때문이다.

lock_guard

read_only인 메소드는 동시 실행해도 아무 문제가 없기 때문에 read_lock과 write_lock을 따로 두어 read_lock끼리는 상호배제없이 사용하도록 하는 것이다.

템플릿

busy waiting을 없애 CPU 낭비를 없앤다. 근데 busy waiting 없애려고 운영체제 호출해서 오버헤드가 크다. critical section이 길어서 오래 걸리는 구간이라면 효율이 올라가겠지만 그게 아니면 낭비이다.

critical section에 도착한 순서로 lock을 얻는다. 큐 형태로 호출한다.

block

상호배제를 해제하여 critical section을 동시에 수행하게 한다. 동시에 실행시켜서 문제가 없으면 그냥 실행하고 충돌해서 문제가 생기면 둘 중 하나를 롤백 시키는 형태이다.

X

하나의 task 관리 객체에 많은 task를 넣어 주는 것은 비효율적이다. task 관리 객체를 로컬 객체로 생성하고 소수의 task를 넣는 방식으로 구현하는 것을 권장한다.

O

셰이더 언어

X

O

General Purpose GPU

NVIDIA 하드웨어만 지원한다.

O

X

OpenCL을 사용하면 된다.

I/O 작업이 느리다. 메모리가 적다. 직렬계산이 느리다. gpu로 계산하려면 데이터 보내줘야 하는데 보내는 부분이 병목현상이 발생한다.

게임은 i/o 작업이 많고 실시간으로 처리해줘야 하는게 많은데 gpu는 그게 느리다.

멀티스레드로 돌리면 P, E 코어 둘 다 같이 돌아가는데 P코어가 먼저 일을 끝내고 E코어를 기다리는 현상이 발생한다. 게임이랑 상극이다.

장점 - 직관적이다. - 의도대로 잘 돌아간다. - 프로그래밍이 쉽다. 단점 - 병렬성이 없어서 성능개선의 여지가 없다. - 우선순위 역전: 높은 우선순위의 스레드가 잠금이 없어서 실행되지 못한다. - 호위현상: 잠금을 잡은 스레드가 실행을 멈춘 동안에는 모든 잠금을 원하는 스레드가 대기해야 한다. - 교착상태: 일명 데드락

확장성이 떨어진다. 복수개의 메소드호출의 atomic화는 어렵다. 알고리즘의 정확성을 증명하는 것이 어렵다.

O

X

O

병렬성, 확장성, 넌블럭킹

Zombie 트랜잭션이 되지 않도록 주의해야 한다. - 동기화 충돌 이후에도 트랜잭션이 계속 실행될 수 있다. 성능이 좋지 않다. - 모든 read/write를 api를 통해서 해야 하므로 성능이 좋지 않다.

O

캐시 태그에 트랜잭션비트를 추가하였다. 트랜잭션이 끝나고 캐시가 충돌했는지 확인하다. 충돌이 없으면 그냥 캐시에 있는 값 쓰고 아니면 캐시에 있는 값 invalid에 넣는다.

X. L1까지 허용

critical section이 최대한 작아야 성능이 좋기 때문이다.

goto를 써서 transaction 구간이 커지면 성능에 안 좋은 영향을 미친다.

생산성, 확장성, 정확성, 성능

STM 단점 성능: 오버헤드가 커서 코어가 매우 많지 않으면 오히려 성능 저하 HTM 단점 범용성: 일부 CPU에서만 지원 제한성: hw 용량의 한계로 알고리즘이 제한된다. High Contention 상황에서 lock-free 보다 성능 저하가 있다. 한계: 코어의 개수가 많아질 경우 성능향상의 한계가 찾아온다.

X

O

모든 알고리즘에 적용이 불가능하다. 오버헤드가 크다.

O

Channel

O

X. 그런 명령어는 없다. 싱글 스레드 알고리즘인데 멀티 스레드로 돌아간다.

태스크 자체가 너무 작아지면 문제가 있다. 그럴경우는 싱글로 돌려주어야 한다.

구현 난이도가 있기 때문이다.

X. coroutine에 가까운 것이다.

생산성, 성능, I/O 문제