  Nowadays large-scale distributed machine learning systems have been deployed
to support various analytics and intelligence services in IT firms. To train a
large dataset and derive the prediction/inference model, e.g., a deep neural
network, multiple workers are run in parallel to train partitions of the input
dataset, and update shared model parameters. In a shared cluster handling
multiple training jobs, a fundamental issue is how to efficiently schedule jobs
and set the number of concurrent workers to run for each job, such that server
resources are maximally utilized and model training can be completed in time.
Targeting a distributed machine learning system using the parameter server
framework, we design an online algorithm for scheduling the arriving jobs and
deciding the adjusted numbers of concurrent workers and parameter servers for
each job over its course, to maximize overall utility of all jobs, contingent
on their completion times. Our online algorithm design utilizes a primal-dual
framework coupled with efficient dual subroutines, achieving good long-term
performance guarantees with polynomial time complexity. Practical effectiveness
of the online algorithm is evaluated using trace-driven simulation and testbed
experiments, which demonstrate its outperformance as compared to commonly
adopted scheduling algorithms in today's cloud systems.
