ps-lite概述

概述

ps-lite旨在构建高可用分布式的机器学习应用。在ps-lite框架中，多个节点运行在多台物理机器上用于处理机器学习问题。通常会运行一个schedule节点和多个worker/server节点。、

ps-lite架构

• Worker：worker节点负责主要的工作，如读取数据，计算梯度等。它通过push和pull的方式和server节点进行通信。例如，worker节点push计算得到的梯度到server，或者从server节点pull最新的模型。
• Server：server节点用于维护和更新模型权重。每个server节点维护其中一部分模型信息。
• Scheduler：scheduler节点用于监听其他节点的存活状态。也可以用于发送控制命令道其它节点，并且收集其它节点的工作进度。

分布式优化

假设我们想要解决下面的问题：

其中(y_i,x_i)是样本集，w是权重。
我们想要通过minibatch随机梯度下降（SGD，其中batch大小是b）的方式来解决这个问题。在时间t时，该算法首先随机挑选b个样本，然后通过下面的公式更新权重w

我们给出两个例子来说明ps-lite实现分布式解决这一问题的基本思想。

异步SGD

在第一个例子中，我们将SGD扩展为异步SGD。我们让server节点来维护w，server k获取到w的第k个分片，标识为w_k。当从worker接收到梯度后，server k会更新它所维护的权重：

t = 0;
while (Received(&grad)) {
  w_k -= eta(t) * grad;
  t++;
}

方法返回server从任意worker节点接收的梯段，方法返回时间时的训练速率。
对于一个worker，每次它都会做四件事情：

Read(&X, &Y);  // 读取一个minibatch X 和 Y
Pull(&w);           // 从server pull当前的权重
ComputeGrad(X, Y, w, &grad);  // 计算梯度
Push(grad);    // push梯度到server

ps-lite会提供和方法，用于和存有正确部分数据的server进行通信。

异步SGD的语义和单机版本不同。因为单机版本worker之间没有通信，所以就可能导致当一个worker节点正在计算梯度时权重发生变化。换句话说，每个worker都可能正在使用过期的权重。下图展示了2个server节点和3个worker节点的通信过程：

同步SGD

同步SGD的语义与单机算法完全相同，该模式使用scheduler来管理数据的同步。

for (t = 0, t < num_iteration; ++t) {
  for (i = 0; i < num_worker; ++i) {
     IssueComputeGrad(i, t);
  }
  for (i = 0; i < num_server; ++i) {
     IssueUpdateWeight(i, t);
  }
  WaitAllFinished();
}

和发布命令给worker和server，这个过程中函数会一直等待，指定所有命令发布完成。
当worker接受到命令后，它会执行下面的函数：

ExecComputeGrad(i, t) {
   Read(&X, &Y);  // 读取 b / num_workers 个minibatch样本
   Pull(&w);           // 从server拉取最新的权重
   ComputeGrad(X, Y, w, &grad);  // 计算梯度
   Push(grad);       // push梯度到server
}

这个过程和异步SGD几乎一模一样，只是每次要处理b / num_workers个样本。
而server节点相对于异步SGD还要执行额外的一些步骤：

ExecUpdateWeight(i, t) {
   for (j = 0; j < num_workers; ++j) {
      Receive(&grad);
      aggregated_grad += grad;
   }
   w_i -= eta(t) * aggregated_grad;
}

选择哪种方式？

与单机算法相比，分布式算法增加了两个额外的开销，一是数据通信开销，即通过网络发送数据的开销；另一个是由于不完善的负载均衡和机器性能差异带来的同步开销。这两个开销可能会主宰大规模集群和TB级别数据的应用性能。

假设：

变量名称	变量含义
f	凸函数
n	样本数量
m	worker数量
b	minibatch大小
	最大延迟
Tcomm	一个minibatch的数据通信开销
Tsync	同步开销

权衡结果如下：

SGD	收敛放缓	额外开销
同步
异步

从中我们得到如下结论：

• minibatch大小决定了收敛速度和通信开销
• 最大允许延迟决定了收敛速度和同步开销。在同步SGD中，=0， 因此会有很大的同步开销。而在异步SGD中，使用了无穷大的来消除同步开销。在实际应用中，无穷大的一般不可能出现，但是我们也设置了一个的上限来花费一些同步开销来保证收敛速度。