Online Scheduling Algorithm for Heterogeneous Distributed Machine Learning Jobs

doi:10.1109/TCC.2022.3143153

Online Scheduling Algorithm for Heterogeneous Distributed Machine Learning Jobs

2023-04-01

8

PRE

AI

DOI：10.1109/TCC.2022.3143153

Original

Original request for help

Save

Abstract

En 中文

Distributed machine learning (ML) has played a key role in today's proliferation of AI services. A typical model of distributed ML is to partition training datasets over multiple worker nodes to update model parameters in parallel, adopting a parameter server or AllReduce architecture. ML training jobs are typically resource elastic, completed using various time lengths with different resource configurations. A fundamental problem in a distributed ML cluster is how to explore the demand elasticity of ML jobs and schedule them with different resource configurations, such that the utilization of resources is maximized and average job completion time is minimized. To address it, we propose an online scheduling algorithm to decide the execution time window, the number and the type of concurrent workers and parameter servers for each job upon its arrival, with a goal of minimizing the weighted average completion time. Our online algorithm consists of (i) an online scheduling framework that groups unprocessed ML training jobs into a batch iteratively, and (ii) a batch scheduling algorithm that configures each ML job to maximize the total weight of scheduled jobs in the current iteration. Our online algorithm guarantees a good parameterized competitive ratio with polynomial time complexity. Extensive evaluations using realworld data demonstrate that it outperforms state-of-the-art schedulers in today's AI cloud systems.

Keywords:

Distributed machine learning

online scheduling

Online Scheduling Algorithm for Heterogeneous Distributed Machine Learning Jobs

Abstract

Journal

Organization