面向大规模矩阵乘法的编码计算方案设计与实现.docx

面向大规模矩阵乘法的编码计算方案设计与实现 摘要：为了更好地使用编码计算提高分布式机器学习算法运行效率，需要对大规模矩阵乘法的编码计算方案性能开销进行充分的研究。该文考察了面向大规模矩阵乘法的编码计算方案的任务完成时间，同时也考虑了所有参与分布式计算的节点总的计算开销，给出了各个工作节点完成计算任务的时间，均匀分布场景下总的任务完成时间和集群机器总的计算时间的表达式，对比分析了3种编码方案的性能，并通过实验对比了不同情况对任务完成时间与计算节点总计算开销影响，提出了一个启发式算法，提供了不同编码计算方案的选择依据。 互联网的飞速发展和大数据处理框架的进步推动了大规模的机器学习部署，并促进了分布式机器学习算法在更多领域中的应用Tandon等上述研究都是通过提出编码方案来增加对掉队节点的鲁棒性，并未对各自编码方案的性能开销展开研究，本文重点考察了面向分布式机器学习的各编码计算方案的任务完成时间和机器计算总时间两类开销。本文定义了面向分布式机器学习的编码计算的两个性能指标：一是某个使用该编码方案的计算任务完成时间，即完成整个计算任务所需要的时间；二是整个计算任务的机器计算总时间，即整个分布式计算系统中所有工作节点对该计算任务进行计算的时间的总和。通过计算由n个工作节点组成的分布式系统中第i个完成计算任务的节点的密度函数，给出工作节点计算任务完成时间符合均匀分布场景下计算任务的完成时间和机器计算总时间的表达式；对比分析了这一场景下3种应用于矩阵乘法的编码方案的完成时间和机器计算总时间，并通过实验对比了指数分布场景下不同情况对任务完成时间与计算节点总计算开销影响，提供了计算方案选择的依据。1 分布式计算开销示例在机器学习算法中，我们经常要执行矩阵乘法的操作。我们考虑这样一个矩阵乘法问题：通过输入矩阵A和向量X计算出矩阵B=AX。由于工作节点的内存大小有限，矩阵A按列被分成3个大小相等的子矩阵，即A=[A图1所示的分布式计算系统由1个主节点和3个工作节点组成，每个工作节点分别预先存储子矩阵A图2所示的分布式计算系统由1个主节点和5个工作节点组成，使用（5,3)MDS编码将矩阵A分成的3个子矩阵编码为5个编码矩阵A假设图2中5个计算节点的完成时间分别为2,4,6,8,10 ms，主节点在接收到任意3个节点的计算结果后就立刻通知剩余的其他2个节点停止计算（根据MDS编码性质，任意3个节点的计算已足够得到矩阵B），所以任务完成时间T=6 ms，机器计算总时间C=2+4+6+6+6=24 ms。从上述结果可以看出，相较于未编码方案，虽然编码方案的任务完成时间减少了，但是机器计算总时间比未编码方案更高。2 模型建立在一个由1个主节点和n个工作节点组成的分布式计算系统中，由于每个工作节点内存有限，先将总的计算任务分成若干个大小相等的子任务，然后使用编码技术将这些子任务编码成n个大小相同的编码计算任务，发送给每个工作节点进行计算，主节点在接收到任意k个工作节点的计算结果后，即可计算出最终结果。我们通过以下两个性能指标评估一个编码方案的性能：任务完成时间（T）：从主节点将子任务分配给每个工作节点开始，直到主节点接收到足够多的工作节点提交的计算结果，能够完成整个计算任务所需要的时间；机器计算总时间（C）：整个分布式计算系统中所有工作节点对该计算任务进行计算的时间的总和。假设这n个工作节点的计算任务完成时间分别为t由于接收到k个工作节点的计算结果后，主节点即可计算出最终结果，任务完成时间T为主节点接收到第k个计算结果的时间，即X由于工作节点在进行计算任务时可能会由于各种原因导致计算速度相较于正常节点更慢或是更快，使得每个工作节点完成计算任务的时间可能会不同，每个工作节点计算任务的完成时间t微分可得X上面的密度十分直观，为了使X在分布式计算系统中，存在这样一种情形，工作节点的计算速度不仅仅会因为某些原因变慢，还会因为一些原因变快。例如系统中大多数的计算节点要同时执行若干计算任务，而当一些节点只执行更少的甚至只有一个计算任务时，计算速度会随之不断增加。假设工作节点在执行一个计算任务时，节点的计算完成时间最快为a，最慢为b，每个工作节点的完成时间在（a,b）上是等可能的，那么这些工作节点的计算完成时间在（a,b）上服从均匀分布。另外，由于b的取值可以无限大，而a的取值最小为一个大于0的值，为了便于实际计算，可以取大多数节点的完成时间为均匀分布的概率分布为求解该密度函数的期望为任务完成时间，即第i个计算任务的完成时间为机器计算总时间为3 3种编码方案性能的对比分析对于给定的任何一种编码策略，本文将完成一个计算任务所需等待的最小工作节点数定义为该编码策略的恢复阈值