TL;DR
This paper introduces KGAccel, the first domain-specific hardware accelerator on FPGAs designed to speed up Knowledge Graph Reasoning (KGR) tasks, particularly those leveraging Reinforcement Learning (RL). By developing novel compression techniques and an on-chip RL environment, KGAccel achieves significant speedups and energy efficiency improvements over traditional CPU and GPU approaches.
What Problem Does This Paper Address?
Knowledge graphs (KGs) are powerful tools for organizing vast amounts of information, enabling applications like question answering and recommendation systems. However, KGs are often incomplete, requiring reasoning capabilities to infer missing facts. While hardware accelerators exist for general graph tasks, they often fall short for KGR, which involves complex models and long training times, especially for RL-based approaches. Existing solutions primarily focus on embedding-based models and struggle with the dynamic and sparse action spaces inherent in RL-based KGR. This paper addresses the need for a specialized hardware accelerator that can efficiently handle the unique demands of RL-based KGR, bridging the gap between general-purpose hardware and this computationally intensive AI task.
Methods
The core of KGAccel is its domain-specific architecture implemented on FPGAs. Key innovations include:
- Domain-Specific Accelerator for RL-based KGR: KGAccel is designed from the ground up for KGR tasks using RL. It integrates both the KG environment and the RL agent onto a single FPGA, minimizing data transfer overhead.
- Knowledge Graph Compression (CSR Format): To handle the large size of KGs and fit them into limited on-chip FPGA memory, the authors employ the Compressed Sparse Row (CSR) format. This significantly reduces storage overhead and optimizes memory access.
- Resource-Aware Mechanism for High-Speed Training: A fine-tuned systolic array-based neural network accelerator is used for the policy network. This design integrates forward propagation and weight updates in a single pass, crucial for efficient RL training.
- On-Chip KG RL Environment: Unlike previous RL accelerators that keep the environment on the CPU, KGAccel maintains the KG environment on-chip. This drastically reduces communication latency between the agent and its environment.
- Context-Switching Mechanism: For smaller FPGAs with limited on-chip memory, a hierarchical memory scheme is used. Entity embeddings are partially stored on-chip, and a context-switching mechanism is employed to swap them from off-chip DRAM when needed, enabling efficient operation on resource-constrained edge devices.
- Imitation Learning: To accelerate agent training, an imitation learning approach is incorporated. A "teacher" (supervised policy) guides the agent when it fails, speeding up learning and improving convergence.
Datasets
The paper evaluates KGAccel using two widely used knowledge graph datasets:
- FB15K-237: A common KG dataset for evaluating reasoning capabilities.
- NELL-995: Another standard KG dataset for reasoning tasks.
Key Insights and Ideas
- FPGA Suitability for KGR: The inherent parallelism, reconfigurability, and near-memory computing capabilities of FPGAs make them exceptionally well-suited for KGR tasks, outperforming GPUs which are often bottlenecked by data transfer.
- On-Chip Environment is Crucial: Maintaining the KG environment on-chip, rather than relying on CPU-FPGA communication, is a key enabler for reducing latency and improving the efficiency of RL-based KGR.
- Compression is Essential for Edge Deployment: The CSR compression technique is vital for fitting large KGs into the limited on-chip memory of smaller FPGAs, making edge deployment feasible.
- Integrated Training and Inference: By integrating the KG environment, RL agent, and policy network on a single FPGA, KGAccel achieves significant performance gains by minimizing data movement.
Key Results
KGAccel demonstrates substantial performance improvements:
- Speedup: Up to 65x speedup over CPU and 8x speedup over GPU on a large-size FPGA (Alveo U280). On a resource-limited FPGA (ZCU104), it achieves over 15x speedup compared to the CPU.
- Energy Efficiency: Over 30x higher energy efficiency compared to CPU. Specifically, KGAccel on Alveo U280 shows 45x higher energy efficiency compared to state-of-the-art RL-based reasoning models on Intel Xeon Silver 4114. On ZCU104, it shows over 50x energy efficiency improvement over the CPU.
- Accuracy: The paper reports competitive reasoning accuracy, with detailed results presented in figures and appendices, showing comparable or superior performance to embedding-based methods like TransE and TransR.
Limitations and Future Work
- Limited On-Chip Memory on Smaller FPGAs: For smaller FPGAs like ZCU104, only a portion of entity embeddings can be stored on-chip. This necessitates context switching, which can increase training time, especially with more reasoning hops.
- Future Work: The authors suggest exploring solutions to mitigate context switching overhead, such as using larger FPGA boards or enhancing CPU-FPGA bandwidth with optimized interconnect IPs. They also aim to further optimize the KGAccel architecture for even greater efficiency and performance.
Summary updated