# US 2013/0254751 A1 · Parallelism From Functional Decomposition

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0254751 A1
- Document ID: US20130254751A1
- Status: Published application
- Kind: A1
- Application number: 13/425,136
- Filed: 2012-03-20
- Published: 2013-09-26
- Earliest claimed: 2012-03-20
- Assignees: Massively Parallel Technologies, Inc.
- Inventors: Kevin D. Howard
- Web page: https://patentgrep.com/patent/US20130254751A1

## CPC

- G06F 8/20: Software design
- G06F 8/30: Creation or generation of source code
- G06F 8/34: Graphical or visual programming
- G06F 9/4498: {Finite state machines}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method for performing functional decomposition of a software design to generate a computer-executable finite state machine. Initially, the software design is received in a form wherein functions in the software design are repetitively decomposed into (1) data and control transformations. Included between the functions are control flow indicators which have transformation-selection conditions associated therewith. The data transformations and the control transformations are translated into states in the finite state machine. The transformation-selection conditions associated with the control transformations are translated into state transitions in the finite state machine.

## Claims

### Claim 1

A method for performing functional decomposition of a software design to generate a computer-executable finite state machine, the method comprising:
decomposing functions in the software design into data transformations and control transformations repetitively until each of the decomposed data transformations consists of a respective linear code block;
wherein the data transformations accept and generate data, and the control transformations evaluate conditions and send and receive control indications to and from associated instances of the data transformations;
converting the software design to a graphical diagram including a plurality of graphical symbols interconnected to hierarchically represent the data transformations and the control transformations in the software design, wherein:
a first type of the graphical symbols comprise bubble symbols indicating functional decomposition elements within the software design, and a second type of the graphical symbols comprise control flow indicators between the functions, which indicators have transformation-selection conditions associated therewith; and
the bubble symbols include control bubbles and process bubbles, wherein the control bubbles indicate the control transformations, and the process bubbles indicate the data transformations;
translating the data transformations and the control transformations into states in the finite state machine, wherein, at a given decomposition level, the first state is one of the control transformations and subsequent states each comprise a decomposed said linear code block with no control structure; and
translating the transformation-selection conditions associated with the control transformations into state transitions in the finite state machine;
wherein the translating steps are performed by a computer system.

### Claim 2 (depends on 1)

The method of claim 1, wherein the graphical diagram includes a looping structure which is indicated, by an arrow symbol, as being associated with one of the data transformations.

### Claim 3 (depends on 1)

The method of claim 1, wherein each of the functions thus decomposed receives an execution-stream identifier representing a corresponding program thread.

### Claim 4 (depends on 1)

The method of claim 1, wherein the finite state machine is an executable program constructed from the linear code blocks resulting from the transformations, and the transformation-selection conditions are the state transitions constructed from the control flow as determined from the control bubbles.

### Claim 5 (depends on 1)

The method of claim 1, wherein the data transformations accept and generate data using at least one input and one output variable, and the control transformations include only transitions with no associated code blocks.

### Claim 6 (depends on 1)

The method of claim 1, wherein the control transformations include a non-event control item comprising a condition that changes the sequence of execution of program logic within the software design.

### Claim 7 (depends on 6)

The method of claim 6, wherein each said non-event control item is selected from the list consisting of if-then-else, go to, function calls, and function returns.

### Claim 8 (depends on 1)

The method of claim 1, wherein each of the control flow indicators comprises a function-order arrow and an associated condition constituting a regular conditional expression.

### Claim 9 (depends on 1)

The method of claim 1, wherein data is passed only to a data transformation via a data store.

### Claim 10 (depends on 1)

The method of claim 1, wherein the decomposition ends when none of the data transformations can be decomposed into a set of data transformations grouped together with a control transformation.

### Claim 11 (depends on 1)

The method of claim 1, wherein the decomposition ends when the decomposition results in the same graph as the decomposed transformation.

### Claim 12 (depends on 1)

The method of claim 1, wherein:
only one said control bubble exists at each decomposition level;
each said process bubble is invoked by a control bubble;
each said process bubble transmits and receives data from a data store via a data flow;
each said control bubble receives and uses data as part of determining which said process bubble is to be called; and
each said process bubble returns control to its calling control bubble.

### Claim 13 (depends on 1)

The method of claim 1, wherein the finite state machine is generated by performing steps comprising:
comparing successive decomposition levels to determine if lower-level process bubbles are associated or un-associated, wherein the process bubbles are associated if one of the control bubbles links together a pair of the process bubbles, otherwise the process bubbles are unassociated;
wherein, for each of the lower level process bubbles that are associated:
the single control bubble that associates the process bubbles of level x forms the first state on the finite state machine of level (x+1);
each of the control bubbles at level x is translated into a state transition vector of the finite state machine of level (x+1); and
each of the process bubbles of the next lower decomposition level is translated into a state of the of the finite state machine of level (x+1);
if any of the process bubbles of level x are unassociated, then:
decomposing any non-recursively defined process bubble into a decomposed process bubble of level (x+1); and
wherein decomposition is complete when a level (x+1) decomposition consists of un-associated process bubbles.

### Claim 14 (depends on 1)

The method of claim 1, wherein processing parallelism is determined by associating, with input data of a transformation, data intent information indicating an intended use of the data, by indicating one of:
(1) particle-like usage wherein the data represents particles that move throughout a matrix,
(2) field-like usage wherein a force affects data across a large section of the matrix simultaneously;
(3) search-like usage wherein data interacts with a larger set of data, giving some result, and
(4) series expansions/contractions wherein calculation of the terms of a mathematical series is performed.

### Claim 15 (depends on 1)

The method of claim 1, wherein inputs and outputs to/from terminator blocks indicate, by inclusion of a matrix index designator, that data for a matrix is being transmitted via separate, parallel data lines.

### Claim 16 (depends on 1)

The method of claim 1, wherein processing topology is determined by associating, with input data of a transformation, information indicating the preferred topology for executing the finite state machine.

### Claim 17 (depends on 1)

The method of claim 1, wherein processing parallelism is determined by associating, with input data of a transformation, data intent information indicating an intended use of the data.

### Claim 18

A method for performing functional decomposition of a software design to generate a computer-executable finite state machine, the method comprising:
receiving the software design in the form of a graphical diagram including a plurality of graphical symbols interconnected to hierarchically represent the data transformations and the control transformations in the software design, wherein:
the software design is in a form wherein functions in the software design are repetitively decomposed into data transformations and control transformations until each of the data transformations consists of a respective linear code block; wherein the data transformations accept and generate data, and the control transformations evaluate conditions and send and receive control indications to and from the data transformations;
a first type of the graphical symbols comprise bubble symbols indicating functional decomposition elements within the software design, a second type of the graphical symbols comprise control flow indicators between the functions, which indicators have transformation-selection conditions associated therewith; and
the bubble symbols include control bubbles and process bubbles, wherein the control bubbles indicate the control transformations, and the process bubbles indicate the data transformations;
translating the data transformations and the control transformations into states in the finite state machine, wherein, at a given decomposition level, the first state is one of the control transformations and subsequent states each comprise a decomposed said linear code block with no control structure; and
translating the transformation-selection conditions associated with the control transformations into state transitions in the finite state machine;
wherein the translating steps are performed by a computer system.

### Claim 19 (depends on 18)

The method of claim 18, wherein the graphical diagram includes a looping structure which is indicated, by an arrow symbol, as being associated with one of the data transformations.

### Claim 20 (depends on 18)

The method of claim 18, wherein each of the functions thus decomposed receives an execution-stream identifier representing a corresponding program thread.

### Claim 21 (depends on 18)

The method of claim 18, wherein the finite state machine is an executable program constructed from the linear code blocks resulting from the transformations, and the transformation-selection conditions are the state transitions constructed from the control flow as determined from the control bubbles.

### Claim 22 (depends on 18)

The method of claim 18, wherein the data transformations accept and generate data using at least one input and one output variable, and the control transformations include only transitions with no associated code blocks.

### Claim 23 (depends on 18)

The method of claim 18, wherein the control transformations include a non-event control item comprising a condition that changes the sequence of execution of program logic within the software design.

### Claim 24 (depends on 23)

The method of claim 23, wherein each said non-event control item is selected from the list consisting of if-then-else, go to, function calls, and function returns.

### Claim 25 (depends on 18)

The method of claim 18, wherein each of the control flow indicators comprises a function-order arrow and an associated condition constituting a regular conditional expression.

### Claim 26 (depends on 18)

The method of claim 18, wherein data is passed only to a data transformation via a data store.

### Claim 27 (depends on 18)

The method of claim 18, wherein the decomposition ends when none of the data transformations can be decomposed into a set of data transformations grouped together with a control transformation.

### Claim 28 (depends on 18)

The method of claim 18, wherein the decomposition ends when the decomposition results in the same graph as the decomposed transformation.

### Claim 29 (depends on 18)

The method of claim 18, wherein:
only one said control bubble exists at each decomposition level;
each said process bubble is invoked by a control bubble;
each said process bubble transmits and receives data from a data store via a data flow;
each said control bubble receives and uses data as part of determining which said process bubble is to be called; and
each said process bubble returns control to its calling control bubble.

### Claim 30 (depends on 18)

The method of claim 18, wherein the finite state machine is generated by performing steps comprising:
comparing successive decomposition levels to determine if lower-level process bubbles are associated or un-associated, wherein the process bubbles are associated if one of the control bubbles links together a pair of the process bubbles, otherwise the process bubbles are unassociated;
wherein, for each of the lower level process bubbles that are associated:
the single control bubble that associates the process bubbles of level x forms the first state on the finite state machine of level (x+1);
each of the control bubbles at level x is translated into a state transition vector of the finite state machine of level (x+1); and
each of the process bubbles of the next lower decomposition level is translated into a state of the of the finite state machine of level (x+1);
if any of the process bubbles of level x are unassociated, then:
decomposing any non-recursively defined process bubble into a decomposed process bubble of level (x+1); and
wherein decomposition is complete when a level (x+1) decomposition consists of un-associated process bubbles.

### Claim 31 (depends on 18)

The method of claim 18, wherein processing parallelism is determined in part by associating, with input data of a transformation, data intent information indicating an intended use of the data, by indicating of one of:
(1) particle-like usage wherein the data represents particles that move throughout a matrix,
(2) field-like usage wherein a force affects data across a large section of the matrix simultaneously;
(3) search-like usage wherein data interacts with a larger set of data, giving some result, and
(4) series expansions/contractions wherein calculation of the terms of a mathematical series is performed.

### Claim 32 (depends on 18)

The method of claim 18, wherein inputs and outputs to/from terminator blocks indicate, by inclusion of a matrix index designator, that data for a matrix is being transmitted via separate, parallel data lines.

### Claim 33 (depends on 18)

The method of claim 18, wherein processing topology is determined by associating, with input data of a transformation, information indicating the preferred topology for executing the finite state machine.

### Claim 34 (depends on 18)

The method of claim 18, wherein processing parallelism is determined by associating, with input data of a transformation, data intent information indicating an intended use of the data.

### Claim 35

A method for performing functional decomposition of a software design to generate a computer-executable finite state machine, the method comprising:
receiving the software design in a form wherein:
functions in the software design are repetitively decomposed into data transformations that accept and generate data, and control transformations that evaluate conditions and send and receive control indications to and from the data transformations; and
control flow indicators are included between the functions, which indicators have transformation-selection conditions associated therewith;
translating the data transformations and the control transformations into states in the finite state machine, wherein, at a given decomposition level, the first said state is one of the control transformations and subsequent said states each comprise a decomposed said linear code block with no control structure; and
translating the transformation-selection conditions associated with the control transformations into state transitions in the finite state machine.

### Claim 36 (depends on 35)

The method of claim 35, wherein the graphical diagram includes a looping structure which is indicated, by an arrow symbol, as being associated with one of the data transformations.

### Claim 37 (depends on 35)

The method of claim 35, wherein each of the functions thus decomposed receives an execution-stream identifier representing a corresponding program thread.

### Claim 38 (depends on 35)

The method of claim 35, wherein the finite state machine is an executable program constructed from the linear code blocks resulting from the transformations, and the transformation-selection conditions are the state transitions constructed from the control flow as determined from the control bubbles.

### Claim 39 (depends on 35)

The method of claim 35, wherein the data transformations accept and generate data using at least one input and one output variable, and the control transformations include only transitions with no associated code blocks.

### Claim 40 (depends on 35)

The method of claim 35, wherein the control transformations include a non-event control item comprising a condition that changes the sequence of execution of program logic within the software design.

### Claim 41 (depends on 40)

The method of claim 40, wherein each said non-event control item is selected from the list consisting of if-then-else, go to, function calls, and function returns.

### Claim 42 (depends on 35)

The method of claim 35, wherein each of the control flow indicators comprises a function-order arrow and an associated condition constituting a regular conditional expression.

### Claim 43 (depends on 35)

The method of claim 35, wherein data is passed only to a data transformation via a data store.

### Claim 44 (depends on 35)

The method of claim 35, wherein the decomposition ends when none of the data transformations can be decomposed into a set of multiple data transformations grouped together with a control transformation.

### Claim 45 (depends on 35)

The method of claim 35, wherein the decomposition ends when the decomposition results in the same graph as the decomposed transformation.

### Claim 46 (depends on 35)

The method of claim 35, wherein:
only one said control bubble exists at each decomposition level;
each said process bubble is invoked by a control bubble;
each said process bubble transmits and receives data from a data store via a data flow;
each said control bubble receives and uses data as part of determining which said process bubble is to be called; and
each said process bubble returns control to its calling control bubble.

### Claim 47 (depends on 35)

The method of claim 35, wherein the finite state machine is generated by performing steps comprising:
comparing successive decomposition levels to determine if lower-level process bubbles are associated or un-associated, wherein the process bubbles are associated if one of the control bubbles links together a pair of the process bubbles, otherwise the process bubbles are unassociated;
wherein, for each of the lower level process bubbles that are associated:
the single control bubble that associates the process bubbles of level x forms the first state on the finite state machine of level (x+1);
each of the control bubbles at level x is translated into a state transition vector of the finite state machine of level (x+1); and
each of the process bubbles of the next lower decomposition level is translated into a state of the of the finite state machine of level (x+1);
if any of the process bubbles of level x are unassociated, then:
decomposing any non-recursively defined process bubble into a decomposed process bubble of level (x+1); and
wherein decomposition is complete when a level (x+1) decomposition consists of un-associated process bubbles.

### Claim 48 (depends on 35)

The method of claim 35, wherein processing parallelism is determined by associating, with input data of a transformation, data intent information indicating an intended use of the data, by indicating of one of:
(1) particle-like usage wherein the data represents particles that move throughout a matrix,
(2) field-like usage wherein a force affects data across a large section of the matrix simultaneously;
(3) search-like usage wherein data interacts with a larger set of data, giving some result, and
(4) series expansions/contractions wherein calculation of the terms of a mathematical series is performed.

### Claim 49 (depends on 35)

The method of claim 35, wherein inputs and outputs to/from terminator blocks indicate, by inclusion of a matrix index designator, that data for a matrix is being transmitted via separate, parallel data lines.

### Claim 50 (depends on 35)

The method of claim 35, wherein processing topology is determined by associating, with input data of a transformation, information indicating the preferred topology for executing the finite state machine.

### Claim 51 (depends on 35)

The method of claim 35, wherein processing parallelism is determined by associating, with input data of a transformation, data intent information indicating an intended use of the data.