FASTCF: FPGA-based Accelerator for STochastic-Gradient-Descent-based Collaborative Filtering
FASTCF: FPGA-based Accelerator for STochastic-Gradient-Descent-based Collaborative Filtering
复制标题
DOI：
10.1145/3174243.3174252
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Shijie Zhou;R. Kannan;Yu Min;V. Prasanna
中科院分区：
文献类型：
--
作者：
Shijie Zhou;R. Kannan;Yu Min;V. Prasanna
使用随机梯度下降（SGD）的稀疏矩阵分解是用于从观测导出潜在特征的流行技术。SGD被广泛用于协同过滤（CF），它本身是推荐系统的一种众所周知的机器学习技术。在本文中，我们开发了一个基于FPGA的加速器，FASTCF，以加速基于SGD的CF算法。FASTCF由并行流水线处理单元组成，通过访问共享的片上缓冲区，同时处理不同的用户评级。我们通过对FPGA上基于SGD的CF加速的具体设计挑战的整体分析来设计FASTCF。基于我们对这些设计挑战的分析，我们开发了一种二分图处理方法，该方法具有一种新的3级分层分区方案，能够最大限度地减少冲突调度和片上特征向量数据的处理，从而显着加速该二分图的处理。首先，我们开发了一个快速的启发式分区的输入图到诱导子图，这使得FASTCF有效地缓冲顶点数据重用和完全隐藏通信开销。其次，我们将每个子图的所有边划分为匹配，以提取最大并行度。第三，我们调度每个匹配内的边的执行，以减少对共享的片上缓冲器的并发存储器访问冲突。与未优化的基线设计相比，分层分区方法可减少高达60倍的数据依赖性，减少4.2倍的存储库冲突，并提高15.4倍的速度。我们实现了FASTCF基于国家的最先进的FPGA和评估其性能使用三个大的现实生活中的数据集。实验结果表明，FASTCF维持高达每秒2170亿次浮点运算（GFLOPS）的高吞吐量。与最先进的多核和GPU实现相比，FASTCF分别实现了13.3倍和12.7倍的加速。
Sparse matrix factorization using Stochastic Gradient Descent (SGD) is a popular technique for deriving latent features from observations. SGD is widely used for Collaborative Filtering (CF), itself a well-known machine learning technique for recommender systems. In this paper, we develop an FPGA-based accelerator, FASTCF, to accelerate the SGD-based CF algorithm. FASTCF consists of parallel, pipelined processing units which concurrently process distinct user ratings by accessing a shared on-chip buffer. We design FASTCF through a holistic analysis of the specific design challenges for the acceleration of SGD-based CF on FPGA. Based on our analysis of these design challenges, we develop a bipartite graph processing approach with a novel 3-level hierarchical partitioning scheme that enables conflict-minimizing scheduling and processing of on-chip feature vector data to significantly accelerate the processing of this bipartite graph. First, we develop a fast heuristic to partition the input graph into induced subgraphs; this enables FASTCF to efficiently buffer vertex data for reuse and completely hide communication overhead. Second, we partition all the edges of each subgraph into matchings to extract the maximum parallelism. Third, we schedule the execution of the edges inside each matching to reduce concurrent memory access conflicts to the shared on-chip buffer. Compared with non-optimized baseline designs, the hierarchical partitioning approach results in up to 60x data dependency reduction, 4.2x bank conflict reduction, and 15.4x speedup. We implement FASTCF based on state-of-the-art FPGA and evaluate its performance using three large real-life datasets. Experimental results show that FASTCF sustains a high throughput of up to 217 billion floating-point operations per second (GFLOPS). Compared with state-of-the-art multi-core and GPU implementations, FASTCF demonstrates 13.3x and 12.7x speedup, respectively.