-
Concurrent Non-Blocking Binary Search Tree
Intro 이전의 글에서 Concurrent non-blocking linked list를 알아보았다. 이번에는 Linearlization 및 lock-free-locks의 개념과 함께, 조금 더 복잡하고 활용도가 있는 Binary search tree의 구현에 대해서 알아보자. Linearizability BST는 Linked List와 다른 구조를 가지고 있지만, 원하는 성질 자체는 비슷하다. 여러 개의 프로세서가 동시에 효율적으로 작업할 수 있고, 그 결과들이 모두 옳아야 한다. 그런데, 여기서 ‘옳음’의 정의가 모호하다. Sequential한 환경에서는 임의의 시점에 하나의 연산만 동작할 수 있지만, Parallel한 환경에서는 동시에 여러 개의 연산이 동작할 수 있기 때문이다. 예를...
-
Concurrent Non-Blocking Linked List
Intro Competitive Programming에서 다루는 대부분의 자료구조들은 Sequential한 환경을 기준으로 고안되고 구현된다. 하지만 이제 단일 프로세서의 성능 개선 한계에 가까워지면서, 멀티 프로세서를 잘 활용하는 것의 중요성이 더욱 더 커지고 있다. 기존에 단일 프로세서에서 동작하던 로직을 몇몇의 일반적인 Lock이나 Shared Message Queue등을 통해 멀티 프로세서에서 동작하도록 하는 것은 성능상의 한계가 있다. 그러한 기초적이고 일반적인 방법을 통해서는 여전히 많은 부분들이 Sequential하게 남아 있어, 프로세서의 개수를 많이 늘린다고 해서 성능 개선이 많이 증가하지 않기 때문이다. 관련 분석으로는 Amdahl의 법칙을...
-
FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores
Introduction 이번 글에서는 작년 11월에 처음 arXiv에 게재되었고 ICLR 2024 poster로 발표될 예정인 FlashFFTConv에 대해 다루어 보고자 한다. 먼저 introduction에서는 논문과 조금 다르게 필자가 생각하는 motivation들을 적어 보고자 한다. Scaling Law of LLM Scaling Laws for Neural Language Models는 OpenAI에서 연구한 결과를 정리한 article로, 다음 [Figure 1]의 결과를 제시한다. [Figure 1]은 여러 metric들이 지수적으로 증가함에 따라, LLM의 성능이 개선되는 것을 잘 보여주고 있다. 이러한 transformer 기반 모델의 특성은 현재 LLM을 NLP의 중심으로 만들었을 뿐만 아니라...
-
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 모델들은 실수의 행렬곱이라는 병렬화가 매우 잘...
-
Massively Parallel Computation
이 글에서는 parallelism과 관련하여 최근에 제시된 두 계산 모델에 대해 간단히 알아본다. 또한, 그 계산 모델 상에서 돌아가는 잘 알려진 (그러면서도 이론적으로 중요한) 문제에 대한 알고리즘 및 계산 이론적 결과를 알아본다. 다만 이 주제에 대해 deep 하고 formal한 내용은 전혀 다루지 않는다. 전반적으로 두 계산 모델에 대한 이해를 조금 만드는 정도를 목표로 한다. 이 글에서 “높은 확률”은 최소한 1 - (polynomially small) 이상이라 이해하면 좋다. Massively Parallel Computing Model (MPC) 먼저, Massively Parallel Computing Model(MPC)에...
-
HPX parallel partition 알고리즘
안녕하세요. 오늘은 제가 예전에 HPX 라는 오픈소스에 구현했던 parallel partition 알고리즘에 대해 간단히 소개하고 설명하는 시간을 가져보도록 하겠습니다. » 이 글을 좀 더 좋은 가독성으로 읽기 « 출처 먼저 이 포스팅에서 다루는 알고리즘/코드의 출처는 다음과 같습니다. HPX : https://github.com/STEllAR-GROUP/hpx 관련 MR : https://github.com/STEllAR-GROUP/hpx/pull/2778 소스코드 : https://github.com/STEllAR-GROUP/hpx/blob/master/hpx/parallel/algorithms/partition.hpp 소개 parallel partition 알고리즘은 여러 개의 연산 유닛 (쉽게 말하면 cpu) 들을 이용해서 partition 알고리즘을 수행하는 것을 말합니다. 이 포스팅에서는 독자가 partition 알고리즘에 대해서 이미 알고있다고 가정합니다. partition 알고리즘에...