Method for Exploiting Massive Parallelism

A computer-implemented method of identifying and extracting mutually independent computations in a dataflow program for exploiting massive parallelism, the method comprising:

• receiving a dataflow program having a number of actors and a multiplicity of connections connecting the actors, the dataflow program providing:
• specified consumption rates on the multiplicity of connections;
• specified production rates on the multiplicity of connections;
• a specified number of initial samples on at least a part of the multiplicity of connections, the initial samples providing input for a first set of actors;
• generating, from the specified consumption rates, the specified production rates, and the specified number of initial samples, at least one model of a precedence graph for the dataflow program, the model:
• representing dependence constraints between distinct firings of the number of actors;
• having a number of vertices, having associated therewith an actor-index pair;
• having edges representing precedent constraints;
• for the at least one model:
• determining a feedback distance between multiple firings of a same actor in the model;
• determining sets of parallel regions for at least a part of the vertices of the model, such that each set of parallel regions comprises a given number of actor firings of a same actor, the given number being dependent on the determined feedback distance;
• composing mutually independent component regions, each component region comprising at least a part of one or more sets of parallel regions;
• composing one or more composite regions comprising one or more component regions and/or one or more sets of parallel regions, the composite regions being composed so as to satisfy a predetermined criteria;
• extracting composite regions from the model.

A computer program product stored in a non-transitory computer readable medium for identifying and extracting mutually independent computations in a dataflow program for exploiting massive parallelism, the computer program product comprising software instructions which, when run on a computer, causes the computer to:

• receive a dataflow program having a number of actors and a multiplicity of connections connecting the actors, the dataflow program providing:
• specified consumption rates on the multiplicity of connections;
• specified production rates on the multiplicity of connections;
• a specified number of initial samples on at least a part of the multiplicity of connections, the initial samples providing input for a first set of actors;
• generate, from the specified consumption rates, the specified production rates, and the specified number of initial samples, at least one model of a precedence graph for the dataflow program, the model:
• representing dependence constraints between distinct firings of the number of actors;
• having a number of vertices, having associated therewith an actor-index pair;
• having edges representing precedent constraints;
• for the at least one model:
• determine a feedback distance between multiple firings of a same actor in the model;
• determine sets of parallel regions for at least a part of the vertices of the model, such that each set of parallel regions comprises a given number of actor firings of a same actor, the given number being dependent on the determined feedback distance;
• compose mutually independent component regions, each component region comprising at least a part of one or more sets of parallel regions;
• compose one or more composite regions comprising one or more component regions and/or one or more sets of parallel regions, the composite regions being composed so as to satisfy a predetermined criteria;
• extract composite regions from the model.

A method of configuring a multitude of data processors to perform a process, the method comprising

• receiving a dataflow program having a number of actors and a multiplicity of connections connecting the actors, the dataflow program providing:
• specified consumption rates on the multiplicity of connections;
• specified production rates on the multiplicity of connections;
• a specified number of initial samples on at least a part of the multiplicity of connections, the initial samples providing input for a first set of actors;
• generating, from the specified consumption rates, the specified production rates, and the specified number of initial samples, at least one model of a precedence graph for the dataflow program, the model:
• representing dependence constraints between distinct firings of the number of actors;
• having a number of vertices, having associated therewith an actor-index pair;
• having edges representing precedent constraints;
• for the at least one model of the precedence graph:
• determining a feedback distance between multiple firings of a same actor in the model;
• determining sets of parallel regions for at least a part of the number of vertices of the model, such that each set of parallel regions comprises a given number of actor firings of a same actor, the given number being dependent on the determined feedback distance;
• composing mutually independent component regions, each component region comprising at least a part of one or more sets of parallel regions;
• composing one or more composite regions comprising one or more component regions and/or one or more sets of parallel regions, the composite regions being composed so as to satisfy a predetermined criteria;
• extracting composite regions from the model for performing the process and scheduling the identified and extracted mutually independent computations in the dataflow program onto the multitude of data processors.