Operations controller for a fault tolerant multiple node processing system

Abstract

A task communicator for each node in a multiple node processing system having a data memory storing data received from a voter interface which is used for the execution of tasks by an associated applications processor, a next task register storing the identification code of the next task to be executed by the applications processor received from a scheduler through a scheduler interface. An input handler passes the identification code of the next task and the data required for the execution of that task to an input FIFO register interfacing the applications processor. An output FIFO register temporarily stores the data generated by the applications processor and an output handler generates inter-node messages containing data stored in the output FIFO and passes these inter-node messages to a transmitter through a transmitter interface for transmission to all of the other nodes in the processing system.

Claims

What is claimed is:

1. In a multiple node processing system having a plurality of nodes, each node having an applications processor operative to execute a predetermined set of tasks wherein each task in said predetermined set of tasks is executed by more than one node, and an operations controller for selecting the tasks in the order that they are to be executed by the applications processor, the operations controller further controlling the operation of its own node through the exchange of inter-node messages including data value messages, each containing data resulting from the execution of a task by the node that sent said data value message and task completed/started messages identifying the task just completed and the new task started by the node sending said task completed/started message, said data value messages including a message type code identifying the message as containing data values, and a data identification code uniquely identifying the particular data value, the operations controller having a plurality of subsystems including a receiver for receiving said data value messages and said task completed/started messages generated by said other nodes, a task scheduler for selecting and scheduling the tasks to be executed by said applications processor for generating a task identification code identifying the next task to be executed by said applications processor and a task terminated signal in response to receiving inter-node data value messages from all the nodes scheduled to execute the task containing the identity of the terminated task, and a task communicator for transferring to said applications processor the identity of the task selected by said task scheduler and the data values required for the execution of the task selected and for generating said data value messages and said task completed/started messages which are sent to all of the nodes in said multiple node processing system, said task communicator comprising:

a data memory for storing data values, said data memory having at least two partitions identified by a context bit, each partition having a plurality of entries for storing said data values;

a context bit memory for storing a context bit for each data identification code, said context bit identifying said data values stored in said data memory which are ready for use in the execution of tasks by said applications processor;

a task terminated recorder for complementing said context bit in said context bit memory in response to said task terminated signal generated by said task scheduler;

a store data control for storing said data values contained in said data value messages received by said receiver in said data memory using said message type code, data identification code and the complement of said context bit stored in said context bit memory associated with said data identification code for said data value as an address for the appropriate entry in said data memory;

a next task register for storing said task identification code of a task selected by said task scheduler for execution by said applications processor;

an input FIFO register accessible by said applications processor for storing said task identification code of the next task to be executed by said applications processor and said data values required for the execution of said next task;

input handler means, responsive to said applications processor completing the preceding task for generating a task completed/started message sent to all of the nodes in said multiple node processing system, for transferring said task identification code stored in said next task register to said input FIFO register, and for accessing said data memory for said data values required for the execution of said next task and store said data values in said input FIFO register, said input handler means responsive to said context bits stored in said context bit memory to identify which data values in said data memory are to be transferred to said input FIFO register for the execution of said next task;

an output FIFO register for storing said data values generated by said applications processor during the execution of each task; and

output handler means for generating said data value messages which are sent to all the nodes in said multiple node processing system, said data value messages containing said data values stored in said output FIFO register and said identification code for said data values.

2. The task communicator of claim 9 further comprising:

a pointer table having an entry for each node, each entry operative to store task and data identification codes;

a DID list storing for each task a first set of data identification codes in the sequence said data values, stored in said data memory, are required by said applications processor for the execution of that task and for storing for each task a second set of data identification codes in the sequence which said data values are generated by said applications processor;

an input pointer list storing, for each task stored in said DID list, a pointer to a first data identification code in said first set of data identification codes for the associated task;

an output pointer list storing, for each task stored in said DID list, a pointer to a first data identification code in said second set of data identification codes for the associated task; and

wherein said input handler means has means for storing said task identification code for said next task in said pointer table, means for accessing said input pointer list with said task identification code of said next task stored in said pointer table to get a pointer to said first set of data identification codes stored in said DID list, means for accessing said DID list to get a first data identification code for a first data value needed by said applications processor for executing said next task, and means for accessing said data memory to extract said data value from said data memory and store said data value in said input FIFO register, said input handler further having means for sequentially indexing said pointer to said first set of data identification codes stored in said DID list to get said data identification codes for said remaining data values stored in said data memory for the execution of said next task, for accessing said data memory with said data identification codes to extract said remaining data values and for storing said remaining data values in said input FIFO register.

3. The task communicator of claim 2 wherein the last data identification code in said first and second sets of data identification codes is a null data identification code, said input handler means includes means for detecting said null data identification code to stop the indexing of said pointer to said DID list.

4. The task communicator of claim 2 wherein said output handler means has means responsive to said applications processor completing a task for accessing said pointer table to get said task identification code stored in said pointer table, which is indicative of the task currently being executed by said applications processor, means for accessing said output pointer list with said task identification code to get a pointer to said DID list, means for accessing said DID list with said pointer to get a data identification code from said second set of data identification codes for a first data value resulting from the execution of said task currently being executed by said applications processor, and means for appending said data identification code to said first data value stored in said output FIFO register, said output handler means further having means for indexing said output pointer to said second set of data identification codes stored in said DID list to get said data identification code for each data value generated by said applications processor in the execution of said task currently being executed by said applications processor.

5. The task communicator of claim 4 wherein said DID list also stores a message type code for each data identification code which is transmitted with said data identification code to said output handler means, said output handler means having means for appending said message type code to a first byte of a data value message containing said data value identified by the data identification code.

6. The task communicator of claim 3 wherein said output handler means has means for detecting said null data identification code to stop the indexing of said pointer to said DID list.

7. The task communicator of claim 2 wherein said operations controller has a voter for voting on said data values received in data value messages from all of the other nodes in the multiple node processing system to generate a voted data value, and a deviance checker for generating a deviance error vector identifying each node which sent a data value message whose data value differed from said voted data value by more than a predetermined amount and wherein said voted data value received from said voter also includes said deviance error vector, said store data control has means for storing said deviance error vectors in a special partition of said data memory using said message type, said data identification code, a deviance bit, and a context bit set to 0, as an address, and wherein said task communicator further includes a deviance error register, said task terminated recorder has means for accessing said output pointer table with said task identification code of said terminated task to get a pointer to said DID list, means for accessing said DID list with said pointer to get said data identification codes for said terminated task, means for appending a deviance bit to said data identification codes to generate an address to said deviance error vector stored in said data memory, and means for accessing said data memory using said address to get said deviance error vectors associated with said terminated task, said task terminated recorder further having means for "OR"ing said deviance error vectors to generate "OR"ed values for said deviance error vector and storing said "OR"ed values of said deviance error vectors in said deviance error register.

8. The task communicator of claim 7 wherein said voter periodically requests the data identification code for the data values it is currently processing, said task communicator further including a NUDAT bit memory for storing a NUDAT bit for each data identification code indicating that said data value stored has not been previously used by said voter, said task terminated recorder including means for setting said NUDAT bit for each data identification code extracted from said DID list for said terminated task.

9. The task communicator of claim 8 further including a DID request handler for supplying said voter with a data identification code of a data value that was received from an identified node in response to said voter transmitting a node identification code to said DID request handler identifying the node from which said data value was received.

10. The task communicator of claim 9 wherein said DID request handler has means for accessing said pointer table with said node identification code to get a pointer to said DID list, means for accessing said DID list with said pointer to get the data identification code stored in the entry identified by said pointer, means for accessing said NUDAT bit memory for the data identification code identified by said pointer to get said NUDAT bit, and means for passing said data identification code and said NUDAT bit to said voter, said DID request handler further having means for resetting said NUDAT bit associated with said data identification code passed to said voter, for indexing said pointer to a next data identification code in said DID list and for storing said indexed data identification code in said pointer table for the node identified in said request from said voter.

11. The task communicator of claim 10 wherein said task scheduler passes said task identification code of the task started by each node to said task communicator, said task communicator further includes a task started recorder for storing a pointer to said DID list in said pointer table identifying the first entry for that task in said second set of data identification codes.

12. The task communicator of claim 11 wherein said task communicator has a sequence error register, said task started recorder has means for accessing said pointer table with the identification code of the node starting a new task to get the currently store pointer to said DID list, means for accessing said DID list with said currently stored pointer to get said data identification code stored in that entry, and means for recording a sequence error in said sequence error register when said data identification code is not a null data identification code, said task started recorder further including means for accessing said output pointer table with said task identification code of said started task to get a new pointer to said DID list and storing said new pointer in said pointer table.

13. The task communicator of claim 12 wherein said applications processor generates an error report identifying any errors it has detected in its operation, said applications processor storing said error report in said output FIFO register after all the data values for that task have been generated, and wherein said task communicator has an applications processor reported error register, said output handler means having means for transferring said error report from said output FIFO register to said applications processor reported error register.

14. The task communicator of claim 13 wherein said operations controller has a fault tolerator subsystem, said task communicator further having error reporter means for transmitting the content of said deviance error register, said sequence error register, and said applications processor reported error register to said fault tolerator subsystem.

Description

CROSS REFERENCE

This invention is related to commonly assigned, copending patent applications Ser. Nos. 038,818 and 039,190 filed concurrently on Apr. 15, 1987.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention is related to the field of multiple node processing systems and in particular to an operations controller for each node in the multiple node processor system each operations controller one for controlling the operation of its own node in a fault tolerant manner.

2. Description of the Prior Art

The earliest attempts to produce fault tolerant computer systems provided redundant computers in which each computer simultaneously executed every task required for the control operation. Voting circuits monitoring the outputs of the multiple computers determined a majority output which was assumed to be the correct output for the system. In this type of system, a faulty computer may or may not be detected and the faulty computer may or may not be turned off.

the redundant computer concept, although highly successful, is expensive because it requires multiple computers of equivalent capabilities. These systems require powerful computers because each computer has to perform every task required for the operation of the system. As an alternative, the master-slave concept was introduced in which the operation of several computers was controlled and coordinated by a master control. The master control designated which tasks were to be executed by the individual computers. This reduced the execution time of the control operation because all the computers were no longer required to execute every task, and many of the tasks could be executed in parallel. In this type of system when a computer is detected as faulty, the master could remove it from active participation in the system by assigning the task that would normally have been assigned to the faulty computer to the other computers. The problem encountered in the master-slave concept is that the system is totally dependent upon the health of the master and if the master fails then the system fails. This defect may be rectified by using redundant master controls, however, the increased cost of redundant masters limits the applicability of these systems to situations where the user is willing to pay for the added reliability. Typical of such situations are the controls of nuclear power plants, space exploration and other situations where failure of the control system would endanger lives.

Recent improvements to the master-slave and redundant execution fault tolerant computer systems discussed above are exemplified in the October 1978 proceedings of the IEEE, Volume 66, No. 10, which is dedicated to fault tolerant computer systems. Of particular interest are the papers entitled "Pluribus: An Operational Fault Tolerant Microprocessor" by D. Katuski et al., Pages 1146-1159 and "SIFT: The Design and Analysis of a Fault Tolerant Computer for Aircraft Control" by J. H. Wensley et al., Pages 1240-1255. The SIFT system uses redundant execution of each system task and of the master control functions. The Pluribus system has a master copy of the most current information which can be lost if certain types of faults occur.

More recently a new fault tolerant multiple computer architecture has been disclosed by Whiteside et al, in U.S. Pat. No. 4,356,546, in which each of the individual task execution nodes has an applications processor and an operations controller which functions as a master for its own node.

The present invention is an operations controller for a fault tolerant multiple node processing system based on the system taught by Whiteside et al in U.S. Pat. No. 4,323,966 which has improved fault tolerance and control capabilities. A predecessor of this operations controller has been described by C. J. Walter et al in their paper "MAFT: A Multicomputer Architecture for Fault-Tolerance in Real-Time Control Systems" published in the proceedings of the Real-Time System Symposium, San Diego, Dec. 3-6, 1985.

SUMMARY OF THE INVENTION

The invention is an operations controller for each node in a fault tolerant multiple node processing system. Each node has an applications processor for executing a predetermined set of tasks and an operations controller for establishing and maintaining its own node in synchronization with every other node in the system, for controlling the operation of its own node, and for selecting the task to be executed by its own applications processor in coordination with all of the other nodes in the system through the exchange of inter-node messages.

The operations controller has a transmitter for transmitting all of the inter-node messages generated by its own operations controller to all the other nodes in the system. The transmitter has an arbitrator for deciding the order in which the inter-node messages are to be transmitted when two or more messages are ready for transmission. The operations controller further has a plurality of receivers, each receiver associated with a respective one node and only receiving messages from that node and a message checker for checking each received message for physical and logical errors to generate an inter-node error report containing an error status byte identifying each detected error. The message checker polls each of the receivers to unload the received messages in a repetitive sequence. A voter subsystem has a voter for voting on the content of all error free messages containing the same information to generate a voted value and has a deviance checker for generating an inter-node error report identifying each node which sent a message used in the generation of the voted value whose content differed from the voted value by more than a predetermined amount.

The operations controller also has a fault tolerator for passing all error free messages received from the message checker to the voter subsystem, for generating an inter-node error message containing all of the error reports accumulated by all of the subsystems of its own operations controller, for generating a base penalty count for each node in the system based on the number of detected errors and the severity of the detected errors identified in such inter-node error reports, for globally verifying the base penalty count for each node through the exchange of inter-node base penalty count messages, and for generating a system state vector identifying each node whose base penalty count exceeds a predetermined exclusion threshold. The operations controller further includes task scheduler for selecting the next task to be executed by its own applications processor from an active task list, for maintaining a global data base on the scheduling and execution of each node through the exchange of task completed/started messages and for generating an error report whose scheduling process differs from the scheduling process replicated for that node.

The operations controller also has a data memory and a task communicator for storing the voted values in the data memory. The task communicator further has means for passing the identity of the task selected by the scheduler to the applications processor, means for extracting the voted values required for the execution of the selected task and passing them to the applications processor, means for generating the task completed/started messages identifying the task just completed and the new task started by the applications processor and for generating internode data value messages containing the data values generated by the applications processor in the execution of the selected tasks.

The operations controller further includes a synchronizer for synchronizing the operation of its own node with all of the other non-faulty nodes in the system through the exchange of inter-node time-dependent messages.

The object of the invention is an architecture for a multiple node fault tolerant processing system based on the functional and physical partitioning of the application task and the overhead functions.

Another object of the invention is a distributed multiple node processing system in which no one node is required to execute every task of the applications task and in which failure of one or more nodes need not prevent execution of any applications task.

Another object of the invention is a multiple node computer architecture in which task selection and fault detection are globally verified.

Another object of the invention is a fault tolerant computer architecture in which the exclusion or readmittance of a node into the active set of nodes is made on a global basis.

These and other objects of the invention will become more apparent from a reading of the specification in conjunction with the drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of the multi-computer architecture;

FIG. 2 is a block diagram of the Operations Controller;

FIG. 3 is the master/atomic period timing diagram;

FIG. 4 is the atomic/subatomic period timing diagram;

FIG. 5 is a block diagram of the Transmitter;

FIG. 6 is a circuit diagram of one of the interfaces;

FIG. 7 is a block diagram of the Arbitrator;

FIG. 8 shows waveforms for the Self-Test Arbitration Logic;

FIG. 9 is a block diagram of the Longitudinal Redundancy Code Generator;

FIG. 10 is a block diagram of a Receiver;

FIG. 11 is a block diagram of the Message Checker;

FIG. 12 is a block diagram of the decision logic for the Between Limits Checker;

FIG. 13 is the format for the error status byte generated by the Message Checker;

FIG. 14 is a block diagram of the Fault Tolerator;

FIG. 15 shows the partitioning of the Fault Tolerator RAM;

FIG. 16 shows the format of the Message partition of the Fault Tolerator RAM;

FIG. 17 shows the format of the Error Code Files partition of the Fault Tolerator RAM;

FIG. 18 shows the format of the Group Mapping partition of the Fault Tolerator RAM;

FIG. 19 shows the format of the Error Code Files partition of the Fault Tolerator RAM;

FIG. 20 shows the format of the Penalty Weight partition of the Fault Tolerator RAM;

FIG. 21 is a block diagram of the Fault Tolerator's Message Checker Interface;

FIG. 22 is a block diagram of the Fault Tolerator's Error Handler;

FIG. 23 is a block diagram of the Error Handler's Error Consistency Checker;

FIG. 24 is a block diagram of the Error Handler's Validity Checker;

FIG. 25 illustrates the format of the error byte in an error message;

FIG. 26 is a timing diagram of the reconfiguration sequence;

FIG. 27 is a block diagram of the Voter Subsystem;

FIG. 28 is a flow diagram for the Upper and Lower Medial Value Sorters;

FIG. 29 is a circuit diagram of the Lower Medial Value Sorter;

FIG. 30 is a flow diagram for the Averaging Circuit;

FIG. 31 is a circuit diagram of the Averaging Circuit;

FIG. 32 is a flow diagram of the Deviance Checker;

FIG. 33 is a circuit diagram of a Deviance Checker;

FIG. 34 is a block diagram of the Scheduler;

FIG. 35 shows the data format of the Scheduler RAM;

FIG. 36 shows the data format of the Scheduler ROM;

FIG. 37 is a block diagram of the Scheduler's Task Selector Module;

FIG. 38 is a flow diagram of the Wake-Up Sequencer's operation;

FIG. 39 is a flow diagram of the Execution Timer's operation;

FIG. 40 is a flow diagram of the TIC Handler's operation;

FIG. 41 is a flow diagram of the TIC Handler's Selection Queue Update sub-process;

FIG. 42 is a flow diagram of the TIC Handler's Completion/Termination sub-process;

FIG. 43 is a flow diagram of the TIC Handler's Execution Timer Reset sub-process;

FIG. 44 is a flow diagram of the TIC Handler's Priority Scan List Update sub-process;

FIG. 45 is a flow diagram of the Priority Scanner's operation;

FIG. 46 is a flow diagram of the Next Task Selector's operation;

FIG. 47 is a block diagram of the Reconfigure Module;

FIG. 48 is a flow diagram for the Task Swapper's operation in response to a Node being excluded from the operating set;

FIG. 49 is a flow diagram of the Task Swapper's operation in response to a Node being readmitted to the operating set;

FIG. 50 is a flow diagram of the Task Reallocator's operation in response to a Node being excluded from the operating set;

FIG. 51 is a flow diagram of the Task Status Matcher's operation;

FIG. 52 is a block diagram of the Task Communicator;

FIG. 53 is a partial block diagram of the Task Communicator showing the elements associated with the operation of the Store Data Control;

FIG. 54 is a flow diagram of the Store Data Control's operation;

FIG. 55 is a partial block diagram of the Task Communicator showing the elements associated with the operation of the DID Request Handler;

FIG. 56 is a flow diagram of the DID Request Handler's operation;

FIG. 57 is a partial block diagram of the Task Communicator showing the elements associated with the operation of the Task Terminated Recorder;

FIG. 58 is a flow diagram of the Task Terminated Recorder's operation;

FIG. 59 is a partial block diagram of the Task Communicator showing the elements associated with the operation of the Task Started Recorder;

FIG. 60 is a flow diagram of the Task Started Recorder's operation;

FIG. 61 is a partial block diagram of the Task Communicator showing the elements associated with the operation of the AP Input Handler;

FIG. 62 is a flow diagram of the AP Input Handler's operation;

FIG. 63 is a partial block diagram of the Task Communicator showing the elements associated with the operation of the AP Output Handler:

FIG. 64 is a flow diagram showing the AP Output Handler's operation:

FIG. 65 shows the format of the DID information as stored in the DID List;

FIG. 66 shows the format of the DID information with the NUDAT bit appended;

FIG. 67 is a partial block diagram of the Task Communicator showing the subsystems involved in "reconfiguration";

FIG. 68 is a flow diagram showing the operation of the Reconfigure Control during reconfiguration;

FIG. 69 is a partial block diagram of the Task Communicator showing the subsystems involved in "reset";

FIG. 70 is a flow diagram of the Reset Control during reset;

FIG. 71 is a block diagram of the Synchronizer;

FIG. 72 shows the format of the Synchronizer Memory;

FIG. 73 shows the format of the Message Memory;

FIG. 74 shows the format of the Time Stamp Memory;

FIG. 75 shows the format of the Scratch Pad Memory;

FIG. 76 shows the waveforms of the signals generated by the Timing Signal Generator;

FIG. 77 is a block diagram of the Synchronizer Control;

FIG. 78 is a flow diagram showing the operation of the Data Handler and Expected Message Checker;

FIG. 79 is a flow diagram showing the operation of the Within Hard Error Window and Soft Error Window Checker and the Time Stamper;

FIG. 80 is a flow diagram for the operation of the "HEW to warning count";

FIG. 81 is a partial block diagram of the Synchronizer showing the elements associated with the operation of the Message Generator;

FIG. 82 is a flow diagram of the operation of the Message Generator and the Transmitter Interface;

FIG. 83 shows the waveforms of the timing signals for generating a TIC message;

FIG. 84 shows the waveforms of the timing signals for generating a sync System State message;

FIG. 85 shows the format of the "cold start" pre-sync message;

FIG. 86 is a flow diagram showing the operation of the Synchronizer during a "cold start";

FIGS. 87 and 87a are flow diagrams showing the generation of the HEW to warning signal during "cold start";

FIG. 88 is a flow diagram showing the storing of data during a "cold start";

FIG. 89 is a flow diagram showing the operation of the Operating Condition Detector during a "cold start";

FIG. 90 is a timing diagram used in the description of the "cold start";

FIG. 91 is a flow diagram of the operation of the Synchronizer during a "warm start";

FIG. 92 is a timing diagram used in the description of a "warm start";

FIG. 93 is a flow diagram of the operation of the Byzantine Voter to generate Byzantine voted task completed vector and Byzantine voted branch condition bits for the Scheduler;

FIG. 94 is a perspective of the Byzantine Voter's three-dimensional memory;

FIG. 95 shows the two-dimensional format of ISW vectors resulting from the first Byzantine vote on the three-dimensional ISW matrices; and

FIG. 96 is a functional circuit diagram of the Byzantine Voter.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The multi-computer architecture for fault tolerance is a distributed multi-computer system based on the functional and physical partitioning of the application tasks and the overhead functions, such as fault tolerance and systems operations. As shown in FIG. 1, the multi-computer architecture consists of a plurality of Nodes 10a through 10n, each having an Operations Controller 12 for performing the overhead functions and an Applications Processor 14 for executing the application tasks.

For each application, the multi-computer architecture is required to execute a predetermined set of tasks, collectively called application tasks. Each Node is allocated an active task set which is a subset of the application tasks. Each Node in coordination with all of the other Nodes is capable of selecting tasks from its active task set and executing them in a proper sequence. The active task set for each Node may be different from the active task set allocated to the other Nodes and each task in the application tasks may be included in the active task set of two or more Nodes depending upon how many Nodes are in the system and the importance of the task to the particular application. In this way, the multi-computer architecture defines a distributed multi-computer system in which no one Node 10 is required to execute every one of the application tasks, yet the failure of one or more Nodes need not prevent the execution of any application task. As shall be more fully explained later on, the active task set in each Node is static for any given system configuration or system state and will change as the system state changes with an increase or decrease in the number of active Nodes. This change in the active task set called "reconfiguration" takes place automatically and assures that every one of the important or critical application tasks will be included in the active task set of at least one of the remaining active Nodes in the system.

Each Node 10a through 10n is connected to every other Node in the multi-computer architecture through its Operations Controller 12 by means of a private communication link 16. For example, the Operations Controller "A" is the only Operations Controller capable of transmitting on communication link 16a. All of the other Nodes are connected to the communication link 16a and will receive every message transmitted by the Operations Controller "A" over communication link 16a. In a like manner, the Operations Controller "B" of Node 10b is the only Operations Controller capable of transmitting messages on communication link 16b, and Operations Controller N of the Node 10n is the only Operations Controller capable of transmitting messages on communication link 16n.

External information from sensors and manually operated devices collectively identified as Input Devices 20 are transmitted directly to the Applications Processors 14 of each Node through an input line 18. It is not necessary that every Applications Processor receive information from every sensor and/or Input Device, however, each Applications Processor 14 will receive the information from every sensor and/or Input Device which it needs in the execution of the applications task.

In a like manner, the Applications Processor 14 in each Node will transmit data and control signals, resulting from the execution of the applications task to one or more actuators and/or display devices collectively identified as Output Devices 22. The data and/or control signals generated by the Applications Processor 14 in the individual Nodes 10a through 10n may be combined by a Combiner/Voter Network 24 before it is transmitted to the Output Devices 22. Further, when multiple values of the same data and/or control signals are generated by two or more of the Nodes, the Combiner/Voter Network 24 may also be used to generate a single voted value which is transmitted to the Output Devices 22. The use or omission of a Combiner/Voter Network 24 is optional. It is not necessary that every actuator or display receive the output generated by every Node in the system. The specific actuator or display only needs to be connected to the Node or Nodes whose Applications Processor 14 is capable of generating the data or command signals it requires.

The network of Operations Controllers 12 is the heart of the system and is responsible for the inter-node communications, system synchronization, data voting, error detection, error handling, task scheduling, and reconfiguration. The Applications Processors 14 are responsible for the execution of the application tasks and for communications with the Input Devices 20 and Output Devices 22. In the multi-computer architecture, the overhead functions performed by the Operations Controllers 12 are transparent to the operations of the Applications Processor 14. Therefore, the structure of the Applications Processor 14 may be based solely upon the application requirements. Because of this, dissimilar Applications Processors 14 may be used in different Nodes without destroying the symmetry of the multi-computer architecture.

The structural details of the Operations Controller 12 in each Node 10a through 10n are shown in FIG. 2. Each Operations Controller 12 has a Transmitter 30 for serially transmitting messages on the Node's private communication link 16. For discussion purposes, it will be assumed that the Operations Controller illustrated in FIG. 2 is the Operations Controller A as shown in FIG. 1. In this case, the Transmitter 30 will transmit messages on the private communication link 16a. Each Operations Controller also has a plurality of Receivers 32a through 32n, each of which is connected to a different private communication link. In the preferred embodiment, the number of Receivers 32a through 32n is equal to the number of Nodes in the multi-computer architecture. In this way, such Operations Controller 12 will receive all of the messages transmitted by every Node in the system including its own. Each Receiver 32a through 32n will convert each message received over the private communication link to which it is connected from a serial format to a parallel format then forward it to a Message Checker 34. Each Receiver 32a through 32n will also check the vertical parity and the longitudinal redundancy codes appended to each of the received messages and will generate an error signal identifying any errors detected.

The Message Checker 34 monitors the Receivers 32a through 32n and subjects each received message to variety of physical and logical checks. After completion of these physical and logical checks, the messages are sent to a Fault Tolerator 36. Upon the detection of any errors in any message, the Message Checker 34 will generate an error status byte which is also transmitted to the Fault Tolerator 36.

The Fault Tolerator 36 performs five basic functions. First, the Fault Tolerator performs further logical checks on the messages received from the Message Checker 34 to detect certain other errors that were not capable of being detected by the Message Checker 34. Second, the Fault Tolerator passes error free messages to a Voter 38 which votes on the content of all messages containing the same information to generate a voted value. Third, it passes selected fields from the error free messages to other subsystems as required. Fourth, the Fault Tolerator aggregates the internal error reports from the various error detection mechanisms in the Operations Controller and generates Error messages which are transmitted to all of the other Nodes in the system by the Transmitter 30. Finally, the Fault Tolerator 36 monitors the health status of each Node in the system and will initiate a local reconfiguration when a Node is added or excluded from the current number of operating Nodes. The Fault Tolerator 36 maintains a base penalty count table which stores the current base penalty counts accumulated for each Node in the system. Each time a Node transmits a message containing an error, every Node in the system, including the one that generated the message, should detect this error and generate an Error message identifying the Node that sent the message containing the error, the type of error detected, and a penalty count for the detected error or errors. Each Fault Tolerator 36 will receive these Error messages from every other Node and will increment the base penalty count for that Node which is currently being stored in the base penalty count table, if the detection of the error is supported by Error messages received from a majority of the Nodes. The magnitude of the penalty count increment is predetermined and is proportional to the severity of the error. If the incremented base penalty count exceeds an exclusion threshold, as shall be discussed later, the Fault Tolerator initiates a Node exclusion and a reconfiguration process in which the faulty Node is excluded from active participation in the system and the active task sets for the remaining Nodes are changed to accommodate for the reduction in the number of active Nodes.

The Fault Tolerator 36 will also periodically decrement the base penalty count for each Node in the system so that a Node which was previously excluded may be readmitted into the active system. When a previously excluded Node continues to operate in an error free manner for a sufficient period of time, its base penalty count will be decremented below a readmittance threshold which will initiate a Node readmittance and reconfiguration process in which the previously excluded Node is readmitted into the active system. When the previously excluded Node is readmitted into the system the active task set for each Node is readjusted to accommodate for the increase in the number of active Nodes in the system.

The Voter 38 performs an "on-the-fly" vote using all of the current copies of the data values received from the Fault Tolerator 36. The voted data value and all copies of the received data are passed to a Task Communicator 44 which stores them in a Data Memory 42. The Voter will select a voted data value using an appropriate algorithm as shall be discussed relative to the Voter 38 itself. Each time a new copy of a data value is received, a new voted data value is generated which is written over the prior voted data value stored in the Data Memory 42. In this manner, the Data Memory 42 always stores the most current voted data value assuring that a voted data value is always available for subsequent processing independent of one or more copies of the data value failing to be generated or "hang" causing a late arrival. The Voter 38 will also perform a deviance check between the voted data value and each copy of the received data value, and will generate an error vector to the Fault Tolerator identifying each Node which generated a data value which differed from the voted data value by more than a predetermined amount. This arrangement will support both exact and approximate agreement between the copies of the data values. The Voter 38 supports several data types, included pack boolean values, fixed point formats, and the IEEE standard 32-bit floating point format.

A Scheduler 40 has two modes of operation, normal and reconfiguration. In the normal mode of operation the Scheduler 40 is an event driven, priority based, globally verified scheduling system which selects from its active task set the next task to be executed by its associated Application Processor 14. For a given system configuration (set of active Nodes) the active task set assigned to each Node is static. Each time the associated Applications Processor begins a task, the Scheduler 40 selects the next task to be executed. The Applications Processor will immediately begin the execution of the selected task and the Task Communicator 44 will immediately initiate the generation of a message informing all of the other Nodes of the identity of the selected task, the identity of the preceding task finished by the Applications Processor 14, and the branch conditions of the preceding task. Conditional branching is controlled by the Applications Processor 14 and is determined by conditions in the applications environment. The precedence relationship between a task and its successor task may include conditional branches, concurrent forks, and join operations implemented at task boundaries.

Conditional branching provides an efficient means of switching operational modes and avoids the necessity of scheduling tasks not required by the current conditions. An interactive consistency voting process guarantees agreement on the branch conditions generated by the other Nodes which executed the same task.

The Scheduler 40 in each Node replicates the scheduling process for every other Node in the system and maintains a global data base on the scheduling and execution of tasks by each Node. Upon the receipt of a message from another Node identifying the task completed and the task started, the Scheduler 40 will compare the task completed with the task previously reported as started and generate a scheduling error signal if they are not the same. The Scheduler 40 will also compare the task reported as started with a task it has scheduled to be started by that Node. If they are different, the Scheduler will also generate a scheduling error signal. The Scheduler 40 will pass all scheduling error signals to the Fault Tolerator 36. All of the Scheduler's error detection mechanisms are globally verified and have been designed to ensure that failure of one or more copies of a task does not upset scheduling.

In the reconfiguration mode of operation, a reversible path independent reconfiguration algorithm provides graceful degradation of the workload as faulty Nodes are excluded from the operating system. Because the algorithm is reversible it also supports graceful restoration of the workload as previously excluded Nodes are readmitted following an extended period of error free operation.

In reconfiguration, the active task set allocated to each Node is altered to compensate for the change in the number of active Nodes. During reconfiguration after the exclusion of a faulty Node, the active task set, or at least the critical task of a faulty Node's active task set, may be reallocated and included in the active task set of the other Nodes. In other instances, individual tasks may be globally disabled and replaced with simpler tasks, and some noncritical tasks may be disabled with no replacement. The reconfiguration process readjusts the active task set for the active Nodes to accommodate the system capabilities. The algorithm supports true distributed processing, rather than just a replication of uniprocessor task loads on redundant Nodes.

The Task Communicator 44 functions as an input/output (I/O) interface between the Operations Controller 12 and the Applications Processor 14. The Applications Processor 14 signals the Task Communicator 44 when it is ready for the next task. A simple handshaking protocol is employed to synchronize communications between the Applications Processor 14 and the Task Communicator 44. Upon receipt of this signal the Task Communicator 44 reads the selected task from the Scheduler 40 and transfers it to the Applications Processor 14. Concurrently, the Task Communicator 44 will initiate the transmission of the task completed/task started message identifying the task completed by the Applications Processor 14, the task being started by the Applications Processor and the branch conditions of the completed task. The Task Communicator 44 will then fetch the data required for the execution of the started task from the Data Memory 42 and temporarily store it in a buffer in the order in which it is required for the execution of the started task. The Task Communicator will pass these data values to the Applications Processor as they are requested. Effectively, the Task Communicator 44 looks like an input file to the Applications Processor 14.

The Task Communicator 44 also receives the data values generated by the Applications Processor 14 in the execution of the selected task and generates Data Value messages which are broadcast by the Transmitter 30 to all of the other Nodes in the system. The Task Communicator will also append to the Data Value message a data identification (DID) code and a message type (MT) code which uniquely identifies the message as a Data Value message.

A Synchronizer 46 provides two independent functions in the operation of the multi-computer architecture. The first function pertains to the synchronization of the operation of the Nodes 10a through 10n during steady state operation, the second function pertains to the synchronization of the Nodes on start up. During steady state operation, the Synchronizer 46 effects a loose frame base synchronization of the Nodes by the exchange of messages which implicitly denote local clock times. The Synchronizer 46 in each Node counts at its own clock rate, up to a "nominal sync count," then issues a presynchronization System State message which is immediately broadcast by the Transmitter 30 to all of the other Nodes in the system. As the presynchronization System State messages from all the Nodes in the system, including its own, are received at each Node, they are time stamped in the Synchronizer as to their time of arrival from the Message Checker 34. The time stamps are voted on to determine a voted value for the arrival time of the presynchronization System State messages from all the Nodes. The difference between the voted time stamp value and the time stamp of the Node's own presynchronization System State message is an error estimate which is used to compute a corrected sync count. The error estimate includes any accumulated skew from previous synchronization rounds and the effects of clock drift. The Synchronizer 46 will then count up to the corrected sync count and issue a synchronization System State message which is immediately transmitted by the Transmitter 30 to all of the other Nodes in the system. The synchronization System State messages will also be time stamped as to their arrival in the Synchronizers in each Node in the system.

The time stamps of all presynchronization and synchronization System State messages are all compared with the voted time stamp value to determine which Nodes are in synchronization with its own Node and which are not. When the difference in the time stamps exceeds a first magnitude a soft error signal is generated signifying a potential synchronization error. However, if the time stamp difference exceeds a second magnitude, larger than the first magnitude, a hard error signal is generated signifying a synchronization error has definitely occurred. The soft and hard error signals are transmitted to the Fault Tolerator 36 and are handled in the same manner as any other detected error. Start up is defined as a process for creating a functional configuration of Nodes called an "operating set." If an "operating set" is in existence, and the functional configuration is changed by the admittance or readmittance of one or more Nodes, the process is called a "warm start." If no "operating set" is in existence, it is called a "cold start." In a warm start, the Synchronizer 46 will recognize the existence of an operating set and will attempt to achieve synchronization with the operating set. A cold start is initiated by a power on reset (POREST) signal generated in response to the initial application of electrical power to the system. Each Synchronizer 46 will attempt to achieve point-to-point synchronization with all the Nodes until an operating set is formed. Once an operating set is formed, those Nodes are not included in the operating set will switch to the warm start process and will attempt to achieve synchronization with the operating set.

INTER-NODE MESSAGES

The operation of the multi-computer architecture depends upon the exchange of data and operational information by the exchange of inter-node messages. These inter-node messages are data-flow instructions which indicate to each individual Operations Controller how it should be processed.

The various inter-node messages and their information content are listed on Table 1.

                  TABLE I
    ______________________________________
    Inter-Node Message Format
    Message
    Type   Description/ Byte
    Number Abbreviation Number     Context
    ______________________________________
    MT0    One Byte     1          NID/Message Type
           Data Value   2          Data ID
                        3          Data Value
                        3          Data Value
                        4          Block Check
    MT1    Two Byte     1          NID/Message Type
           Data Value   2          Data I.D.
                        3-4        Data Value
                        5          Block Check
    MT1    Task Interactive
                        1          NID/Message Type
           Consistency (TIC)
                        2          Data I.D. = 0
                        3          Task Completed
                                   Vector
                        4          Task Branch
                                   Condition Bits
                        5          Block Check
    MT2    Four Byte    1          NID/Message Type
           Data Value   2          Data I.D.
           (D4B)        3-6        Data Value
                        7          Block Check
    MT3    Four Byte    1          NID/Message Type
           Data Value   2          Data I.D.
           (D4B2)       3-6        Data Value
                        7          Block Check
    MT4    Base Penalty 1          NID/Message Type
           Count        2          Base Count 0
           (BPC)        3          Base Count 1
                        4          Base Count 2
                        5          Base Count 3
                        6          Base Count 4
                        7          Base Count 5
                        8          Base Count 6
                        9          Base Count 7
                        10         Block Check
    MT5    System State 1          NID/Message Type
           (SS)         2          Function Bits
                        3          Task Completed
                                   Vector
                        4          Tank Branch
                                   Condition Bits
                        5          Current System
                                   State
                        6          New System State
                        7          Period Counter
                                   (High)
                        8          Period Counter
                                   (Low)
                        9          ISW Byte
                        10         Reserved
                        11         Block Check
    MT6    Task Completed/
                        1          NID/Message Type
           Started      2          Completed Task ID
           (TC/S)       3          Started Task ID
                        4          Branch Condition/
                                   ECC
                        5          Block Check
    MT7    Error        1          NID/Message Type
           (ERR)        2          Faulty Node ID
                        3          Error Byte 1
                        4          Error Byte 2
                        5          Error Byte 3
                        6          Error Byte 4
                        7          Penalty Base
                                   Count
                        8          Penalty Increment
                                   Count
                        9          Block Check
    ______________________________________

                  TABLE II
    ______________________________________
    FLT-TSC Abitration Logic Table
                Poll Next Then
                              Poll Next Then
    Current Message
                Alternate     Wait for Message
    ______________________________________
    Fault Tolerator
                Task Communicator
    Task Communicator
                Fault Tolerator
    System State              Fault Tolerator
    (Master Period)
    System State
                Task Communicator
    (Atomic Period)
    Interactive Task Communicator
    Consistency
    Self Test                 Task Communicator
    ______________________________________

                  TABLE 3
    ______________________________________
    Message Checker Inerface Context Storage
    Bit  Description   When Written
    ______________________________________
    13   TIC Flag      MT1,    Byte Count = 2 (DID = 0)
    12   Partition Context Bit Byte Count = 15
    11-9 Message Type Code     Byte Count = 1
    8    Branch Condition Bit
                       MT6,    Byte Count = 4
     7-0 Started TID   MT6,    Byte Count = 3
    ______________________________________

                  TABLE IV
    ______________________________________
    Fault Detection Mechanisms
    Error              Subsystem Sym/Asym
    ______________________________________
    Messgae Vertical Parity
                       MSC       A
    Message Longitudinal Redundancy
                       MSC       A
    Message Length     MSC       A
    Synchronization - Hard
                       MSC       A
    Synchronization - Soft
                       MSC       A
    Send Note ID       MSC       S
    Invalid Message Type
                       MSC       S
    Invalid Data ID    MSC       S
    Task ID Sequence   FLT       S
    Data ID Sequence   FLT       S
    Data Limit         MSC       S
    Data Deviance      FLT       S
    Task Run Time      SCH       S
    Current System State
                       FLT       S
    Next System State  FLT       S
    Penalty Count Base Deviance
                       FLT       S
    Penalty Count Increment Deviance
                       FLT       S
    Missed BPC Message FLT       S
    Unsupported Error Report
                       FLT       S
    Missing Error Report
                       FLT       S
    Self Detection Monitor
                       FLT       S
    M.P. Misalignment  SYN       S
    Sync Sequence Error
                       SYN       S
    Sync Missing Message
                       SYN       S
    Too Many Data Messages
                       VTR       S
    AP Reported Error  TSC       S
    Last DID Shipped   TSC       S
    Wrong Message during SEW
                       FLT       A
    Too Many Error Reports
                       VTR       S
    Too Many BPC       VTR       S
    Exceeded Max. No. of Errors
                       FLT       A
    ______________________________________