FPGA 기반 레벨별 탐색을 위한 B+ 트리 인덱스 구조의 효율적 배치 검색 알고리즘

본 논문은 필드 프로그래머블 게이트 어레이 (FPGA) 에서 실행에 최적화된 B+ 트리 기반 인덱스 구조를 위한 검색 알고리즘을 소개합니다. 우리는 레벨별 처리를 통해 검색 키의 일괄 (batch) 를 처리함으로써 트리의 노드를 효율적으로 탐색하고 재사용하는 구현을 제시합니다. 이 접근법은 비용이 많이 드는 글로벌 메모리 액세스를 줄이고, 로드된 B+ 트리 노드의 재사용성을 향상시키며, FPGA 에서 직접 병렬 검색 키 비교를 가능하게 합니다. 고수준 합성 (HLS) 방식을 사용하여 가변 배치 크기, 사용자 정의 가능한 노드 크기, 임의의 트리 깊이를 지원하는 유연하고 구성 가능한 검색 커널 설계를 개발했습니다. 최종 설계는 AMD Alveo U250 데이터 센터 가속기 카드에 구현되었으며, AMD EPYC 7542 프로세서 (2.9 GHz) 에서 실행되는 TLX 라이브러리의 B+ 트리 검색 알고리즘과 비교 평가되었습니다. 검색 키 1,000 개의 배치 크기, 100 만 개의 엔트리를 포함하는 B+ 트리, 그리고 트리 오더 16 조건에서 단일 커널 FPGA 설계는 단일 스레드 CPU 구현 대비 4.9 배의 속도 향상을 보였습니다. FPGA 에서 네 개의 커널 인스턴스를 병렬로 실행한 경우, 16 개 스레드를 사용하는 CPU 구현 대비 2.1$ imes$의 성능 향상을 달성했습니다.