CS/Multicore & GPU
[Multicore] 효율적인 Matrix Multiplication - 멀티쓰레드와 캐시
0. Matrix Multiplication 아래는 N * N 크기의 행렬 A, B를 곱하여 그 결과인 N * N 행렬 C를 구하는 과정입니다. 결과로 나오는 C 행렬의 (i, j)번째 값을 계산하기 위해서는 위 그림처럼 A 행렬의 i번째 행과 B행렬의 j번째 열의 원소들을 곱해야 합니다. 위 과정을 코드로 보면 아래와 같으며 두 개의 N * N 행렬의 곱셈에 드는 시간 복잡도는 O(N^3)임을 알 수 있습니다. for i = 1 to n for j = 1 to n for k = 1 to n C(i, j) = C(i, j) + A(i, k) * B(k, j) 자, 그러면 위 연산을 어떻게 멀티쓰레딩을 통해 병렬로 처리할 수 있을까요? 앞으로 몇 가지 방법에 대해 소개를 할텐데, 각 방법이 동작하는 방식과..
CS/Multicore & GPU
[Multicore] 쓰레드의 Workload 관리와 Thread Pool에 대해
1. 쓰레드의 Workload 밸런스 8개의 쓰레드를 가지고 천 만개의 원소를 가진 배열의 각 원소에 대해 특정한 연산(더하기나 빼기 등)을 하는 작업을 한다고 해보겠습니다. 그러면 우리는 각 쓰레드에 10,000,000 / 8 = 1,250,000 개의 원소에 대한 연산을 할당하고, 쓰레드가 작업을 마치면 결과를 모아서 다음 과정을 이어나갈 수 있습니다. 하지만 실제 멀티쓰레드 환경은 언제나 위와 같이 각 쓰레드가 동일하거나 비슷한 수준의 작업량을 할당받는 보장이 없습니다. 어떤 쓰레드는 다른 쓰레드보다 훨씬 더 많은 작업을 처리해야 할 수 있고, 또 다른 쓰레드는 정말 적은 양의 작업을 마치고 다른 쓰레드들이 끝나길 기다려야 할 수 있죠. 위 그림은 시간에 따른 4개 쓰레드의 작업 진행 상황입니다. ..
CS/Multicore & GPU
[Multicore] Race Condition과 Locks
1. 들어가면서 멀티쓰레딩에서 Race Condition과 Lock은 가장 기초적이면서 중요한 개념입니다. 멀티쓰레딩이라는 개념을 단순하게 정의해봐도, 여러 개의 쓰레드가 공유되는 자원을 바탕으로 분산 처리를 하는 것이기 때문입니다. 그래서 이번 포스팅은 운영체제 시간에 배웠던 Race Condition과 Lock 개념을 되짚어보고, 코드를 통해 좀 더 구체적으로 공부해보려고 합니다. 먼저 아래는 Race Condition과 Lock의 정의입니다. [1] Race Condition A race condition occurs when two threads access a shared variable at the same time. The first thread reads the variable, and t..
