![](https://csdnimg.cn/release/download_crawler_static/16834384/bg4.jpg)
Algorithm 1 Distributed Subgradient Descent
Solving (1) in the Parameter Server
Worker r = 1, . . . , m:
1: Load a part of training data {y
i
k
, x
i
k
}
n
r
k=1
2: Pull the working set w
(0)
r
from servers
3: for t = 1 to T do
4: Gradient g
(t)
r
←
P
n
r
k=1
∂`(x
i
k
, y
i
k
, w
(t)
r
)
5: Push g
(t)
r
to servers
6: Pull w
(t+1)
r
from servers
7: end for
Servers:
1: for t = 1 to T do
2: Aggregate g
(t)
←
P
m
r=1
g
(t)
r
3: w
(t+1)
← w
(t)
− η
g
(t)
+ ∂h(w
(t)
4: end for
worker 1
g
1
+...
+g
m
w
servers
g
1
w
1
g
m
w
m
worker m
...
2. push
training
data
4. pull
4. pull
2. push
3. update
1. compute
1. compute
Figure 2: One iteration of Algorithm 1. Each
worker only caches the working set of w.
3 Two Relaxations of Data Consistency
We now introduce the two relaxations that are key to the proposed system. We encourage the reader
interested in systems details such as server key layout, elastic scalability, and continuous fault toler-
ance, to see our prior work [4].
3.1 Asynchronous Task Dependency
We decompose the workloads in the parameter server into tasks that are issued by a caller to a remote
callee. There is considerable flexibility in terms of what constitutes a task: for instance, a task can be
a push or a pull that a worker issues to servers, or a user-defined function that the scheduler issues
to any node, such as an iteration in the distributed subgradient algorithm. Tasks can also contains
subtasks. For example, a worker performs one push and one pull per iteration in Algorithm 1.
Tasks are executed asynchronously: the caller can perform further computation immediately after
issuing a task. The caller marks a task as finished only once it receives the callee’s reply. A reply
could be the function return of a user-defined function, the (key,value) pairs requested by the pull,
or an empty acknowledgement. The callee marks a task as finished only if the call of the task is
returned and all subtasks issued by this call are finished.
iter 10:
iter 11:
iter 12:
gradient
gradient
gradient
push & pull
push & pull
pu
By default callees execute tasks in parallel for best
performance. A caller wishing to render task execu-
tion sequential can insert an execute-after-finished
dependency between tasks. The diagram on the
right illustrates the execution of three tasks. Tasks
10 and 11 are independent, but 12 depends on 11. The callee therefore begins task 11 immediately
after the gradients are computed in task 10. Task 12, however, is postponed to after pull of 11.
Task dependencies aid implementing algorithm logic. For example, the aggregation logic at servers
in Algorithm 1 can be implemented by having the updating task depend on the push tasks of all
workers. In this way, the weight w is updated only after all worker gradients have been aggregated.
3.2 Flexible Consistency Models via Task Dependency Graphs
The dependency graph introduced above can be used to relax consistency requirements. Independent
tasks improve the system efficiency by parallelizing the usage of CPU, disk and network bandwidth.
However, this may lead to data inconsistency between nodes. In the diagram above, the worker r
starts iteration 11 before the updated model w
(11)
r
is pulled back, thus it uses the outdated model
w
(10)
r
and compute the same gradient as it did in iteration 10, namely g
(11)
r
= g
(10)
r
. This inconsis-
4