Learned Index techniques show faster lookup speed compared to traditional index structures such as B-trees. For the learned index model training, CPU needs to perform linear algebraic operations like QR decomposition. In the learned index where keys can be inserted and deleted, the models must be retrained periodically to deal with newly inserted keys. However, in the CPU-based learned index, bottlenecks occur due to problems such as share of CPU resources and inefficiency of model training in the CPU. In this thesis, I propose a matrix decomposition based on matrix memoization and a new model training algorithm to solve this problem. Also, I propose a model training hardware accelerator based on heterogeneous CPU-FPGA system, propose a template architecture using design space exploration, and accelerate learned index.
머신 러닝 기반 인덱스는 B-트리와 같은 기존 인덱스보다 더 빠른 검색 속도를 보인다. CPU는 머신 러닝 기반 인덱스의 모델 훈련을 위해 QR 분해와 같은 선형 대수 연산을 수행한다. 또한 키의 삽입과 제거가 가능한 머신 러닝 기반 인덱스에서는 새로 삽입된 키를 처리하기 위해 주기적으로 모델을 다시 학습되어야 한다. 하지만, CPU 기반의 머신 러닝 기반 인덱스에서는 CPU 자원의 분배, 학습의 비효율성 등의 문제로 병목이 발생한다. 본 논문에서는 이 문제를 해결하기 위해 행렬의 메모이제이션을 기반으로 한 행렬 분해와 이를 활용한 새로운 모델 학습 알고리즘을 제안한다. 또한 CPU-FPGA 이기종 시스템을 기반으로 하는 모델 학습 하드웨어 가속기와 디자인 공간 탐색을 활용한 템플릿 아키텍처를 제안하여 머신 러닝 기반 인덱스를 가속하였다.
