.png){kind=icon}
.png){kind=icon}
Return
Accelerating Stochastic Gradient Descent Based Matrix Factorization on FPGA
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2020.2974744.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Matrix Factorization (MF) based on Stochastic Gradient Descent (SGD) is a powerful machine learning technique to derive hidden features of objects from observations. In this article, we design a highly parallel architecture based on Field-Programmable Gate Array (FPGA) to accelerate the training process of the SGD-based MF algorithm. We identify the challenges for the acceleration and propose novel algorithmic optimizations to overcome them. By transforming the SGD-based MF algorithm into a bipartite graph processing problem, we propose a 3-level hierarchical partitioning scheme that enables conflict-minimizing scheduling and processing of edges to achieve significant speedup. First, we develop a fast heuristic graph partitioning approach to partition the bipartite graph into induced subgraphs; this enables to efficiently use the on-chip memory resources of FPGA for data reuse and completely hide the data communication between FPGA and external memory. Second, we partition all the edges of each subgraph into non-overlapping matchings to extract the maximum parallelism. Third, we propose a batching algorithm to schedule the execution of the edges inside each matching to reduce the memory access conflicts to the on-chip RAMs of FPGA. Compared with non-optimized FPGA-based baseline designs, the proposed optimizations result in up to 60x data dependency reduction, 4.2x bank conflict reduction, and 15.4x speedup. We evaluate the performance of our design using a state-of-the-art FPGA device. Experimental results show that our FPGA accelerator sustains a high computing throughput of up to 217 billion floating-point operations per second (GFLOPS) for training very large real-life sparse matrices. Compared with highly-optimized GPU-based accelerators, our FPGA accelerator achieves up to 12.7x speedup. Based on our optimization methodology, we also implement a software-based design on a multi-core platform, which demonstrates 1.3x speedup compared with the state-of-the-art multi-core implementation.
Keywords:
Field programmable gate arrays
Acceleration
Training
System-on-chip
Optimization
Partitioning algorithms
Bipartite graph
Machine learning
sparse matrix factorization
training acceleration
bipartite graph representation
FPGA accelerator
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
Organization
View more organizations