조인을 이용한 병렬 순서 집합

순서 집합은 이론적 알고리즘 설계 및 분석, 그리고 실제 프로그래밍에서 가장 중요한 데이터 유형 중 하나입니다. 본 논문에서는 AVL 트리, 레드-블랙 트리, 가중치 균형 트리 및 트리탭을 포함한 네 가지 균형 이진 탐색 트리(BST)를 기반으로 두 개의 순서 집합에서의 집합 연산인 합집합, 교집합 및 차집합을 연구합니다. 우리는 각 균형 BST에 대해 다르게 구현되어야 하는 Join이라는 단일 서브루틴만을 도입하였으며, 이를 통해 순서 집합을 위한 일반적이고 간단하며 효율적인 병렬 함수를 구현할 수 있습니다. 우리는 처음에 이 Join 기반 집합 함수의 작업 효율성을 네 가지 균형 BST에 대해 작용하는 일반적인 증명을 사용하여 증명합니다. 또한 네 가지 균형 스킴 모두에서 우리의 알고리즘을 구현하고 테스트했습니다. 흥미롭게도, 네 가지 데이터 구조와 세 가지 집합 함수에 대한 구현이 시간과 가속도 면에서 유사한 성능을 보여줍니다(64코어에서 45배 이상). 우리는 또한 우리의 구현 성능을 다른 기존 라이브러리 및 알고리즘과 비교합니다.