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..
CS/Algorithm
[BOJ] 백준 16929 Two dots - Python/Java
문제 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 해설 이 문제에서 정의하는 싸이클을 판단하는 기준은 여러가지가 있는 것 같습니다. 저같은 경우에는 [1] '시작 노드와 연결된 간선(최대 4개)에 대해 동일한 간선을 이용하지 않고 다시 시작 노드로 돌아올 수 있다면, 싸이클이 형성된다' 라고 생각했습니다. 그런데 다른 분들의 풀이를 보니 [2] '시작 노드에 대해서는 방문 체크를 하지 않은 채 DFS 탐색을 하다가, 그 경로의 길이..
CS/OS
[운영체제/OS] Blocking / NonBlocking, Sync / Async
0. 들어가면서 이번 포스팅에서는 Blocking/Non-Blocking(블록킹, 논블록킹)과 Sync/Async(동기, 비동기) 개념에 대해 정리해보고, 각각의 개념이 어떻게 쓰이는지를 정리해보려고 합니다. 아래 두 영상에서 이 개념들을 정말 잘 설명해주신 것 같아서 해당 영상을 참고해서 정리했습니다. 꼭 한 번 시청해보세요! 멍토의 Blocking vs Non-Blocking, Sync vs Async 우의 Block vs Non-Block & Sync vs Async 1. Blocking, Non-Blocking, Sync, Async 먼저 Blocking, Non-Blocking, Sync, Async 네 가지 개념에 대해 이해해보겠습니다. Blocking: 다른 작업을 하는동안 자신의 작업에 ..
CS/Algorithm
[BOJ] 백준 12100 2048(Easy) - Python/Java
문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 해설 배열의 회전이나 변환, 슬라이싱을 얼마나 잘할 수 있는지를 보는 문제 같았습니다. 문제에서 요구하는 시뮬레이션 상황을 구현하기 위해서는 배열의 원소들을 상하좌우로 미는 함수를 구현해야 하는데요. 배열을 적절히 인덱싱해서 상하좌우에 해당하는 함수를 각각 구현할 수도 있지만, 저는 왼쪽으로 미는 함수 하나만 구현해놓고 배열의 전치(Transpose)와 대칭(Mi..
CS/Algorithm
[BOJ] 백준 16973 직사각형 탈출 - Python/Java
문제 https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 해설 일반적인 너비우선탐색(BFS) 문제가 약간 변형된 문제입니다. 보통 격자점이 주어지고 너비 우선 탐색을 하는 문제에서는 이동(탐색)하는 주체가 단위 격자점의 크기와 동일한데요. 이 문제에서는 격자점의 일부를 이루는 직사각형이 이동(탐색)을 하는 주체로 설정된 것입니다. 따라서 기존의 BFS 문제를 풀 때와 달리 아래와 같이 고민해야 하는 부분이 생깁니다. 1) ..
CS/Algorithm
[BOJ] 백준 15681 트리와 쿼리 - Python/Java
문제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 해설 해당 문제의 해설은 문제에서 주어지는 [힌트] 부분에 상세하게 제시되어 있어서 이 내용을 따라서 구현하기만 하면 정답을 구할 수 있습니다. 그래도 간단하게나마 제 해설을 적어보겠습니다. 1. 이 문제에서는 노드들을 그래프 형태로 입력받은 뒤, 트리의 루트 노드가 주어지기 때문에 루트를 기준으로 DFS를 수행하면 트리 구조를 ..
CS/Algorithm
[BOJ] 백준 2482 색상환 - Python/Java
문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 해설 이 문제에서 중요한 조건은 색상들이 "원형"으로 놓여져있다는 것인데요. 원형 배열에서는 맨 앞의 원소와 맨 마지막 원소가 서로 인접해있기 때문에, 이 둘의 관계를 적절히 처리해주는 것이 문제를 푸는데 핵심적인 열쇠가 됩니다. 저는 이 문제를 해결하기 위해 다음의 두 케이스를 나누어 생각하고, 두 케이스에서 구한 답을 총 경우의 수에 더해서 정답을 냈는데요(원형 배열에서 아래와 같이 두 가지 케이스로 나누어 문..
CS/Algorithm
[BOJ] 백준 1013 Contact - Python/Java
문제 https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 해설 이 문제의 포인트는 정규표현식 (100+1+ | 01)+ 을 통해 앞에서부터 문자열 매칭을 시도하면 '틀린다'는 것입니다. 그 이유는 기본적으로 Greedy한 선택이 이 문제의 정답을 보장하지 않기 때문인데요. 예를 들어 100011001 이라는 문자열을 보겠습니다. 정규표현식을 통해 앞에서부터 최대한 많은 문자열을 매칭시키면 아래와 같은 결과가 나옵니다. [정규표현식 이용]..
