Toward efficient online scheduling for large-scale distributed machine learning system

<p>Thanks to the rise of machine learning (ML) and its vast applications, recent years have witnessed a rapid growth of large-scale distributed ML frameworks, which exploit the massive parallelism of computing clusters to expedite ML training jobs. However, the proliferation of large-scale distributed ML frameworks also introduces many unique technical challenges in computing system design and optimization. In a networked computing cluster that supports a large number of training jobs, a central question is how to design efficient scheduling algorithms to allocate workers and parameter servers across different machines to minimize the overall training time. Toward this end, in this paper, we develop an online scheduling algorithm that jointly optimizes resource allocation and locality decisions. Our main contributions are three-fold: i) We develop a new analytical model that considers both resource allocation and locality; ii) Based on an equivalent reformulation and close observations on the worker-parameter server locality configurations, we transform the problem into a mixed cover/packing integer program, which enables approximation algorithm design; iii) We propose a meticulously designed randomized rounding approximation algorithm and rigorously prove its performance.Collectively, our results contribute to a comprehensive and fundamental understanding of distributed ML system optimization and algorithm design.</p>

Name thesis:degree_name

Master of Science

Level thesis:degree_level

thesis

Discipline thesis:degree_discipline

Computer Science

Department dc:contributor.department

Department of Computer Science

Year dc:date.issued

2019

Author dc:creator

• Yu, Menglu

Advisor dc:contributor.advisor

• Jia Liu

Language dc:language.iso

en

Identifier

archive/lib.dr.iastate.edu/etd/17374/

OAI identifier oai:identifier

oai:dr.lib.iastate.edu:20.500.12876/31557