Operations controller for a fault tolerant multiple node processing system

• US 4,914,657 A
• Filed: 04/15/1987
• Issued: 04/03/1990
• Est. Priority Date: 04/15/1987
• Status: Expired due to Term

• Current Assignee: Allied Corp. (Honeywell International Inc.)
• Original Assignee: Alliedsignal Inc. (Honeywell International Inc.)
• Inventors: Kieckhafer, Roger M., Finn, Alan M., Walter, Chris J.
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US07/038,813
• Time in Patent Office: 1,084 Days
• Field of Search: 371/9, 371/11, 371/36, 364/200
• US Class Current: 714/4.3
• CPC Class Codes: G06F 11/0724 in a multiprocessor or a multi-core unit multiprocessors per se G06F15/80
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/1658 Data re-synchronization of a redundant component, or initial sync of replacement, additional or spare unit
• CPC Class Codes: G06F 11/181 Eliminating the failing redundant component
• CPC Class Codes: G06F 11/182 based on mutual exchange of the output between redundant processing components
• CPC Class Codes: G06F 11/187 Voting techniques
• CPC Class Codes: G06F 11/188 where exact match is not required
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 15/161 Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning casings, cabinets, racks or drawers for data centers H05K5/00
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

An operations controller for a multiple node fault tolerant processing system having a transmitter for transmitting inter-node messages, a plurality of receivers, each receiving inter-node messages from only one of the nodes and a message checker for checking each received message for physical and logical errors. A fault tolerator assembles all of the errors detected and decides which nodes are faulty based on the number and severity of the detected errors. A voter generates a voted value for each value which is received from the other nodes which is stored in a data memory by a task communicator. A scheduler selects the tasks to be executed by an applications processor which is passed to the task communicator. The task communicator passes the selected task and the data required for the execution of that task to the applications processor and transmits the data resulting from that task to all of the nodes in the system. A synchronizer synchronizes the operation of its own node with all of the other nodes in the system.

Claims

1. In a fault tolerant multiple node processing system wherein each node has an applications processor for executing a predetermined set of tasks, wherein each task in said predetermined set of tasks is included in the predetermined set of tasks of at least one other node in the processing system 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 from an active task list the tasks to be executed by its own application processor in coordination with all of the other nodes in the system through the exchange of inter-node messages with all of the other nodes in the system, said active task list containing a selected subset of said predetermined set of tasks, the operations controller comprising:

a transmitter for transmitting all of the inter-node messages generated by its own operations controller to all the nodes in the system including its own node over a private communication link, said transmitter having an arbitrator for deciding the order in which said inter-node messages are to be transmitted when two or more messages are ready for transmission at the same time;

a plurality of receivers, each receiver associated with a respective one of said multiple nodes and only receiving messages from that node;

a message checker connected to said plurality of receivers for checking each received message for physical and logical errors to generate an internal error report containing an error status byte identifying each detected error, said message checker polling each of said receivers to unloadd the received messages in a repetitive sequence;

a voter subsystem having a voter for voting on the content of all error free messages having a value produced by the execution of the same task in said at least one other node to generate a voted value and a deviance checker for generating an internal error report containing a deviance vector identifying each node which sent a message used in the generaion of said voted value whose value differed from the voted value by more than a predetermined deviance value;

a fault tolerator connected to said message checker, said voter subsystem and said transmitter for passing all error free messages received from said message checker to said voter subsystem, for generating an inter-node error message containing all of said error reports accumulated by all the subsystems which is sent to all of the nodes in the system by said transmitter, for generating a base penalty count message containing a base penalty count for each node in the system based on the number of errors detected and the severity of the detected errors identified in said internal error reports which is sent to all of the nodes in the system by said transmitter, 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;

a task scheduler connected to said fault tolerator for selecting the next task to be executed by the node'"'"'s own applications processor from said active task list, for replicating the scheduling of other nodes in the system, for maintaining a global data base in the scheduling and execution of tasks by each node through the exchange of task completed/started messages received from the fault tolerator, and for generating an error report identifying each node whose scheduling process differs from the scheduling process replicated for that node, said task scheduler further having meand to reconfigure said active task list in response to said system state vector received from the fault tolerator indicating a change in the number of non-excluded nodes;

a data memory;

a task communicator connected to said voter subsystem, said data memory, said task scheduler, the transmitter and the applications processor for storing said voted values received from said voter subsystem in said data memory, for passing the identity of the task selected by the task scheduler to the applications processor, for extracting from said data memory the voted values required for the execution of the selected task and passing them to the applications processor, for generating said task completed/started messages identifying the task just completed and the new task started by the applications processor which is transmitted to all the nodes by said transmitter, and for generating inter-node data value messages containing the data values generated by the applicationsprocessor in the execution of the selected tasks which are also transmitted to all the nodes by said transmitter; and

a synchronizer connected to said message checker, said task scheduler and said transmitter 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, said synchronizer generating a time-dependent message which is transmitted by said transmitter to all the nodes in the system, storing a time stamp signifying the local time which each time-dependent message received from said message checker is and correcting the synchronization of said task scheduler of its own node based on the difference between the time stamp of its own time-dependent message and a voted time stamp derived from the time stamps for all the time-dependent messages received within a predetermined time window.

2. The operations controller of claim 1 wherein said transmitter comprises:

a first interface for receiving the inter-node messages generated by said fault tolerator;

a second interface for receiving the inter-node messages generated by said task communicator;

a synchronizer interface for receiving said inter-node time-dependent messages generated by said synchronizer;

an arbitrator connected to said first, second, and synchronizer interfaces responsive to said first, second, and synchronizer interfaces having received messages to be transmitted for arbitrating the priorities of these messages to generate a transmit signal identifying which message is to be transmitted, said arbitrator delaying the transmission of the inter-node messages received by said first and second interfaces if their transmission will interfere with the transmission of said time dependent messages;

a parallel-to-serial converter for converting said inter-node messages to a serial format for transmission over said private communication link to all of the noes in said processing system; and

a first multiplexer connected to said first, said second, and said synchronizer interfaces, said arbitrator and said parallel-to-serial converter for passing the inter-node message stored in one of said first, second, and synchronizer interfaces to said parallel-to-serial converter in response to said transmit signal generated by said arbitrator.

3. The operations controller of claim 2 wherein each of said inter-node messages has a message type code identifying the type of information contained in the message and a data identification code which uniquely identifies the particular data value contained in the message, said message checker comprising:

sequencer means connected to said plurality of receivers for context switching among said plurality of receivers in a predetermined sequence to unload the received inter-node messages from said plurality of receivers;

a context storage connected to said plurality of receivers and said sequencer means for storing the relevant information pertaining to the message being processed, said context storage having one entry for each node, each of said entries storing at least the message type code, the data identification code, a byte count which identifies the specific byte being processed and an error status byte;

error check logic means connected to said plurality of receivers, said sequencer means and said context storage for checking the node identification code contained in the message with reference to the expected node identification code associated with the receiver which received the message, for checking the message type code, for checking the data identification code against a maximum data identification code, and for checking the number of bytes contained in the message, said error check logic means recording all detected errors in said error status byte stored in said context storage;

between limits checker means connected to said plurality of receivers and said error check logic means for checking the data value contained in the mesages against predetermined maximum and minimum limit values and for reporting an exceeds limit error to said error check logic means whenever the data value contained in a message is not within said maximum and minimum limit values, said error check logic means recording said exceeds limits error in said error statusbyte; and

multiplexer means connected to said sequencer, context storage and said fault tolerator for passing on each received message to said fault tolerator for further processing, said multiplexer means appending to each message, as it is passed on, an error report containing said error status byte currently stored in said context storage.

4. The operations controller of claim 3 wherein said fault tolerator comprises:

a data memory connected to said message checker for storing the content of all error free inter-node messages received from said message checker;

an error file for storing the content of all of the received error reports;

error handler means connected to said message checker, said synchronizer, said task scheduler and said voter subsystem for storing the error reports received from said message checker, said synchronizer, said task scheduler and said voter subsystem in said error file and for generating a base penalty count for each node from the content of said error file, said base penalty count being indicative of the operational status of that particular node, said error handler means further having means for determining which nodes are faulty and for excluding such faulty nodes, in coordination with all of the other nodes in the system, from participating in the operation of said multiple node processing system through the exchange of said inter-node messages, said inter-node messages including error messages, each containing the content of said error file for a particular node and a base penalty count message containing the base penalty count of each node; and

interface means for storing in said data memory all of the error free messages passed by said message checker, for passing the identities of the faulty nodes to said task scheduler and said synchronizer, and for passing all error reports to said error handler.

5. The operations controller of claim 4 wherein said voter subsystem comprises:

an upper medial value sorter for sorting the data values received from said fault tolerator to generate an upper medial value;

a lower medial value sorter for sorting the data values received from said fault tolerator to generate a lower medial value;

averaging means connected to said upper and lower medial value sorters for averaging said upper and lower medial values to generate said voted value;

deviance checker means connected to said upper and lower media value sorters for comparing in parallel the content of each received message with said upper and lower medial values to generate said deviance vector; and

loader means connected to said fault tolerator for loading the content of the messages received from said fault tolerator into said upper and lower medial value sorters and said deviance checker means.

6. The operations controller of claim 5 wherein said task scheduler comprises:

a task activity list containing an entry for each active task in said multiple node processing system, each entry containing an execution periodicity and a node allocation for that task;

a priority scan list containing a selected portion of the tasks in said taskactivity list which are available for execution, said selected portion of said tasks being stored in their preferred order of execution;

a completion status list storing the same selected portion of said tasks stored in said priority scan list;

a selection queue storing for each node the tasks ready for selectionin their preferred order of execution;

a period counter for counting fundamental timing periods to generate a period count corresponding to the number of fundamental periods which have expired since the beginning of a new master period;

wake-up sequencer means connected to said task activity list, said priorityscan list and said completion status list for interrogating said task activity list to transfer to said priority scan list and said completion status list all of the tasks contained in said task activity list whose periodicity is greater than said period count;

prioritiy scan means connected to said priority scan list and said selection queue for transferring to said selection queue for each node entry three tasks stored in said priority scan list which are ready for execution by that node in their preferred order of execution;

task selector means connected to said selection queue for selection in said preferred order of execution a task currently stored in said selection queue for its own node as the next task scheduled for execution by its own applications processor; and

a task interactive consistency handler connected to said fault tolerator for updating the status of each task in said task activity list, said priority scan list, said completion status list and said selection queue which are identified in inter-node messages reporting the completion of a task.

7. The operations controller of claim 6 wherein said inter-node messages have a data identification code identifying the type of data contained in that inter-node message and a message type code identifying the type of the inter-node message, said task communicator comprising:

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

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

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

a store data control connected to said voter subsystem for storing said voted values in said data memory using said message type code, said data identification code and the complement of said context bit associated with the voted value as an address for the appropriate entry in said data memory;

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

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

an input handler connected to said next task register, said data memory and said transmitter, responsive to the applications processor completing the preceding task to generate said task completed/started message sent to said transmitter to transmit to sall of the nodes in the processing system, to transfer the task identification code of said next task stored in said next task register to said input FIFO register, and to access said data memory for the voted values required for the execution of said next task, said input handler using said context bits to identify which voted values in said data memory are to be used in the execution of said next task;

an output FIFO register for receiving from said applications processor the data vaues resulting from the execution of each task; and

an output handler connected to said output FIFO register for generating data value messages sent to said transmitter for transmission to all the nodes in said multiple processing system, said data value messages containing the data values stored in the said output FIFO register and the identification code for the data values.

8. The operations controller of claim 7 wherein said time-dependent messages include alternating sync and pre-sync time-dependent messages, said synchronizer comprising:

a message interface connected to said message checker for receiving said sync and pre-sync time-dependent messages;

counter means for generating a local time;

a time stamp memory having one entry for each node in the system, each entry storing a time stamp for the most recent time-dependent message received from the associated node;

a time stamper connected to said message interface, and said counter means, said time stamper responsive to receiving a time-dependent message from said message interface for each node for generating a time stamp corresponding to the local time at which said time-dependent message is received and for storing said time stamp in said time stamp memory in the entry associated with the node from which the time-dependent message was received;

a time stamp voter connected to said time stamp memory for generating a voted time stamp corresponding to a medial value of the time stamps stored in said time stamp memory for said pre-sync time-dependent messages;

a sync correction generator connected to said time stamp memory and said time stamp voter for generating sync delta having a value corresponding to the difference between said voted time stamp and the time stamp of its own pre-sync time-dependent message;

means connected to said sync correction generator for adding said sync delta to a nominal transmission timing interval to generate an actual transmission timing interval, said nonimal transmission timing interval corresponding to a nominal timing interval between the end of the transmission of the sync time-dependent message and the passing of the pre-sync time-dependent message to said transmitter; and

message generator means connected to said means for adding and said transmitter for generating said sync and pre-sync time-dependent messages, said message generator means passing said pre-sync time-dependent messages to said transmitter at the end of said nominal transmission timing interval and passing said sync time-dependent messages to the transmitter at the end of said actual transmission timing interval.