Ho, Qirong, et al. "More effective distributed ml via a stale synchronous parallel parameter server." Advances in neural information processing systems. 2013.
Abstract
Stale Synchronous Parallel (SSP) model은 정확도를 보장하면서도 계산에 사용되는 시간의 비율을 늘림으로써 학습을 효율적으로 할 수 있도록 한다. 과거의 파라미터 버전을 사용하여 중앙 스토리지와 데이터 교환을 하지 않아도 된다. 다만 Stale 값의 수명에 제한을 둠으로써 정확도를 보장한다. 이 알고리즘은 완전한 동기식 알고리즘 또는 비동기식 알고리즘에 비해 빠른 학습을 보인다.
Introduction
딥러닝 모델의 Scability에는 두 가지의 요구 사항이 있다.
˙ 방대한 양의 데이터
˙ 방대한 모델의 사이즈
이를 해결하기 위해 분산딥러닝이 탄생하였다. 분산 딥러닝은 크게 두 가지의 방향으로 발전되고 있다.
˙ 단순한 분산 시스템을 사용하여 제한된 딥러닝 모델을 학습, 강력한 이론적 근거 제공
(e.g. Cyclic delay, Model pre-partitioning...)
˙ 이론적 근거는 부족하지만 high-throughput을 달성하도록 학습
(e.g. GraphLab, Spark...)
분산 딥러닝의 최종 목표는 다음과 같다
˙ 임의의 주어진 클러스터에서 작동되어야 하며, 최대한 모두 계산하는데 시간을 소요하도록 함
˙ 다양한 ML method 지원
˙ Correctness 보장
Parameter server는 중앙 집중식 key-value 스토리지 모델이다. 이는 데이터 Read/Update 동기화를 관리할 뿐만 아니라 공유 데이터에 대한 Read/Write 접근을 용이하게 한다.
본 연구에서는 Stale Synchronous Parallel (SSP) model로의 Parameter server를 제안한다. SSP 모델에서 각 Woker는 파라미터 $\theta$ 를 기반으로 업데이트 $\delta$ 를 계산한다.
$\theta \leftarrow \theta + \delta $
Worker가 파라미터 $\theta$ 를 $c$ iteration 마다 읽는다. $\theta$ 는 $0$ 부터 $c-s-1$ iteration까지 모든 업데이트가 반영된 파라미터이다.
$s \geq 0$ 는 Staleness thershold로 정의되고 Worker는 $0$ 부터 $c-s-1$ 까지의 파라미터 업데이트는 신뢰하고 계산한다. 이렇게 Bounded staleness를 설정함으로써 두 가지 효과를 불러올 수 있다.
˙ 다른 Worker를 기다릴 필요없이 계산에 집중할 수 있다.
˙ Parameter server와의 데이터 전달에 시간을 적게 사용한다.
SSP parameter server는 SSP table을 통해 구현한다. 많은 모델에 대해 다양한 DML 알고리즘을 지원할 수 있도록한다. SSP table에는 가능할 때마다 Worker의 캐시에서 데이터를 읽어오고 필요할 때에는 Parameter server에서 파라미터를 읽어온다. SSP table을 구현함으로써 성능을 높일 수 있지만 단일 머신에 맞지 않는 큰 모델을 지원한다. 추가적으로, 느린 Worker가 성능을 저하하는 'last reducer' 문제를 시스템 기반으로 솔루션을 제공한다.
이 연구에서는 SSP 모델을 BSP 모델, Async 업데이트 모델과 여러가지 알고리즘에 대해 비교하였다. 총 3개의 알고리즘 : Matrix Factorization, Topic Modeling, Lasso Regression에 실험을 진행하였다. 그 결과, BSP, Async 시스템보다 빠른 수렴을 보인다는 것을 보인다. 최종적으로, BSP와 Asnyc 시스템의 장단점을 조절한 'sweet spot' 에 이르렀다고 평가한다.
Stale Synchronous Parallel Model of Computation
여기서 clock이란 파라미터 업데이트의 단위이며, clock의 끝에서만 파라미터 업데이트를 commit한다. Staleness를 s로 하였을 때 다음과 같은 법칙을 따른다.
˙ 빠른 Worker와 느린 Worker는 s 이하의 간격을 갖는다.
˙ clock c에 commit이 이루어지면 업데이트 u는 타임스탬프를 c로 저장한다.
˙ Worker가 c 시점에 데이터를 읽으면, 그것은 타임스탬프 [0, c - s - 1]까지의 효과를 보는 것이다. c - s - 1 이상의 효과를 볼 수도 있다.
˙ Read-my-writes : Worker 자기 자신은 업데이트를 모두 볼 수 있다.
위 그림은 Staleness threshold가 3인 경우이다. Worker 1은 검은색으로 표현된 clock까지 모든 업데이트가 적용된 결과를 볼 수 있다. 추가로 초록색으로 표현된 read-my-writes, 자신의 업데이트도 볼 수 있다. 하지만 파란색으로 표현된 다른 Worker의 업데이트 내역을 보지 않는다.
SSPtable : an Efficient SSP System
SSPtable을 구현함으로써 ML 알고리즘의 수렴속도를 향상시킬 수 있다. SSPtable은 분산 클라이언트-서버 아키텍쳐를 따른다. 아래 그림처럼 Process cache와 Thread cache를 두어 스레드간 동기화를 줄임으로써 성능을 향상시킨다.
각 캐시는 데이터가 업데이트된 clock $r_{thread}$, $r_{proc}$를 저장하고 있다. $r_{thread} \geq c - s$이면 Thread cache에서 데이터를 읽는다. 그렇지 않으면 $r_{proc} \geq c - s$를 확인하고 Process cache에서 데이터를 읽는다. 모두 만족하지 않으면, 이제서야 Parameter server에 데이터를 요청하여 데이터를 받고 캐시들을 업데이트한다. (이때 $r_{thread}$와 $r_{proc}$도 업데이트한다.)
이러한 구현을 통해 느린 스레드가 s clock마다 Parameter server에 접근하게 제한한다. 빠른 스레드는 빠르게 Parameter server에서 데이터를 읽어올 수 있어 기다리지 않고 보다 계산에 집중할 수 있게 한다.
Theoretical Analysis of SSP
Worker p, Clock c에서 업데이트가 이루어지는 파라미터를 'noisy state'라고 하고 $\tilde{x}_{p, c}$라 표시한다. 위에서 도시한 $x \leftarrow x + u $에서 업데이트항을 3개로 세분화할 수 있다.
˙ 'pre-window' update : [0, c - s - 1]에서 모든 Worker의 업데이트
˙ 'read-my-writes' update : [c - s, c - s -1]에서 Worker 자기 자신의 업데이트
˙ 'in-window' update : $S_{p, c}$내의 업데이트, Worker 자기 자신을 제외한 [c - s, c + s - 1]의 업데이트를 의미한다. SSP에서 이를 최대한 많이 전달하여 반영하게 하는 것이 중요하다. Staleness s = 0 이면 BSP 모델과 같다.
수렴성을 증명하는 방법으로 'true' sequence를 정의한다. 이는 아래 식과 같고, $t \, mod \, P $로 묶은 다음 $\llcorner t/P \lrcorner$위에 있는 것을 더한 것으로 생각할 수 있다.
$$x_t = x_0 + \sum_{t'0}^{t}{u_{t'}}, \,\,\,\,\,\, where \,\, u_t = u_{t mod P, \, \llcorner t/P \lrcorner} $$
Staleness가 1 이상일 때, 'noisy state'은 다음과 같이 나타낼 수 있다.
$A$는 고려되지 않은 업데이트의 집합이고, $B$는 추가로 더 고려된 업데이트의 집합이다. 이는 다음과 같은 조건을 가진다.
$$|A_t| + |B_t| \leq 2s(P-1)$$
$$min(A_t \cup B_t) \geq max(1, t-(s+1)P)$$
$$max(A_t \cup B_t) \leq t + sP$$
이는 true state와 noisy state의 차이는 최대 $2s(P-1)$만큼 떨어져있다는 것을 의미한다.
위의 Boundary 조건을 이용하여 convex function $f_t(x)$의 minimizer를 찾는 문제의 Boundary를 정할 수 있다. (자세한 증명 방식은 논문 참고)
F와 L은 고정 상수이며, T가 증가함에 따라 수렴한다는 것을 알 수 있다. T가 무한대로 갈 수록 true state의 loss function과 noisy state의 loss function이 같아진다.
Experiments
여기서는 BSP와 완전 비동기식 알고리즘에 비해 SSP 모델이 좋은 성능이라는 것을 보인다. LDA Top Modeling, Matrix Factorization, Lasso Regression 딥러닝 모델에 대해 실험을 진행했다.
3개의 ML 알고리즘에서 SSP는 나머지 알고리즘에 비해 훨씬 빠르게 수렴하는 것을 볼 수 있다. 이러한 차이는 머신 수가 많을수록, Data batch가 작을 수록 커진다. 그 이유는 Staleness가 Network communication을 줄여주기 때문이다.
Topic Modeling 문제에서 Compute Time은 Staleness에 따라 거의 똑같다. 하지만, Network waiting time은 Staleness가 증가함에 따라 급격히 감소하는 것을 볼 수 있다. 이를 통해 SSP는 Network 통신 시간에 사용되는 시간을 효과적으로 줄여준다는 것을 알 수 있다.
위에 그림에서 추가로 Iteration Quantity를 측정하였는데, 이는 시간에 따라 실행된 Clock의 수를 의미한다. 예상한대로 Staleness가 클수록 많이 실행되어 빠르게 업데이트가 이루어지는 것을 볼 수 있다. 하지만 Quality 입장에서는 실행된 clock에 비해서는 수렴이 빠르게 이루어지지 않는 것을 볼 수 있다. 위의 수학적 증명에서 s가 커질수록 boundary가 커져 수렴이 늦게 이루어지기 때문이다.
Iteration Quantity와 Quality는 Staleness에 따른 Trade off가 존재한다. 따라서, 이 두개를 고려한 적당한 Staleness를 설정해야하고 이를 'sweet spot'이라 한다.
Related Work and Discussion
학계에서는 중앙서버와의 통신 시간을 줄이기 위해 Cyclic-delay 아키텍쳐를 연구한적이 있다. 본 연구는 고정된 옛날 데이터가 아닌 어느정도의 허용된 범위 안의 데이터를 계산에 활용한다는 점에서 다르다. 또한, 캐시를 이용하여 처리량을 높였다는 것을 강조했다.
Hadoop, GraphLab과 같은 분산 플랫폼에 비해 SSPtable은 table/matrix 기반의 프로그래밍 모델 API를 제공하여 쉽게 분산 버전의 ML 알고리즘을 구현할 수 있다. BSP는 SSP의 특수한 경우로 생각할 수 있으므로 보다 여러 분산 알고리즘에서 일반성있게 동작한다.
분산 딥러닝에서는 Consistency에 대한 중요한 논의가 이루어진다. TACT 모델 연구의 경우 Numerical error, Order error, Staleness 3가지 관점에서 이를 논의하였다. SSPtable의 vector clock은 Lamport clock에서 영감을 얻었으며, Clock을 통해 데이터를 최신성을 탐색한다는 점에서 다르다.
