-
CUDA #01: Introduction to Many-Core Programming
Introduction Many-Core Programming Many-core processor는 많은 수의 core를 가져 대규모의 병렬 연산이 가능한 프로세서를 의미하며, 이를 활용하는 것을 many-core programming이라고 부른다. 유사한 용어인 multi-core는 수~수십 개 정도의 core들에 대한 의미를 주로 포함하는 것과는 달리, many-core는 그보다 훨씬 많은 수천~수만 개의 core들에 대하여 사용한다. 최근 many-core programming은 GPU(Graphics Processing Unit)가 게임, 계산과학, 인공지능 등 다양한 workload들을 처리하기 시작하면서 매우 중요해지고 있는 추세이다. 특히 GPT, ViT 등 Transformer 기반의 거대 AI 모델들은 실수의 행렬곱이라는 병렬화가 매우 잘...
-
Communication complexity
Introduction two-party model of deterministic communication (늘 그렇듯이) Alice와 Bob이라는 이름의 두 사람이 있다. 함수 $f: X \times Y \rightarrow Z$에 대해, Alice는 $x \in X$, Bob은 $y \in Y$를 알고 있을 때 두 사람이 $f(x,y)$를 최소 bit의 커뮤니케이션으로 알아내는 것이 목표이다. 즉, 목표는 $f(x,y)$의 값을 두 명이 알아내는 것이고, cost가 주고받은 bit의 개수일 때 cost를 minimize하는 문제이다. 먼저 여러 가지 $f$의 예를 살펴보며 각각 어떤 방식으로 해결하는 것이 확인해 보자. Example 1. $EQ_n: \{...
-
플로우 그래프 커팅
개요 Problem Solving을 하다 보면, 주어진 문제에서 플로우 그래프를 모델링했을 때 그래프의 크기가 너무 커서 단순히 플로우 알고리즘을 사용할 경우에 시간 초과를 받게 되는 상황이 종종 발생합니다. 이 글에서는 위와 같은 상황에서 추가적인 관찰을 통해 플로우 그래프의 크기를 줄이는 몇 가지 방법을 소개합니다. 문제마다 필요한 관찰과 해결 방법이 제각기 다를 수 있으므로 다양한 연습 문제를 예시로 들어서 설명하겠습니다. 디닉 알고리즘의 구현체를 통일하기 위해 AtCoder Library의 MaxFlow를 사용하겠습니다. 연습 문제 AtCoder Beginner Contest 320 G. Slot...
-
Secure Matrix Multiplication with Homomorphic Encryption - 1
Introduction 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 간단하게 말해서, 어떤 두 plaintext $m_0, m_1$을 encrypt한 것이 $ct_0, ct_1$이라고 할 때, $dec(ct_0+ct_1) = m_0 + m_1$이 성립합니다. 동형암호 scheme 중에서도, 두 가지 연산, 즉 addition과 multiplication을 제한 없이 사용할 수 있다면 그런 동형암호 scheme을 Fully Homomorphic Encryption, 줄여서 FHE라고 부릅니다. 현재 나와 있는 대부분의 동형암호 scheme의 경우, RLWE problem의 Hardness에 의존하고 있습니다. 대표적인 FHE scheme으로는 BGV, BFV, CKKS, TFHE 등이...
-
Number Theory Techniques
https://www.acmicpc.net/category/detail/4072 해당 링크는 12월 3일에서 12월 10일까지 열렸던 BOJ Bundle이라는 백준 커뮤니티 대회이다. 이번 글에서는 대회에 사용되었던 정수론 테크닉들을 몇 개 소개해보려 한다. F. Queens’ Rye Cafe 요약: 분모가 $N$이하인 $[0, 1]$의 기약분수들을 정렬하였을 때, $a/b$의 $j$번째 다음 항을 구해야 한다. Farey Sequence의 성질을 이용하는 문제이다. 특히 이번 ICPC 2023 예선 G에 출제되면서 더욱 유명해진 것 같다. Farey Sequence란 정렬된 기약분수의 수열을 생성하는 방법이다. 기본적으로 두 기약분수 $(0/1, 1/1)$에서 시작한다. 매 차례마다 두 기약분수 $a/b$와...