HD-Tree: 고성능 Lock-Free NNS KD-Tree = HD-Tree: High performance Lock-Free Nearest Neighbor Search KD-Tree

다국어 초록 (Multilingual Abstract)

Supporting NNS method in KD-Tree algorithm is essential in multidimensional data applications. In this paper, we propose HD-Tree, a high-performance Lock-Free KD-Tree that supports NNS in situations where reads and writes occurs concurrently. HD-Tree reduced the number of synchronization nodes used in NNS and requires less atomic operations during Lock-Free method execution. Comparing with existing algorithms, in a multi-core system with 8 core 16 thread, HD-Tree’s performance has improved up to 95% on NNS and 15% on modifying in oversubscription situation.

국문 초록 (Abstract)

KD-Tree에서 NNS의 구현은 다차원 데이터를 다루는 응용 프로그램에서 필수적이다. 본 논문에서는 자료구조의 동시 수정, 검색이 일어나는 멀티스레드 상황에서 NNS를 지원하는 고성능 Lock-Free KD-Tree인 HD-Tree를 제안한다. HD-Tree는 동기화에 사용되는 노드 수를 최소화하고, 사용하는 원자 연산자의 수를 감소시켜 성능을 개선하였다. 실험 결과 HD-Tree는 8코어 16스레드의 멀티코어 시스템에서 기존의 NNS보다 성능이 최대 95% 향상되었고, 삽입/삭제연산은 코어보다 스레드가 많은 상황에서 기존 알고리즘보다 최대 15%향상된 성능을 보여준다.

참고문헌 (Reference)

1 M. Herlihy, "Wait-Free Synchronization" 13 (13): 124-149, 1991

2 D. Dechev, "Understanding and Effectively Preventing the ABA Problem in Descriptor-based Lock-free Designs" 2010

3 M. Herlihy, "The Art of Multiprocessor Programming" Morgan Kaufmann 2012

4 "Steam Hardware&Software Survey"

5 F. Ellen, "Non-blocking binary search trees" ACM 131-140, 2010

6 J. L. Bentley, "Multidimensional binary search trees used for associative searching" 18 (18): 509-517, 1975

7 H. Wen, "Interval-based memory reclamation" 2018

8 M. Michael, "Hazard pointers: Safe memory reclamation for lock-free objects" 15 (15): 491-504, 2004

9 A. Natarajan, "FEAST: A Lightweight Lock-free Concurrent Binary Search Tree" 2020

10 B. Chatterjee, "Concurrent linearizable nearest neighbour search in lockfree-kd-tree" 2018

11 T. Brown, "A general technique for non-blocking trees" ACM 329-342, 2014