EFFICIENT EXECUTION OF GRAPH-BASED PROGRAMS

• US 20140359563A1
• Filed: 12/13/2013
• Published: 12/04/2014
• Est. Priority Date: 06/04/2013
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Xie, Binglong, Quan, Shuxue, Bi, Ning, Ren, Jianfeng, Kandhadai, Ananthapadmanabhan Arasanipalai, Xu, Lei
• Granted Patent: US 9,348,560 B2
• Time in Patent Office: Days
• US Class Current: 717/106
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method includes accessing, at a computing device, data descriptive of a graph representing a program. The graph includes multiple nodes representing execution steps of the program and includes multiple edges representing data transfer steps. The method also includes determining at least two heterogeneous hardware resources of the computing device that are available to execute code represented by one or more of the nodes, and determining one or more paths from a source node to a sink node based on a topology of the graph. The method further includes scheduling execution of code at the at least two heterogeneous hardware resources. The code is represented by at least one of the multiple nodes, and the execution of the code is scheduled based on the one or more paths.

Claims

1. A method comprising:

accessing, at a computing device, data descriptive of a graph representing a program, wherein the graph includes multiple nodes representing execution steps of the program and includes multiple edges representing data transfer steps;

determining at least two heterogeneous hardware resources of the computing device that are available to execute code represented by one or more of the multiple nodes;

determining one or more paths from a source node to a sink node based on a topology of the graph;

determining cost functions associated with the one or more paths; and

scheduling execution of code at the at least two heterogeneous hardware resources, wherein the code is represented by at least one of the multiple nodes, and wherein the execution of the code is scheduled based on the cost functions.

2. The method of claim 1, wherein a first node of the multiple nodes is scheduled to execute on a first hardware resource of the at least two heterogeneous hardware resources, wherein a second node of the multiple nodes is scheduled to execute on a second hardware resource of the at least two heterogeneous hardware resources, and wherein the first hardware resource has a first type that is different than a second type of the second hardware resource.

3. The method of claim 2, wherein the first type is one of a central processing unit (CPU) type, a digital signal processor (DSP) type, a graphics processing unit (GPU) type, a field programmable gate array (FPGA) type, and a reconfigurable instruction cell array (RICA) type, and wherein the second type is another of the CPU type, the GPU type, the DSP type, the FPGA type, and the RICA type.

4. The method of claim 1, further comprising generating the data by processing a visual representation of the graph to generate executable code corresponding to the multiple nodes.

5. The method of claim 1, wherein scheduling execution of the code represented by at least one of the multiple nodes at the at least two heterogeneous hardware resources comprises selecting a particular path of the one or more paths as a limiting path based at least partially on the topology of the graph.

6. The method of claim 5, wherein the limiting path is selected further based on a count of nodes associated with each of the one or more paths, and wherein the limiting path is a path that is associated with a largest count of nodes among the one or more paths.

7. The method of claim 5, wherein the limiting path is selected further based on a cost function associated with each node.

8. The method of claim 7, wherein the cost function of a particular node has a fixed value.

9. The method of claim 7, wherein the cost function of a particular node corresponds to an execution time associated with code represented by the particular node.

10. The method of claim 7, wherein the cost function of a particular node corresponds to power used to execute instructions corresponding to the particular node.

11. The method of claim 7, wherein the cost function of a particular node is determined based on statistical analysis of historical data associated with execution of program code that corresponds to the particular node at the computing device.

12. The method of claim 5, wherein selecting the particular path as the limiting path includes estimating a time to traverse each of the one or more paths and selecting as the limiting path a path having a longest time to traverse from the source node to the sink node among the one or more paths.

13. The method of claim 5, wherein selecting the particular path as the limiting path includes estimating power used to traverse each of the one or more paths and selecting as the limiting path a path having a particular power usage among the one or more paths.

14. The method of claim 1, wherein the cost functions associated with the one or more paths are determined based on a cost function associated with each node, a cost function associated with each edge, and a cost function associated with synchronizing paths that join at a particular node, and wherein a particular cost function associated with a particular edge accounts for data transfer constraints of the computing device.

15. An apparatus for generating, for a particular parallel hardware configuration, a program based on a graph associated with an application, the apparatus comprising:

a memory, wherein the memory is configured to store data descriptive of a graph, wherein the graph includes a first node representing a first execution task of a program, a second node representing a second execution task of the program, and an edge representing a data transfer between the first node and the second node; and

a processor configured to generate, based on the data, program code of the program, wherein the program code includes a first state indicator associated with the first node and indicating a first statefulness characteristic of the first execution task.

16. The apparatus of claim 15, wherein the first execution task is divisible into at least a first sub-task and a second sub-task, and wherein the first statefulness characteristic indicates whether the first sub-task and the second sub-task may be executed in parallel.

17. The apparatus of claim 16, wherein state data associated with the first sub-task and the second sub-task is maintained during execution of the first sub-task and the second sub-task, and wherein the statefulness characteristic indicates that the first sub-task and the second sub-task may not be executed in parallel.

18. The apparatus of claim 15, wherein the program code further includes a second state indicator associated with the second execution task and indicating a second statefulness characteristic of the second execution task, wherein the second statefulness characteristic indicates that the second execution task is stateless, and wherein the second execution task is not divisible into multiple sub-tasks.

19. An apparatus for generating, for a particular parallel hardware configuration, a program based on a graph associated with an application, the apparatus comprising:

means for storing data descriptive of a graph, wherein the graph includes a first node representing a first execution task of a program, a second node representing a second execution task of the program, and an edge representing a data transfer between the first node and the second node; and

means for generating, based on the data, program code of the program, wherein the program code includes a first state indicator associated with the first node and indicating a first statefulness characteristic of the first execution task.

20. The apparatus of claim 19, further comprising means for allocating an envelope to a requesting node of the graph, wherein the envelope includes metadata and a payload, wherein the metadata includes an envelope type indication, a transport type indication, a timestamp, or a combination thereof, and wherein the payload includes execution task results of an execution task corresponding to the requesting node of the graph.

21. The apparatus of claim 20, wherein the envelope includes a transport flag indicating access rights associated with the envelope, and wherein the transport flag indicates read-only access or read and write access.

22. The apparatus of claim 21, wherein the transport flag is automatically set to indicate read-only access in response to determining that an output pin of the requesting node is connected to multiple input pins of the graph, and wherein setting the transport flag to indicate read-only access prevents parallel nodes of the graph from modifying the envelope.