Verification of a dataflow representation of a program through static type-checking

Patent metadata

Field	Value
Publication number	US-9760348-B2
Application number	US-95491510-A
Country	US
Kind code	B2
Filing date	Nov 29, 2010
Priority date	Nov 29, 2010
Publication date	Sep 12, 2017
Grant date	Sep 12, 2017

Abstract

Functionality is described for providing a compiled program that can be executed in a parallel and a distributed manner by any selected runtime environment. The functionality includes a compiler module for producing the compiled program based on a dataflow representation of a program (i.e., a dataflow-expressed program). The dataflow-expressed program, in turn, includes a plurality of tasks that are connected together in a manner specified by a graph (such as a directed acyclic graph). The compiler module also involves performing static type-checking on the dataflow-expressed program to identify the presence of any mismatch errors in the dataflow-expressed program. By virtue of this approach, the above-described functionality can identify any errors in constructing the graph prior to its instantiation and execution in a runtime environment.

First claim

What is claimed is:

1. A method, performed by physical computing functionality, for producing a compiled program, comprising:
receiving a dataflow-expressed program, the dataflow-expressed program including a plurality of tasks connected together in a manner specified by a graph, each task having at least one input associated with a specified type and an output associated with a specified type; and
in a course of compiling the dataflow-expressed program to a compiled parallel program expressed in a parallel form that is executable by any runtime environment selected from a plurality of candidate runtime environments providing a plurality of computing resources for executing the compiled program in a parallel manner, the compiled parallel program agnostic with respect to features provided by the candidate runtime environments, performing static typechecking on the dataflow-expressed program to identify presence of any mismatch errors in the dataflow-expressed program before the dataflow-expressed program instantiation and execution in the runtime environment to ensure that the nodes of the graph connect together in a permitted manner.

2. The method of claim 1 , wherein the dataflow-expressed program expresses the graph as a directed acyclic graph (DAG), and wherein said performing static type-checking comprises statically verifying dataflow connections of the DAG.

3. The method of claim 1 , wherein each task in the dataflow-expressed program is expressed as an object that specifies each type of each respective input, and a type of the output.

4. The method of claim 1 , wherein said performing static type-checking comprises, for each task, determining whether a type associated with each input that is supplied to the task matches an expected input type.

5. The method of claim 1 , wherein said performing static type-checking comprises, for each task, determining whether a number of inputs that are supplied to the task matches an expected number of inputs.

6. The method of claim 1 , further comprising identifying and correcting any mismatch error that is identified, prior to executing the compiled program in a selected runtime environment.

7. The method of claim 1 , further comprising:
receiving at least one selection consideration;
identifying and invoking a scheduler module that is deemed appropriate for executing the compiled program based on said at least one selection consideration; and
running the compiled program in a runtime environment that is associated with the scheduler module that has been selected, as directed by the scheduler module.

8. The method of claim 7 , wherein said running comprises:
at a time of execution of a work item within the compiled program, receiving at last one condition factor;
selecting an instantiation of the work item based on said at least one condition factor; and
performing the work item using the instantiation that is selected.

9. The method of claim 8 , wherein said at least one condition factor comprises one or more of:
heuristic information that identifies a user instruction;
amount information that identifies an amount of data to be processed by the work item; or
resource information that identifies amounts and kinds of computing resources that are available to perform the work item.

10. A physical and tangible computer readable storage device, which is not a transitory propagating signal, for storing computer readable instructions, the computer readable instructions providing a type-checking module when executed by one or more processing devices, the computer readable instructions comprising:
logic configured to receive a dataflow-expressed program, the dataflow-expressed program including a plurality of tasks connected together in a manner specified by a graph, each task having at least one input associated with a specified type and an output associated with a specified type, the dataflow express program to be compiled to a compiled parallel program expressed in a parallel form that is executable by any runtime environment selected from a plurality of candidate runtime environments providing a plurality of computing resources for executing the compiled program in a parallel manner, the compiled parallel program agnostic with respect to features provided by the candidate runtime environments; and
logic configured to perform static type-checking on the dataflow-expressed program to statically verify dataflow connections in the graph before the dataflow-expressed program instantiation and execution in the runtime environment to ensure that the nodes of the graph connect together in a permitted manner,
said logic configured to perform static-checking comprising:
logic configured to determine, for each task, whether a type associated with each input that is supplied to the task matches an expected input type; and
logic configured to determine, for each task, whether a number of inputs that are supplied to the task matches an expected number of inputs.

11. The computer readable storage device of claim 10 , wherein the dataflow-expressed program expresses the graph as a directed acyclic graph.

12. The computer readable storage device of claim 10 , wherein each task in the dataflow-expressed program is expressed as an object that specifies each type of each respective input, and a type of the output.

13. An environment for producing and executing a compiled parallel program, comprising:
compilation functionality, implemented by physical computing functionality, for producing the compiled parallel program, the compilation functionality comprising:
a graph-generation module configured to provide a dataflow-expressed program, the dataflow-expressed program including a plurality of tasks connected together in a manner specified by a directed acyclic graph, each task having at least one input associated with a specified type and an output associated with a specified type; and
a compiler module configured to produce the compiled parallel program based on the dataflow-expressed program, the compiled parallel program expressed in a parallel form that is executable by the environment providing a plurality of computing resources for executing the compiled program in a parallel manner, the compiled parallel program agnostic with respect to features provided by a set of candidate runtime environments including the environment, the compiler module comprising:
a type-checking module configured to perform static type-checking on the dataflow-expressed program to identify the presence of any mismatch errors in the dataflow-expressed program before the dataflow-expressed program instantiation and execution in the environment to ensure that the nodes of the directed acyclic graph connect together in a permitted manner.

14. The environment of claim 13 , wherein the graph-generation module is configured to provide the dataflow-expressed program using application programming interface (API) resources provided by a library module.

15. The environment of claim 13 , wherein each task in the dataflow-expressed program is expressed as an object that specifies each type of each respective input, and a type of the output.

16. The environment of claim 13 , wherein the type-checking module comprises:
logic configured to determine, for each task, whether a type associated with each input that is supplied to the task matches an expected input type; and
logic configured to determine, for each task, whether a number of inputs that are supplied to the task matches an expected number of inputs.

17. The environment of claim 13 , further comprising a runtime s

Assignees

• Varadarajan Krishnan
• Chu Michael L
• Microsoft Technology Licensing Llc

Inventors

• Varadarajan Krishnan
• Chu Michael L

Classifications

• G06F8/433 Primary

  Dependency analysis; Data or control flow analysis · CPC title

• G06F8/437

  Type checking · CPC title