-
yhunroh's profile image
yhunroh
September 28, 2024
Advanced SIMD Guide
Intro 최근에 SIMD 연산을 활용해서 최적화를 해 볼 기회가 있었습니다. 그 과정에서 겪었던 어려운 점들과 흥미로운 점들, 그리고 유용한 점들을 모아 공유하고자 합니다. 확인해보니, 암호학 분야를 깊게 보시는 blisstoner께서 기존에 SIMD에 관한 소개글을 포스팅하신 것이 있습니다. Link 이 글에서는 좀더 다양한 연산들, 주의해야 할 점들, 그리고 어떻게 쉽게 개발할 수 있을지를 집중적으로 설명해봅니다. 간단하게 다시 짚고 넘어가자면, SIMD (Single Instruction Multiple Data) 연산은 다수의 데이터에 동일한 연산을 한꺼번에 적용하고자 하는 목표를 가집니다. 여러 개의 데이터를...
-
yhunroh's profile image
yhunroh
July 29, 2024
Software Combining
Intro 지난 포스트들에서는 구체적인 자료구조 (BST, List 등)을 concurrent하게 어떻게 구현할 수 있을지를 살펴보았다. 이번에는 조금 더 일반적인 트릭인 software combining 에 대해서 알아보자. 표현이 조금 모호할 수 있으나, 이 주제의 관심사는 ‘여러 스레드가 효율적으로 하나의 shared object에 연산을 하는 방법’의 한 갈래로, 한 스레드가 여러개의 스레드의 연산을 한꺼번에 처리해주는 것에 대한 논의이다. 그렇기 때문에 software ‘combining’이라는 이름으로 불린다. 가장 일반적인 논의는 ‘임의의 sequential한 object를 concurrent하게 wrapping하는 법’인 universal construction에 대한 것이 되겠지만, 이번 포스트에서는...
-
yhunroh's profile image
yhunroh
June 29, 2024
Concurrent Augmented Tree
Intro 이전의 글에서 Concurrent Non-Blocking Binary Search Tree를 알아보았다. 이번에는 단순히 Insert, Delete, Find만 지원하는 트리가 아니라, Range Query를 지원하는 자료구조에 대해서 알아보자. Key Points & Brainstorming 이전의 글에서 알아봤던 lock-free-locks로 만든 leaf tree, 그리고 Ellen Tree는 모두 Insert, Delete, 그리고 Find (혹은 Lookup) 연산만을 지원한다. 아주 중요한 연산들이지만, 실제로 자료구조를 사용할 때는 더 다양한 종류의 연산들이 필요한 경우가 많다. 흔히 Seqential한 환경에서 생각해볼 수 있는 연산은, Range sum 연산이다. key_l과 key_r이 주어졌을 때, 트리...
-
yhunroh's profile image
yhunroh
March 27, 2024
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한 환경에서는 동시에 여러 개의 연산이 동작할 수 있기 때문이다. 예를...
-
yhunroh's profile image
yhunroh
February 26, 2024
Concurrent Non-Blocking Linked List
Intro Competitive Programming에서 다루는 대부분의 자료구조들은 Sequential한 환경을 기준으로 고안되고 구현된다. 하지만 이제 단일 프로세서의 성능 개선 한계에 가까워지면서, 멀티 프로세서를 잘 활용하는 것의 중요성이 더욱 더 커지고 있다. 기존에 단일 프로세서에서 동작하던 로직을 몇몇의 일반적인 Lock이나 Shared Message Queue등을 통해 멀티 프로세서에서 동작하도록 하는 것은 성능상의 한계가 있다. 그러한 기초적이고 일반적인 방법을 통해서는 여전히 많은 부분들이 Sequential하게 남아 있어, 프로세서의 개수를 많이 늘린다고 해서 성능 개선이 많이 증가하지 않기 때문이다. 관련 분석으로는 Amdahl의 법칙을...
-
yhunroh's profile image
yhunroh
October 23, 2023
Gradient Boosting Overview
소개 Machine Learning에 대한 대중적인 인식은 대부분 Deep Learning, Neural Networks에 치중되어 있지만, 그 밖에도 활발하게 연구되면서 활용되고 있는 알고리즘들이 많이 있습니다. 이 글에서는 그 중에서 Gradient Boosting에 알고리즘에 대한 소개와 이해를 목표로 합니다. 신경망의 근간이 되는 Gradient Descent 알고리즘과 이름이 비슷하지만, Gradient Boosting 알고리즘과 Gradient Descent 알고리즘은 구조적으로 큰 유사성이 없습니다. 둘 다 loss function을 최소화한다는 유사점은 있지만, 작동 원리는 상이하며 각자에 기대하는 역할이 구분됩니다. Gradient Boost 알고리즘은 결정 트리, 랜덤 포레스트 알고리즘에 기반하며,...
-
yhunroh's profile image
yhunroh
September 25, 2023
Mojo Overview
소개 https://www.modular.com/mojo Mojo는 파이썬의 생태계를 그대로 흡수하면서 C와 비견할 만한 성능과 low-level 기능들까지 갖추는 것을 지향하는 언어입니다. 주로 AI 연구 및 서비스, 데이터 분석 및 처리를 타겟층으로 하여 개발되고 있습니다. Mojo는 Modular라는 기업에서 개발하고 있으며, Co-Founder인 Chris Lattner는 Swift, LLVM, Clang, MLIR를, 또 다른 Co-founder인 Tim Davis는 Tensorflow, Android ML에서 각각 주도적인 역할을 한 것으로 알려져 있습니다. 특히 수십명에 달하는 Modular 팀에 AI Infra, Dev 직군이 무척 많다는 것으로부터 현재 팀의 방향성은 AI 생태계를 개선하는...