Managing invocation of tasks

Patent metadata

Field	Value
Publication number	US-10310864-B2
Application number	US-201715685339-A
Country	US
Kind code	B2
Filing date	Aug 24, 2017
Priority date	Sep 2, 2014
Publication date	Jun 4, 2019
Grant date	Jun 4, 2019

Abstract

A graph-based program specification includes components, at least one having at least one input port for receiving a collection of data elements, or at least one collection type output port for providing a collection of data elements. Executing a program specified by the graph-based program specification at a computing node, includes: receiving data elements of a first collection into a first storage in a first order via a link connected to a collection type output port of a first component and an input port of a second component, and invoking a plurality of instances of a task corresponding to the second component to process data elements of the first collection, including retrieving the data elements from the first storage in a second order, without blocking invocation of any of the instances until after any particular instance completes processing one or more data elements.

First claim

What is claimed is:

1. A method for parallel processing of data in a multiple processor computing system, the method including:
storing a graph-based program specification including a plurality of components corresponding to tasks and links between ports of the components, at least some of the plurality of components each having at least one of:
(1) at least one input port for receiving a collection of data elements to be processed by a corresponding task, or
(2) at least one collection type output port for providing a collection of data elements to be processed by a task corresponding to a component linked to the collection type output port; and

executing a program specified by the graph-based program specification, the executing including:
receiving two or more data elements of a particular collection of data elements in a first order via a link connected to a collection type output port of a first component of the plurality of components and an input port of a second component of the plurality of components, and
instantiating a plurality of runners as processes or process threads in the multiple processor computing system with at least some of the runners being configured for concurrent execution, and invoking a plurality of instances of a task corresponding to the second component, wherein invoking each instance of a task includes executing said instance in the context of a runner of the plurality of runners, including invoking each instance of the plurality of instances to begin processing a particular received data element of the particular collection of data elements in response to receiving that particular received data element, and including invoking the instances in a second order, without blocking invocation of any of the instances for any particular instance to begin or complete processing one or more data elements,
wherein the second order is different from the first order.

2. The method of claim 1 wherein invoking one or more instances of the task corresponding to the second component includes invoking a plurality of instances of the task corresponding to the second component.

3. The method of claim 2 wherein invoking the plurality of instances of the task corresponding to the second component includes invoking a plurality of sequentially executing instances of the task corresponding to the second component.

4. The method of claim 2 wherein invoking a plurality of instances of the task corresponding to the second component includes invoking a plurality of concurrently executing instances of the task corresponding to the second component.

5. The method of claim 4 wherein each instance of the task of the plurality of instances of the task corresponding to the second component corresponds to a different, non-overlapping subset of the particular collection of data elements.

6. The method of claim 5 wherein each different, non-overlapping subset of the particular collection of data includes a single data element.

7. The method of claim 1 wherein the input port of the second component is a collection type input port for receiving a collection of data elements to be processed by the task corresponding to the second component, and invoking one or more instances of the task corresponding to the second component includes invoking a single instance of the task corresponding to the second component.

8. The method of claim 7 wherein the single instance of the task corresponding to the second component processes the data elements of the particular collection of data elements iteratively.

9. The method of claim 1 wherein the executing further includes generating an output including a first number of data elements that is the same as a second number of data elements in the particular collection.

10. The method of claim 9 wherein the two or more data elements of the particular collection of data elements are received into a first storage, and the executing further includes providing the output to a second storage in a third order that is independent of the first order of the particular collection of data elements.

11. The method of claim 1 wherein the executing further includes generating an output including a first number of data elements that is different from a second number of data elements in the particular collection.

12. The method of claim 1 wherein at least some of the plurality of components each have
at least one scalar type input port for receiving a single data element to be processed by a corresponding task, and
at least one scalar type output port for providing a single data element to be processed by a task corresponding to a component linked to the scalar type output port; and
executing the program specified by the graph-based program specification further includes:
receiving a single data element at a scalar type input port of a third component of the plurality of components from a scalar type output port of a fourth component of the plurality of components via a link connecting the scalar type output port to the scalar type input port; and
invoking an instance of a task corresponding to the third component in response to receiving the single data element at the scalar type input port.

13. The method of claim 12 wherein executing the program specified by the graph-based program specification further includes preventing invocation of the task corresponding to the third component until after the single data element is received at the scalar type input port.

14. The method of claim 12 wherein executing the program specified by the graph-based program specification further includes preventing invocation of tasks corresponding to components depending, both directly and indirectly, from the third component until after the single data element is received at the scalar type input port.

15. The method of claim 1 further including determining the presence of the link connected to the collection type output port of the first component and the input port of the second component, the presence of said link signaling that the data elements within the first collection can be reordered.

16. A non-transitory computer-readable medium having software stored thereon, the software including instructions for causing a parallel computing system to:
store a graph-based program specification including a plurality of components corresponding to tasks and links between ports of the components, at least some of the plurality of components each having at least one of:
(1) at least one input port for receiving a collection of data elements to be processed by a corresponding task, or
(2) at least one collection output port for providing a collection of data elements to be processed by a task corresponding to a component linked to the collection output port; and

execute a program specified by the graph-based program specification, the executing including
receiving two or more data elements of a particular collection of data elements in a first order via a link connected to a collection type output port of a first component of the plurality of components and an input port of a second component of the plurality of components, and
instantiating a plurality of runners as processes or process threads in the multiple processor computing system with at least some of the runners being configured for concurrent execution, and invoking a plurality of instances of a task corresponding to the second component, wherein invoking each instance of a task includes executing said instance in the context of a runner of the plurality of runners, including invoking each instance of the plurality of instances to

Assignees

• Ab Initio Technology Llc

Inventors

• Stanfill Craig W
• Shapiro Richard
• Kukolich Stephen A
• Wholey Iii Joseph Skeffington

Classifications

• G06F9/4494 Primary

  data driven · CPC title

• G06F8/34

  Graphical or visual programming · CPC title

• G06F9/465

  Distributed object oriented systems (remote method invocation [RMI] G06F9/548) · CPC title

• G06F9/4482

  Procedural · CPC title

• G06F9/46

  Multiprogramming arrangements · CPC title