一种地理分布式机器学习参数服务器放置方法

摘要

本发明公开了一种地理分布式机器学习参数服务器放置方法，针对地理分布式机器学习(Geo‑DML)中的通信瓶颈问题，本发明通过聚类，根据物理距离和链路带宽将地理上分散在广域网拓扑中的工作节点划分为不同的簇(Cluster)。然后在各个簇中选取合适的节点作为该簇参数聚合的本地参数服务器(LPS,Local Parameter Server)，再选取合适的节点作为全局参数聚合的全局参数服务器(GPS,Global Parameter Server)，以减小通信开销。

权利要求

1.一种地理分布式机器学习参数服务器放置方法，其特征在于，包括以下步骤：S1、根据链路物理长度和链路带宽，将地理上分散在广域网拓扑中的工作节点划分为不同的簇；

步骤S1包括以下分步骤：

S11、根据链路物理长度和链路带宽，计算地理上分散在广域网拓扑中每条链路的权重；

S12、根据每条链路的权重构建的权重集合，计算任意两个工作节点间的最短路径；

S13、将每个工作节点初始化为一个簇；

S14、根据任意两个工作节点间的最短路径，将距离最近的两个簇合并为一个簇；

S15、重复步骤S14，直到距离最近的两个簇之间的距离大于设定阈值，簇划分完成；

S2、判断当前簇的数量是否为1，若是，则跳转至步骤S3，若否，则跳转至步骤S4；

S3、对唯一簇进行本地参数服务器和全局参数服务器的放置；

步骤S3包括以下分步骤：

S31、遍历唯一簇中每个工作节点，计算每个工作节点和剩余工作节点的平均距离；

S32、选取唯一簇中平均距离最小的工作节点作为唯一簇的本地参数服务器和全局参数服务器，实现对唯一簇的本地参数服务器和全局参数服务器的放置；

S4、对所有簇进行本地参数服务器和全局参数服务器的放置；

步骤S4包括以下分步骤：

S41、遍历所有簇中每个工作节点，计算每个簇中每个工作节点和剩余工作节点的平均距离，选取每个簇中平均距离最小的工作节点作为该簇的本地参数服务器；

S42、遍历广域网拓扑中的每个工作节点，计算每个工作节点与所有本地参数服务器的平均距离；

S43、选取广域网拓扑中平均距离最小的工作节点作为广域网拓扑的全局参数服务器，并将该工作节点移除所在簇，实现对所有簇的本地参数服务器和全局参数服务器的放置。

2.根据权利要求1所述的地理分布式机器学习参数服务器放置方法，其特征在于，所述步骤S11中计算地理上分散在广域网拓扑中每条链路的权重的公式为：其中，we为链路e的权重，de为链路e的物理距离，β1为第一权重参数，β2为第二权重参数，d为包含所有链路物理长度的向量，B为包含所有链路带宽的向量，|| ||∞为向量中最大的绝对值，min()为向量中最小分量的值，Be为链路e的带宽。

3.根据权利要求1所述的地理分布式机器学习参数服务器放置方法，其特征在于，所述步骤S14包括以下分步骤：

S141、根据任意两个工作节点间的最短路径，计算每个簇与剩余簇的簇距离；

S142、将最小的簇距离对应的两个簇合并为一个簇。

4.根据权利要求3所述的地理分布式机器学习参数服务器放置方法，其特征在于，所述步骤S141中簇距离为：最小距离、最大距离或平均距离；

所述最小距离的计算公式为：

所述最大距离的计算公式为：

所述平均距离的计算公式为：

其中，Ci为第i个簇，Cj为第j个簇，dist(u，v)为任意工作节点u和v间的距离，为取任意两个簇i，j中任意两工作节点u，v距离的最小值，Distmin(i，j)为第i个簇与第j个簇中工作节点的最小距离， 为取任意两个簇i，j中任意两工作节点u，v距离的最大值，Distmax(i，j)为第i个簇与第j个簇中工作节点的最大距离，|Ci|为第i个簇中的工作节点数，|Cj|为第j个簇中的工作节点数，Distavg(i，j)为第i个簇与第j个簇中工作节点的平均距离，α1为第三权重参数，α2为第四权重参数，pdist(u，v)为任意两个工作节点间的最短路径的物理距离，|| ||∞为向量中最大的绝对值，min()为向量中最小分量的值，Bw(u，v)为节点u到节点v的最短路径所经过的链路中带宽最小的链路带宽，pdist为包含所有工作节点间物理距离的向量，Bw为包含所有节点间最短路径中最小链路带宽的向量。

说明书

一种地理分布式机器学习参数服务器放置方法

技术领域

[0001] 本发明涉及通信领域，具体涉及一种地理分布式机器学习参数服务器放置方法。

背景技术

[0002] 由于数据量和模型规模的不断扩大，传统机器学习无法满足应用需求，于是分布式机器学习成为主流。而近年来一种用于训练全球数据的地理分布式机器学习(Geo‑DML,
Geo‑Distributed Machine Learning)逐渐兴起。Geo‑DML是近年来兴起的可以训练全球数
据的系统。一些大型网络服务提供商(如谷歌、亚马逊、微软等)为了给全球的用户提供高质
量低延迟的服务，在全球各地运营着数十个数据中心，并收集了大量的全球用户数据，比如
谷歌在世界各地拥有36个数据中心和1500多个边缘服务器集群。这为地理分布式机器学习
提供了物质基础。

[0003] 但由于数据中心是地理分布的，它们之间的通信协作需要通过广域网(WAN)链路实现，而数据中心内部的通信是通过局域网(LAN)实现的。在完成多机协作的过程中，数据
中心间的通信必不可少，但是在大型训练中要传输的数据量很多，花在通信上的时间占比
很高就有可能抵消由数据并行节约的时间。在Geo‑DML的场景下，广域网的带宽资源又更加
稀缺，这加剧了在分布式机器学习中员原本就存在的通信代价过高的问题。

[0004] 如何降低通信代价已经成为了分布式机器学习领域一个被广泛研究的课题。目前已经有异步随机梯度下降、模型的压缩和稀疏化、梯度的量化和稀疏化等方法，都可以有效
缓解分布式机器学习通信瓶颈。而数据中心的划分、数据中心内部本地参数服务器的位置、
全局的参数服务器在整体拓扑的位置对于通信成本都有一定影响，好的数据中心的划分和
参数服务器选址可以在一定程度上降低通信代价。

发明内容

[0005] 针对现有技术中的上述不足，本发明提供的一种地理分布式机器学习参数服务器放置方法解决了如何有效降低通信开销的问题。

[0006] 为了达到上述发明目的，本发明采用的技术方案为：一种地理分布式机器学习参数服务器放置方法，包括以下步骤：

[0007] S1、根据链路物理长度和链路带宽，将地理上分散在广域网拓扑中的工作节点划分为不同的簇；

[0008] S2、判断当前簇的数量是否为1，若是，则跳转至步骤S3，若否，则跳转至步骤S4；

[0009] S3、对唯一簇进行本地参数服务器和全局参数服务器的放置；

[0010] S4、对所有簇进行本地参数服务器和全局参数服务器的放置。

[0011] 进一步地，步骤S1包括以下分步骤：

[0012] S11、根据链路物理长度和链路带宽，计算地理上分散在广域网拓扑中每条链路的权重；

[0013] S12、根据每条链路的权重构建的权重集合，计算任意两个工作节点间的最短路径；

[0014] S13、将每个工作节点初始化为一个簇；

[0015] S14、根据任意两个工作节点间的最短路径，将距离最近的两个簇合并为一个簇；

[0016] S15、重复步骤S14，直到距离最近的两个簇之间的距离大于设定阈值，簇划分完成。

[0017] 进一步地，步骤S11中计算地理上分散在广域网拓扑中每条链路的权重的公式为：

[0018]

[0019] 其中，we为链路e的权重，de为链路e的物理距离，β1为第一权重参数，β2为第二权重参数，d为包含所有链路物理长度的向量，B为包含所有链路带宽的向量，|| ||∞为向量中最
大的绝对值，min()为向量中最小分量的值，Be为链路e的带宽。

[0020] 进一步地，步骤S14包括以下分步骤：

[0021] S141、根据任意两个工作节点间的最短路径，计算每个簇与剩余簇的簇距离；

[0022] S142、将最小的簇距离对应的两个簇合并为一个簇。

[0023] 进一步地，步骤S141中簇距离为：最小距离、最大距离或平均距离；

[0024] 所述最小距离的计算公式为：

[0025] 所述最大距离的计算公式为：

[0026] 所述平均距离的计算公式为：

[0027]

[0028] 其中，Ci为第i个簇，Cj为第j个簇，dist(u，v)为任意工作节点u和v间的距离，为取任意两个簇i，j中任意两工作节点u，v距离的最小值，Distmin
(i，j)为第i个簇与第j个簇中工作节点的最小距离， 为取任意两
个簇i，j中任意两工作节点u，v距离的最大值，Distmax(i，j)为第i个簇与第j个簇中工作节
点的最大距离，|Ci|为第i个簇中的工作节点数，|Cj|为第j个簇中的工作节点数，Distavg(i，
j)为第i个簇与第j个簇中工作节点的平均距离，α1为第三权重参数，α2为第四权重参数，
pdist(u，v)为任意两个工作节点间的最短路径的物理距离，|| ||∞为向量中最大的绝对
值，min()为向量中最小分量的值，Bw(u，v)为节点u到节点v的最短路径所经过的链路中带
宽最小的链路带宽，pdist为包含所有工作节点间物理距离的向量，Bw为包含所有节点间最
短路径中最小链路带宽的向量。

[0029] 进一步地，步骤S3包括以下分步骤：

[0030] S31、遍历唯一簇中每个工作节点，计算每个工作节点和剩余工作节点的平均距离；

[0031] S32、选取唯一簇中平均距离最小的工作节点作为唯一簇的本地参数服务器和全局参数服务器，实现对唯一簇的本地参数服务器和全局参数服务器的放置。

[0032] 进一步地，步骤S4包括以下分步骤：

[0033] S41、遍历所有簇中每个工作节点，计算每个簇中每个工作节点和剩余工作节点的平均距离，选取每个簇中平均距离最小的工作节点作为该簇的本地参数服务器；

[0034] S42、遍历广域网拓扑中的每个工作节点，计算每个工作节点与所有本地参数服务器的平均距离；

[0035] S43、选取广域网拓扑中平均距离最小的工作节点作为广域网拓扑的全局参数服务器，并将该工作节点移除所在簇，实现对所有簇的本地参数服务器和全局参数服务器的
放置。

[0036] 综上，本发明的有益效果为：

[0037] (1)、针对地理分布式机器学习(Geo‑DML)中的通信瓶颈问题，本发明提出了一种新的解决思路，即通过聚类，根据物理距离和链路带宽将地理上分散在广域网拓扑中的工
作节点划分为不同的簇(Cluster)。然后在各个簇中选取合适的节点作为该簇参数聚合的
本地参数服务器(LPS，Local Parameter Server)，再选取合适的节点作为全局参数聚合的
全局参数服务器(GPS,Global Parameter Server)，以减小通信开销。

[0038] (2)本发明综合考虑了链路的物理距离和带宽，保证在同一簇中的节点距离不会太远，并且保证LPS到本地节点距离以及GPS到各LPS的距离比较平衡，不会出现因为其中一
个节点的距离太远通信时间太长拖慢整个训练进度的情况，可以在全局拓扑中合理地划分
簇，并找到最适合放置本地参数服务器LPS和全局参数服务器GPS的位置，而合理的簇划分
和参数服务器位置可以让每次参数同步的通信时延最小化，有效降低通信成本。

附图说明

[0039] 图1为一种地理分布式机器学习参数服务器放置方法的流程图；

[0040] 图2为地理分布式机器学习(Geo‑DML)的结构示意图。

具体实施方式

[0041] 下面对本发明的具体实施方式进行描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，
只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易
见的，一切利用本发明构思的发明创造均在保护之列。

[0042] 如图1～2所示，一种地理分布式机器学习参数服务器放置方法，包括以下步骤：

[0043] S1、根据链路物理长度和链路带宽，将地理上分散在广域网拓扑中的工作节点划分为不同的簇；

[0044] 步骤S1包括以下分步骤：

[0045] S11、根据链路物理长度和链路带宽，计算地理上分散在广域网拓扑中每条链路的权重；

[0046] 步骤S11中计算地理上分散在广域网拓扑中每条链路的权重的公式为：

[0047]

[0048] 其中，we为链路e的权重，de为链路e的物理距离，β1为第一权重参数，β2为第二权重参数，d为包含所有链路物理长度的向量，B为包含所有链路带宽的向量，|| ||∞为向量中最
大的绝对值，min()为向量中最小分量的值，Be为链路e的带宽。

[0049] S12、根据每条链路的权重构建的权重集合，计算任意两个工作节点间的最短路径；

[0050] S13、将每个工作节点初始化为一个簇；

[0051] S14、根据任意两个工作节点间的最短路径，将距离最近的两个簇合并为一个簇；

[0052] 步骤S14包括以下分步骤：

[0053] S141、根据任意两个工作节点间的最短路径，计算每个簇与剩余簇的簇距离；

[0054] 步骤S141中簇距离为：最小距离、最大距离或平均距离；

[0055] 所述最小距离的计算公式为：

[0056] 所述最大距离的计算公式为：

[0057] 所述平均距离的计算公式为：

[0058]

[0059] 其中，Ci为第i个簇，Cj为第j个簇，dist(u，v)为任意工作节点u和v间的距离，为取任意两个簇i，j中任意两工作节点u，v距离的最小值，Distmin
(i，j)为第i个簇与第j个簇中工作节点的最小距离， 为取任意两
个簇i，j中任意两工作节点u，v距离的最大值，Distmax(i，j)为第i个簇与第j个簇中工作节
点的最大距离，|Ci|为第i个簇中的工作节点数，|Cj|为第j个簇中的工作节点数，Distavg(i，
j)为第i个簇与第j个簇中工作节点的平均距离，α1为第三权重参数，α2为第四权重参数，
pdist(u，v)为任意两个工作节点间的最短路径的物理距离，|| ||∞为向量中最大的绝对
值，min()为向量中最小分量的值，Bw(u，v)为节点u到节点v的最短路径所经过的链路中带
宽最小的链路带宽，pdist为包含所有工作节点间物理距离的向量，Bw为包含所有节点间最
短路径中最小链路带宽的向量。

[0060] S142、将最小的簇距离对应的两个簇合并为一个簇。

[0061] S15、重复步骤S14，直到距离最近的两个簇之间的距离大于设定阈值，簇划分完成。

[0062] S2、判断当前簇的数量是否为1，若是，则跳转至步骤S3，若否，则跳转至步骤S4；

[0063] S3、对唯一簇进行本地参数服务器和全局参数服务器的放置；

[0064] 步骤S3包括以下分步骤：

[0065] S31、遍历唯一簇中每个工作节点，计算每个工作节点和剩余工作节点的平均距离，其计算公式为上式(4)；

[0066] S32、选取唯一簇中平均距离最小的工作节点作为唯一簇的本地参数服务器和全局参数服务器，实现对唯一簇的本地参数服务器和全局参数服务器的放置。

[0067] S4、对所有簇进行本地参数服务器和全局参数服务器的放置。

[0068] 步骤S4包括以下分步骤：

[0069] S41、遍历所有簇中每个工作节点，计算每个簇中每个工作节点和剩余工作节点的平均距离，选取每个簇中平均距离最小的工作节点作为该簇的本地参数服务器；

[0070] S42、遍历广域网拓扑中的每个工作节点，计算每个工作节点与所有本地参数服务器的平均距离；

[0071] S43、选取广域网拓扑中平均距离最小的工作节点作为广域网拓扑的全局参数服务器，并将该工作节点移除所在簇，实现对所有簇的本地参数服务器和全局参数服务器的
放置。