Coding has been widely used as a way to mitigate the effect of system noises in many engineering applications. Research has also been conducted to distribute large-scale computations required for machine learning and data analytics to the computing clusters such as Amazon EC2. In this dissertation, we show that the latency due to the computation scale and complexity can be dramatically reduced by coding under the distributed cloud computing environment. In the first part, we suggest the optimal load allocation for coded distributed computing with heterogeneous workers. Specifically, we focus on a scenario in which the workers with a same computing capability belong to a group for analysis. We find that load balancing among the groups plays an important role in minimizing the latency. Based on the load balancing, we demonstrate that the distribution of time for each group to complete the given tasks is asymptotically constant. Moreover, we suggest the theoretic lower bound for the expected latency and show that the proposed load allocation asymptotically achieves the lower bound. In the second part, as a generalization of the first part, we propose the optimal worker assignment and load allocation to minimize the expected latency in the presence of multiple masters. Based on the optimal load allocation in the first part, we find the necessary condition for worker assignment to minimize the time required for multiple masters to complete the given tasks. Using the necessary condition, we obtain the optimal worker assignment and load allocation. Furthermore, we show that the optimal worker assignment and load allocation achieve the lower bound of the expected latency, which is shown to be the theoretic limit. In the third part, we consider the problem of estimating the time-dependent ability of workers participating in the distributed computing over heterogeneous clusters. We propose a method for estimating the workers' ability based on the expectation maximization algorithm combined with the particle method. Exploiting the proposed estimation of the workers' ability, one can devise the optimal load allocation and worker assignment for minimizing the latency in the heterogeneous distributed computation with the workers having time-varying abilities. Lastly, we propose code designs to achieve low latency in a communication network environment between a master and a cloud. The proposed codes are designed by applying the interpolation of Reed-Muller and polar code. In addition, the algebraic structures of the proposed codes are analyzed.
부호는 여러 공학적인 응용상황에서 시스템 노이즈의 영향을 경감시키기 위한 방법으로 널리 사용되어져왔다. 또한, 머신러닝이나 데이터 분석을 위해 요구되어지는 대규모의 연산들을 아마존 EC2와 같은 컴퓨팅 클러스터들로 오프로딩하여 수행하는 방법에 대한 연구도 활발히 진행되어져 왔다. 본 학위 논문에서는 분산 클라우드 컴퓨팅 환경을 고려하였을때, 복잡하고 대규모인 연산에서 필연적으로 발생하는 지연시간을 코딩을 통해 획기적으로 줄일 수 있음을 보인다. 먼저 이기종 부호화 분산 컴퓨팅 환경에서 사용자의 연산 시간을 최소화하기 위한 최적의 작업량 분배 방법을 제안한다. 특히 같은 컴퓨팅 능력을 가진 클러스터들을 분석을 위해 그룹으로 간주하는 시나리오를 고려한다. 최적의 작업량 분배 방법을 도출하는 과정에서 작업량 균등 조정이 연산 시간을 최소화 하는데 중요한 역할을 한다는 것을 발견하였다. 작업량 균등 조정 조건을 기반으로 하여, 최적의 작업량 분배가 이루어졌을 때 각 그룹이 일을 마치는 시간의 분포가 점근적으로 상수가 된다는 것을 증명한다. 더욱이 연산 시간의 이론적인 한계를 제시하고 최적의 작업량 분배 방법이 적용되었을 때 연산시간이 그 한계를 달성한다는 것을 증명한다.두 번째로는, 첫 번째 부분에서 다룬 문제를 일반화 하여 다수 사용자의 전체 연산 시간을 최소화 하는 최적의 작업자 할당 및 작업량 분배 방법을 제시한다. 최적의 작업량 분배 방법을 기반으로 하여, 작업자 할당 방법이 다수 사용자의 연산 시간을 최소화하기 위한 필요조건을 찾았다. 이 필요조건을 이용하여, 도출된 최적의 작업자 할당 방법이 주어지는 경우 점근적으로 다수 사용자의 연산 시간의 이론적 한계를 달성한다는 것을 보인다. 세 번째로는, 분산 컴퓨팅 환경에서 작업자의 컴퓨팅 능력이 시간이 따라 변화하는 시나리오를 고려한다. 입자법과 결합된 기댓값 최대화 알고리즘을 기반으로 한 작업자의 컴퓨팅 능력 추정 방법을 제안한다. 작업자의 능력에 대한 추론은 사용자의 연산 시간을 최소화하기 위해 첫 번째 부분과 두 번째 부분의 결과인 최적의 작업자 할당과 작업량 분배에 사용될 수 있다. 마지막으로 사용자와 클라우드 사이의 통신 네트워크 환경에서 낮은 지연 시간을 갖는 부호 디자인 방법을 제시한다. 제안된 부호들은 리드 뮬러 부호와 극 부호의 내삽법을 응용하여 디자인되었다. 이에 더하여 제안된 부호의 대수적 구조들에 대한 분석이 제시된다.
