Distributed computing system with dual independent communications paths between computers and employing split tokens

Claims

We claim:

1. A computer system comprising:

(a) a plurality of computers, each said computer having first input/output interface means to a communicatiosn network and second input/output interface means for interfacing a communications network, each said second input/output interface means including bypass means for bypassing the associated said computer with a bit stream of data passing through said second input/output interface means;

(b) global communications network means interconnecting respective ones of said first input/output interface means for providing respective ones of said computers with the ability to broadcast messages simultaneously to the remainder of said computers; and,

(c) meshwork communications network means interconnecting respective ones of said second input/output interface means for providing respective ones of said computers with the ability to establish a communications link with another of said computers through said bypass means of the remainder of said computers; and wherein,

(d) communications between respective ones of said computers includes the use of split tokens each having a moving first portion which is sent from computer to computer and a resident second portion which is disposed in the memory of at least one of said computers and wherein the storage location address of said second portion is contained within said first portion.

2. The computer system of claim 1 wherein:

said split tokens represent both functions to be executed by said computers and data to be employed in the execution of said functions.

3. The computer system of claim 1 wherein:

said first input/output interface means each includes detecting and terminating means for detecting a collision between messages being broadcast over said global communications network means and for terminating the broadcasting of a message in favor of a message with superior right to the use of said global communications network means whereby collisions between messages from a plurality of said computers are detected and avoided, said detecting a terminating means comprising:

said messages broadcast by said computers over said global communications network means each including a leading module identifying portion, and

each said first input/output interface means including means for testing the last bit broadcast contents of said global communications network means as message from its associated said computer are being broadcast over said global communications network means on a bit-by-bit basis and for terminating the broadcasting of a message when said last bit broadcast contents of said global communications network means is not identical to the previous bit of the message just broadcast by said first input/output interface means indicating that another said computer was first in time on said global communications network means.

4. The computer system of claim 3 wherein additionally:

said messages broadcast by said computers over said global communications network means each include a priority code preceding a module identifying portion whereby another said computer which was first in time on said global communications network means will automatically relinquish said global communications network means to the message of another said computer which is of a higher priority.

5. The computer system of claim 3 wherein additionally:

(a) said messages broadcast by said computers over said global communications network means each include a reserved portion of fixed length and normally containing no data immediately following said module identifying portion;

(b) said first input/output interface means at each said computer includes first logic means for broadcasting a data bit over said global communications network means during said reserved portion when it has terminated the sending of a message as a result of a detected collision; and,

(c) said first input/output interface means at each said computer further includes second logic means for testing said global communications network means during said reserved portion and for not immediately broadcasting a new message following the termination of a broadcast message when said data bit is detected during said reserved portion whereby a said computer which has control of said global communications network means will relinquish said global communications network means for a message of another said computer which has previously relinquished said global communications network means whereby computer lockout from access to said global communications network means is prevented and equal access to all said computers is guaranteed.

6. The computer system of claim 1 wherein:

(a) said messages broadcast by said computers over said global communications network means each include a cyclic redundancy check code for the preceding bits and a trailing portion of fixed length and normally containing no data;

(b) said first input/output interface means at each said computer includes third logic means for testing each said message as received by means of said cyclic redundancy check code and for broadcasting a data bit over said global communications network means during said trailing portion if a said received message is in error; and,

(c) said first input/output interface means at each said computer further includes fourth logic means for testing said global communications network means during said trailing portion and for rebroadcasting its last broadcast message as not having been received if it senses said data bit during said trailing portion.

7. The computer system of claim 1 wherein:

(a) said bypass means of said second input/output interface means at each said computer includes a receiver for receiving inputs to the associated said computer, a transmitter for transmitting outputs from the associated said computer, a plurality of inputs and outputs connected to respective ones of said inputs and outputs of others of said computers interconnected by said meshwork communications network means, and crossbar switch means interconnecting said inputs and said outputs for bypassing said receiver and said transmitter at the associated said computer and for interconnecting one of said plurality of inputs to one of said plurality of outputs whereby a bypass link between said ones of said plurality of inputs and outputs is established.

8. The computer system of claim 7 wherein:

said bypass means of said second input/output interface means at each said computer includes means for sensing a unique signal on said meshwork communications network means indicating that said bypass link is to be terminated and for causing said crossbar switch means to open said bypass link when said unique signal is sensed.

9. The computer system of claim 7 wherein:

said bypass means of said second input/output interface means at each said computer includes repeater means for inverting the clock pulses passing through said crossbar switch means and for resampling data passing therethrough with said inverted clock pulses whereby narrowing of data pulses and loss of synchronization between data passing therethrough and the clock pulses associated therewith is eliminated.

10. A communications network system with the capability of sensing and avoiding message collisions for interconnecting a plurality of computers comprising:

(a) each computer having input/output interface means for interfacing to a communications network;

(b) global communications network means interconnecting respective ones of said input/output interface means for providing respective ones of said computers with the ability to broadcast messages simultaneously to the remainder of said computers; and,

(c) detecting and terminating means included as part of each said input/output interface means for detecting a collision between messages being broadcast over said global communications network means and for terminating the broadcasting of a message in favor of a message with superior right to use of said global communications network means whereby collisions between simultaneous messages from a plurality of the computers are detected and avoided; and wherein,

(d) the messages broadcast by the computers over said global communications network means each includes a leading module identifying portion;

(e) said first input/output interface means each includes means for testing the last bit broadcast contents of said global communications network means as messages from its associated computer are being broadcast serially over said global communications network means on a bit-by-bit basis and for terminating the broadcasting of a message when said last bit broadcast contents of said global communications network means is not identical to the previous bit of the message just broadcast by said first input/output interface means thus indicating that another computer was first in time on said global communications network means; and,

(f) the messages broadcast by the computers over said global communications network means each include a leading priority code preceding said module identifying portion whereby another computer which was first in time on said global communications network means will relinquish said global communications network means to the message of another computer which is of a higher priority.

11. The computer system of claim 10 wherein additionally:

(a) the messages broadcast by the computers over said global communications network means each include a fixed length non-data portion immediately following said module identifying portion;

(b) said first input/output interface means at each computer includes first logic means for broadcasting a data bit over said global communications network means during said fixed length immediately following non-data portion when it has terminated the sending of a message as a result of a detected collision; and,

(c) said first input/output interface means at each computer further includes second logic means for testing said global communications network means during said fixed length immediately following non-data portion and for not immediately broadcasting a new message following the termination of a broadcast message when said data bit is detected during said fixed length immediately following non-data portion whereby a computer which has control of said global communications network means will relinquish said global communications network means to the message of another computer which has previously relinquished said global communications network means whereby computer lockout from access to said global communications network means is prevented and equal access to all the computers is guaranteed.

12. The computer system of claim 10 wherein:

(a) the messages broadcast by the computers over said global communications network means each include a cyclic redundancy check code for the preceding bits and a fixed length trailing non-data portion;

(b) said first input/output interface means at each computer includes third logic means for testing each message as received by means of said cyclic redundancy check code and for broadcasting a data bit over said global communications network means during said fixed length trailing non-data portion; and,

(c) said first input/output interface means at each computer further includes fourth logic means for testing said global communications network means during said fixed length trailing non-data portion and for rebroadcasting its last broadcast message as not having been received if it senses said data bit during said fixed length trailing non-data portion.

13. A computer system comprising:

(a) a plurality of computers wherein each said computer is controlled by a resident copy of a common operating system; and,

(b) communications network means interconnecting respective ones of said computers for allowing respective ones of said computers to broadcast messages to all others of said computers simultaneously and for allowing respective ones of said computers to transmit and receive data and functions to and from others of said computers; wherein,

(c) the initiation of functions within respective ones of the computers is accomplished by the broadcasting of function tokens as messages on said communications network means; and,

(d) communication and transfer of both functions and data between respective ones of said computers is by means of split tokens each having a moving first portion which is moved from computer to computer and a resident second portion which is disposed in the memory of at least one of said computers and wherein the location of said second portion is part of said first portion.

14. The computer system of claim 13 wherein:

(a) selected ones of said function tokens are duplicate tokens which cause the associated function to be accomplished on at least two separate ones of said computers; and,

(b) said common operating system at each said computer includes logic for sensing duplicate tokens, for voting on the results produced by the associated function at each of said at least two separate ones of said computers, and for selecting the said results with the highest probability of being correct for use as the results of said associated function.

15. The computer system of claim 13 wherein:

said broadcasting of said function tokens is initiated by the broadcasting of data tokens required for the performance of a function as messages on said communications network means.

16. The computer system of claim 13 wherein:

ones of said function tokens have a time of execution associated with them and said broadcasting of said function tokens is initiated by the associated said time of execution being reached.

17. The computer system of claim 16 wherein:

said communications network means maintains a common system time employed by said computers connected thereto for time based activities and the time stamping of said tokens.

18. The computer system of claim 13 wherein: `said moving firs portion of said split tokens is broadcast over said communications network means to all said computers simultaneously and said resident second portion is transferred over said communications network means from one said computer to another.

19. The computer system of claim 13 wherein:

(a) each said computer has first input/output interface means for interfacing to a communications network and second input/output interface means for interacting to a communications network, each said second input/output interface means including bypass means for bypassing the associated said computer with a bit stream passing through said second input/output interface means; and wherein said communications network means comprises:

(b) global communications network means interconnecting respective ones of said first input/output interface means for providing respective ones of said computers with the ability to broadcast messages simultaneously to the remainder of said computers; and,

(c) meshwork communications network means interconnecting respective ones of said second input/output interface means for providing respective ones of said computers with the ability to establish a communications link with another of said computers through said bypass means of the remainder of said computers.

20. The computer system of claim 19 wherein:

said first input/output interface means each includes detecting and terminating means for detecting a collision between messages being broadcast over said global communications network means and for terminating the broadcasting of a message in favor of a message with superior right to use of said global communications network means whereby collisions between messages form a plurality of said computers are detected and avoided, said detecting and terminating means comprising,

said messages broadcast by said computers over said global communications network means each including a leading module identifying portion; and,

said first input/output interface means each including means for testing the last bit broadcast contents of said global communications network means as messages from its associated said computer are being broadcast over said global communications network means on a bit-by-bit basis and for terminating the broadcasting of a message when said last bit broadcast contents of said global communications network means is not identical to the previous bit indicating that another said computer was first in time on said global communications network means.

21. The computer system of claim 20 wherein additionally:

said messages broadcast by said computers over said global communications network means each include a priority code preceding said module identifying portion whereby another said computer which was first in time on said global communications network means will automatically relinquish said global communications network means to the message of another said computer which is of a higher priority.

22. The computer system of claim 20 wherein additionally:

(a) said messages broadcast by said computers over said global communications network means each include a fixed length non-data portion immediately following said module identifying portion;

(b) said first input/output interface means at each said computer includes first logic means for broadcasting a data bit over said global communications network means during said fixed length immediately following non-data portion when it has terminated the sending of a message as a result of a detected collision; and,

(c) said first input/output interface means at each said computer further includes second logic means for testing said global communications network means during said fixed length immediately following non-data portion and for not immediately broadcasting a new message following the termination of a broadcast message when said data bit is detected during said fixed length immediately following non-data portion whereby a said computer which has control of said global communications network means will relinquish said global communications network means for the message of another said computer which has previously relinquished said global communications network means whereby computer lockout from access to said global communications network means is prevented and equal access to all said computers is guaranteed.

23. The computer system of claim 19 wherein:

(a) said messages broadcast by said computers over said global communications network means each include a cyclic redundancy check code for the preceding bits and a fixed length trailing non-data portion;

(b) said first input/output interface means at each said computer includes third logic means for testing each said message as received by means of said cyclic redundancy check code and for broadcasting a data bit over said global communications network means during said fixed length trailing non-data portion as a result of messages received with errors; and,

(c) said first input/output interface means at each said computer further includes fourth logic means for testing said global communications network means during said fixed length trailing non-data portion and for rebroadcasting its last broadcast message as not having been received if it senses said data bit during said fixed length trailing non-data portion.

24. The computer system of claim 20 wherein:

(a) said bypass means of said second input/output interface means at each said computer includes a receiver for receiving inputs to the associated said computer, a transmitter for transmitting outputs from the associated said computer, a plurality of inputs and outputs connected to respective ones of said inputs and outputs of others of said computers interconnected by said meshwork communications network means, and crossbar switch means interconnecting said inputs and said outputs for bypassing said receiver and said transmitter at the associated said computer and for interconnecting one of said plurality of inputs to one of said plurality of outputs whereby a bypass link between said ones of said plurality of inputs and outputs is established.

25. The computer system of claim 24 wherein:

said bypass means of said second input/output interface means at each said computer includes means for sensing a unique signal on said meshwork communications network means indicating that said bypass link is to be terminated and for causing said crossbar switch means to open said bypass link when said unique signal is sensed.

26. The computer system of claim 24 wherein:

said bypass means of said second input/output interface means at each said computer includes repeater means for inverting the clock pulses passing through said crossbar switch means and for resampling data passing therethrough with said inverted clock pulses whereby narrowing of data pulses and loss of synchronization between data passing therethrough and the clock pulses associated therewith is eliminated.

27. A computer interconnecting system for interconnecting a plurality of computers for the transfer of data systems therebetween comprising:

(a) each computer having input/output interface means for interfacing to a communications network, each said input/output interface means including bypass means for bypassing the associated computer with a bit stream passing through said input/output interface means;

(b) meshwork communications network means interconnecting respective ones of said input/output interface means for providing respective ones of the computers with the ability to establish a communications link with another of the computers through said bypass means of the remainder of the computers;

(c) said bypass means of said input/output interface means at each computer including a receiver for receiving inputs to the associated computer, a transmitter for transmitting outputs from the associated computer, a plurality of inputs and outputs connected to respective ones of said inputs and outputs of others of the computers interconnected by said meshwork communications network means, crossbar switch means interconnecting said inputs and said outputs for bypassing said receiver and said transmitter at the associated computer and for interconnecting one of said plurality of inputs to one of said plurality of outputs whereby a bypass link between said ones of said plurality of inputs and outputs is established;

(d) said bypass means of said input/output interface maens at each computer includnig means for sensing a unique signal on said meshwork communications network means indicating that said bypass link is to be terminated and for causing said crossbar switch means to open said bypass link when said unique signal is sensed; and,

(e) said bypass means of said input/output interface means at each computer further including repeater means for inverting the clock pulses passing through said crossbar switch means and for resampling data passing therethrough with said inverted clock whereby narrowing of data pulses and loss of synchronization between data passing therethrough and the clock pulses associated therewith is eliminated.

28. In a computer system comprising a plurality of computers and a communications network interconnecting respective ones of the computers for allowing respective ones of the computers to broadcast messages to all the computers simultaneously and for allowing respective ones of the computers to transmit and receive data and function initiations to and from others of the computers, the improvement comprising:

(a) each computer being controlled by a resident copy of a common operating system; and,

(b) the initiation of functions within respective ones of the computers being accomplished by the broadcasting of function tokens as messages on the communications network means; and wherein,

(c) communication and transfer of both function tokens and data between respective ones of the computers is by means of split tokens each having a moving first portion which is transmitted as a message from computer to computer and a resident second portion which is disposed in the memory of at least one of said computers and wherein the location address of said second portion is contained in said first portion.

29. The improvement to a computer system of claim 28 wherein:

(a) selected ones of said function tokens are duplicate tokens which cause the associated function to be executed in at least two separate ones of the computers; and,

(b) said common operating system at each computer includes logic for sensing duplicate tokens, for voting on the results produced by the associated function at each computer, and for selecting for use the said results with the highest probability of being correct.

30. The improvement to a computer system of claim 28 wherein:

said broadcasting of said function tokens is initiated by the broadcasting as messages on the communications network of data tokens required for the performance of a function.

31. The improvement to a computer system of claim 28 wherein:

selected ones of said function tokens have a time of execution associated with them and said broadcasting of said function tokens is initiated by the associated said time of execution being reached.

32. The improvement to a computer system of claim 31 wherein:

the communications network includes means for maintaining a common system time employed by the computers for time based activities and the time stamping of said tokens.

33. The improvement to a computer system of claim 28 wherein:

said moving first portion of said split tokens is broadcast over said communications network means to all said computers simultaneously and said resident second portion is transferred over the communications network only between a computer wherein it is resident and a computer requiring it to execute a function.

TECHNICAL FIELD

A distributed computing system comprising a plurality of interconnected computers operating in a novel distributed variation of dataflow execution mode to provide flexible fault tolerance, to ease software design and concurrency specification, and to dynamically balance the loads; a distributed operating system resident on all computers; a real-time multiple-access global bus using Lanning code arbitration with deterministic access delay; and a point-to-point circuit-switched network.

DESCRIPTION OF THE PRIOR ART

Future spacecraft computers will require greater autonomy, flexibility, fault tolerance and higher throughput. The necessary solution is a new flexible computational system that will support a wide range of instruments, attain a tolerable arbitrary level of fault and damage tolerance, and provide a greater range of throughput capability. Designers of future spacecraft systems will confront a variety of new applications in onboard computing. The traditional roles of spacecraft computers are expanding to encompass tasks previously assigned to ground based systems. Increased autonomy is becoming a major goal at all levels to improve both efficiency and reliability. Greater flexibility will be needed to accommodate evolving requirements for existing spaceborne systems. Also, new instruments and engineering subsystems will require greater computational throughput.

Considering the range of payloads on such diverse systems as the Space Station, Earth Observing System, planetary spacecraft, and a host of Space Shuttle experiments, there exists the potential need for many hundreds of general purpose computing systems. The Space Station alone may require dozens, if not hundreds, of computers when payloads are included.

Reliability issues include the operating environment as well as fault and damage tolerance. One environmental issue that has plagued current generation computing components is their intolerance to ionizing radiation damage and to a single event upset (SEU). SEUs arise in small feature size parts due to trapped ions, solar flares and cosmic rays. The ability for space systems to evolve to a newer, high density technology such as VHSIC is a daunting problem. Solutions, in many cases, may have to come from architectural restructuring in new and novel ways.

Computer system architectures have various facets. There is the structure of the computers themselves, i.e. one or many. Operating systems and the associated support software can be configured in many ways. Then there is the consideration of how multiple computers will communicate with one another. Early systems employed one large computer doing the work on a batch input basis. Later, data acquisition and processing functions were made "real time" in many cases but still employing one large computer to do the work. Sometimes, priority levels were assigned to the various tasks within the computer and the tasks shared the computing ability of the hardware on an unequal basis with the more important tasks being done first and the tasks of lesser importance being done on a time available basis. The advent of multi-processors (i.e. multiple computers linked together to perform a common function) created many new problems for the computer architects. Particularly sensitive in the military and space environments are the concepts of fault tolerance and "graceful degradation"; that is, with one computer, when it is not working, nothing gets done, but, with multiple computers, if a portion of the computing capability is inoperative for any reason, it is expected that the remaining capability will take over at least critical functions and keep them operational.

A few examples of various architectural approaches known in the computer art are depicted in simplified form in FIGS. 1-4. FIG. 1 depicts a contemporary token ring network 10 wherein a plurality of computer nodes 12 are disposed along a circular communications path 14. To send messages between one another, each node samples the data on the path 14 looking for a "token" (i.e. a particular bit pattern not otherwise appearing) signifying the end of a message. When the token is located, the node 12 puts its message on the path 14 immediately following the found token and appends a new token at the end of its message to flag the end thereof. If a token is not found within a given time, the node 14 puts its message on anyway assuming network failure of some sort and hopes for the best. In such case, the network 10 degrades into what is referred to as a "contention" network wherein each node simply puts its messages on the network at will and if they are not acknowledged by the receiver as having been properly received within a given time, repeats the process until successful sending and receiving has been achieved. Some inter-computer communications networks operate on that basis all the time. Obviously, in either the token ring approach or the contention approach, some nodes can dominate the communications path and prevent other nodes from communicating at all. All in all, such approaches which may be acceptable in some ground based general computer systems are not acceptable for systems employed in the space applications being considered herein.

A common prior art approach to both hardware and software interconnection and hierarchy is depicted in FIG. 2. In this case, a plurality of task-oriented, working level computers 16 are interconnected in a multi-processor environment. The software in the computers 16 is primarily that required to perform user functions or tasks such as data acquisition and processing. Supervising computers 18 are connected to monitor the computers 16 and contain operating system type software for assigning and reassigning tasks to the computers 16 for the purpose of distributing the workload for maximum system efficiency and to accomplish fault tolerance and graceful degradation as necessary. Typically, there is a master computer 20 which has ultimate control of the whole system. The master computer 20 provides the system interface and is used to start up and configure the system in general, among other tasks. As can be appreciated, such an approach is complex to create, complex to debug, and subject to high overhead problems. Moreover, there must be redundancy on the supervising and master computer levels to prevent system failure if one of those computers fails or is destroyed.

FIG. 3 depicts a data-driven approach to computer architecture which is known in the art. Each task 22 is caused to execute when the data from the preceding tasks 22 required for its execution are provided by those preceding tasks.

Finally, FIG. 4 depicts a basic eight node element of a so-called "hypercube" approach to computer architecture wherein as many as 64,000 individual computing nodes 16 are interconnected. The hypercube is characterized by implementing an approach such as that depicted in FIG. 2. The nodes 16 are interconnected by a first communications network 24 over which the nodes 16 transfer their data, etc. The supervising computers 18 are connected to the nodes 16 by a second communications network 26 over which reconfiguration and redistribution/reassignment of task instructions are sent so that the same communications paths are not employed for the two different purposes.

Many fault tolerance approaches with prior art computer architectures are hardware intensive, requiring elaborate hardware synchronization mechanisms. Even with this investment in hardware, the application software is often subject to constraints, and requires additional overhead to support the underlying