-
Aggregated Funnels
Intro 저번 글에서 Software Combining이 무엇인지, 이를 이용해 fetch-and-add를 어떻게 구현할 수 있는지를 살펴보았다. 이번에는 fetch-and-add 연산을 더 빠르게 만들어주는 Aggregating Funnels 알고리즘을 알아보자. Aggregating Funnels는 PPoPP 2025에서 발표될 논문에서 소개된 알고리즘이다. 본인은 알고리즘 설계 및 실험 수행에 주로 참여하였다. 실험 코드 또한 https://github.com/Diuven/aggregating-funnels 에 공개되어 있다. Combining Funnels와 목표하는 바는 비슷하고, 둘 다 Software Combining의 접근을 취하지만, 작동 방식 및 성능은 상당히 다르다. 이 글에서는 알고리즘의 개요와 성능에 대해서 설명한다. Key Points & Brainstorming...
-
ptrace로 프로세스 제어 및 응용하기
Intro 안녕하세요. 이번 글에서는 리눅스에서 제공하는 시스템 콜인 ptrace를 활용하여 프로세스를 제어하는 방법을 다루어보려 합니다. ptrace는 프로세스(process)를 추적(trace)하고 디버깅하는 데 사용되는 강력한 기능을 제공합니다. 우리가 흔히 사용하는 GDB(GNU Debugger)도 내부적으로 ptrace를 사용하여 디버깅 기능을 수행합니다. 본 글에서는 ptrace가 제공하는 여러 기능을 살펴본 후, 이를 응용하여 간단한 예제 프로그램을 만들어 보겠습니다. 본 글은 기본적인 시그널 제어 및 프로세스 핸들링을 이해하고 있다는 가정 하에 작성되었습니다. 시그널과 프로세스에 대한 기본적인 이해가 없는 경우, 먼저 해당 내용을 숙지하신 후...
-
Cartesian Tree를 활용한 문제 해결
Cartesian Tree Cartesian Tree는 대소 관계가 있는 값의 배열으로부터 유도되는 Binary Tree로, 구간의 min/max와 관련된 문제에 사용하면 편리한 자료 구조입니다. 배열의 최솟값 또는 최댓값에 해당하는 인덱스를 루트로 하게 되는데, Min Cartesian Tree의 경우 최솟값에 해당하는 $\mathrm{array}[i] = \min_{l \leq i \leq r}(\mathrm{array}[i])$인 $i$가 루트가 되며, $[l, r]$번째 원소의 최솟값에 대응되는 노드 $i$의 왼쪽 자손은 $[l, i-1]$에서의 최솟값, 오른쪽 자손은 $[i+1, r]$에서의 최솟값에 해당하는 인덱스가 됩니다. 자주 사용하게 되는 성질 몇 가지가 있는데, 각 노드의 subtree가...
-
PS에서 C++ 상속 활용하기 2
지난 글에 이어, PS에서 상속을 활용할 수 있는 사례 하나를 더 소개해보도록 하겠습니다. 행렬 라이브러리 PS 문제를 풀다보면, 가끔 행렬을 이용해서 풀어야 하는 문제들을 만날 수 있습니다. 이러한 문제들을 풀기 위해서는 행렬 곱셈 등의 연산을 구현해야 합니다. 비록 코드가 길지는 않지만, 이러한 행렬 곱셈을 매번 구현하는 것은 귀찮은 일이니, 행렬에 관한 라이브러리를 만들어두고 필요할 때마다 가져다 쓰는 것이 편할 것입니다. (더 빠른 행렬 곱셈 알고리즘이나, 반복문의 반복 순서 조정을 통한 캐시 히트율 개선 등 성능적...
-
Gomory-Hu algorithm을 응용해 minimum odd cut 문제 해결하기
Introduction $T$-join 문제의 LP-relaxation을 생각해보자. (이 문제의 정의는 필자의 이전 글들에서 여러번 언급 했으므로 자세한 설명은 생략한다.) \[\begin{align*} \text{minimize:} & & \sum_{e \in E} c_e \cdot x_e && \\ \text{subject to:} & & x(\delta(S)) \ge 1 & &\forall S \subseteq V, \lvert S \cap T \rvert \equiv 1\pmod2 \\ & & x_e \ge 0 & & \forall e \in E \end{align*}\] 이 문제의 경우, LP의 optimal solution이 integral 하여, LP를 해결하면 원본 문제를 효율적으로 (다항...