Synchronizer for a fault tolerant multiple node processing system
First Claim
1. In a multiple node processing system having a plurality of nodes, an application processor for processing a predetermined set of tasks and an operations controller for controlling its own node, the operations controller having a transmitter for transmitting a synchronizer for synchronizing its own node with all of the nodes in the system through an exchange of inter-node time-dependent messages comprising alternating presync and sync time-dependent messages separated in time by a nominal timing interval, said synchronizer comprising:
- a message interface for receiving the 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 a most recent time-dependent message received from an associated node;
a time stamper connected to said message interface, said counter means and said time stamp memory, said time stamper responsive to receiving a time-dependent message from each node for generating a time stamp corresponding to a local time at which said time-dependent message is received and for storing said time stamp in said time stamp memory in an 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 said 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 a difference between said voted time stamp and the time stamp of its own pre-sync time-dependent message;
means connected to sid sync correction generator for adding said sync delta to a nominal transmission timing interval for generating an actual transmission timing interval, said nominal transmission timing interval corresponding to a nominal timing interval between the end of the transmission of said sync time-dependent message and a passing of said pre-sync time-dependent message to said transmitter; and
message generator means connected to said means for adding 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 an end of said nominal transmission timing interval and passing said sync time-dependent messages to said transmitter at an end said actual transmission timing interval.
1 Assignment
0 Petitions
Accused Products
Abstract
A synchronizer for each node in a multiple node processing system having a message interface for receiving sync and pre-sync time-dependent message, counter means for generating a local time, a time stamp memory having an entry for each node in the multiple node processing system, a time stamper responsive to receiving a time-dependent message from a node for storing the local time in the entry of said time stamp memory for that node to generate a time stamp. The synchronizer has a time stamp voter for generating a medial time stamp value from all the time stamps in the time stamp memory, a sync correction generator for generating a sync delta having a value corresponding to the difference between the voted time stamp and the node'"'"'s own time stamp, means for adding said sync delta to a nominal transmission timing interval to generate an actual transmission timing interval, and a message generator for generating a pre-sync time dependent message passed to the transmitter at the end of the nominal transmission timing interval and for generating a sync time-dependent message passed to the transmitter at the end of said actual transmission timing interval.
-
Citations
24 Claims
-
1. In a multiple node processing system having a plurality of nodes, an application processor for processing a predetermined set of tasks and an operations controller for controlling its own node, the operations controller having a transmitter for transmitting a synchronizer for synchronizing its own node with all of the nodes in the system through an exchange of inter-node time-dependent messages comprising alternating presync and sync time-dependent messages separated in time by a nominal timing interval, said synchronizer comprising:
-
a message interface for receiving the 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 a most recent time-dependent message received from an associated node; a time stamper connected to said message interface, said counter means and said time stamp memory, said time stamper responsive to receiving a time-dependent message from each node for generating a time stamp corresponding to a local time at which said time-dependent message is received and for storing said time stamp in said time stamp memory in an 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 said 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 a difference between said voted time stamp and the time stamp of its own pre-sync time-dependent message; means connected to sid sync correction generator for adding said sync delta to a nominal transmission timing interval for generating an actual transmission timing interval, said nominal transmission timing interval corresponding to a nominal timing interval between the end of the transmission of said sync time-dependent message and a passing of said pre-sync time-dependent message to said transmitter; and message generator means connected to said means for adding 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 an end of said nominal transmission timing interval and passing said sync time-dependent messages to said transmitter at an end said actual transmission timing interval. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A Byzantine voter comprising:
-
a voter memory having transverse and lateral rows and columns for storing a three-dimensional cube of data, said transverse and lateral rows and columns each having an equal number of bit positions; a data register connected to said vector memory having a plurality of bit positions, said plurality of bit positions at least equal to said number of bit positions in said transverse and lateral rows and columns of said voter memory; an address generator connected to said voter memory for generating addresses enabling said voter memory to unload said data stored in said rows and columns into said data register, one row or one column at a time in a selected sequence; a plurality of AND gates each having one input connected to a respective one of said bit positions in said data register, said AND gates each having a second input and an output; decoder means connected to said address generator and said AND gates responsive to said addresses generated by said address generator for generating individual signals applied to said second input of each of said plurality of AND gates, said decoder means generating an inhibit signal which deactivates one of said plurality of AND gates in a sequential manner each time new data is loaded into said data register; a plurality of multiplexers, one associated with each AND gate, each of said plurality of multiplexers having a first input connected to said output of its associated AND gate, each multiplexer further having a second input and an output; a message counter connected to said plurality of multiplexers for generating a reference number which is applied to said second input of each of said plurality of multiplexers, said reference number corresponding to a 2'"'"'s complement of one half of the number of data values to be processed; a plurality of adders for generating sum data and voted data, each having a first input connected to said output of a respective one of said multiplexers, each of said adders having a second input, a sum output outputting said sum data and an overflow output outputting said voted data; a plurality of accumulators for storing said sum data, each accumulator having an input connected to said sum output of a respective one of said plurality of adders, each of said plurality of accumulators having an output connected back to said second input of the adder to add said sum data back into said adder; a voted data register having a plurality of bit positions, each bit position associated with a respective one of said plurality of adders, each of said bit positions connected to the overflow output of its associated adder and storing said voted data; an output gate connected to said voted data register for passing said voted data stored in said voted data register back to said voter memory in response to a recycle signal; and control logic means responsive to an input signal signifying a particular type of data stored in said voter memory for generating sequence signals identifying the sequence that data from said voter memory is to be loaded into said data register, for generating a load reference number signal enabling said plurality of multiplexers to load said reference number into said plurality of accumulators through said adders, for generating an add signal enabling said multiplexers to pass said data stored in said data registers to said adders to be added to said sum data stored in said accumulators, and for generating said recycle signal when necessary enabling said voted data to be stored in said voter memory. - View Dependent Claims (23, 24)
-
Specification