Semi-Dynamic Load Balancing: Efficient Distributed Learning in Non-Dedicated Environments

먼저 간단히 논문의 개요를 살펴보자면, 요즘 머신러닝은 이기종 리소스를 보유한 전담 작업자가 아니라, 클러스터에서 더많이 훈련이 됩니다. 이떄, 다른워커보다 훨씬 느리게 실행되는 스트래글러는 부정적인 영향을 미칩니다. (오른쪽 그림, 빨간색 화살표) 여기서 스트래글러가 의미하는것은 적은수의 스레드가 주어진 반족을 실행하는데 다른 스레드보다 오래걸릴떄 발생하는 문제를 의미합니다. 모든 스레드는 동기화되어야해서 모든 스레드는 가장 느린 스레드(스트래글러)의 속도로 진행할수밖에 없기 때문입니다. 이 논문의 핵심은 이 샘플 배치의 크기를 적절하게 조정해서 작업자의 부하를 즉각적인 처리기능에 맞게 조정하는것입니다.

이 논문에서는 ML 워크로드의 스트래글러를 제거하기 위해 SEMI Dynamic Load balancing이라는 새로운 방법을 제안합니다. 그리고 이방법을 이용해서 LP_BSP를 구현합니다. 여기서 BSP란 병렬 소프트웨어와 하드웨어 개발의 기준이 되는 모델로 PRAM 모델의 일종입니다.

**Pram ⇒ 공유 메모리르를 사용해서 프로세스간에 병렬 통신을 지원하는 구조입니다.

이 체계에서 빠른 작업자는 각 iteraiton이 끝날때마다 느린 작업자(스트래글러)를 기다려야함으로 스트래글러는 모델의 학습 효율성을 저하시킵니다. 이 기존의 BSP모델의 단점을 보완한것이 LP-BSP 모델입니다.

들어가기 앞서서 이 논문에서 자주 쓰이는 개념들에 대해 간단히 짚고 넘어갑니다. 클러스터는 다음과 같이 두가지 종류로 나뉘는데, 전자의 경우, 전용 클러스터라고 불리며 후자의 경우 비전용 클러스터라고 합니다.

전자는 높은 효율성을 보이지만, 유지관리 비용이 많이 들고 널리 엑세스가 불가함으로 쉐어링이 되지 않는 문제를 가지고있습니다.

후자의 경우, 비전용 클러스터로 앞서 설명한 이기종 하드웨어로 구성되어있으며, cpu 와 gpu의 빠른 발전속도에 맞게 aws같은곳에서 이기종 하드웨어 세트로 모델을 학습시킬수 있습니다. 이 경우 dynamic하게 리소스들이 할당되며, 싸고 용량문제가 비교적 적게 발생합니다.

최근 비전용 클러스터(위에서 설명드린) 에서 주로 모델 훈련이 이루어지는 한편, 더 심각한 스트레글러 문제가 발생합니다. 스트래글러의 경우에도 크게 두가지로 나뉠수가 있는데 비결정론적 스트래글러, 결정론적 스트레글러로 나뉠수가 있습니다.

전자의 경우, os 지터같은 일시적인 장애로 인해 발생하며, 일시적이로 아주 미미합니다

** os jiter: e.g. 백그라운드 데몬 프로레서의 에약 / 비동기 이벤트 처리로 인해 발생하는 간섭

하지만 후자의 경우, 전자에 비해 훨씬 심각하고 오래 지속됩니다. 그리고 이는 앞서 설명드린 비전용 클러스터에서만 발생합니다.

간단히 말하면, 스트래글러는 적은 수의 스레드에서 주어진 반복을 실행해야하는데 다른 스레드보다 오래걸릴때 발생하는 문제입니다 모든 스레드가 동기화되어야해서 각 스레드는 iteraiton마다 가장 느린 스레드의 속도로 진행되어 문제가 발생하는것입니다.

이제 이런 스트래글러를 해결하기위해 과거에 행해졌던 여러가지 시도들에 대해 살펴봅니다.

ASP 방식은 다른 worker를 기다리지 않고 독립적으로 다음 반복을 수행합니다. 이렇게 하면 컴퓨팅 주기를 낭비하지않고 하드웨어적으로 효율이 높습니다. 그런데 가장큰 문제가 global하게 매개변수가 동기화가 제대로 되지않아 부실한 매개변수를 사용하게 될 확률이 높아집니다. 이는 앉은 품질의 업데이트를 만들어내기 때문에 더 많은 Iteraitondl 필요하게되고 결국엔 그렇게 효과적인 스트래글러 해결방법은 아닌듯합니다.

SSP 방식은 앞서 ASP 와 BSP를 섞어놓은 방법입니다. 매개변수 비활성이 특정한 임계값에 도달할때만 스트래글러를 기다려줍니다. 하지만, SSP는 주로 비결정적 스트레글러에만 초점을 맞춘 방법이기 때문에, 결정적 클러스터에 적용할경우 지연이 자주 발생할수 있습니다. ASP 와 BSP가 섞인 방법이기 떄문에 여전히 스트래글러가 발생시 기다려야하는 문제가 남아있고 해결되지 않았습니다.

Redundant execution이라는 방법은, 스트래글러 worker에 여러 복사본을 두어서 먼저 완료된 작업의 결과만 받아들이는 방법입니다. 그런데 이 방법은 차선책일뿐, 일부의 스트래글러만 완화해주지만 최악의 스트래글러의 경우 전혀 도움이 되지 않습니다. 복제본이 모두 느리다면 큰 효과가 없기 때문입니다. 또 복제본을 만들기 때문에 추가적인 리소스를 소비해야 한다는것이 단점입니다.

지금까지의 방법들은 전부 스트래글러가 발생할경우 이를 완화하는 방법들만을 다루었지 스트레글러의 근본원인에 대해 서는 다루지 않았습니다. 애초에 스트레글러가 발생하는것을 방지하면 더 근본적으로 문제를 해결할수 있습니다. 이를 위해서는 로드밸런싱 기술에 의존할 필요가 있습니다. 이 로드밸런싱(부하분산) 은 병렬처리에서의 고전적인 연구주제이며 두가지 (static , dynamic) 방식으로 나뉩니다.

전자는 정적 부하분산방법이고 후자는 동적 부하분산 방법입니다.

정적 부하분산은 라운드 로빈같이 정적인 양을 다루며, 동적 부하분산은 부하가 많은 작업자의 일을 런타임부하가 적은 작업자로 재분배해줍니다

아래 그림은 FLEXRR 이라고 최근의 Dynamic한 load balancing 방법입니다. 주어진 임계값에 대해서 다른 작업자보다 뒤처지면(slow) Fast한 작업자에게 일을 제공합니다

이 논문에서는 이 dynamic load balancing 개념을 사용해서 Sem-dynamic loac balancing이라는 전략을 제공합니다

앞서 말한방법들을 바탕으로 새로운 전략을 내놓았습니다. 각 iteraiton 안에서는 정적으로 부하를 유지하지만, 다른 iteraiton에서는 동적으로 유지합니다. 이게 무슨말이냐 하면, 각 iteraiton의 경계부분에서 각 worker들의 상태를 측정합니다. 요즘에는 iteration의 크기가 아주 작고 iteraiton안에서도 엄청나게 큰 변화가 일어나는것이 아니기 때문에 (위 그래프에서 보면 배치 사이즈별로 iteraion time이 몇초 혹은 0.몇초 대로 굉장히 작음을 알수있습니다) iteraiton 의 경계부분에서 측정해도 충분합니다.

한마디로 iteraiton 전부를 볼필요없이 경계부분만 살펴본다는것입ㄴ디ㅏ

두번쨰로, 각 경계에서 스태글러를 감지해냅니다.

세번쨰로, 각 iteraiton 별 경계에서 스트래글러를 감지해내고 배치크기를 조정해줍니다.

이러한 로드밸런싱 전략을 사용할것이라고 합니다.

이제 앞에서 load balancing 전략을 정해주었으니, 비전용 클러스터에서 효율적인 분산학습을 위해 LB-BSP라는 새로운 방법을 제시합니다. 먼저 모델학습 반복과정에서 iteration이 걸리는 총 시간은 t 이고, 이 t는 tm + tp로 이루어집니다 (위 피피티에 설명)

x 는 배치를 의미합니다. 그런데 정해놓고 보니, cpu와 gpu 클러스터에 각각 다른 문제가 발생합니다. cpu 클러스터에서는 ti와 xi가 선형적으로 증가하는데 ( 배치 사이즈가 커지면 프로세싱 시간인 t도 늘어난다) , Gpu는 비선형적입니다. 그래서 cpu와 gpu를 각각 따로따로 살펴보기로 합니다.

cpu는 gpu같은 가속기가 없기 때문에 다음과같은 상황에서 주로 쓰입니다 ( 피피티 위에 설명)

그리고 앞 피피티에서 말한것처럼 x,v 간에 선형관계를 이루고 있습니다. 그리고 t에서 tp가 99퍼를 차지하고 있기 떄문에 tm은 무시해도 별 영향이 없습니다.

Γ (x) 값이 선형적이기 떄문에 tp와 배치사이즈(x) 는 비례하게됩니다. 그래서 다음 반복에 대해 작업자 배치 크기를 결정하기 위해서는 현재 반복에서 샘플처리속도만 알면됩니다.

그런데 문제가, 샘플처리속도가 항상 일정한것이 아니라 동적으로 달라지기 때문에, NARX라는 방법을 사용합니다

NARX는 RNN의 일종으로 과거속도와 현재속도, cpu및 메모리 사용량같은 과거와 현재값을 모두 받아들이는 방법이라, 보다 좋은 성능을 보인다고 합니다.

위 알고리즘을 간단히 살펴보면, 이전 피피티에서 언급했던 샘플 처리 속도 (v)의 과거 값 / CPU 및 메모리 사용량 (c / m)의 두 구동 리소스의 현재 과거 값들을 받아옴을 확인할수 있습니다.

tp와 해당 함수의 식을 조합해서 v(속도)를 구하고 이 속도를 F (NARX 함수) 에 넣어서 계산해줍니다. 앞 피피티의 연산식을 활용하여 새로운 배치사이즈를 리턴해줍니다.

앞서 cpu 클러스터에 대해 살펴보았고 이번에는 gpu 클러스터에 대한 성능을 특성화 한다음 알고리즘을 제시해주었습니다. 우선 gpu의 성능으로는 앞서 cpu에서는 tm을 무시해주었지만 gpu에서는 무시해주면 안됩니다. gpu에서 계산은 cpu에서보다 훨씬 빠르고 이에따라 통신시간도 무시할수 없어졌습니다.

또 gpu를 수행하기 위한 일련의 준비작업(메모리간에 매개변수 교환, 처리커널 시작..)에도 상당한 오버헤드가 발생하기 떄문에 이 것들도 무시할수 없어졌습니다.

세번쨰로, tesla100 같은 최신의 고급 gpu의 경우 샘플배치가 너무 작아서 일정 크기이상으로 샘플 배치크기를 줄인다면 성능이 확 떨어지게 됩니다.

네번쨰, 각 반복동안 중간겨로가와 매개변수등을 모두 gpu 메모리에 저장해야함으로, 최대 배치크기를 제한해야합니다. (메모리부족을 예방하기위해)

앞 피피티에서 살펴본것들을 바탕으로 다음 알고리즘을 살펴보면

우선 각 iteration에서 가장 느린 작업자를 스트래글러로 지정해주고 가장 빠른 작업자를 리더로 지정해줍니다.

먼저 위 피피티에서 세번쨰문제를 해결하기위해 특정 배치크기 이하로 떨어지는것을 예방해줍니다.

두번쨰로 여전히 스트래글러의 크기가 리더보다 크다면, 리더의 배치크기를 조금 줄여주고, 스트래글러의 배치크기를 조금 늘려주는 방향으로 균형을 잡아갑니다

세번쨰로 반대가 된다면 파인튜닝을 통해 스위치 해줍니다.

*파인튜닝 : 기존에 학습되어져 있는 모델을 기반으로 아키텍쳐를 새로운 목적으로 변형하고 이미 학습된 모델 weights 로 부터 학습을 업데이트하는 방법을 의미합니다.

마지막으로 cpu,gpu별로 결과값을 살펴보면, 그래프 3개짜리에서 보면 (A) 그래디언트 업데이트당 시간의 평균 / worker의 수를 의미합니다. (B)는 통계적 효율성으로 목표하는 정확도에 도달하는데 필요한 업데이트수를 의미합니다. (한마디로 목표한 정확도에 이르기까지 반복하는 iteraion수를 의미합니다.) (c)는 목표정확도에 도달하는데 필요한 전체시간을 보여줍니다.(=목표한 정확도에 도달하는데 필요한 전체 시간)

세개 그래프 값에서 모두 LB-BSP 이 가장 적은 업데이트수와 시간을 가짐을 확인할수 있습니다.

아래그래프 2개를 보면, 마이크로 벤치마크를 실시한것으로 인스턴스 4개만 실시한것을 비교한것입니다. ( 인스턴스 4개를 합쳐준것을 cluster A라고 부릅니다) iteraion 횟수가 점점 늘어날수록 일정한값에 도달함을 알수 있습니다. 또 iteraion 횟수가 점점 늘어날수록 4개 인스턴스 값의 배치 처리시간이 거의 같아져서 straggler 문제가 해결됨을 확인할수 있습니다

cpu에서도 살펴봅니다. 여기선 table B 와 같이 인스턴스들을 합친 cluster-B를 만들어 살펴봅니다.

figure 9 는 cluaster B 에서 서로 다른방식으로 SVM 과 ResNet-32를 훈련할떄의 평균반복시간을 보여줍니다. LB-BSP가 가장 짧은 시간으로 최고의 효율성을 이끌어낼수있음을 확인할수 있습니다.

FIgure 10은 NARX 모델을 사용했을떄의 예측성능을 추가로 평가해준것입니다. 클러스터 B에서 m4.2xlarge 인스턴스 하나에 대한 resnet-32 훈련 프로세스에서 무작위로 iteration을 골라 살펴본것입니다. 이를 통해 NARX가 기존의 방법 뿐만아니라 프로세싱 속도 예측도 잘한다는 추가적인 기능도 확인할수 있습니다.

+)

• NARX 그래프에 대한 내용에서 accuracy 라고 잘못 설명했던 부분을 정정합니다.

→ 그래프의 내용은 m4.2xlarge 스턴스 하나에 대한 ResNet-32 훈련 프로세스에서 iteration을 무작위로 선택한 구간으로, LP-BSP의 성능을 나타내기위한 지표라기보다 , NARX의 성능을 더 보여주기위해 추가적으로 진행해준 실험에 대한 표였습니다. (cluster-B 를 사용해서 prediction을 실시해준 결과를 나타낸준것 )

• 19p Figure 4 그래퍼에서 xo 가 의미하는것은 최대 배치사이즈 제한값입니다. 메모리 부족문제를 방지하기위해서 배치사이즈크기의 최대값을 지정해준것을 의미합니다

Uploaded by Notion2Tistory v1.1.0