[논문]HD-Tree: 고성능 Lock-Free NNS KD-Tree

이상기; 정내훈

doi:10.7583/jkgs.2020.20.5.53

초록
AI-Helper

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

Abstract ▼ AI-Helper

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 ...

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.

Keyword

표/그림 (12)

그림 [Fig. 1] Epoch Based memory Reclamation
그림 [Fig. 2] KD-Tree
그림 [Fig. 3] External tree
그림 [Fig. 4] Nearest Neighbor Search
그림 [Fig. 5] Search in HD-Tree
그림 [Fig. 6] Initial state of HD-Tree
그림 [Fig. 7] Insert in HD-Tree
그림 [Fig. 8] Remove in HD-Tree
그림 [Fig. 9] The structures and Read/Write Operations in HD-Tree
그림 [Fig. 10] NNS in HD-Tree
그림 [Fig. 11] NNS Operations in HD-Tree
그림 [Fig. 12] Result of the experiment

AI 본문요약
AI-Helper

문제 정의

본 논문에서는 멀티코어 시스템을 충분히 활용할 수 있는 고성능 Lock-Free NNS KD-Tree인 HD-Tree를 제안한다. HD-Tree는 기존에 제안된 JAVA로 구현된 병행 KD-Tree[1]를 C++로 변환한 것을 기반으로 하였다.

제안 방법

본 논문에서는 멀티코어 시스템을 충분히 활용할 수 있는 고성능 Lock-Free NNS KD-Tree인 HD-Tree를 제안한다. HD-Tree는 기존에 제안된 JAVA로 구현된 병행 KD-Tree[1]를 C++로 변환한 것을 기반으로 하였다. C++에서의 성능 개선을 위해 새로운 메모리 재사용 구조를 추가하고, 개선된 동기화 방법을 사용하여 기존 알고리즘이 가지고 있는 성능상의 문제를 해결하였다.
HD-Tree는 기존에 제안된 JAVA로 구현된 병행 KD-Tree[1]를 C++로 변환한 것을 기반으로 하였다. C++에서의 성능 개선을 위해 새로운 메모리 재사용 구조를 추가하고, 개선된 동기화 방법을 사용하여 기존 알고리즘이 가지고 있는 성능상의 문제를 해결하였다.
실험은 각 스레드가 임의의 2차원 점을 키 값으로 사용하여 2초 동안 실행하는 것을 5번씩 반복하여 실행시간의 평균값으로 초당 실행된 작업 수를 계산해서 비교하였다.

데이터처리

LFKD-Tree_C++를 구현할 때 NNS에서 사용한 후 비활성화된 NNC노드를 후처리하지 않으면 비교가 불가능할 정도로 성능이 떨어지기 때문에 NNC노드를 후처리하는 루틴을 추가하여 알고리즘의 문제를 해결한 상태로 성능을 비교하였다.

이론/모형

본 논문에서는 노드를 물리적으로 제거할 때 모든 스레드가 참조를 끝마칠 때 까지 유예기간을 두어 노드를 안전하게 제거할 수 있도록 도와주는 EBR알고리즘을 사용한다. [Fig.

성능/효과

NNS에서 Key space가 1K x 1K일 경우 관리 하는 노드 수가 늘어나서 메모리를 관리하는 EBR 알고리즘의 오버헤드가 커지기 때문에 스레드 수가 적을 때 HD-Tree가 JAVA보다 성능이 떨어지는 경우가 생기지만, 기존 알고리즘이 가지고 있던 문제점을 해결했기 때문에 스레드 수가 늘어나는 만큼 성능이 향상되는 것을 확인할 수 있다.
동기화 방법을 개선한 HD-Tree의 NNS는 기존 알고리즘의 C++구현보다 성능이 최대 95%만큼 좋아졌다.
본 논문에서는 기존의 Lock-Free KD-Tree의 동기화 방법을 수정해서 성능을 개선한 HD-Tree를 제안하였다. 기존 NNS알고리즘에서 Lock-Free 리스트를 사용하여 노드를 관리하는 부분을 총 스레드 개수만큼의 고정크기 배열로 변경하는 것으로 지나친 리스트 순회로 성능이 떨어지던 문제를 해결하여 높은 성능을 얻었고, 트리의 노드를 제거하는 부분에서 사용하는 CAS의 수를 줄이고 연결된 제거가 필요한 노드들을 한 번에 처리할 수 있도록 변경하여 높은 경합 상황에서의 성능이 향상되었다.

후속연구

향후 연구과제는 동기화 알고리즘을 더욱 최적화하거나 병행 NNS알고리즘을 더욱 발전시켜 KD-Tree 내부의 기준거리 미만의 노드들을 수집하여 반환하는 연산과 같은 게임개발에 유용한 기능을 추가하는 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	KD-Tree에서 다차원 데이터를 다루는 응용 프로그램에서 필수적 구현은?	KD-Tree에서 NNS의 구현은 다차원 데이터를 다루는 응용 프로그램에서 필수적이다. 본 논문에서는 자료구조의 동시 수정, 검색이 일어나는 멀티스레드 상황에서 NNS를 지원하는 고성능 Lock-Free KD-Tree인 HD-Tree를 제안한다.
	KD-Tree는 어떤분야에서 주로 사용하는가?	KD-Tree는 게임, 기계학습, 이미지검색 등 컴퓨터 그래픽스를 활용한 분야에서 주로 사용된다. 이러한 분야에서 다차원 데이터를 활용하기 위해 일반적으로 NNS(Nearest Neighbor Search)를 사용하기 때문에 멀티코어 시스템에서 이를 제대로 활용하기 위해서는 검색, 삽입, 삭제 작업이 병행하게 일어나는 상황에서 NNS를 지원해야한다.
	Lock-Free 자료구조를 구현할 경우 hazard pointer, EBR과 같은 메모리를 관리를 위한 Lock-Free 알고리즘이 추가적으로 필요한 이유는?	기술자 기반 동기화 방법을 사용할 경우 노드를 제거할 때 다른 스레드가 제거될 노드에 접근하여 발생하는 제거 타이밍 문제와 ABA문제[8]가 존재한다. 때문에 Lock-Free 자료구조를 구현할 경우 hazard pointer[9], EBR(Epoch Based memory Reclamation)[3]과 같은 메모리를 관리를 위한 Lock-Free 알고리즘이 추가적으로 필요하다.

참고문헌 (11)

B. Chatterjee, I. Walulya, and P. Tsigas. "Concurrent linearizable nearest neighbour search in lockfree-kd-tree". ICDCN '18: Proceedings of the 19th International Conference on Distributed Computing and Networking, 2018.
A. Natarajan, A. Ramachandran and N. Mittal. "FEAST: A Lightweight Lock-free Concurrent Binary Search Tree". ACM Transactions on Parallel Computing. 2020.
H. Wen, J. Izraelevitz, W. Cai, H. A. Beadle and M. L. Scott. "Interval-based memory reclamation". ACM SIGPLAN Notices. 2018.
Steam Hardware&Software Survey: July 2020. https://store.steampowered.com/hwsurvey/cpus/
M. Herlihy and N. Shavit. "The Art of Multiprocessor Programming Revised Reprint". Morgan Kaufmann, 2012.
J. L. Bentley. "Multidimensional binary search trees used for associative searching". CACM, vol. 18, no. 9, pp. 509-517, 1975.
M. Herlihy. "Wait-Free Synchronization". ACM Transactions on Programming Languages and Systems (TOPLAS), 13 (1): 124-149, Jan. 1991.
D. Dechev, P. Pirkelbauer and B. Stroustrup. "Understanding and Effectively Preventing the ABA Problem in Descriptor-based Lock-free Designs". 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, 2010.
M. Michael, "Hazard pointers: Safe memory reclamation for lock-free objects", IEEE Transactions on Parallel and Distributed Systems, 15 (6): 491-504. 2004.

상세보기
F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. "Non-blocking binary search trees". In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC'10). ACM, New York, NY, 131-140. 2010.
T. Brown, F. Ellen, and E. Ruppert. "A general technique for non-blocking trees". In Proceedings of the 19th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP'14). ACM, New York, NY, 329-342. 2014.

이 논문을 인용한 문헌

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] HD-Tree: 고성능 Lock-Free NNS KD-Tree
HD-Tree: High performance Lock-Free Nearest Neighbor Search KD-Tree 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

Keyword

표/그림 (12)

표/그림 (12)

AI 본문요약
AI-Helper

문제 정의

제안 방법

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (11)

이 논문을 인용한 문헌

활용도 분석정보

활용도 Top5 논문

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] HD-Tree: 고성능 Lock-Free NNS KD-Tree HD-Tree: High performance Lock-Free Nearest Neighbor Search KD-Tree 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

Keyword

표/그림 (12) 모든 표/그림 보기

표/그림 (12) 슬라이드로 보기

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (11)

이 논문을 인용한 문헌

활용도 분석정보

활용도 Top5 논문 더보기

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] HD-Tree: 고성능 Lock-Free NNS KD-Tree
HD-Tree: High performance Lock-Free Nearest Neighbor Search KD-Tree 원문보기

초록
AI-Helper

표/그림 (12)

표/그림 (12)

AI 본문요약
AI-Helper

활용도 Top5 논문