Computer Science/멀티코어

LockFreeHashing

Fine-grained Lock의 문제 멀티 쓰레드 상황에서 Hash에 consistency를 유지하고 싶다면 hash의 key에 lock을 걸어서 사용하는게 일반적인 방식일 것이다. 우리는 Hash를 사용하는 이유는 시간복잡도가 매우 낮기 때문일 것이다. 하지만 hash key 1개당 가지고 있는 데이터 수가 늘어나게 되면 이러한 시간복잡도로 인한 장점은 무색해진다. 따라서 Bucket 크기를 늘려야하는 시점이 오게 된다. Fine-grained Lock을 사용하는 상황에서 bucket을 증가시킨다고 하면 어떤 식으로 증가시켜야할까? 다음 그림을 보자 이 상황에서 우리가 bucket의 크기를 늘리게 된다면 늘어난 bucket에 대해 lock을 할당해야할 것이다. 하지만 lock의 갯수를 늘리는게 맞는 ..

LockFreeList

1. Locking Mechanism의 문제 우리가 멀티쓰레드 상황에서 쓰레드간 공유자원에 대하여 consistency를 위해 Locking Mechanism을 사용하곤 한다. 이러한 Lock의 경우 다음과 긑은 문제를 야기하게 된다. DeadLock : 당연하다. Priority Inversion : OS의 스케줄링에 따르면 우선순위가 낮은 프로세스가 먼저 Lock을 획득하게 되어 우선순위가 역전되는 현상이 발생한다. Convoying : Locking을 획득하고 이를 해제하기 까지 가장 속도가 느리게 걸리는 프로세스에 의해 다른 프로세스들의 속도 또한 지연되는 현상을 의미한다. Async-signal unsafety : function이 signal handler에서도 안전하게 호출될 수 있는 것을 ..

[CUDA] GPU에서 코드 돌리기

병렬 프로그래밍의 종류 : SIMD vs SPMD SIMD(Single Instruction Multiple Data), SPMD(Single Program Multiple Data)에서 알 수 있듯이 여러 데이터를 가지고 병렬로 수행하는 단위가 Instruction이냐 Data이냐 라는 차이가 존재한다. 우리가 Instruction이라는 말에서도 알 수 있듯이 SIMD는 쓰레드별 동기화가 반드시 필요하게 되고 이러한 동기화는 하드웨어의 지원으로 이뤄지게 된다. SPMD는 반면에 동기화에 대해 SIMD보다 느슨하게 이뤄지는 게 특징이다. GPU는 이 중에 SPMD에 해당하는 Machine이다. GPU의 여러 쓰레드는 같은 code를 실행하지만 다른 데이터를 가지고 code를 실행한다. GPU의 용어 1...