-
Rust의 GC를 직접 구현해보자
서론 Rust는 GC가 없는 언어입니다. 하지만 지난 글에서 살펴보았듯이 Rust에서도 GC가 필요한 경우가 있습니다. 그래서 이번 글에서는 Rust에서 GC를 직접 구현해보려고 합니다. GC 구조 설계 Rust는 ownership 시스템으로 인해 GC를 구현하는 것이 까다롭습니다. C/C++ 등의 언어에서는 단순히 포인터를 사용하면 되지만 Rust에서는 포인터를 사용할 때마다 ownership을 고려해야 합니다. 물론 unsafe를 사용하면 ownership을 고려하지 않고도 포인터를 사용할 수 있지만, 이번 글에서는 unsafe를 최대한 사용하지 않고 GC를 구현해보려고 합니다. Rust에서 GC를 구현하기 위해서는 다음과 같은 구조가 필요합니다. 그럼...
-
Massively Parallel Computation
이 글에서는 parallelism과 관련하여 최근에 제시된 두 계산 모델에 대해 간단히 알아본다. 또한, 그 계산 모델 상에서 돌아가는 잘 알려진 (그러면서도 이론적으로 중요한) 문제에 대한 알고리즘 및 계산 이론적 결과를 알아본다. 다만 이 주제에 대해 deep 하고 formal한 내용은 전혀 다루지 않는다. 전반적으로 두 계산 모델에 대한 이해를 조금 만드는 정도를 목표로 한다. 이 글에서 “높은 확률”은 최소한 1 - (polynomially small) 이상이라 이해하면 좋다. Massively Parallel Computing Model (MPC) 먼저, Massively Parallel Computing Model(MPC)에...
-
The Cut-Matching Game: Expanders via Max Flow
알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 알고리즘 연구에서 분할 정복이 가지는 중요성은 어마어마하지만, 그래프에 대한 분할 정복에 대해서는 좋은 결과를 얻지 못했다. 오랜 시간 동안 이러한 분할 정복 은 트리, 평면 그래프, 혹은 이와 유사한 그래프에서만 가능한 것으로 알려져 있었다. 하지만, 그래프 알고리즘과 최적화 이론의 결합이 여러 의미 있는 성과들을 내면서, 이러한 분할...
-
2023 SCON
개요 지난 5월 20일에 진행된 2023 SCON이 성공적으로 종료되었습니다. SCON은 Soongsil Programming Contest의 약자로, 숭실대학교 IT대학 재학생들을 대상으로 하는 ICPC 성격의 3인 팀 대회입니다. 이 글에서는 2023 SCON에 출제된 문제의 풀이에 대해서 다룹니다. 대회 개최와 운영에 관한 이야기는 운영진의 블로그(링크)에서 확인하실 수 있습니다. 문제 목록 대회에는 아래 목록의 10문제가 사용되었고, 저는 이 중에서 3문제(E,F,I)를 출제했습니다. SCON에는 competitive programming 분야에 익숙하지 않은 학생들이 다수 참가하며 대회 시간이 3시간으로 짧은 편이고, 교내 ICPC 수상자가 모두 출제진으로 빠졌음을...
-
BFV scheme에 대한 소개 - 5
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV Multiplication을 어떻게 처리하는지에 대해서 설명을 했습니다. 이번 글에서는 저번 글에서 다 하지 못한 설명을 마무리하도록 하겠습니다. Backgrounds 이번 글은 기본적으로 저번 글에서 설명한 내용을 이어서 하는 것이기 때문에, 따로 Background는 필요하지 않으나, 저번 글의 내용을 이해하는 것이 중요합니다. 특히 FastBConv 함수의 정의에 대해서 잘 기억해 주세요. Step 4. 앞의 step 3의 결과를 다시 불러와 봅시다. \[FastRNSFloor_q(t \cdot ct[j], B_{sk})...