DISTRIBUTED COMPUTING ENVIRONMENT USING REAL-TIME SCHEDULING LOGIC AND TIME DETERMINISTIC ARCHITECTURE

• US 20030140172A1
• Filed: 05/19/1999
• Published: 07/24/2003
• Est. Priority Date: 05/26/1998
• Status: Active Grant

• Current Assignee: Dow Global Technologies, Inc. (Dow, Inc.)
• Original Assignee: Dow Global Technologies, Inc. (Dow, Inc.)
• Inventors: WOODS, RANDY D., DUPREE, WAYNE P., VERNIERS, GERRIT H., FERNANDEZ, GEORGE P., JACHIM, DAVID M., CHURCHILL, STEPHEN G.
• Granted Patent: US 6,748,451 B2
• Time in Patent Office: Days
• US Class Current: 709/248
• CPC Class Codes: G04G 15/006 for operating at a number of different times cigar or cigarette receptacles or boxes with means for limiting the frequency of smoking A24F15/005
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: H04J 3/0638 Clock or time synchronisation among nodes; Internode synchronisation synchronization for ring networks H04L12/422; data switching networks with synchronous transmission H04L12/43
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests

Abstract

A system is presented for a plurality of computer nodes in mutual data communication to execute logic in a coordinated manner. The approach features aligning the definition of the time in the nodes so that each node has essentially the same definition of time; defining a schedule of communications for each computer node, with the schedule having future moments defined for initiating each communication; communicating each schedule to its respective node; and initiating each communication at the time defined in the schedule. The computer network has a message carrier supporting multiple communication paths; a plurality of computers coupled to the message carrier, a clock system for maintaining time synchronism among the computers; and a scheduler coupled to the message carrier for determining the sequence of communication between the computers. The message carrier establishes communication between selected computers based on the time-deterministic tasks being performed by the computers. A computer node in the plurality of computer nodes executes logic in coordination with the other nodes by defining a communication request list of each communication needed by the computer node with any other computer node respective to a future time period, sending the communication request list to the master scheduler, receiving back a communication schedule back from the master scheduler, defining a local task schedule from the communication schedule, and then executing the communication at the scheduled time.

Claims

1. A computer implemented method for enabling a plurality of computer nodes in mutual data communication to execute logic in a coordinated manner, comprising:

aligning real-time time between said plurality of computer nodes so that each computer node has essentially the same real-time time;

defining a schedule of communications for each computer node, said schedule having a different time in the future defined for initiating each respective communication;

communicating each schedule to its respective computer node; and

initiating each communication from each node at the time defined in its schedule.

2. A computer network architecture, comprising:

a message carrier supporting multiple communication paths;

a plurality of computers coupled to said message carrier, said computers being programmed to perform time-deterministic tasks by cycling through a plurality of different operating states, including a communication state;

a clock system accessible by all said computers for maintaining time synchronism among said computers; and

a scheduler coupled to said message carrier for determining the sequence of communication between said computers by causing said message carrier to establish communication between selected computers based on said time-deterministic tasks being performed by said computers.

3. A computer implemented method for enabling a computer node in a plurality of computer nodes to execute logic in coordination with the other nodes in said plurality of computer nodes, comprising:

connecting a message carrier to each computer node in said plurality of computer nodes;

providing master scheduling capability in one computer node to establish a master scheduler;

defining, in each computer node, a communication request list of each communication needed by said computer node with any other computer node respective to a future time period;

sending said communication request list from each computer node to said master scheduler via said message carrier;

receiving, in each computer node, a communication schedule from said master scheduler via said message carrier;

defining, in each computer node, a local task schedule from said communication schedule.

4. A computer implemented method for enabling a plurality of member nodes to execute logic in a coordinated manner, comprising:

connecting a message carrier to each member node in said plurality of member nodes;

providing a master scheduler in data communication with each said member node via said message carrier;

defining a reference moment time value for said plurality of member nodes;

communicating said reference moment time value to each member node and said master scheduler via said message carrier;

defining a communication request list in each said member node showing each communication needed by said member node with any other member node in a future time period;

communicating said communication request list from each member node to said master scheduler via said message carrier;

defining, in said master scheduler, scheduled communications between member nodes at communication event times respective to said reference moment time value and also respective to each said communication listed in each said received communication request list;

defining, in said master scheduler, a communication schedule for each member node respective to said scheduled communications;

sending each said communication schedule from said master scheduler to each respective member node via said message carrier;

defining, in each member node, the difference in time between said reference moment time value and the time when said reference moment time value is communicated into said member node;

defining, in each member node, a local task schedule from said communication schedule and from said difference in time for the member node so that the member node will communicate to other member nodes via said message carrier at said scheduled communication event times;

executing said scheduled communications between said member nodes respective to each scheduled communication via said message carrier according to said respective local task schedules.

5. The method of claim 4 wherein said step of defining a reference moment time value is performed by said master scheduler.

6. The method of claim 4 wherein said step of defining a communication request list in each said member node limits said communications to a maximum number in said future time period.

7. The method of claim 4 wherein each communication has a duration time attribute and the value of said duration time attribute is less than a fixed maximum value.

8. The method of claim 4 wherein the step defining a reference moment time value for said plurality of member nodes is done by a global time system.

9. A computer implemented method for enabling a plurality of member nodes to execute logic in a coordinated manner, comprising:

connecting a message carrier to each member node in said plurality of member nodes, each node having a central processing unit;

providing a master scheduler in data communication with each said member node via said message carrier;

defining a reference moment time value as a moment in time for said plurality of member nodes;

communicating said reference moment time value to each member node and said master scheduler via said message carrier;

defining into a communication request list in each said member node, each access to any other member node needed by said member node in achieving a future task increment respective to a future time period;

communicating said communication request list from each said member node to said master scheduler via said message carrier;

defining, in said master scheduler, a communication event data object respective to each said access to any other member node needed by said member node in achieving a future task increment, said communication event data object having an accessing member identification attribute value, an accessed member identification attribute value, and an access duration attribute value;

collecting, in said master scheduler, all defined communication event data objects into a communication event set;

determining in said master scheduler a summed accessed value for each member node in said communication event set as a sum of all access duration attribute values in all communication event data objects having a accessed member identification attribute value respective to said member node;

determining in said master scheduler a summed accessing value for each member node in said communication event set as a sum of all access duration attribute values in all communication event data objects having an accessing member identification attribute value respective to said member node;

scheduling in said master scheduler and into the earliest available time in a schedule, a future communication task respective to said reference moment time value between the accessing member node having the highest said summed accessing value respective to said communication event set and the accessed member node respective to the accessed member identification attribute value in the communication event data object having the highest affiliated access duration attribute value for all communication event data objects respective to said accessing member node, said future communication task having a task initiation time equal to the earliest available time in the schedule, an accessing member node identifier attribute respective to the accessing member, and an accessed member node identifier attribute respective to the accessed member node;

removing, in said master scheduler, the communication event data object respective to the accessed member node identifier attribute in the scheduled future communication task and the accessed member node identifier attribute in the scheduled future communication task to redefine the communication event set to those communication event data objects which have not been scheduled; and

repeating, in said master scheduler, respective to the redefined communication event set, the steps of determining a summed accessed value, determining a summed accessing value, scheduling a future communication task, and removing all communication event data objects respective to scheduled member nodes until all communication event data objects have been scheduled into a communication schedule for each member node;

sending each said communication schedule from said master scheduler to each respective member node via said message carrier;

defining, in each member node, the difference in time between said reference moment time value and the time when said reference moment time value is communicated into said member node;

defining, in each member node, a local task schedule from said communication schedule and from said difference in time for the member node so that the member node will communicate to other member nodes via said message carrier at said scheduled communication event times; and

executing said scheduled communications between member nodes respective to each scheduled communication event via said message carrier according to said respective local task schedules.

10. A computer implemented method for scheduling communications between member objects in a plurality of member objects functioning as a collective group, comprising the steps of:

providing a computer;

defining in said computer, for each member object, a communication event data object respective to each access to any other member object needed by said member object in achieving a future task increment, said communication event data object having an accessing member identification attribute value, an accessed member identification attribute value, and an access duration attribute value;

collecting, in said computer, all defined communication event data objects into a communication event set;

determining, in said computer, a summed accessed value for each member object in said communication event set as a sum of all access duration attribute values in all communication event data objects having a accessed member identification attribute value respective to said member object;

determining, in said computer, a summed accessing value for each member object in said communication event set as a sum of all access duration attribute values in all communication event data objects having an accessing member identification attribute value respective to said member object;

defining a set of sequential future time increments within a scheduling period respective to a schedule;

scheduling, in said computer, into the earliest available time in the first of said future time increments, a future communication task based on the first available communication event data object in said communication event set between

the accessing member object having the highest said summed accessing value respective to said communication event set and

the accessed member object having the highest said summed accessed value respective to said communication event set if a communication event data object exists between said accessed member object and said accessing member object,

said future communication task having a task initiation time equal to the earliest available time in the schedule, an accessing member object identifier attribute respective to the accessing member object, an accessed member object identifier attribute respective to the accessed member object, and said access duration attribute value;

removing from scheduling candidacy, in said computer, the communication event data object respective to the accessed member object identifier attribute in the scheduled future communication task and the accessing member object identifier attribute in the scheduled future communication task to redefine the communication event set to those communication event data objects which have not been scheduled;

repeating, in said computer respective to the redefined communication event set, the steps of determining a summed accessed value, determining a summed accessing value, scheduling a future communication task, and removing all communication event data objects respective to scheduled member objects until all communication event data objects have been scheduled which can be scheduled into said first future time increment; and

recurrently executing, in said computer respective to the redefined communication event set and sequentially respective to each of the remaining of said plurality of future time increments, the steps of determining a summed accessed value, determining a summed accessing value, scheduling a future communication task, and removing all communication event data objects respective to scheduled member objects, and repeating such steps until all communication event data objects have been scheduled which can be scheduled into each said future time increment and until all communication event data objects have been scheduled into said scheduling period.

11. The method according to 10, wherein said defining is confined to future task increments which are needed within a predefined time period and said scheduling is respective to said predefined time period.

12. The method according to 11, further comprising the step of connecting a message carrier to each member object in said plurality of member objects, said message carrier having a plurality of channels for permitting concurrency in said communication events, said step of scheduling being respective to said plurality of channels as a group wherein said earliest available time is respective to any channel in said message carrier.

13. The method according to claim 12 wherein each said member object is a member node being in data communication with said message carrier, each member node having a central processing unit.

14. A computer implemented method for scheduling tasks for resource objects in a plurality of resource objects functioning as a collective group, comprising the steps of:

providing a computer;

defining, in said computer, a set of future tasks for said collective group;

defining, in said computer, each resource object needed for each future task in said set of future tasks;

defining, in said computer, each interaction needed between any two resource objects respective to said set of future tasks;

defining, in said computer, a use instance for each said resource object in achieving each said interaction, said use instance having an use duration attribute value;

defining, in said computer, an accessing resource object and an accessed resource object respective to each said use instance;

firstly determining, in said computer, a summed accessing time value for each accessing resource object as a sum of all use duration attribute values for all said use instances respective to that resource object when it is the accessing resource object;

secondly determining, in said computer, a summed accessed time value for each accessed resource object as a sum of all use duration attribute values for all said interactions between said accessed resource object and said accessing resource object;

defining, in said computer, a set of sequential future time increments within a scheduling period respective to a schedule;

scheduling, in said computer, into the earliest available time in the first of said future time increments, a future resource interaction event based on the first available future task in said set of future tasks between

the accessing resource object having the highest said summed accessing value respective to said set of future tasks and

the accessed resource object having the highest said summed accessed value respective to said set of future tasks if a use instance exists between said accessed resource object and said accessing resource object,

said future resource interaction event having an initiation time equal to the earliest available time in the schedule, an accessing resource object identifier attribute respective to the accessing resource object, an accessed resource object identifier attribute respective to the accessed resource object, and said use duration attribute value;

removing from scheduling candidacy, in said computer, the use instance respective to the accessed resource object in the scheduled future resource interaction event and the accessing member object identifier attribute in the scheduled future resource interaction event to redefine the set of future tasks to those future tasks for which interactions have not been scheduled;

repeating, in said computer, respective to the redefined future task set, the steps of determining a summed accessed value, determining a summed accessing value, scheduling a future communication task, and removing all use instances respective to scheduled resource objects until all use instances have been scheduled which can be scheduled into said first future time increment; and

recurrently executing, in said computer, respective to the redefined future task set and sequentially respective to each of the remaining of said plurality of future time increments, the steps of determining a summed accessed value, determining a summed accessing value, scheduling a future resource interaction event, removing all resource objects respective to scheduled resource objects, and repeating such steps until all resource interaction events have been scheduled which can be scheduled into each future time increment and until all resource interaction events have been scheduled into said scheduling period.

15. A computer implemented apparatus for enabling a plurality of computer nodes in mutual data communication to execute logic in a coordinated manner, comprising:

means for aligning real-time time between said plurality of computer nodes so that each computer node has essentially the same real-time time;

means for defining a schedule of communications for each computer node, said schedule having a different time in the future defined for initiating each respective communication;

means for communicating each schedule to its respective computer node;

means for initiating each communication from each node at the time defined in its schedule.

16. A computer-implemented apparatus having a message carrier, comprising:

a plurality of member nodes, each member node being in data communication with said message carrier, each member node having

a central processing unit,

time phase logic for receiving from said message carrier a reference moment message having a reference moment time value and for defining the difference in time between said reference moment time value and the time of receiving said reference moment message,

communication definition logic for identifying each internodal communication needed by said member node in a future time period and for establishing a communication request list respective to all said internodal communications,

communication request sending logic for communicating said communication request list via said message carrier to a master scheduler,

communication task receiving logic for receiving a communication schedule via said message carrier from said master scheduler,

task integration logic for defining a local task schedule from said communication schedule and said difference in time, and

communication implementation logic for communicating via said message carrier with other member nodes according to said local task schedule; and

a master scheduler in data communication with said plurality of member nodes via said message carrier, said master scheduler having scheduler logic executed by a central processing unit, said scheduler logic having

reference moment definition logic for defining said reference moment time value as a moment in time, reference moment communication logic for creating a reference moment message having said reference moment time value and for communicating said reference moment message via said message carrier to each member node,

communication request receiving logic for receiving each said communication request list from each said member node via said message carrier,

communication schedule definition logic for scheduling communications between member nodes at communication event times respective to said reference moment time value and also respective to each said internodal communication listed in each said received communication request list and for further defining a communication schedule for each member node respective to said scheduled communications, and

member node communication schedule response logic for sending each said communication schedule to each respective member node via said message carrier.

17. The apparatus of claim 16, wherein each member node further comprises a variable speed oscillator.

18. The apparatus of claim 16, wherein each member node further comprises time alignment logic and oscillator rate adjustment logic.

19. The apparatus of claim 16, wherein said message carrier comprises a crossbar switch.

20. The apparatus of claim 16, wherein said message carrier comprises a network topology.

21. The apparatus of claim 16, wherein said message carrier comprises a radio frequency communications system.