Patent Description:
Each layer of the network generates an output from a received input in accordance with current values of a respective set of network parameters.

Neural networks and other machine learning models can be processed for training or inference on a plurality of computing devices, collectively referred to in this specification as a distributed computing network.

A distributed computing network can be heterogeneous, meaning that the computing devices of the distributed computing network can include one or more different types of processing units, e.g., central processing units ("CPUs"), graphics processing units ("CPUs"), and tensor processing units ("TPUs"), as well as other forms of special-purpose logic circuitry, such as field-programmable gate arrays ("FPGAs"), and application-specific integrated circuits ("ASICs"). A heterogeneous distributed computing network can also include different generations of the same type of processing unit, e.g., the distributed computing network is considered heterogeneous if it includes a combination of first-generation TPUs, second-generation TPUs, and third-generation TPUs.

An individual computing device can be heterogeneous, meaning that the individual computing device can include multiple processing units of different types. In this specification, a distributed computing network that includes a heterogeneous computing device is considered a heterogeneous distributed computing network. A heterogeneous distributed computing network can receive a job representing a set of operations to execute on the network.

<CIT> relates to methods and apparatus to schedule applications in heterogeneous multiprocessor computing platforms, wherein information regarding performance (e.g., execution performance and/or power consumption performance) of a plurality of processor cores of a processor is stored (and tracked) in counters and/or tables. Logic in the processor determines which processor core should execute an application based on the stored information.

Dependent claims define embodiments thereof. This specification describes technologies for scheduling jobs on a heterogeneous distributed computing network having a plurality of computing devices of a plurality of different computing device types.

These technologies generally involve a recommendation engine configured to receive operations to be executed on the distributed computing network, as part of a job. From the job, the recommendation engine can extract features representing a predicted performance for the job on each type of computing device present in the distributed computing network.

From the features, the recommendation engine can predict a performance metric for each of the different types of computing device present in the distributed computing network. The recommendation engine is configured to generate recommendations for one or more types of computing device to schedule the job to, as well as a quantity specifying the amount of computing resources of each type that is recommended to be assigned. The recommendation can be provided as input to a scheduling system, which can use the predicted performance metrics and other metrics to generate a schedule for partitioning and assigning the computational graph across a plurality of computing devices of the distributed computing network.

The set of performance metrics can be ranked. Higher-ranked metrics can correspond to types of computing devices that are predicted to execute the operations of the computational graph more efficiently than types of computing devices that correspond to lower-ranked metrics.

The scheduler can use the received recommendations in addition to other metrics, such as cost, device availability, and preferences among users requesting scheduling, to more efficiently schedule operations on a distributed computing network than without using the performance metrics.

In some implementations, the recommendation is a report that can be provided to a user and that details different types of computing devices and which types are predicted to perform better than others.

Performance metrics can vary depending on a corresponding objective function used by the recommendation engine to measure performance. Types of performance measured can include run-time performance, energy performance, and cost-to-operate performance, but in general can be any measurement corresponding to performance of the job across the distributed computing network.

Regardless of the type of performance measured by the recommendation engine, the recommendation engine can predict a set of performance metrics even when historical information about the performance of previous jobs on different types of computing devices is sparse or largely unavailable.

In general, one innovative aspect of the subject matter described in this specification includes a recommendation engine configured to generate performance metrics by training and executing a machine learning model. The machine learning model is configured to receive, as input, a computational graph representing the operations of an input job, and generate, as output, a set of performance metrics measuring predicted performance of the computational graph on each type of computing device in the distributed computing network. The recommendation engine can train the machine learning model and generate the set of performance metrics for the computational graph according to an objective function.

The machine learning model can include a graph convolutional neural network ("GCN"). The GCN can be trained to receive, as input, a computational graph for a job, and generate, as output, an embedding representing features of the computational graph. An embedding is a data structure, e.g., a vector, of a relatively lower dimensionality that maps values of a data structure of a relatively higher dimensionality, e.g., an image or a graph. Embeddings represent translations of categorical values as real numbers, and collectively are part of an embedding space. Embeddings in the embedding space can be compared and visually represented as clusters, to facilitate identification of "similar" embeddings, where similarity is defined by an objective function used to train a machine learning model.

The recommendation engine can also include a collaborative filtering system, e.g., a neural collaborative filtering network, that is configured to receive the embedding of the computational graph, as input, and generate, as output, a set of performance metrics according to the objective function. The set includes a performance metric for each type of computing device in the distributed computing network.

The recommendation engine can generate the set of performance metrics without processing a computational graph through a machine learning model. In some implementations, the recommendation engine can be configured to simulate performance of operations of a computational graph across different types of computing devices using a simulator. A simulator can simulate the performance of executing an input computational graph for each type of computing device. The output of the simulator is a set of performance metrics, similar to the machine learning model approach described briefly, above.

The subject matter described in this specification can be implemented in particular implementations, including methods, systems, and computer-readable storage media, so as to realize one or more of the following advantages. A recommendation engine implementing the subject matter described in this specification can generate performance metrics as a recommendation to a scheduler to improve the efficiency of the scheduler in assigning jobs to one or more computing devices in a distributed computing network. The recommendation engine can generate recommendations using sparse historical information about previous jobs executed on computing devices of different types, which would otherwise be unusable to conventional recommendation systems because of a lack of information, i.e., because of the cold start problem.

The cold start problem generally refers to the problem of drawing inferential conclusions from a sparsity of information. For example, the cold start problem can occur in the context of predicting qualitative information about the performance of machine learning jobs across a heterogeneous distributed computing network. Specifically, historical performance for machine learning jobs is limited for a number of reasons.

One reason is because machine learning jobs are generally executed on a distributed network of hardware accelerators. Hardware accelerators are computing devices that include specialized hardware for performing certain types of operations, e.g., matrix multiplication, more efficiently over non-specialized-or "general purpose"-computing devices. Hardware accelerators are generally more computationally efficient than their general purpose counterparts, but are also generally more expensive, both because of the cost of the hardware and associated energy costs to power and maintain the accelerators. As a result, historical information about performance of machine learning jobs on different types of hardware accelerators is generally limited to a few types of hardware accelerators available to a particular user executing the job.

Another reason information of historical performance of machine learning jobs is limited is because of the volatility of machine learning models. Metadata describing the machine learning job, e.g., a job name or architectural characteristics describing the machine learning model for the job, often changes, particularly during training when an optimal architecture is still being learned. As a result, comparing machine learning jobs executed on different types of computing devices to predict performance of a machine learning job is difficult.

The recommendation engine implementing the subject matter can improve the performance of a heterogeneous distributed computing network that generally includes a number of computing devices that are non-fungible, i.e., are not able to perform the same operations at all or with the same level of efficiency and accuracy as other computing devices in the network. Homogenizing a distributed computing network to include computing devices of a single device is cost-prohibitive and inefficient, especially because a heterogeneous distributed computing network is flexible to executing different jobs optimized for certain types of computing devices. Therefore, the recommendation engine can leverage the variety of computing device types in a distributed computing network to facilitate generating schedules and/or recommendations tailored for each input job.

Also from the set of performance metrics, the recommendation engine can generate recommendations for a user to analyze. The recommendations can be reports that indicate recommended computing device types to execute a job on, to provide new insight as to which types of computing devices are better for executing a particular job than others.

According to implementations, there are provided methods, systems, and apparatus, including computer programs encoded on computer storage media, for scheduling operations represented as a computational graph on a distributed computing network. A method includes: receiving data representing operations to be executed in order to perform a job on a plurality of hardware accelerators of a plurality of different accelerator types; generating, for the job and from at least the data representing the operations, features that represent a predicted performance for the job on hardware accelerators of the plurality of different accelerator types; generating, from the features, a respective predicted performance metric for the job for each of the plurality of different accelerator types according to a performance objective function; and providing, to a scheduling system, one or more recommendations for scheduling the job on one or more recommended types of hardware accelerators.

<FIG> illustrates an example recommendation engine <NUM>. The recommendation engine <NUM> can receive a job <NUM>, as input, and generate a recommendation <NUM>, as output. Optionally, the recommendation engine <NUM> can be configured to receive a plurality of jobs 105A-N and generate a plurality of recommendations 110A-N. Description of the jobs and recommendations will be made in reference to the job <NUM> and the recommendation <NUM>.

Computing device types are different categories of computing devices grouped by a common characteristic. Computing device types can include: architectural features, e.g., memory or processing capacity; processor or circuit logic, e.g., FGPA, ASIC, or TPU; and generations within a same family of computing device, e.g., a first-generation TPU or a second-generation TPU.

The recommendation <NUM> is a recommendation for which certain types of computing devices of a plurality of different types of computing devices of a distributed computing network are recommended by the recommendation engine <NUM> for executing the job <NUM>. The recommendation <NUM> can provide suggestions, e.g., as a text report, to a user for which types of computing devices to execute the job <NUM> on, according to different characteristics of the computing devices. These characteristics can include a recommended device memory-size, model, and how computing devices in the distributed computing network assigned the job <NUM> should be arranged relative to one another for improved execution of the job <NUM>.

In addition to a recommendation of one or more types of computing device to assign the job to, the recommendation <NUM> can include a value quantifying how much computing resources from each type of computing device should be allocated for the job. For example, the recommendation <NUM> can include a quantity of devices of each type, e.g., two accelerators of a first type and three accelerators of a second type; or, the recommendation can include a ratio of devices, e.g., a <NUM>:<NUM> ratio between computing devices of two different types.

In some implementations, the value quantifying the computing resources of each type of computing device can be specified in terms of aggregate computational resources. For example, the recommendation <NUM> recommends assigning enough computing devices of a first type such that a total amount of compute resources assigned from the first type of computing device meets a recommended threshold.

The recommendation <NUM> can also include hints or reasons for why the recommendation engine <NUM> generated recommendations as it did, e.g., reasons explaining the similarity in performance of a recommended type of computing device relative to other types. The reasons can also include previous observations for the performance of jobs similar to the job <NUM> on recommended types of computing devices in the past, e.g., an observation that jobs that include many convolutional operations perform better on the recommended types of computing devices, e.g., because of the hardware configuration of the computing devices.

The recommendation engine <NUM> is configured to rank each type of computing device corresponding a respective performance metric in the set of performance metrics. The ranking depends on the objective function used to generate the performance metrics. The objective function can be any function measuring a characteristic of a given job that is of interest, e.g., run-time performance, energy cost, or productivity as a function of computing resources dedicated to the job.

For example, if the objective function measures performance of each type of computing device by computational throughput while executing a given job, then the recommendation engine <NUM> ranks types of computing devices with respective metrics representing higher throughput over other types of computing devices with respective metrics representing lower throughput.

As another example, the recommendation engine <NUM> can generate performance metrics using an objective function that measures performance of each type of computing device by energy consumption while executing a given job. With this example objective function, the recommendation engine <NUM> is configured to rank certain types of computing devices with overall lower energy consumption higher than other types of computing devices with overall higher energy consumption.

The recommendation can be hand-written as a product of expert analysis, the recommendation engine <NUM> can be configured to infer reasons or hints automatically, or the recommendation engine <NUM> can be configured to generate recommendations both automatically and using expert analysis. In some implementations, the recommendation engine <NUM> is configured to infer reasons or hints by making correlations between characteristics of a type of computing device with the performance ranking for that type of computing device.

For example, the recommendation engine <NUM> can generate a recommendation that identifies a larger memory capacity with better performing types of computing devices, because the recommendation engine <NUM> correlates higher ranking types of computing devices with having a larger memory capacity. The recommendation engine <NUM> can correlate multiple characteristics of each type of computing device with its respective performance metric to generate a richer recommendation.

The job <NUM> can collectively represent operations represented in a computational graph <NUM> and optional metadata <NUM> related to the computational graph <NUM> or the job <NUM> itself. A computational graph is graph of nodes each connected to at least one other node by an edge. Each node represents an operation to be performed by one or more computing devices in a distributed computing network. For any two nodes u and v in the computation graph, an edge (u, v) is a directed edge and represents a data dependency from u to v. A data dependency from u to v means the operation represented by node u generates an output that is input to the operation represented by node v.

The operations in the computational graph <NUM> can be operations of a software program configured for execution on a distributed computing network. For example, operations in the computational graph <NUM> can be operations for training or executing a machine learning model, e.g., a neural network.

The metadata <NUM> can include information about the job <NUM>, e.g., a job name, information about the user sending the job <NUM> to the recommendation engine <NUM>, a priority level for assigning the job <NUM> as compared with other jobs, and a predetermined resource allocation requirement for the job <NUM>. The metadata <NUM> can also include statistics for the computational graph collected while the computational graph was compiled, e.g., floating-point operations per second ("FLOPS"), and average or peak memory usage. The metadata <NUM> can also include statistics for the computational graph collected while the computational graph was executed, e.g., memory usage, processor core usage, and statistical information types of computing devices having previously executed the job <NUM>, e.g., FLOPS or duty cycle.

<FIG> shows an example scheduling system <NUM>. The scheduling system <NUM> includes a recommendation engine <NUM>, a scheduler engine <NUM>, and a distributed computing network <NUM>. The scheduling system <NUM> can receive, as input, a job <NUM> that includes a computational graph <NUM> and optional metadata <NUM>. Although the example scheduling system <NUM> is shown as configured to receive the job <NUM> that includes operations represented as a computational graph, the scheduling system <NUM> can be configured in other implementations to receive data representing the operations for the job <NUM> in other formats, e.g., as a series of function calls of an appropriately configured Application Program Interface ("API").

The scheduler engine <NUM> is configured to send the computational graph <NUM> and the optional metadata <NUM> to the recommendation engine <NUM>. The recommendation engine <NUM> is configured to predict a set of performance metrics for each type of computing device in the distributed computing network <NUM> and generate recommendations for scheduling operations to different types of hardware accelerators, using the performance metrics. Then, the scheduler engine <NUM> can receive the recommendations from the recommendation <NUM>.

The scheduler engine <NUM> can be any conventional scheduling system for scheduling jobs on a distributed computing environment. The scheduler engine <NUM> can implement any conventional scheduling algorithm for scheduling jobs to the distributed computing network <NUM>, augmented with the recommendations from the recommendation engine <NUM>.

For example, the scheduler engine <NUM> can implement priority scheduling using a set of characteristics for the job <NUM>, in addition to the recommendations generated by the recommendation engine <NUM>. The set of characteristics the scheduler engine <NUM> uses to schedule the job <NUM> can include, for example, a user-assigned priority level and characteristics about a user submitting the job <NUM> for scheduling, e.g., a priority level for the user to have access sending jobs to the distributed computing network <NUM>. The characteristics can be obtained from the metadata <NUM> or from another source, e.g., user-provided.

In addition to a set of characteristics for the job <NUM>, the scheduler engine <NUM> can schedule jobs according to globally-imposed requirements, e.g., to schedule jobs of a certain type with higher priority than others, or to favor some types of computing devices over others, e.g., because of energy cost.

In scheduling the job <NUM>, the scheduler engine <NUM> can partition the computational graph <NUM> into a plurality of subgraphs. Each subgraph is linked to another subgraph by an edge, representing the flow of data as output from one subgraph to input for another subgraph.

The scheduler engine <NUM> can decide which computing devices to assign a respective subgraph based on the recommendations generated by the recommendation engine <NUM>. For example, the recommendation engine <NUM> can indicate that a first type of computing device is better performed to process the job <NUM>, predicting a higher performance metric for the first type of computing device over other types of computing devices in the distributed computing network <NUM>. Then, using the recommendations, the scheduler engine <NUM> can partition the computational graph <NUM> into a plurality of subgraphs and assign the subgraphs with a preference to the first type of computing device.

The scheduling is described as a "preference" to the first type of computing device because other imposed requirements to the scheduler engine <NUM> can still result in the scheduler engine <NUM> scheduling subgraphs to a computing device type that is ranked lower by performance metric, and subsequently, by recommendation. In general, the set of performance metrics from the recommendation engine <NUM> enriches the decision-making by the scheduler engine <NUM> in assigning subgraphs to the distributed computing network <NUM>.

For example, if computing devices of a highest ranked performance metric are unavailable in the distributed computing environment <NUM>, e.g., because those computing devices are not currently in operation, the scheduler engine <NUM> can schedule a job on computing devices of a type that is less-recommended by the recommendation engine <NUM> according to the received recommendations. As another example, the scheduler engine <NUM> can be configured to assign more highly recommended types of computing devices to the job <NUM> depending on a priority level assigned to the job <NUM> or the status of the user from which the job <NUM> originated.

<FIG> illustrates a recommendation pipeline <NUM> using a machine learning model. A recommendation engine can be configured to process an input job <NUM> and generate performance metrics <NUM> using the recommendation pipeline <NUM>. As described above with reference to <FIG> and <FIG>, the performance metrics <NUM> can then be sent to a scheduling system for scheduling the job <NUM>, and/or be used to generate a recommendation.

The recommendation pipeline <NUM> begins with the input job <NUM> having a computational graph and optional metadata, as described above. A graph convolutional neural network <NUM> can receive the computational graph of the input job <NUM> and the metadata.

A graph convolutional neural network is a neural network having a plurality of layers, including an input layer and an output layer that receives a graph as input and performs convolutional operations on the input graph. The graph convolutional neural network <NUM> can be trained to receive, as input, the computational graph, and generate, as output, an embedding representing features of the computational graph. An embedding from a graph convolutional neural network can represent features from neighboring nodes of a given node in the computational graph, to generate embeddings representing "similar" computational graphs. Features from neighboring nodes of a given node can be performed by performing convolutional operations on the neighboring nodes.

The graph convolutional neural network <NUM> can be trained jointly with a neural collaborative filtering network-described below-to generate embeddings for similar computational graphs according to an objective function. When the graph convolutional neural network <NUM> and the neural collaborative filtering network are trained jointly, resultant output from the neural collaborative filtering network is a set of performance metrics for each type of computing device, even for computing device types where historical data of performance for the type of input job is sparse or non-existent.

Turning to the architectural details of the graph convolutional neural network ("GCN") <NUM>, at each layer, the GCN <NUM> can execute one or more activation functions from respective input received at the layer. The one or more activation functions can be any conventional activation function, e.g., ReLU, sigmoid, or tanh.

Also at each layer, the GCN <NUM> can generate multiple outputs from one or more activation functions at the layer, to extract features from each node in the computational graph, as well as to extract separate features from inputs and outputs to each node in the computational graph, and features from neighbors of the node. To do so, the recommendation engine can, for example, augment the computational graph to include self-loops at each node in the computational graph, to extract features at not only neighboring nodes to any given node in the computational graph, but the given node itself.

To extract features from inputs and outputs of a given node in the computational graph separately, the GCN <NUM> can separately aggregate activation function outputs for outputs and inputs of the node, respectively, to learn whether performance of the computational graph on a particular type of computing device is dominated by the inputs or the outputs.

The recommendation engine can update the weights using a backpropagation technique, e.g., backpropagation using stochastic gradient descent. For each layer, the recommendation engine can compute a gradient of the activation function against a ground-truth value. The ground-truth can be the historical performance metric of a computational graph on each type of computing device. The recommendation engine can update weights based on the computed gradient of activation outputs that include at least one of: (i) the respective output of the node-wise computation, (ii) the aggregated respective activation outputs of each node output of each node in the layer, or (iii) the aggregated respective activation outputs of each node input of each node in the layer.

Equation <NUM> is an example layer-wise propagation rule for the GCN <NUM>: <MAT>.

l is a layer in the GCN <NUM> and Hl is a tensor of activation functions at layer l. A tensor is a multidimensional array of numeric or other values, e.g., strings, having a specific order that corresponds to the dimensionality of the array. For example, a scalar value is a <NUM>th-order tensor, a vector of numeric values is a <NUM> st-order tensor, and a matrix is a <NUM>nd-order tensor.

Equation <NUM> defines Hl+<NUM>, where σ(·) denotes an activation function, and [ ] denotes concatenation. H<NUM>, i.e., the input layer, is defined as H<NUM> = X ∈ RN*D, where X is a node feature tensor of the computational graph representing N-dimensional feature vectors for each operation represented by the computational graph, having D nodes in total.

A is an adjacency matrix of an input computational graph. An adjacency matrix is a matrix in which the elements of the matrix indicate whether nodes within the graph are adjacent, i.e., linked by a common edge, or not. In Equation <NUM>, Â = A + IN and represents an adjacency matrix in which each node is considered adjacent to itself, i.e., each node has a self-loop to allow the GCN <NUM> to learn features for each given node and not just its neighbors, as described above.

Also in Equation <NUM>, Din and Dout are matrices representing the input and output degrees of each node in the computational graph. Representing the computational graph as Din and Dout enables the GCN <NUM> to learn features of inputs and outputs of each node in the computational graph, separately, which can improve how the GCN <NUM> ultimately generates the embedding for the computational graph.

Also in Equation <NUM>, Vl and Wl are separate trainable weight tensors for layer l. Elements of the trainable weight tensors can be updated by the recommendation engine during training.

Equation <NUM> is another example layer-wise propagation rule for the GCN <NUM>, used in some implementations: <MAT>.

Equation <NUM> is functionally equivalent to Equation <NUM>. Rather than using an adjacency matrix Â augmented with self-loops as described above in reference to Equation <NUM>, Equation <NUM> includes a separate term HlUl, where Ul is another trainable weight tensor for the layer l. Therefore, Equation <NUM> can also be used to define layers to learn features for each individual node at layer l.

Whether the GCN <NUM> defines each layer according to Equation <NUM> or Equation <NUM>, the GCN <NUM> can learn a combination of, at each layer:.

Next in the recommendation pipeline <NUM>, the embedding from the GCN <NUM> can be provided as input to a neural collaborative filtering network <NUM>. The neural collaborative filtering network <NUM> can be trained to receive the embedding, as input, and generate as output, a set of performance metrics <NUM> for the input job <NUM>. In general, collaborative filtering refers to a class of techniques for making predictions or recommendations for one agent in response to a task, using information collected from actions or preferences of multiple other agents in response to the same task.

The neural collaborative filtering network ("NCF network") <NUM> is a neural network having a plurality of layers, e.g., a feedforward neural network such as a multilayer perceptron, which has been trained to generate performance metrics that correspond to a position of an input embedding within an embedding space. The GCN <NUM> and the NCF network <NUM> can be trained jointly to generate embeddings for a plurality of computational graphs such that embeddings close to each other in the embedding space correspond to computational graphs that perform similarly according to the objective function used by the GCN <NUM> and the NCF network <NUM>.

Training the GCN <NUM> and the NCF <NUM> jointly means that activation outputs during a forward pass are computed as if the GCN <NUM> and NCF network <NUM> were one neural network. Specifically, the output embedding for the GCN <NUM> is provided as input to the NCF network <NUM>. The input embedding for the NCF network <NUM> is processed and a set of performance metrics are generated for the computational graph.

On the backward pass, weights at each layer of the NCF network <NUM> are updated, e.g., backpropagation using stochastic gradient descent and a loss function. The gradient obtained from the input layer of the NCF network <NUM> is passed to the output layer of the GCN <NUM>, and backpropagation can continue to update the weights of each layer in the GCN <NUM>.

The loss function used to train the NCF network <NUM> and the GCN <NUM> can be a loss between an expected set of performance metrics for a job, and a predicted set of performance metrics generated as output to the NCF network <NUM>. The NCF network <NUM> and the GCN <NUM> can be trained until meeting a predetermined training condition, e.g., a number of iterations of weight updates, or until a computed loss function reaches a predetermined threshold.

After the recommendation engine generates the set of performance metrics using the NCF network <NUM>, if the recommendation engine is processing a plurality of input jobs at a time, then the recommendation engine can next perform clustering <NUM> on respective performance metrics for each job, according to the recommendation pipeline <NUM>. The clustering step <NUM> can be executed by a clustering machine learning model trained to receive a plurality of sets of performance metrics, and generate, as output, the sets of performance metrics clustered by similar performance metrics within each set. Clustering allows the recommendation engine to further identify types of computing devices that can perform better or worse for the input job <NUM> based on predicted performance of other jobs on those types of computing devices. In some implementations, this step is skipped.

The recommendation engine can translate a set of performance metrics to one or more recommendations <NUM>. The recommendation engine can generate the recommendations according to a set of rules, e.g., recommend types of hardware accelerators over other types based on which types ranked higher in the set of performance metrics; or by statistical analysis, e.g., as described above with reference to <FIG>.

Although the translation step <NUM> is shown as occurring after the clustering step <NUM> and before a runability check <NUM> (described below), in some implementations the translation <NUM> is performed after the runability check <NUM> or in processing pipelines in which the clustering step <NUM> is not performed at all.

The recommendation engine can perform the runability check <NUM> before providing recommendations <NUM> translated from the set of performance metrics. The runability check <NUM> is a check to ensure that types of devices recommended for performing the job <NUM> on can actually run the job. If a type of computing device fails the runability check <NUM>, the recommendation engine can remove the recommendation corresponding to the type of computing device. In some implementations, the runability check <NUM> is not performed.

A type of computing device can fail a runability check for the input job <NUM> for a variety of reasons. The reasons can be tied to hardware specifications and the overall configuration of the type of computing device. For example, a type of computing device can fail a runability check if the type of computing device does not support one or more operations represented by the computational graph for the job <NUM>.

<FIG> illustrates a recommendation pipeline <NUM> using a simulator <NUM>. A simulator can be configured to simulate execution of a computational graph on different types of computing devices on a distributed computing network. To do so, the simulator <NUM> can receive (i) an input job <NUM> that includes a computational graph and optional metadata; and (ii) respective hardware specifications <NUM> corresponding to each type of computing device present in the distributed computing network. The solid arrows in <FIG> represent the flow of the recommendation pipeline <NUM>, while the dotted arrow represents that the hardware specifications <NUM> can be provided to the simulator prior to executing the recommendation pipeline <NUM>.

As described above, with reference to the scheduling system <NUM> of <FIG>, the simulator <NUM> can be configured to receive data representing the operations in other formats besides specified in a computational graph.

The simulator <NUM> can be configured to simulate performance at a particular distributed computing network, by receiving, as input, the hardware specifications <NUM> representing each type of computing device in the distributed computing network, e.g., the number of computing devices, memory capacity/bandwidth and computational performance of each computing device, and other low-level details for the hardware specification of each computing device. A simulator can be configured to generate a set of performance metrics according to an objective function corresponding to the type of performance metric sought.

The simulator <NUM> can be configured to simulate performance of executing the computational graph with additional functionality and compatibility guarantees. In some implementations, the simulator <NUM> determines whether a type of computing device is compatible to execute the operations represented in the computational graph. In these implementations, the simulator <NUM> takes the role of the runability check in the pipeline.

Then, the simulator <NUM> can use hardware specifications for a given type of computing device and predict a performance metric for executing the input job <NUM> on the distributed computing network. Specifically, the simulator <NUM> can generate simulated results of executing the computational graph on a type of computing device, and measure a performance metric for those simulation results according to an objective function. Comparing <FIG> and <FIG>, in implementations in which the simulator <NUM> is used, the simulator <NUM> replaces the GCN <NUM> and the NCF network <NUM>.

The recommendation engine can perform a clustering step <NUM> and a runability check <NUM> prior to generating a recommendation <NUM>, similar to the clustering <NUM> and the runability check <NUM> in the recommendation pipeline <NUM>, described above with reference to <FIG>. In some implementations, the clustering step <NUM> is skipped. Also, if the simulator <NUM> is configured to simulate executing the computational graph according to whether each type of computing device is compatible to perform the operations represented in the computational graph, then the runability check <NUM> can be skipped.

The processing pipeline <NUM> includes a performance metric to recommendation translation step <NUM>, and the recommendation engine can be configured to receive the set of performance metrics from the simulator <NUM> (optionally, after the clustering step <NUM>), and generate recommendations, as described above with reference to <FIG>. The recommendation can generate recommendations <NUM> that can be provided to a scheduler for use in scheduling the job <NUM>, and/or used to generate recommendations for a user's consumption.

The recommendation engine can be configured to generate performance metrics without recommendations corresponding to the performance metrics. For example, the recommendation engine can send performance metrics for analysis by a user or another system configured to receive a set of performance metrics as input.

In some implementations, the recommendation engine includes or is interconnected with an engine separately configured to translate recommendations from the set of performance metrics according to different rules.

In some implementations, the recommendation engine can send the performance metrics as a user-readable report and/or for display on a display of a user device. The sent performance metrics can be further processed for analysis, e.g., the recommendation engine can generate statistical data from the performance metrics for analysis.

<FIG> is a flowchart of an example process <NUM> for generating performance metrics by a recommendation engine. For convenience, the process <NUM> will be described as being performed by an engine of one or more computers, located in one or more locations, and programmed appropriately in accordance with this specification. For example, a recommendation engine, e.g., the recommendation engine <NUM> of <FIG>, appropriately programmed, can perform the process <NUM>.

Receive, by the recommendation engine, data representing operations to be executed in order to perform a job on a plurality of computing devices of a plurality of different computing device types (step <NUM>). As described with reference to <FIG>, the recommendation engine can receive data specifying a computational graph and part of a job. The operations can correspond to any software program, including operations to train and/or execute a machine learning model.

Generate, by the recommendation engine, for the job and from at least the data representing the operations, features that represent a predicted performance for the job on computing devices of the plurality of different computing device types (step <NUM>). As described above with reference to <FIG> and <FIG>, the recommendation engine can extract features, e.g., as an embedding. In implementations in which the recommendation engine simulates a distributed computing network, the features extracted can be simulation results for each type of computing device in a distributed computing network.

Generate, by the recommendation engine and from the features, a respective predicted performance metric for the job for each of the plurality of different computing device types according to a performance objective function (step <NUM>). As described in <FIG> and <FIG>, the recommendation engine can generate predicted performance metrics using a machine learning model or a simulator for the distributed computing network.

Provide, to a scheduling system, one or more recommendations for scheduling the job on one or more recommended types of hardware accelerators (step <NUM>). The recommendations can be for recommended types and amounts of computing resources to assign. The scheduling system is configured to schedule the job for execution (i) by one or more of the plurality of hardware accelerators and (ii) based on data that includes the one or more recommendations (step <NUM>). As described above with reference to <FIG>, the recommendation engine can provide the recommendations to a scheduler engine, which, in turn, can schedule an input job using the performance metrics and additional data.

Embodiments of the subject matter and the actions and operations described in this specification can be implemented in digital electronic circuitry, in tangibly-embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, e.g., one or more modules of computer program instructions, encoded on a computer program carrier, also called a computer program product, for execution by, or to control the operation of, data processing apparatus. The carrier may be a tangible non-transitory computer storage medium. Alternatively or in addition, the carrier may be an artificially-generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. The computer storage medium can be or be part of a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them. A computer storage medium is not a propagated signal.

Data processing apparatus can include special-purpose logic circuitry, e.g., an FPGA (field programmable gate array), an ASIC (application-specific integrated circuit), or a GPU (graphics processing unit). The apparatus can also include, in addition to hardware, code that creates an execution environment for computer programs, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

A computer program, which may also be referred to or described as a program, software, a software application, an app, a module, a software module, an engine, a script, or code, can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages; and it can be deployed in any form, including as a stand-alone program or as a module, component, engine, subroutine, or other unit suitable for executing in a computing environment, which environment may include one or more computers interconnected by a data communication network in one or more locations.

A computer program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub-programs, or portions of code.

The processes and logic flows described in this specification can be performed by one or more computers executing one or more computer programs to perform operations by operating on input data and generating output. The processes and logic flows can also be performed by special-purpose logic circuitry, e.g., an FPGA, an ASIC, or a GPU, or by a combination of special-purpose logic circuitry and one or more programmed computers.

Computers suitable for the execution of a computer program can be based on general or special-purpose microprocessors or both, or any other kind of central processing unit. The essential elements of a computer are a central processing unit for executing instructions and one or more memory devices for storing instructions and data. The central processing unit and the memory can be supplemented by, or incorporated in, special-purpose logic circuitry.

Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to one or more mass storage devices. The mass storage devices can be, for example, magnetic, magneto-optical, or optical disks, or solid state drives.

To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on, or configured to communicate with, a computer having a display device, e.g., a LCD (liquid crystal display) monitor, for displaying information to the user, and an input device by which the user can provide input to the computer, e.g., a keyboard and a pointing device, e.g., a mouse, a trackball or touchpad. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user's device in response to requests received from the web browser, or by interacting with an app running on a user device, e.g., a smartphone or electronic tablet.

This specification uses the term "configured to" in connection with systems, apparatus, and computer program components. For special-purpose logic circuitry to be configured to perform particular operations or actions means that the circuitry has electronic logic that performs the operations or actions.

While this specification contains many specific implementation details, these should not be construed as limitations on the scope of what is being or may be claimed, but rather as descriptions of features that may be specific to particular embodiments of particular inventions. Moreover, although features may be described above as acting in certain combinations and even initially be claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claim may be directed to a subcombination or variation of a subcombination.

Claim 1:
A system (<NUM>, <NUM>) comprising:
one or more computers and one or more storage devices on which are stored instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
receiving (<NUM>) data (<NUM>, <NUM>) representing operations to be executed in order to perform a job (<NUM>, <NUM>, <NUM>) on a plurality of hardware accelerators of a plurality of different accelerator types, wherein the data representing the operations specifies a computational graph (<NUM>, <NUM>) representing the operations;
generating (<NUM>), for the job and from the computational graph (<NUM>, <NUM>) representing the operations, an embedding representing features of the computational graph, wherein generating comprises processing the computational graph as an input using a machine learning model that has been trained to generate embeddings in an embedding space from the computational graph such that positions of each embedding in the embedding space reflect a respective performance metric of the computational graph on each of the plurality of different accelerator types according to a performance objective function, and wherein embeddings close to each other in the embedding space correspond to computational graphs that perform similarly according to the performance objective function;
generating (<NUM>), from the embedding, a respective predicted performance metric for the job for each of the plurality of different accelerator types according to the performance objective function; and
providing (<NUM>), to a scheduling system, one or more recommendations (<NUM>) determined based on the respective predicted performance metrics for scheduling the job on one or more recommended types of hardware accelerators, wherein the scheduling system is configured to schedule the job for execution (i) by one or more of the plurality of hardware accelerators and (ii) based on the one or more recommendations (<NUM>).