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

요약

본 논문은 FPGA 환경에 최적화된 B+ 트리 기반 인덱스 검색 알고리즘을 제안합니다. 이 접근법은 레벨별 배치 처리를 통해 메모리 액세스를 줄이고 노드 재사용성을 높여, FPGA에서 병렬 검색 키 비교를 효율적으로 수행할 수 있게 합니다. 고수준 합성(HLS) 기법으로 구현된 커널은 실제 하드웨어 가속기에서 CPU 기반 알고리즘 대비 상당한 성능 향상을 입증했습니다.

핵심 포인트

• FPGA에 최적화된 B+ 트리 검색 알고리즘을 제시하여, 메모리 액세스 비용 절감 및 노드 재사용성 극대화를 달성함.
• 레벨별 배치 처리(Level-by-level batch processing)를 통해 트리를 효율적으로 탐색하고 병렬 처리를 가능하게 함.
• HLS 방식을 사용하여 가변 배치 크기, 사용자 정의 가능한 노드 크기 등 높은 유연성을 가진 검색 커널을 설계함.
• 실제 하드웨어 테스트 결과, 단일 커널 FPGA는 CPU 대비 4.9배, 다중 커널 FPGA는 CPU 대비 2.1배의 성능 향상을 보임.