学位论文简介
来自各种领域的多属性之间交互生成的关系型数据形成高阶、高维和大规模稀疏张量（High-order, High-dimension, and Large-scale Sparse Tensors, HHLST），而直接对 HHLST 进行分析是不切实际的。张量分解技术是处理 HHLST 的一种常用方法，它将原始张量投影到低阶或低维空间中表示，同时保留其多阶结构信息，从而实现对原始张量高效的存储、计算、分析和解释。Tucker 分解是主流张量分解技术中的一种，它将原始张量分解为多个低秩因子矩阵和一个核张量，这些因子矩阵提取不同阶的重要特征，而核张量则反映它们之间的相互作用。为了处理这些 HHLST，需要高效且可扩展的并行算法，然而现有的并行 Tucker 分解算法由于其巨大的计算开销与空间开销无法有效处理 HHLST。本研究在多 GPU 平台上针对 HHLST 的高效并行稀疏 Tucker 分解算法进行了研究，其主要工作以及创新点如下：
（1）传统 Tucker 分解求解算法存在着高计算开销与高存储开销的问题。为了解决以上问题，本研究提出了 Tucker 分解的一种变体，命名为 FastTucker 分解。FastTucker 分解使用核矩阵的 R Kruskal 乘积来近似 Tucker 分解中的的核张量，减少了核张量的存储开销。基于此，
提出了基于 SGD 的 FastTucker 分解求解算法 FastTucker_SGD，相比基于 SGD 的 Tucker 分解求解算法 Tucker_SGD 减少了中间矩阵的规模，并将其计算复杂度从指数级降到了多项式级。本研究进一步在多 GPU 上基于 CUDA 平台实现了细粒度并行的高效稀疏 FastTucker 分解算法 cuFastTucker。
（2）cuFastTucker 算法仍存在着部分计算冗余，限制了其效率。本研究提出了一种新的基于 SGD 的 FastTucker 分解求解算法 FasterTucker_SGD，与 FastTucker_SGD 算法相比减少了可复用中间变量与可共享中间变量的冗余计算，同时减少了访存开销。本研究提出了基于 MU 的非负 FastTucker 分解求解算法 FasterNTucker_MU。本研究进一步在多 GPU 上给出了其算法实现 cuFasterTucker 与 cuFasterNTucker。cuFasterTucker 在全局内存中维护可复用中间变量并在计算过程中读取以避免实时对其进行计算，由于其访存开销小于实时计算的计算开销，使得 cuFasterTucker 的整体计算时间大幅度减少。另外，cuFasterTucker 使用均衡 CSF(Balanced-CSF, B-CSF) 张量存储格式并根据其特性对可共享中间变量进行合并计算进一步减少了冗余计算。cuFasterNTucker 能够在非负约束下快速收敛。
（3） FastTucker_SGD 算法和 FasterTucker_SGD 算法都是对整个 FastTucker 分解的非凸优化进行松弛，得到多个凸优化问题，并通过交替求解这些凸优化问题来实现整个优化问题的收敛。虽然交替求解凸优化问题保证了整个非凸优化问题的全局收敛，但在实际应用中表现出缓慢的收敛速度。现有研究表明，张量分解具有简单的优化景观，其局部最优解也是（近似）全局最优解。基于此，本研究提出一种局部搜索算法 FastTucker_SGD 来直接求解 FastTucker 分解的非凸优化问题，相比交替求解凸优化问题具有更快的收敛速度。本研究进一步给出了在多 GPU 上使用 Tensor Core 进行加速的算法实现 cuFastTuckerPlus。
（4）虽然 FastTuckerPlus_SGD 算法相比传统 Tucker 分解算法大幅度减少了中间变量的规模，但在处理高秩的 FastTucker 分解仍有着不可忽略的中间变量数量。这些中间变量会使 GPU 的并行性降低，限制了 cuFastTuckerPlus 算法的高效并行。另外，CP 分解相对 Tucker 分解具有更为简单的优化景观，使用局部搜索算法会有更快的收敛速度。基于此，本研究提出一种两级优化的求解 FastTucker 分解的方法 FastTuckerPro_SGD，使得能够处理具有更高秩要求的 FastTucker 分解。该方法首先对原始张量进行 CP 分解以求得中间矩阵，减少了中间变量的使用。
主要学术成果
Li Hao, Li Zixuan, Kenli Li, Jan S. Rellermeyer, Lydia Y. Chen, Li Keqin. SGD__Tucker: A Novel Stochastic Optimization Strategy for Parallel Sparse Tucker Decomposition[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(7): 1828-1841. (第二作者，IEEE汇刊，CCF A类期刊)
Li Zixuan, Li Hao, Li Kenli, Wu Fan, Lydia Y. Chen, Li Keqin. Locality Sensitive Hash Aggregated Nonlinear Neighborhood Matrix Factorization for Online Sparse Big Data Analysis[J]. ACM/IMS Transactions on Data Science (TDS), 2022, 2(4): 1-27. (第一作者，ACM汇刊)
Li Zixuan, Qin Yunchuan, Xiao Qi, Yang Wangdong, Li Kenli. cuFasterTucker: A Stochastic Optimization Strategy for Parallel Sparse FastTucker Decomposition on GPU Platform[J]. ACM Transactions on Parallel Computing. (已接收，第一作者，ACM汇刊)
Li Zixuan, Hu Yikun, Li Mengquan, Yang Wangdong, Li Kenli. cuFastTucker: A Novel Sparse FastTucker Decomposition For HHLST on Multi-GPUs. ACM Transactions on Parallel Computing. (第一作者，审稿中，ACM汇刊)
Li Zixuan, Duan Mingxing, Luo Huizhang, Yang Wangdong, Li Kenli, Li Keqin. cuFastTuckerPlus: A Stochastic Parallel Sparse FastTucker Decomposition Using GPU Tensor Cores. IEEE Transactions on Parallel and Distributed Systems. (第一作者，审稿中，IEEE汇刊，CCF A类期刊)
