一种缓解矩阵分解并行算法负载不均衡问题的新方法

摘要

现有的并行矩阵分解算法通常采用对矩阵分块的方法,将互不冲突的分块并行地计算.负载不均衡是同步并行算法中常见的问题——各分块中评分数量差异较大,导致线程阻塞和空等待,降低并行效率.本文提出一种"均衡分块"的方法,通过分别调整行块、列块尺寸均衡评分数的分布,达到方体块评分均衡的目标.以块评分数方差衡量"均衡",从理论上分析和证明了均衡分块的可行性;将均衡分块应用于DSGD和CCD++等并行矩阵分解算法,通过大规模分布式实验,验证了该方法能大大提升并行性能."均衡分块"作为一种普适的负载均衡思想,适用于基于矩阵分块、同步的矩阵分解并行算法,具备广泛的应用价值.