-
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 생태계를 개선하는...