System and method for dynamic scheduling of distributed deep learning training jobs

A method using an inner sequence of iterations within an outer sequence of iterations in a nested fashion, wherein a plurality of jobs comprises J jobs, the J being two or more, and a plurality of processing units (PUs) comprises C PUs and the C being two or more, the method comprising:

• during an outer iteration of the outer sequence of iterations:
• estimating a number of remaining epochs required to complete each job of the plurality of jobs;
• estimating a training speed function for each job of the plurality of jobs;
• provisionally assigning one PU to each job of the plurality of jobs;
• iteratively identifying and provisionally assigning to determine an allocation from the plurality of PUs to the plurality of j obs, in the nested fashion within the outer iteration, wherein the identifying and the provisionally assigning, within an inner iteration of the inner sequence of iterations, comprises:
• at a first step within the inner iteration, identifying a greatest Time Improvement for running of job per PU based on a doubling heuristic for providing with a doubling of a number of PUs assigned, wherein the iteratively identifying identifies, at the first step within the inner iteration, that the greatest Time Improvement is associated with a particular job of the inner iteration,
• at a second step within the inner iteration, provisionally assigning to the particular job of the inner iteration, an additional first number of PUs, wherein the additional first number of PUs doubles a number of PUs provisionally assigned to the particular job of the inner iteration, and
• stopping the iteratively identifying and the provisionally assigning when a stopping condition is reached, wherein the stopping condition comprises a condition that no more PUs can be further provisionally assigned to any job of the plurality of jobs;
• assigning each of the provisionally assigned PUs from a conclusion of a most recent inner iteration to PUs of a cluster;
• launching or re-starting the J jobs on the cluster, wherein the launching comprises performing a stochastic gradient descent (SGD) algorithm for each job for at least a first interval;
• outputting weights for any job which has reached a second stopping condition;
• stopping, after elapse of a predetermined interval measured from the launching or restarting, the SGD algorithm for any job which has not reached the second stopping condition;
• and
• beginning a next outer iteration.

A device for scheduling a plurality of jobs to a plurality of processing units (PUs), wherein the plurality of jobs comprises J jobs, the J being two or more, and the plurality of PUs comprises C PUs, the C being two or more, the device comprising:

• one or more processors;
• and
• one or more memories, wherein the one or more memories store instructions, wherein execution of the instructions by the one or more processors causes the device to:
• initialize by provisionally assigning one PU to each job of the plurality of jobs, and
• iteratively identify and provisionally assign to determine an allocation from the plurality of PUs to the plurality of jobs, by:
• at a first step within the iteration, identifying a greatest Time Improvement for PUs based on a doubling heuristic for providing with a doubling of a number of PUs assigned, wherein the iteratively identifying identifies, at the first step within the iteration, that the greatest Time Improvement is associated with a particular job of the iteration,
• at a second step within the iteration, provisionally assigning to the particular job of the iteration, an additional first number of PUs, wherein the additional first number of PUs doubles a number of PUs provisionally assigned to the particular job of the iteration, and
• stopping the iteratively identifying and the provisionally assigning when a stopping condition is reached, wherein the stopping condition comprises a condition that no more PUs can be further provisionally assigned to any job of the plurality of jobs,
• wherein the Time Improvement is determined based on the number of PUs assigned to a jth job, training speed function of the jth job and estimated number of epochs needed to complete the jth job, wherein an epoch corresponds to one set of training data, and wherein j is evaluated from 1, . . . , J within any iteration.

An application specific integrated circuit (ASIC) for scheduling a plurality of jobs to a plurality of processing units (PUs), wherein the plurality of jobs includes J jobs, the J being two or more, and the plurality of PUs comprises C PUs, the C being two or more, the ASIC configured to:

• initialize by provisionally assigning one PU to each job of the plurality of jobs;
• and
• iteratively identify and provisionally assign to determine an allocation from the plurality of PUs to the plurality of jobs, by:
• at a first step within the iteration, identifying a greatest Time Improvement for running of job per PU based on a doubling heuristic for providing with a doubling of a number of PUs assigned, wherein the iteratively identifying identifies, at the first step within the iteration, that the greatest Time Improvement is associated with a particular job of the iteration,
• at a second step within the iteration, provisionally assigning to the particular job of the iteration, an additional first number of PUs, wherein the additional first number of PUs doubles a number of PUs provisionally assigned to the particular job of the iteration, and
• stopping the iteratively identifying and the provisionally assigning when a stopping condition is reached, wherein the stopping condition comprises a condition that no more PUs can be further provisionally assigned to any job of the plurality of jobs,
• wherein the Time Improvement is determined based on the number of PUs assigned to a jth job, training speed function of the jth job and estimated number of epochs needed to complete the jth job, wherein an epoch corresponds to one set of training data, and wherein j is evaluated from 1, . . . , J within any iteration.