Coded distributed computing has been considered as a promising technique which makes large-scale systems robust to the “straggler” workers. Yet, practical system models for distributed computing have not been available that reflect the clustered or grouped structure of real-world computing servers. Neither the large variations in the computing power and bandwidth capabilities across different servers have been properly modeled. We suggest a group-based model to reflect practical conditions and develop an appropriate coding scheme for this model. The suggested code, called group code, employs parallel encoding for each group. We show that the suggested coding scheme can asymptotically achieve optimal computing time in regimes of infinite n, the number of workers. While theoretical analysis is conducted in the asymptotic regime, numerical results also show that the suggested scheme achieves near-optimal computing time for any finite but reasonably large n. Moreover, we demonstrate that the decoding complexity of the suggested scheme is significantly reduced by the virtue of parallel decoding.
이 논문에서는 Maximum Distance Separable (MDS) 성질을 갖는 부호를 이용하여 행렬 곱을 가속화하는 부호화 연산 기술을 다루고 있다. 행렬 곱은 신경망을 학습할 때 연산 시간의 대부분을 차지하여 그 속도를 가속화하는 문제가 중요하게 다루어져왔다. 최근 연구에 따르면, 규격화된 RS 부호를 사용할 때는 높은
복잡도로 인해 부호 길이가 256 이하일 때까지만 제대로 동작한다고 한다. 규모가 커져도 연산을 안정적으로 지원하는 확장성을 보강하기 위해 본 연구는 하나의 긴 MDS 부호를 사용하는 방법 대신 짧은 MDS 부호를 여러 개 사용하는 방식을 제안한다. 좀 더 자세히 말하자면, 우선 현실의 계층성과 이종성을
반영한 그룹형 네트워크 모델을 설계한 후 그 모델에서 각 그룹마다 별도의 MDS 부호를 적용하는 그룹 부호를 제안했다. 해당 모델에서 기존 방식인 하나의 부호를 사용했을 때와 그룹 부호를 사용했을 때의 평균 연산 시간을 분석했으며, 최적화된 부호 길이를 사용할 때는 기존 방식과 같은 평균 연산 시간을 달성하는
것을 보였다. 반면, 기존 방식보다 낮은 부호화 및 복호화 복잡도를 가져 총 연산 시간을 개선할 수 있음을 보였다
