Scheduling artificial intelligence model partitions based on reversed computation graph

Patent metadata

Field	Value
Publication number	US-2021248002-A1
Application number	US-202016789006-A
Country	US
Kind code	A1
Filing date	Feb 12, 2020
Priority date	Feb 12, 2020
Publication date	Aug 12, 2021
Grant date	—

Abstract

Techniques are disclosed for scheduling artificial intelligence model partitions for execution in an information processing system. For example, a method comprises the following steps. An intermediate representation of an artificial intelligence model is obtained. A reversed computation graph corresponding to a computation graph generated based on the intermediate representation is obtained. Nodes in the reversed computation graph represent functions related to the artificial intelligence model, and one or more directed edges in the reversed computation graph represent one or more dependencies between the functions. The reversed computation graph is partitioned into sequential partitions, such that the partitions are executed sequentially and functions corresponding to nodes in each partition are executed in parallel.

First claim

What is claimed is:

1 . A method, comprising:
obtaining an intermediate representation of an artificial intelligence model; obtaining a reversed computation graph corresponding to a computation graph generated based on the intermediate representation, wherein nodes in the reversed computation graph represent functions related to the artificial intelligence model, and one or more directed edges in the reversed computation graph represent one or more dependencies between the functions; and partitioning the reversed computation graph into sequential partitions, such that the partitions are executed sequentially and functions corresponding to nodes in each partition are executed in parallel; wherein the steps are performed by one or more processing devices.

2 . The method of claim 1 , wherein partitioning the reversed computation graph into partitions comprises determining in-degrees of at least a part of the plurality of nodes of the reversed computation graph, wherein an in-degree of a node represents a number of edges directed to the node.

3 . The method of claim 2 , wherein partitioning the reversed computation graph into partitions comprises partitioning the reversed computation graph into the partitions based on the in-degrees.

4 . The method of claim 1 , further comprising determining one or more resources needed to execute functions within a given partition prior to executing the functions in the given partition.

5 . The method of claim 4 , further comprising scheduling one or more functions in the given partition to another partition when at least a portion of the one or more resources needed to execute the functions within the given partition are unavailable.

6 . The method of claim 1 , wherein partitioning the reversed computation graph into sequential partitions further comprises ordering the sequential partitions such that when a first function depends on a second function, the second function is executed in a partition immediately preceding the first function.

7 . The method of claim 6 , wherein the first function and the second function are executed by the same resource.

8 . An apparatus, comprising:
a processor; and a memory storing computer program instructions, the processor executing the computer program instructions in the memory to control the apparatus to: obtain an intermediate representation of an artificial intelligence model; obtain a reversed computation graph corresponding to a computation graph generated based on the intermediate representation, wherein nodes in the reversed computation graph represent functions related to the artificial intelligence model, and one or more directed edges in the reversed computation graph represent one or more dependencies between the functions; and partition the reversed computation graph into sequential partitions, such that the partitions are executed sequentially and functions corresponding to nodes in each partition are executed in parallel.

9 . The apparatus of claim 8 , wherein partitioning the reversed computation graph into partitions comprises determining in-degrees of at least a part of the plurality of nodes of the reversed computation graph, wherein an in-degree of a node represents a number of edges directed to the node.

10 . The apparatus of claim 9 , wherein partitioning the reversed computation graph into partitions comprises partitioning the reversed computation graph into the partitions based on the in-degrees.

11 . The apparatus of claim 8 , wherein the processor executes the computer program instructions in the memory to further control the apparatus to determine one or more resources needed to execute functions within a given partition prior to executing the functions in the given partition.

12 . The apparatus of claim 11 , wherein the processor executes the computer program instructions in the memory to further control the apparatus to schedule one or more functions in the given partition to another partition when at least a portion of the one or more resources needed to execute the functions within the given partition are unavailable.

13 . The apparatus of claim 8 , wherein partitioning the reversed computation graph into sequential partitions further comprises ordering the sequential partitions such that when a first function depends on a second function, the second function is executed in a partition immediately preceding the first function.

14 . The apparatus of claim 13 , wherein the first function and the second function are executed by the same resource.

15 . A computer program product stored on a non-transitory computer-readable medium and comprising machine executable instructions, the machine executable instructions, when executed, causing a processing device to:
obtain an intermediate representation of an artificial intelligence model; obtain a reversed computation graph corresponding to a computation graph generated based on the intermediate representation, wherein nodes in the reversed computation graph represent functions related to the artificial intelligence model, and one or more directed edges in the reversed computation graph represent one or more dependencies between the functions; and partition the reversed computation graph into sequential partitions, such that the partitions are executed sequentially and functions corresponding to nodes in each partition are executed in parallel.

16 . The computer program product of claim 15 , wherein partitioning the reversed computation graph into partitions comprises determining in-degrees of at least a part of the plurality of nodes of the reversed computation graph, wherein an in-degree of a node represents a number of edges directed to the node.

17 . The computer program product of claim 16 , wherein partitioning the reversed computation graph into partitions comprises partitioning the reversed computation graph into the partitions based on the in-degrees.

18 . The computer program product of claim 15 , further comprising determining one or more resources needed to execute functions within a given partition prior to executing the functions in the given partition.

19 . The computer program product of claim 18 , further comprising scheduling one or more functions in the given partition to another partition when at least a portion of the one or more resources needed to execute the functions within the given partition are unavailable.

20 . The computer program product of claim 15 , wherein partitioning the reversed computation graph into sequential partitions further comprises ordering the sequential partitions such that when a first function depends on a second function, the second function is executed in a partition immediately preceding the first function, and wherein the first function and the second function are executed by the same resource.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Li Jin
• Liu Jinpeng
• Maclellan Christopher S

Classifications

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F9/5038

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• G06N3/10

  Interfaces, programming languages or software development kits, e.g. for simulating neural networks · CPC title

• G06F9/5088

  involving task migration · CPC title

• G06F2209/503

  Resource availability · CPC title