分布式机器学习里的 数据并行 和 模型并行 各是什么意思？ - 知乎125被浏览3997分享邀请回答132 条评论分享收藏感谢收起86 条评论分享收藏感谢收起查看更多回答解决大规模机器学习的策略和原则
我的图书馆
解决大规模机器学习的策略和原则
本文内容源自Erix Xing教授16年初的文章[1]，尽管大规模机器学习的手段和方法在业界已经研究多年，也已经形成了不少工业界使用的手段和方法，但这篇文章真正系统地从机器学习算法的本质总结并归纳出如何解决这类问题的原则，并在相应的开源项目上给予工程实现，非常值得阅读和参考。解决大规模机器学习问题，系统框架需要在容易编程和性能，以及正确性之间取得平衡。传统基于Dataflow的框架如Hadoop/Spark，都是采用BSP，集群所有节点都需要等待执行最慢的完成后才能继续。一些基于图的方案，如GraphLab，则引入了新的问题，比如如何切分机器学习程序，计算调度，还有一致性模型。另一方面，机器学习任务抽象成图并不是很直接，把已有的算法移植到基于图的抽象上需要不少工作，而且，基于图的抽象有时还会导致程序不正确，或者陷入次优化。参数服务器是近年浮现出来的针对机器学习算法的良好抽象，然而单纯的参数服务器还缺乏从头打造机器学习算法的良好编程接口，还不能跟Hadoop/Spark这样的项目相提并论。绝大多数机器学习算法都可以归结为类似下面的最优化问题：其中优化目标L包含两部分，一个是损失函数f，用来描述数据如何适应模型，另一部份是一个结构诱导函数，主要用来引入领域知识来给参数施加限制或者惩罚因子。上面这个式子隐藏了解决机器学习问题面临的大数据挑战，比如一个典型的用于图像分类的卷积神经网络，包含数十亿乃至万亿的矩阵型模型参数，而损失函数则呈现出深度递归形式f=f1(f2(f3(...)+...)+...)用来学习类似人类视觉皮层的图像分层表示。图模型，特别是主题模型，经常从数十亿的文档中发现主题，比如从社交媒体中，为了捕捉丰富的语义信息，这也会有数以万亿的参数。把上面的最优化问题更进一步细化，就变成为找到优化目标L对应的模型参数A而迭代的表达式：A(t) = F(A(t ? 1), ?_L(A(t ? 1), x))t表示第几轮迭代。在训练中，计算程序反复迭代执行直到收敛条件或者其他停止条件满足。下一次迭代需要的模型参数A(t)从上一次的迭代参数A(t-1)和数据x中产生，用到2个函数：一个是更新函数?，其优化目标(或损失函数)为L，它利用A(t-1)和数据x产生中间结果，另一个是聚合函数F，它用于把中间结果和A(t-1)结合生成A(t)。大部分机器学习算法都可以简化成为这种结构，例如随机梯度下降，坐标下降，MCMC，变分等。看两个具体例子：第一个是Lasso。它的最优化表达式可写为：也可简化写成矩阵表达式采用坐标下降迭代收敛表达式：可进一步总结出更新函数?和聚合函数F：另一个例子是主题模型。它的最优化表达式可写为：它的参数推导通常借助于变分或者Gibbs取样。以后者为例：其中-=，+=代表自减，自增操作。更新函数?分为两阶段执行：1) 在所有文档的词上执行上述取样操作；2) 输出A(t)，形式暂略，聚合函数F形式为简单的识别函数(identify function)。以上两个例子，对于算法不熟悉的可能难以理解，这里仅列出大致的优化结果，其目的在于阐明机器学习算法的通用表达式。有了这些例子，我们为了就可以深入了解机器学习算法的特性，从而总结出执行大规模分布式程序时，跟传统分布式程序的区别。比如一个传统的MapReduce程序---排序，框架首先把数据x_1,x_2,...,x_n随机分发到M个Mapper，这些Mapper随后把元素哈希成为键值对(h(x_i),x_i)，其中h是order-preserving的，就是说如果x额外的复杂努力，来提供容错，比如基于磁盘的快照，并且跟任务调度结合起来，这里边的工程设计十分复杂。对于机器学习程序来说，需要对中间结果的错误更加健壮。如果一些参数在?函数执行时没有正确得出，也不妨碍整个程序的收敛性。例如SGD程序，不论深度学习，矩阵分解，还是逻辑回归，都会经常使用。在运行时，比如每次迭代后增加小的随机错误ε，这样A(t)=A(t)+ε，即便如此，收敛仍然能够保证，因为SGD总能向正确的方向更新参数(根据梯度)。机器学习算法的这种特性能够很大的影响分布式框架的设计——系统并不需要完美地确保所有任务无误运行，也无须确保机器之间通信正确，乃至从错误中恢复。当资源有限时(比如机器之间带宽有限)，简易容错设计能够让系统更简单和高效。这是大规模机器学习问题跟传统分布式问题的第一点重要区别。然而，另一方面，机器学习算法却比传统的MapReduce程序拥有更加复杂的结构依赖，而这些依赖并不能够从优化的目标函数L和更新函数?容易得出。例如在MapReduce排序中，Reducer等待Mapper结束，这种依赖是确定性的，而在Lasso中，似乎从前面更新函数?的表达式里能够得出容易并行的结论，然而实际并非如此，因为第j个模型参数A_j，它的更新实际上可能依赖所有其他A_k，不正确地并行执行可能会影响程序执行的正确性。上图中展示了数据并行和模型并行的区别。在机器学习中，这两种并行是互补的，同时也是非对称的，意思是：数据并行可以应用到任何对数据采样具备独立同分布假设的机器学习算法中，包含深度学习，Lasso，主题模型等。相比之下，模型并行需要仔细对待，因为模型参数A_j并不总是具备独立同分布假设，例如前边提到的Lasso。下面从更广义的角度来看两者：在数据并行中，数据x被划分到不同计算节点，如果更新函数?可以表达成对各节点计算结果的和，那么就可以应用数据并行。例如把Lasso改写为数据并行模式：在模型并行中，模型A被划分到不同计算节点后，还需要引入一个调度函数S，用来限制更新函数?只工作在模型参数的子集上，避免不同节点都来更新相同的参数。把Lasso以模型并行的方式改写：这里调度函数S_p,(t-1)对于节点p在每次迭代时只更新固定子集的参数。由于每个节点操作的模型参数都会依赖于其他节点的参数，并行更新参数会得出跟顺序更新不同的结果，这会导致更慢地收敛，因此对于调度器来说，不能浪费计算资源去试图并行执行相互依赖的任务，而应寻找到不依赖的子任务让它们并行运行。因此对于调度器来说，应当寻找到依赖成立的边界条件，再来看个在LDA中通过综合数据并行和模型并行实现大规模主题模型的例子：在图中，有3个计算节点并行的在每次迭代中只操作一个数据和参数的子集z_1，z_2，z_3，当完成后进行下一次迭代时，更换相应子集，以此类推，实现大规模并行主题模型。这是大规模机器学习问题和传统分布式问题的第二点重要区别。第三个重要区别是非均匀性收敛。MapReduce排序把数据分发到不同节点执行，各节点的任务和负载基本上是均衡的，然而对于机器学习问题来说，数十亿，甚至更多的参数能够以不同的迭代数目收敛，有的2-3轮迭代即可，有的则需要上百次。第四个重要特性在于紧凑更新。例如上面的Lasso和LDA，更新函数?只会涉及到一小部分模型参数，这是由数据的稀疏本质决定的。另一个例子是深度学习，模型参数A是矩阵，更新函数?可以只涉及小的向量结构。在设计大规模机器学习框架时考虑到这种紧凑更新的特性，可以大大减少存储，计算，以及网络的开销。因此为了能够让机器学习程序高效执行，需要做三件事情：1 决定如何更好的切分成多个任务，究竟采用数据并行，还是模型并行，或者混合方案。2 决定如何调度子任务。3 均衡各节点的负载。这些问题在传统MapReduce类任务框架里已经解决得很好，但对于机器学习算法来说则是挑战。调度器需要能够很好的判定模型参数依赖的边界条件，这是个算法相关的问题，例如Lasso和LDA的条件就不一样。在获取边界条件之后，需要通过调度来平衡节点负载，传统分布式任务的BSP肯定是无法胜任该工作，因为机器学习任务是一种有限异步(非完全异步)，完全同步等待就会造成大量浪费。在机器学习中，需要一种有限异步的同步原语，称为SSP，SSP的背景材料本号之前在参数服务器的介绍中已经提及，点击原文可以阅读参数服务器的背景材料。Eric Xing教授在其Petuum系统里完整地提出了解决分布式机器问题的框架，以参数服务器和并行，调度为核心，称之为SAP(Structure Aware Parallelization)，结构感知的并行计算。SAP提供类似MapReduce一样的简易编程抽象接口，所有机器学习程序只需要实现3个函数：1 schedule，用来确定更新的模型参数以及提供参数依赖检查2 push，用来执行?更新函数3 pull，用来执行F聚合函数其中，push和pull就是参数服务器的原语。根据文献[1]提到的证明，SAP基本上可以做到分布式机器学习算法的理想抽象，据此实现的算法，可以有甚至不止一个数量级的性能提升。在Petuum项目中，Strads调度器就实现了SAP抽象，并应用到若干典型算法，包含Lasso，矩阵分解，还有主题模型等。那么，Petuum框架和Strads调度器，应用于深度学习时，相比已有的方案有哪些特色呢？Petuum有一个集成Caffe的工作叫做Poseidon，利用SSP和数据并行，Poseidon可以在普通网络组成的GPU集群上实现大规模深度集群，而无须Infiniband和RDMA。更进一步的对比，尤其是和最新版支持分布式训练的Tensorflow，以及MXNet，本号将在接下来给出对比和分析。[1] Strategies and Principles of Distributed Machine Learning on Big DataEric P. Xing, Qirong Ho, Pengtao Xie, Wei Dai.arXiv: (2015)
馆藏&55468
TA的最新馆藏
喜欢该文的人也喜欢推荐｜阿里云：PAI分布式机器学习平台编程模型演进之路
文章来源：云栖社区 作者：场景研读
　　来自阿里云大数据事业部的九丰分享了《PAI分布式机器学习平台编程模型演进之路》。他主要介绍了在集团中使用机器学习解决大数据问题时如何通过编程模型的演进逐步解决业务上的痛点。其中，他只要分享了MapReduce、MPI、Parameter Server编程模型的演进过程。
　　以下内容根据大会视频整理而成。
　　什么是PAI？
　　PAI的全称是Platform of Artificial Intelligence，主要在使用机器学习做模型训练时提供整套链路。机器学习即服务，把机器学习作为服务对外推出，大家可以在平台上使用比较先进的机器学习算法。将多种深度学习框架集成到PAI中，同时基于深度学习框架包装成更加易用的组件。具备异构的计算服务能力，把CPU计算能力和GPU计算能力统一调度起来，异构的计算能力透明，大家的注意力是哪些机器学习算法可以帮助业务，不用关心底层资源的申请和分配。PAI也支持在线预测服务，模型一键发布。
　　大规模分布式机器学习的挑战
　　数据规模和特征会不断增加，这就会导致模型复杂度的增加，之前的模型已经不能够处理这么高的复杂度了。特征增加之后，模型变得越来越大，模型很难做到单机加载，所以在模型存储时需要做分片和切分。在常规的机器学习里面，更多的注意力放在理解业务的数据、特征，而现在的注意力会转移到模型本身，更多考虑怎么通过调整模型的结构达到更好的预测效果。
　　编程模型演进MapReduce编程模型
　　MapReduce核心的思想是分而治之，即把数据切分成很多块，每个节点处理其中的一小块。做分布式系统时会面临很多问题，比如希望计算任务可以在MapReduce框架层面做切分和调度。MapReduce从框架层面极大地降低了把任务迁移到分布式计算系统上的难度和门槛。对于数据的分布式存储和划分，数据可分散存储在几千台机器上，并且都有相应副本，不需要担心数据的丢失，底层的分布式存储会统一进行处理。计算任务的同步和计算节点的容错与恢复，若使用普通机器去搭大型计算群的时候，机器的宕机时比较普遍的现象，使用MapReduce则不需要关心这一点。右图是MapReduce的编程模型，最初是用来处理SQL等问题。
　　在机器学习里面，有些算法是基于MapReduce编程模型去实现的。TF-IDF用来评估文档里面单词是否能表示文档主题。首先计算文档里面单词出现的频率，把谓词和叹词去掉，关注真正有意义的词。IDF则是统计该词在所有文档里面出现的频率，将其和文档里出现的频率经过算法计算得出最终结果。这个过程如何通过MapReduce实现呢？在Mapper中迭代的去加载每一篇要训练的文章，在迭代过程中统计每个单词出现的频率。将统计结果放入Reducer中，进行计算，得到TF-IDF结果表。
　　MapReduce编程模型有两个特点：不同计算任务之间独立，每个Mapper和Reducer只会计算自己相关的数据，数据并行度高；适合不需要不同节点通信的机器学习算法。
　　MPI编程模型
　　逻辑回归算法是需要节点间进行通信的，该算法在个性化推荐中可以经常看到。个性化推荐算法是指每个人点击进来之后会进行分类，判断是否会对某些商品感兴趣，然后进行推荐。模型函数如上图中公式所示，定义损失函数，损失函数值越小说明模型拟合越好，寻找损失函数最小值的过程中用到了梯度下降算法。
　　早期，很多逻辑回归算法都是基于MPI编程模型实现的，MPI是消息传递接口，定义了Send，Receive，BC阿斯图，AllReduce接口，支持单机多Instance和多机多Instance，具有高度灵活，描述能力强，大量用于科学计算。
　　MPI使用时有很多限制，首先必须提前知道阶段任务在哪些计算节点上做。在大规模的计算集群里面，所有资源的分配都是动态的，在任务执行之前不知道任务会调度到哪些节点上，但是早期有很多算法需要基于MPI实现，所以对MPI底层做了网络拓扑的建立，做了大量的重构，帮助MPI相关程序能够基于分布式的调度系统调度起来。
　　逻辑回归的实现过程如上图所示。其中，有n个计算节点，首先会加载训练样本，计算梯度，然后本地加和，最后调用AllReduce接口去计算现在模型所在的位置。MPI本身还存在一些缺点：首先MPI中Worker的数目有上限，当需要更多节点的时候会发生性能下降。
　　参数服务器Parameter Server
　　Parameter Server和MPI相比，在更高的层次定义了编程模型和接口。Parameter Server中有三个角色，Server节点用来存储模型，计算节点会加载部分模型、训练数据，每轮迭代时每个节点会计算下个梯度，将节点和Server进行通信。Coordinator用来判断训练是否结束。此外，Parameter Server支持异步通信接口，不需要在不同计算节点间做同步。
　　阿里在2014年下半年，独立自研了PAI Parameter Server计算模型，已在集团内大规模使用。具体做的工作如上图所示。MPI的一个缺点是不支持容错，而每天上万台的集群会出现各种各样的故障，PAI Parameter Server针对大规模集群做了节点容错功能。Parameter Server集成很多算法，比如逻辑回归等。
　　深度学习
　　深度学习是人工神经网络的延伸，相比之下能够支持更深的网络。上图中，Alexnet是卷积神经网络，总共有8层网络，深度学习如果想要获得更好的效果，必须要构建一个更深的神经网络。随着神经网络变深，需要更多的参数，并且模型也会更加庞大。多级训练则需要更高量级的通信量。
　　TensorFlow
　　TensorFlow是谷歌第二代的深度学习框架，支持各种神经网络，具有高度的灵活性，丰富的社区生态，支持CNN、RNN、LSTM等网络。
　　上图中TensorFlow的例子是两层神经网络做图片的分类。上面通过API定义训练图片和测试数据，接着定义了模型（softmax多分类模型），定义损失函数通过交叉熵来做，最后选择优化函数找最优点。下面部分则是通过API把训练数据喂给模型再计算当前模型的准确率。从上例中，可以看出，API非常灵活，基于Python，所以非常方便。
　　PAI TensorFlow
　　将TensorFlow迁移到PAI上之后，将TensorFlow作业服务化，起TensorFlow作业的时候不需要去申请资源、做训练数据的迁移；分布式调度（包括单机和多机）只需提交模型训练Python文件；GPU卡映射；多种数据源，结构化数据和非结构化数据都支持；超参支持，训练模型时会调整学习率，通过超参把参数存进来就不需要每次都调整了；模型在线预测，训练好模型之后可以部署到在线预测服务上，调用API获知模型结果是否正面。
　　PAI Pluto（多机多卡Caffe）
　　Caffe早于TensorFlow，Caffe可以认为是第一代的深度学习框架，使用Caffe时需要通过配置文件配置深度学习的卷积神经网路。目前，很多关于图像的应用都是基于Caffe来做的，使用CNN的网络，比如身份证识别、驾照识别等。其缺点是单机，当训练样本多的时候训练时间非常长。将Caffe底层嫁接到OpenMPI通信框架上，可以支持多机Caffe，能够达到线性加速比。
　　前文提到了PAI上支持的各种编程模型，在公有云上希望把机器学习作为一个服务推出来，包括数据上传、数据清洗、特征工程、模型训练、模型评价。这样就可以在PAI上做一站式的模型训练和预测。
责任编辑：
声明：本文由入驻搜狐号的作者撰写，除搜狐官方账号外，观点仅代表作者本人，不代表搜狐立场。
今日搜狐热点Datartisan 数据工匠 | 数据时代，匠心独运
- 机器学习和统计模型的差异
/ 机器学习和统计模型的差异
机器学习和统计模型的差异
在各种各样的数据科学论坛上这样一个问题经常被问到&&机器学习和统计模型的差别是什么？
这确实是一个难以回答的问题。考虑到机器学习和统计模型解决问题的相似性，两者的区别似乎仅仅在于数据量和模型建立者的不同。这里有一张覆盖机器学习和统计模型的数据科学维恩图。
在这篇文章中，我将尽最大的努力来展示机器学习和统计模型的区别，同时也欢迎业界有经验的朋友对本文进行补充。
在我开始之前，让我们先明确使用这些工具背后的目标。无论采用哪种工具去分析问题，最终的目标都是从数据获得知识。两种方法都旨在通过分析数据的产生机制挖掘 背后隐藏的信息。
两种方法的分析目标是相同的。现在让我们详细的探究一下其定义及差异。
机器学习:一种不依赖于规则设计的数据学习算法。
统计模型：以数学方程形式表现变量之间关系的程式化表达
对于喜欢从实际应用中了解概念的人，上述表达也许并不明确。让我们看一个商务的案例。
让我们用麦肯锡发布的一个有趣案例来区分两个算法。
案例：分析理解电信公司一段时间内客户的流失水平。
可获得数据：两个驱动-A&B
麦肯锡接下来的展示足够让人兴奋。盯住下图来理解一下统计模型和机器学习算法的差别。
从上图中你观察到了什么？统计模型在分类问题中得到一个简单的分类线。 一条非线性的边界线区分了高风险人群和低风险人群。 但当我们看到通过机器学习产生的颜色时， 我们发现统计模型似乎没有办法和机器学习算法进行比较。 机器学习的方法获得了任何边界都无法详细表征的信息。这就是机器学习可以为你做的。
机器学习还被应用在YouTube 和Google的引擎推荐上， 机器学习通过瞬间分析大量的观测样本给出近乎完美的推荐建议。 即使只采用一个16 G 内存的笔记本，我每天处理数十万行的数千个参数的模型也不会超过30分钟。 然而一个统计模型需要在一台超级计算机跑一百万年来来观察数千个参数。
机器学习和统计模型的差异：
在给出了两种模型在输出上的差异后，让我们更深入的了解两种范式的差异，虽然它们所做的工作类似。
所属的学派
基于的假设
处理数据的类型
操作和对象的术语
使用的技术
预测效果和人力投入
以上提到的方面都能从每种程度上区分机器学习和统计模型，但并不能给出机器学习和统计模型的明确界限。
分属不同的学派
机器学习：计算机科学和人工智能的一个分支,通过数据学习构建分析系统，不依赖明确的构建规则。 统计模型：数学的分支用以发现变量之间相关关系从而预测输出。
诞生年代不同
统计模型的历史已经有几个世纪之久。但是机器学习却是最近才发展起来的。二十世纪90年代，稳定的数字化和廉价的计算使得数据科学家停止建立完整的模型而使用计算机进行模型建立。这催生了机器学习的发展。随着数据规模和复杂程度的不断提升，机器学习不断展现出巨大的发展潜力。
假设程度差异
统计模型基于一系列的假设。例如线性回归模型假设：
（1） 自变量和因变量线性相关 （2） 同方差 （3） 波动均值为0 （4） 观测样本相互独立 （5） 波动服从正态分布
Logistics回归同样拥有很多的假设。即使是非线性回归也要遵守一个连续的分割边界的假设。然而机器学习却从这些假设中脱身出来。机器学习最大的好处在于没有连续性分割边界的限制。同样我们也并不需要假设自变量或因变量的分布。
机器学习应用广泛。 在线学习工具可飞速处理数据。这些机器学习工具可学习数以亿计的观测样本，预测和学习同步进行。一些算法如随机森林和梯度助推在处理大数据时速度很快。机器学习处理数据的广度和深度很大。但统计模型一般应用在较小的数据量和较窄的数据属性上。
下面一些命名几乎指相同的东西：
虽然统计模型和机器学习的最终目标是相似的，但其公式化的结构却非常不同
在统计模型中，我们试图估计f 函数 通过
因变量（Y）=f(自变量)+ 扰动 函数
机器学习放弃采用函数f的形式，简化为：
输出（Y）&&& 输入（X）
它试图找到n维变量X的袋子，在袋子间Y的取值明显不同。
预测效果和人力投入
自然在事情发生前并不给出任何假设。 一个预测模型中越少的假设，越高的预测效率。机器学习命名的内在含义为减少人力投入。机器学习通过反复迭代学习发现隐藏在数据中的科学。由于机器学习作用在真实的数据上并不依赖于假设，预测效果是非常好的。统计模型是数学的加强，依赖于参数估计。它要求模型的建立者，提前知道或了解变量之间的关系。
虽然机器学习和统计模型看起来为预测模型的不同分支，但它们近乎相同。通过数十年的发展两种模型的差异性越来越小。模型之间相互渗透相互学习使得未来两种模型的界限更加模糊。
原文链接：
原文作者：TAVISH SRIVASTAVA
翻译： F.xy
由 Editor 于 2015 年 07 月 06 日 发布在最近在做文本处理知识的梳理，关注了CMU提出的GraphLab开源分布式计算系统
这是关于GraphLab的PPT：Distributed GraphLab『
这是CMU的Select实验室发布的一片相关论文：GraphLab A Distributed Framework forMachine Learning in the Cloud『
1.1 GraphLab简介
在海量数据盛行的今天，大规模并行计算已经随处可见，尤其是MapReduce框架的出现，促进了并行计算在互联网海量数据处理中的广泛应用。而针对海量数据的机器学习对并行计算的性能、开发复杂度等提出了新的挑战。
机器学习的算法具有下面两个特点：数据依赖性强，运算过程各个机器之间要进行频繁的数据交换；流处理复杂，整个处理过程需要多次迭代，数据的处理条件分支多。
而MapReduce是典型的SIMD模型，Map阶段集群的各台机器各自完成负载较重的计算过程，数据并行度高，适合完成类似矩阵运算、数据统计等数据独立性强的计算，而对于机器学习类算法并行性能不高。
另一个并行实现方案就是采用纯MPI（Native MPI）的方式。纯MPI实现通过精细的设计将并行任务按照MPI协议分配到集群机器上，并根据具体应用，在计算过程中进行机器间的数据通信和同步。纯MPI的优点是，可以针对具体的应用，进行深度优化，从而达到很高的并行性能。但纯MPI存在的问题是，针对不同的机器学习算法，需要重写其数据分配、通信等实现细节，代码重用率低，机器拓展性能差，对编程开发人员的要求高，而且优化和调试成本高。因而，纯MPI不适合敏捷的互联网应用。
为解决机器学习的流处理，Google提出了Pregel框架，Pregel是严格的BSP模型，采用&计算-通信-同步&的模式完成机器学习的数据同步和算法迭代。Goolge曾称其80%的程序使用MapReduce完成，20%的程序使用Pregel实现。因而，Pregel是很成熟的机器学习流处理框架，但Google一直没有将Pregel的具体实现开源，外界对Pregel的模仿实现在性能和稳定性方面都未能达到工业级应用的标准。
2010年，CMU的Select实验室提出了GraphLab框架，GraphLab是面向机器学习的流处理并行框架[1]。同年， GraphLab基于最初的并行概念实现了1.0版本，在机器学习的流处理并行性能方面得到很大的提升，并引起业界的广泛关注，在2012年GraphLab升级到2.1版本，进一步优化了其并行模型，尤其对自然图的并行性能得到显著改进。
在本章的余下章节，将详细介绍GraphLab的并行框架和具体的源码实现。
1.2 GraphLab并行框架
GraphLab将数据抽象成Graph结构，将算法的执行过程抽象成Gather、Apply、Scatter三个步骤。其并行的核心思想是对顶点的切分，以下面的例子作为一个说明。
图1. Graph对并行思想
示例中，需要完成对V0邻接顶点的求和计算，串行实现中，V0对其所有的邻接点进行遍历，累加求和。而GraphLab中，将顶点V0进行切分，将V0的边关系以及对应的邻接点部署在两台处理器上，各台机器上并行进行部分求和运算，然后通过master顶点和mirror顶点的通信完成最终的计算。
1.2.1 数据模型：GRAPH
顶点是其最小并行粒度和通信粒度，边是机器学习算法中数据依赖性的表现方式。
对于某个顶点，其被部署到多台机器，一台机器作为master顶点，其余机器上作为mirror。Master作为所有mirror的管理者，负责给mirror安排具体计算任务;mirror作为该顶点在各台机器上的代理执行者，与master数据的保持同步。
对于某条边，GraphLab将其唯一部署在某一台机器上，而对边关联的顶点进行多份存储，解了边数据量大的问题。
同一台机器上的所有edge和vertex构成local graph,在每台机器上，存在本地id到全局id的映射表。vertex是一个进程上所有线程共享的，在并行计算过程中，各个线程分摊进程中所有顶点的gather-&apply-&scatter操作。
下面这个例子说明，GraphLab是怎么构建Graph的。
图2 Graph的构建形式
1.2.2 执行模型：GATHER-APPLY-SCATTER
每个顶点每一轮迭代经过gather-&apple-&scatter三个阶段。
1)&&&&&& Gather阶段
工作顶点的边 (可能是所有边，也有可能是入边或者出边)从领接顶点和自身收集数据，记为gather_data_i，各个边的数据graphlab会求和，记为sum_data。这一阶段对工作顶点、边都是只读的。
2)&&&&&& Apply阶段
Mirror将gather计算的结果sum_data发送给master顶点，master进行汇总为total。Master利用total和上一步的顶点数据，按照业务需求进行进一步的计算，然后更新master的顶点数据，并同步mirror。Apply阶段中，工作顶点可修改，边不可修改。
3)&&&&&& Scatter阶段
工作顶点更新完成之后，更新边上的数据，并通知对其有依赖的邻结顶点更新状态。这scatter过程中，工作顶点只读，边上数据可写。
在执行模型中，graphlab通过控制三个阶段的读写权限来达到互斥的目的。在gather阶段只读，apply对顶点只写，scatter对边只写。并行计算的同步通过master和mirror来实现，mirror相当于每个顶点对外的一个接口人，将复杂的数据通信抽象成顶点的行为。
下面这个例子说明GraphLab的执行模型：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&图3. Gather-Apply-Scatter
1.3 GraphLab的源码实现
Graphlab的实现可以分为四层：基础组件层，抽象层，引擎层，应用层。
图4. GraphLab源码结构
1.3.1 基础组件层
提供Graphlab数据传输、多线程管理等基础并行结构的组件模块，下面将主要介绍其通信、数据序列化、数据交换、多线程管理四个功能模块。
1)&&&&&& 通信(dc_tcp_comm.cpp)
Graphlab基于TCP协议的长连接在机器之间进行数据通信。在Graphlab初始化阶段，所有机器建立连接，将socket数据存储在std::vector&socket_info& sock 结构中。
Graphlab使用单独的线程来接收和发送数据，其中接收或发送都可以配置多个线程，默认每个线程中负责与64台机器进行通信。在接收连接中，tcp_comm基于libevent采用epoll的方式获取连接到达的通知，效率高。将这部分抽象成以下伪代码：
listen（）；
for(size_t i = 0;i & ++i)
connect(i);
wait_for_connect（）;
in_thread_num=machine_num / proc_per_
out_thread_num= machine_num / proc_per_
for(每一个线程)
event_add（）；
for(每一个线程)
event_add（）；
for(每一个线程)
In_thread.launch(receive_loop);
for(每一个线程)
In_thread.launch(send_loop)
需要补充的是，Graphlab在数据通信中，并没有采用MPI的接口，但在源码中封装了MPI_tools，其用途是在distributed_control::init时，获取系统参数(包括机器IP和端口)提供两种方式，一种是系统配置中初始化，一种是通过MPI接口实现（dc_init_from_mpi::init_param_from_mpi）。
2)&&&&&& 数据序列化(oarchive & iarchive)
Oarchive通过重载操作符&&将对象序列化后写入ostream中，在Graphlab中对于POD(&Plain Old Data)和非POD数据区分对待， POD类型的数据直接转为为char*写入ostream, 而非POD数据需要用户实现save方法，否则将抛出异常。iarchive的过程与oarchive的过程相反。
所有通过rpc传输的数据都通过oarchive和iarchive转化为stream，比如vertex_program, vertex_data。
图5.&数据序列化
3)&&&&&& 数据传输流(buffered_stream_send2.cpp)
Oarchive，iarchive是数据序列化的工具， 在实际的传输过程中，数据并没有立即发送出去，而是缓存在buffered_stream_send。
4)&&&&&& Pthread_tools：
Thread类封装了lpthread的方法
提供thread_group管理线程队列
封装了锁、信号量、条件变量等同步方法。
1.3.2 抽象层
1)&&&&& dc_dist_object是GraphLab对所有分布式对象的一个抽象，其目标是将分布式处理的数据对象对用户抽象成普通对象，以希望在使用的时候不需要关心其分布式细节。
2)&&&&& buffer_exchange是基于dc_dist_object对需要在顶点间交换的数据提供一个容器。
3)&&&&& distribute_controller是基于dc_dist_object实现的一个整个分布式系统的控制器，提供了机器数据、顶点关系等全局信息。
1.3.3引擎层
1.3.3.1同步引擎
&&&&&&&&&&&&&&&&&&&&& &&&图6.&同步引擎
1) Excange message阶段，master接受来?自mirror的消息；
2) Receive Message阶段，master接收上一轮Scatter发送的消息和mirror发送的消息，将有message的master激活, 对于激活的顶点，master通知mirror激活，并将vectex_program同步到mirrors；
3) Gather阶段，多线程并行gather， 谁先完成，多线程并行localgraph中的顶点，mirror将gather的结果到master；
4) Apply阶段，master执行apply（apply()），并将apply的结果同步到mirror (sync_vertex_data()).
5）Scatter阶段，master和mirror基于新的顶点数据，更新边上数据，并以signal的形式通知相邻顶点。
下面这个例子形象地说明了同步引擎的工作过程：
图7.&顶点2的GraphLab执行过程
1.3.3.2异步引擎
图8. master和mirror状态转移过程
异步引擎中，每个顶点是消息驱动的状态机。
1) 在每一轮执行开始时，Master从全局的调度器(Sceduler)获取消息，获取消息后，master获得锁，并进入Locking状态。同时，master通知mirror获取锁，进入Locking状态。
2) master和mirror分别进行Gathering操作，mirror将gathering结果汇报给master，由master完成汇总。
3) master完成applying之后，将结果同步到mirror上。
4) master和mirror独立的执行scattering，执行完成之后释放锁进入None状态，等待新的任务到来。
5) mirror在scattering状态时，可能再次接收到来自master的locking请求，这种情况下，mirror在完成scattering之后将不会释放锁，而直接进入下一轮任务中。
阅读(...) 评论()}