Simultaneous data-driven and demand-driven computational model for dynamically configured systems

• US 5,249,274 A
• Filed: 10/24/1990
• Issued: 09/28/1993
• Est. Priority Date: 10/24/1990
• Status: Expired due to Fees

• Current Assignee: Vanderbilt University
• Original Assignee: Vanderbilt University
• Inventors: Sztipanovits, Janos, Karsai, Gabor, Biegl, Csaba
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): Loomis, John C.
• Application Number:
  US07/602,961
• Time in Patent Office: 1,070 Days
• Field of Search: 364/200, 364/900, 364/DIG. 1, 364/DIG. 2, 395/600, 395/650, 395/700, 395/200, 395/325, 395/375, 395/800, 395/700 MS File
• US Class Current: 712/201
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083

Abstract

In a model-based dynamically configured system, various processing components are created dynamically, interfaced to each other, and scheduled upon demand. A combination of data driven and demand-driven scheduling techniques are used to enhance the effectiveness of the dynamically configured system.

Claims

1. A method for effecting the transfer of data for use in a model-based dynamically configured system having

a set of connection specifications defining a data flow path having actor nodes and data nodes, wherein data propagates in a forward direction through said data flow path and requests propagate in a reverse direction through said data flow path,

each actor node operating upon received data from data nodes in accordance with a predefined series of instructions, and

each data node acting to receive data from actor nodes, and to store and transmit said data;

said method for effecting the transfer of data through the model comprising the steps of

propagating data from data nodes operating in a data driven mode of operation to connecting actor nodes according to said connection specification as data is available for transmission from each said data driven data node;

propagating data from data nodes operating in a demand driven mode of operation to connecting actor nodes according to said connection specification as data is available for transmission at each of said demand driven data nodes only if said data node has a request, and

simultaneously with said propagating data steps, propagating requests from said actor nodes to said connected data nodes according to said connection specification as said actor nodes generate said request.

2. The method of claim 1 wherein said step of propagating data from data nodes operating in a data driven mode of operation to actor nodes and said step of propagating data from data nodes operating in a demand driven mode of operation to actor nodes comprise the steps of:

storing a data propagation enable flag at each of said data nodes;

storing an outstanding request counter at each of said data nodes;

propagating data immediately from each said data node having data available for transmission to connected actor nodes if the data propagation enable flag of said data node is in a first set state; and

storing available data at each said data node if said data propagation enable flag of said data node is in a second clear state, and propagating said data to a said connected actor node only if the outstanding request counter of said data node is in a first selected state.

3. The method of claim 2 further comprising, after propagating a request from a requesting actor node to a request-receiving data node, the steps of:

propagating said request from said request-receiving data node to at least one connecting request-receiving actor node according to said connection specification if said request-receiving data node does not have the requested data; and

propagating said data from said request-receiving data node to said requesting actor node if said request-receiving data node has the requested data.

4. The method of claim 3 further comprising, after propagating said request from said request-receiving data node to said connected request-receiving actor node, the steps of

executing said request-receiving actor node, if said actor node has the requested data, and

delaying the execution of said request-receiving actor node when less than all of the data required for complete actor node operation is available to said request-receiving actor node.

5. The method of claim 2 further comprising the steps of:

storing an outstanding request counter at each of said actor nodes;

incrementing said request counter of a requesting actor node when said requesting actor node propagates a request; and

decrementing said request counter of said requesting actor node when the requested data is received by the requesting actor node.

6. The method of claim 2 wherein said data flow path further comprises

at least one actor node input port to which a connected data node directs data to be sent to an associated connected actor node;

each actor node input port having an actor node input port request counter, and

wherein said method further comprises the steps of;

incrementing the actor node input port request counter of a requesting actor node when said requesting actor node propagates a request to a request-receiving data node,

incrementing the data node request counter of said request-receiving data node when said request-receiving data node receives said request from said requesting actor node,

decrementing said data node request counter when said request-receiving data node propagates data to said requesting actor node; and

decrementing said actor node input port request counter when said requesting actor node receives the data which satisfies said request.

7. The method of claim 6 wherein said data flow path further comprises;

at least one actor node output port from which said actor node directs data to be sent to a connected data node; and

wherein said method further comprises the step of;

controlling the flow of data in said data flow path by incrementing and decrementing said data node request counter and said actor node input port request counter.

8. The method of claim 6 wherein said data flow path further comprises

at least one actor node output port from which an associated actor node directs data to be sent to a connected data node;

each actor node output port having an actor node output port request counter, and

wherein said method further comprises the steps of;

incrementing the data node request counter of a requesting data node when said requesting data node sends a request to a said request-receiving actor node;

incrementing the actor node output port request counter of said request-receiving actor node when said request-receiving actor node receives a said request from said requesting data node,

decrementing said actor node output port request counter when said request-receiving actor node propagates data to said requesting data node;

decrementing said data node request counter when said requesting data node receives the data which satisfies said request.

9. The method of claim 6 further comprising the step of

propagating a request from a requesting actor node to a connected data node if the value of said actor node input port request counter is greater than the value of the request counter of said connected data node.

10. For use in a model-based dynamically configured system comprising

a set of connection specifications defining a data flow path having actor nodes and data nodes, wherein data propagates in a forward direction through said data flow path and requests propagate in a reverse direction through said data flow path,

each actor node operating upon received data from data nodes in accordance with a predefined series of instructions, and

each data node acting to receive data from actor nodes, and store and transmit said data;

apparatus for effecting the transfer of data through the model comprising

means for propagating data from data nodes operating in a data driven mode of operation to connecting actor nodes according to said connection specification as data is available for transmission from each said data driven data node;

means for propagating data from data nodes operating in a demand driven mode of operation to connecting actor nodes according to said connection specification as data is available for transmission at each of said demand driven data nodes only if said data node has a request, and

means for propagating requests, simultaneously with said means for propagating data, from said actor nodes to said connected data nodes according to said connection specification as said actor nodes generate said requests.

11. The apparatus of claim 10 wherein said means for propagating data from data nodes operating in a data driven mode of operation to actor nodes and said means for propagating data operating in a demand driven mode of operation from data nodes to actor nodes comprise:

means for storing a data propagation enable flag at each of said data nodes;

means for storing an outstanding request counter at each of said data nodes;

means for propagating data immediately from each said data node having data available for transmission to connected actor nodes if the data propagation enable flag of said data node is in a first set state; and

means for storing available data at each said data node if said data propagation enable flag of said data node is in a second clear state, and propagating said data to a said connected actor node only if the outstanding request counter of said data node is in a first selected state.

12. The apparatus of claim 11 further comprising, after propagating a request from a requesting actor node to a request-receiving data node:

means for propagating said request from said request-receiving data node to at least one connecting request-receiving actor node according to said connection specification if said request-receiving data node does not have the requested data; and

means for propagating said data from said request-receiving data node to said requesting actor node if said request-receiving data node has the requested data.

13. The apparatus of claim 12 further comprising, after propagating said request from said request-receiving data node to said connected request-receiving actor node,

means for executing said request-receiving actor node, if said actor node has the requested data, and

means for delaying the execution of said request-receiving actor node when less than all of the data required for complete actor node operation is available to said request-receiving actor node.

14. The apparatus of claim 11 further comprising:

an outstanding request counter at each of said actor nodes;

means for incrementing said request counter of a requesting actor node when said requesting actor node propagates a request, and

means for decrementing said request counter of said requesting actor node when the requested data is received by the requesting actor node.

15. The apparatus of claim 11 wherein said data flow path further comprises

at least one actor node input port to which a connected data node directs data to be sent to an associated connected actor node;

each actor node input port having an actor node input port request counter, and

said apparatus further comprising

means for incrementing the actor node input port request counter of a requesting actor node when said requesting actor node propagates a request to a request-receiving data node;

means for incrementing the data node request counter of said request-receiving data node when said request-receiving data node receives said request from said requesting actor node,

means for decrementing said data node request counter when said request-receiving data node propagates data to said requesting actor node; and

means for decrementing said actor node input port request counter when said requesting actor node receives the data which satisfies said request.

16. The apparatus of claim 15 wherein said data flow path further comprises

at least one actor node input port to which a connected data node directs data to be sent;

at least one actor node output port from which said actor node directs data to be sent to a connected data node; and

said apparatus further comprising

means for controlling the flow of data in said data flow path by incrementing and decrementing said data node request counter and said actor node input port request counter.

17. The apparatus of claim 15 wherein said data flow path further comprises:

at least one actor node output port from which an associated actor node directs data to be sent to a connected data node;

each actor node output port having an actor node output port request counter, and

wherein said apparatus further comprises;

means for incrementing the data node request counter of a requesting data node when said requesting data node sends a request to a said request-receiving actor node;

means for incrementing the actor node output port request counter of said request-receiving actor node when said request-receiving actor node receives a said request from said requesting data node,

means for decrementing said actor node output port request counter when said request-receiving actor node propagates data to said requesting data node;

means for decrementing said data node request counter when said requesting data node receives the data which satisfies said request.

18. The apparatus of claim 15 further including means for propagating a request from a requesting actor node to a connected data node only if the value of said actor node input port request counter is greater than the value of the request counter of said connected data node.