Parallelism From Functional Decomposition

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.

What is claimed is: 
     
         1 . A method for performing functional decomposition to generate a computer-executable finite state machine (FSM), the method comprising:
 receiving, via manual interaction by a user, a graphical diagram of a software design,
 the software design comprising functions that are repetitively decomposed into hierarchical sub-functions including data transformations and control transformations until each of the data transformations consists of a respective linear code block, 
 the graphical diagram comprising hierarchical decomposition levels each respectively representing the sub-functions, each decomposition level comprising:
 a control bubble indicating the control transformations within the software design, 
 a process bubble indicating the data transformations within the software design, and 
 a control flow indicator between the control and process bubbles having a transformation-selection condition associated therewith; 
 
   translating the graphical diagram into a graphical FSM diagram wherein:
 at each of the decomposition levels, the control bubble is a first state indicator in the FSM diagram, the process bubble is a subsequent state indicator in the FSM diagram, and 
 the control flow indicator is a state transition indicator in the graphical FSM diagram; and 
   receiving a manipulation by the user of at least one of the graphical diagram and graphical FSM diagram.   
     
     
         2 . The method of  claim 1 , further comprising generating an FSM as an executable program constructed from the linear code blocks, wherein state transition-selection conditions associated with the control flow indicatorsare state transitions within the FSM. 
     
     
         3 . The method of  claim 1 , the graphical diagram further comprising a looping structure associated with at least one of the process bubbles. 
     
     
         4 . The method of  claim 1 , the process bubble comprising at least one of associated process bubbles and an unassociated process bubble; wherein the process bubbles are associated if the control bubble links together a pair of the process bubbles, otherwise the process bubbles are unassociated. 
     
     
         5 . The method of  claim 4 , the hierarchical decomposition levels comprising a higher-level decomposition level and a lower level decomposition level; wherein if the higher-level decomposition level includes a looping structure, each unassociated process bubble within the lower-level decomposition level is automatically given the same looping structure. 
     
     
         6 . The method of  claim 1 , the graphical diagram further comprising an execution-stream identifier representing a corresponding program thread of each respective function. 
     
     
         7 . 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. 
     
     
         8 . 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. 
     
     
         9 . The method of  claim 8 , wherein each said non-event control item is selected from the list consisting of if-then-else, go to, function calls, and function returns. 
     
     
         10 . 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. 
     
     
         11 . The method of  claim 1 , wherein data is passed only to a data transformation via a data store. 
     
     
         12 . The method of  claim 1 , wherein the lowest level of the hierarchical decomposition levels indicates that none of the data transformations represented in the lowest level can be decomposed into a set of data transformations grouped together with a control transformation. 
     
     
         13 . 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.   
     
     
         14 . The method of  claim 1 , further comprising determining processing topology by associating, with input data of at least one of the control and process transformations, information indicating the preferred topology for executing the finite state machine. 
     
     
         15 . The method of  claim 1 , further comprising determining processing parallelism by associating, with input data of at least one of the control and process transformations, data intent information indicating an intended use of the data.