ITERATION SUPPORT IN A HETEROGENEOUS DATAFLOW ENGINE

• US 20150007182A1
• Filed: 06/27/2013
• Published: 01/01/2015
• Est. Priority Date: 06/27/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rossbach, Chris John, Currey, Jonathan J.
• Granted Patent: US 9,424,079 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

Various embodiments provide techniques and constructs to improve execution speed of distributed iterative computation using heterogeneous specialized resources including, for example, processors and accelerators. Iteration over an arbitrary sub-graph without loop unrolling including for algorithms with data-dependent loop termination and large iteration counts, including as a result of nested iteration, are supported in a resource-efficient manner without adding vertices to a dataflow graph to represent iteration constructs. Instead, some or all of the existing vertices within the sub-graph that is to be iterated upon based on having additional and/or modified ports and channels associated with them.

Claims

1. A system comprising:

at least one computing device;

an accelerator associated with the at least one computing device; and

an application programming interface (API) to expose the accelerator for iterative dataflow, wherein iterative dataflow is controlled based at least on an iteration state representing a loop count or a predicate of a computation, the API including;

a multiport configured to;

accept datablocks as input from a plurality of input channels; and

dequeue a datablock from an input channel of the plurality of input channels;

an iterator port configured to maintain the iteration state of the computation associated with the datablock that was dequeued; and

a scheduler configured to provide the datablock to the accelerator based at least on the iteration state.

2. A system as claim 1 recites, wherein each input channel has an assigned priority and the datablock is dequeued from the input channel of the plurality of input channels based, at least in part, on the assigned priorities of the input channels.

3. A system as claim 1 recites, wherein the iterator port is further configured to propagate control signals when an iteration begins or ends.

4. A system as claim 3 recites, wherein the datablock includes a control code defining the control signals to control when the iteration begins or ends and the application programming interface further includes a module to specify a control-propagation pair that controls propagation of the control code received at a first port to a second port.

5. A method comprising:

receiving identifiers of a plurality of accelerators associated with a computing device, the plurality of accelerators being available to perform accelerator tasks;

receiving a plurality of accelerator tasks at a multiport of the computing device, wherein an accelerator task has an affinity towards one or more of the accelerators and wherein the plurality of accelerator tasks include an iterative computation;

determining, by the computing device, an accelerator task from the plurality of accelerator tasks that is ready for execution based at least on an iteration state;

determining from the plurality of accelerators, one or more accelerators that supports the iterative computation that is ready for execution;

providing, by the computing device, the accelerator task that is ready for execution to one of the determined one or more accelerators, wherein, when the accelerator task that is ready for execution includes the iterative computation, the providing includes providing the iterative computation to a determined accelerator that supports the iterative computation; and

receiving, by the computing device, at least one result from the one of the one or more determined accelerators.

6. A method as claim 5 recites, wherein the determined accelerator that supports the iterative computation, supports the iterative computation for a data-dependent termination criterion.

7. A method as claim 5 recites, wherein the plurality of accelerator tasks are represented by a graph with a node corresponding to each accelerator task, and the iterative computation is represented by a sub-graph with at least one edge corresponding to a dataflow according to iteration of the sub-graph.

8. A method as claim 7 recites, wherein the determined accelerator that supports the iterative computation, supports the iterative computation without repeating iteration of the sub-graph for each iteration.

9. A method as claim 5 recites, further comprising, representing the plurality of accelerator tasks in a graph including a plurality of nodes and a plurality of edges, wherein a node of the plurality of nodes corresponds to the accelerator task that is ready for execution and an edge of the plurality of edges corresponds to a channel that connects two nodes of the plurality of nodes to carry a flow of data as a plurality of datablocks between two of the plurality of accelerator tasks.

10. A method as claim 5 recites, wherein the determined accelerator that supports the iterative computation without unrolling a loop representing the iterative computation.

11. A method as claim 5 recites, further comprising propagating control signals when an iteration begins or ends.

12. One or more computer storage media having computer executable instructions recorded thereon, the computer-executable instructions, upon execution, to configure a computer for iterative dataflow with modules comprising:

a graph module configured to represent a plurality of accelerator tasks in a graph including a plurality of nodes and a plurality of edges, wherein a node of the plurality of nodes corresponds to an accelerator task and an edge of the plurality of edges corresponds to a channel that connects two nodes of the plurality of nodes to carry a flow of data as a plurality of datablocks between two of the plurality of accelerator tasks;

a multiport module configured with connections for a plurality of channels in which the plurality of datablocks are queued for input to the multiport, and configured to dequeue an available datablock of the plurality of datablocks according to an assigned priority of the channel in which the available datablock is queued for input to the multiport; and

an iterator port module configured to maintain an iteration state.

13. One or more computer storage media as claim 12 recites, wherein the iterator port module is further configured to maintain a list of ports within a scope of the iterator port module, and to signal the ports on the list of ports of a change to the iteration state.

14. One or more computer storage media as claim 12 recites, wherein the iterator port module is further configured to propagate control signals along control propagation paths.

15. One or more computer storage media as claim 14 recites, further comprising a predicated channel module configured to evaluate a predicate, wherein the predicate includes a data-dependent criterion, and when the predicated channel module is further configured for backward-forward passing, a combination of the iterator port module and the predicated channel module are configured to conditionally route data to one of:

backward to a beginning of another iteration, or

forward in the graph when a loop completes.

16. One or more computer storage media as claim 12 recites, further comprising a control signal module configured to annotate at least one datablock of the plurality of datablocks with a control code to control a flow of the data between memories of accelerators for performance on the data of respective accelerator tasks of the plurality of accelerator tasks by indicating the channel in which the at least one datablock of a plurality of datablocks is to be queued.

17. One or more computer storage media as claim 16 recites, wherein the iterator port module is further configured to propagate control signals according to the control code when iteration begins or ends.

18. One or more computer storage media as claim 12 recites, further comprising an initializer channel module configured to provide an initial value datablock to initiate an iteration.

19. One or more computer storage as claim 12 recites, further comprising a predicated channel module configured to evaluate a predicate, wherein the predicate includes a data-dependent criterion.

20. One or more computer storage media as claim 19 recites, wherein the predicated channel module is further configured to:

pass the available datablock through a predicated channel to a connected node when the predicate holds for the available datablock, and

when the predicate does not hold for the available datablock, cause an action including one of dropping the available datablock from the predicated channel or queuing the available datablock for re-evaluation.