US5742753A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Mesh interconnected array in a fault-tolerant computer system
Assignee: Boeing Co
•
Filing: 1996-06-06
•
Granted: 1998-04-21
•
Expires: 2016-06-06
Abstract
Abstract Bus interface units (BIUs)(54) perform fault detection, identification, and reconfiguration for all information transfers between redundant central processing units (CPUs)(56) and memory or input/output (I/O)(57A-C) in a mesh interconnected array of a highly reliable fault-tolerant computer system. Errors are detected by self-checking within the BIUs, signal parity checks by the BIUs, cross channel comparisons, and mesh transaction assessments. Fault identification and mesh reconfiguration for the mesh is performed such that no faulty unit remains active in decision making after reconfiguration, and the number of good units isolated during reconfiguration is minimized.
Inventors
- 👤 Arnold W. Nordsieck
- 👤 Christopher A. Young
- 👤 William M. Yost
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 06:28
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/16; G06F11/18; G06F11/181; G06F11/1608; G06F11/1625; G06F11/1666; G06F11/182; G06F11/187
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
439 words
A fault-tolerant computer system, including one or more central processing units (CPUs) each connected to a CPU bus and one or more memory unit each connected to a memory bus, said CPU bus(es) intersecting said memory bus(es), said system further comprising: bus interface units (BIUs) located at the intersections of the CPU bus(es) and the memory bus(es); a transaction means for transmitting a transaction comprising at least one of address data, read data, write data, and control data; a mesh bus for interconnecting predetermined BIUs; said BIUs further comprising: a means for storing a configuration vector representing a BIU's knowledge of the operating status of the BIUs connected to the mesh bus; an error detecting means for detecting correctable, retryable and non-retryable errors in said data of a transaction; an error correcting means for correcting any detected correctable errors; an error asserting means for asserting to all the BIUs via the mesh bus if a retryable or non-retryable error(s) was detected by said error detecting means; a retry means for sending the data back to said error detecting means a preset number of times, if a retryable error remains asserted on the mesh bus; a fault management means for isolating and eliminating said BIU(s) with any detected error(s) remaining after said retry means by reconfiguring the configuration vector of each BIU connected on the mesh bus according to the type of remaining detected error(s) and generating a consensus configuration vector according to the reconfigured configuration vector of each BIU, said fault management means comprising: a self-implicating error means within the fault management means of each BIU for detecting self-implicating errors, shutting down each BIU that detects self-implicating error, asserting the configuration vector of each BIU onto the mesh bus, and generating a consensus configuration vector; a synchronization error means within the fault management means of each BIU for detecting synchronization errors, asserting a first error message to the mesh bus if a synchronization error was detected, performing a first reconfiguration algorithm if a first error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the first reconfiguration algorithm; and memory bus error means within the fault management means of each BIU for detecting memory bus errors, asserting a second error message to the mesh bus if a memory bus error was detected, performing a second reconfiguration algorithm if a second error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the second reconfiguration algorithm; and a continuation means for completing the transaction if no error(s) remain asserted on the mesh bus.
Claim 2
Dependent Claim
439 words
A fault-tolerant computer system, including one or more central processing units (CPUs) each connected to a CPU bus and one or more memory unit each connected to a memory bus, said CPU bus(es) intersecting said memory bus(es), said system further comprising: bus interface units (BIUs) located at the intersections of the CPU bus(es) and the memory bus(es); a transaction means for transmitting a transaction comprising at least one of address data, read data, write data, and control data; a mesh bus for interconnecting predetermined BIUs; said BIUs further comprising: a means for storing a configuration vector representing a BIU's knowledge of the operating status of the BIUs connected to the mesh bus; an error detecting means for detecting correctable, retryable and non-retryable errors in said data of a transaction; an error correcting means for correcting any detected correctable errors; an error asserting means for asserting to all the BIUs via the mesh bus if a retryable or non-retryable error(s) was detected by said error detecting means; a retry means for sending the data back to said error detecting means a preset number of times, if a retryable error remains asserted on the mesh bus; a fault management means for isolating and eliminating said BIU(s) with any detected error(s) remaining after said retry means by reconfiguring the configuration vector of each BIU connected on the mesh bus according to the type of remaining detected error(s) and generating a consensus configuration vector according to the reconfigured configuration vector of each BIU, said fault management means comprising: a self-implicating error means within the fault management means of each BIU for detecting self-implicating errors, shutting down each BIU that detects self-implicating error, asserting the configuration vector of each BIU onto the mesh bus, and generating a consensus configuration vector; a synchronization error means within the fault management means of each BIU for detecting synchronization errors, asserting a first error message to the mesh bus if a synchronization error was detected, performing a first reconfiguration algorithm if a first error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the first reconfiguration algorithm; and memory bus error means within the fault management means of each BIU for detecting memory bus errors, asserting a second error message to the mesh bus if a memory bus error was detected, performing a second reconfiguration algorithm if a second error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the second reconfiguration algorithm; and a continuation means for completing the transaction if no error(s) remain asserted on the mesh bus.
Claim 3
Dependent Claim
36 words
The fault-tolerant computer system of claim 1, wherein said error detecting means further comprises: a single thread read back means for detecting errors of data written to memory when only a single CPU channel is active.
Claim 4
Dependent Claim
34 words
The fault tolerant computer system of claim 1, wherein said error detecting means further comprises: a single thread readback means for detecting errors of data written in memory when only disjoint BIUs are active.
Claim 5
Dependent Claim
79 words
The fault tolerant computer system according to claim 1, wherein said fault management means comprises: CPU bus error means within the fault management means of each BIU for detecting CPU bus errors, asserting a third error message to the mesh bus if a CPU bus error was detected, performing a third reconfiguration algorithm if a third error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the third reconfiguration algorithm.
Claim 6
Dependent Claim
43 words
The fault-tolerant computer system according to claim 4, wherein said fault management means transmits data through the error detecting means in the following order: the self-implicating error means; the synchronization error means; the memory bus error means; and the CPU bus error means.
Claim 7
Dependent Claim
49 words
The fault tolerant computer system according to claim 1, wherein said fault management means further comprises: a storing means for storing the consensus configuration vector; and a reconfiguration means for generating a consensus configuration vector, if the consensus configuration vector does not match a previously stored consensus configuration vector.
Claim 8
Dependent Claim
394 words
A fault-tolerant computing method, including one or more central processing units (CPUs) each connected to a CPU bus and one or more memory units each connected to a memory bus, each CPU bus intersects each memory bus, said method comprising the steps of: transmitting a transaction comprising at least one of address data, read data, write data, or control data; connecting predetermined BIUs by a mesh bus; detecting within said BIUs correctable, retryable and non-retryable errors in said data of the transaction; correcting any correctable errors detected; asserting an error message to all the BIUs via the mesh bus if a retryable or non-retryable error(s) was detected; generating a configuration vector for each BIU, said configuration vector representing the BIU's knowledge of the operating status of all BIUs connected to the mesh bus; completing the transaction if no error messages are asserted on the mesh bus; sending the data back to said error detecting step a preset number of times if a retryable error(s) remains asserted on the mesh bus; isolating and eliminating within said BIUs any remaining retryable or non-retryable error(s) by reconfiguring the configuration vector of each BIU connected on the mesh bus according to the type of detected error(s) and generating a consensus configuration vector according to the reconfigured configuration vector, said step of isolating and eliminating comprising: a step of detecting within each BIU self-implicating errors, shutting down each BIU that detects an uncorrectable self-implicating error, and asserting a message to the mesh bus indicating the status of each BIU and a step of performing a configuration consistency algorithm; a step of detecting within each BIU synchronization errors, asserting a first error message to the mesh bus if a synchronization error was detected, and performing a first reconfiguration algorithm if a first error message is asserted on the mesh bus and a step of performing said configuration consistency algorithm according to the results of the first reconfiguration algorithm; and a step of detecting within each BIU memory bus errors, asserting a second error message to the mesh bus if a memory bus error was detected, and performing a second reconfiguration algorithm if a second error message is asserted on the mesh bus and a step of performing said configuration consistency algorithm according to the results of the second reconfiguration algorithm; and completing the transaction according to the reconfigured configuration vector.
Claim 9
Dependent Claim
394 words
A fault-tolerant computing method, including one or more central processing units (CPUs) each connected to a CPU bus and one or more memory units each connected to a memory bus, each CPU bus intersects each memory bus, said method comprising the steps of: transmitting a transaction comprising at least one of address data, read data, write data, or control data; connecting predetermined BIUs by a mesh bus; detecting within said BIUs correctable, retryable and non-retryable errors in said data of the transaction; correcting any correctable errors detected; asserting an error message to all the BIUs via the mesh bus if a retryable or non-retryable error(s) was detected; generating a configuration vector for each BIU, said configuration vector representing the BIU's knowledge of the operating status of all BIUs connected to the mesh bus; completing the transaction if no error messages are asserted on the mesh bus; sending the data back to said error detecting step a preset number of times if a retryable error(s) remains asserted on the mesh bus; isolating and eliminating within said BIUs any remaining retryable or non-retryable error(s) by reconfiguring the configuration vector of each BIU connected on the mesh bus according to the type of detected error(s) and generating a consensus configuration vector according to the reconfigured configuration vector, said step of isolating and eliminating comprising: a step of detecting within each BIU self-implicating errors, shutting down each BIU that detects an uncorrectable self-implicating error, and asserting a message to the mesh bus indicating the status of each BIU and a step of performing a configuration consistency algorithm; a step of detecting within each BIU synchronization errors, asserting a first error message to the mesh bus if a synchronization error was detected, and performing a first reconfiguration algorithm if a first error message is asserted on the mesh bus and a step of performing said configuration consistency algorithm according to the results of the first reconfiguration algorithm; and a step of detecting within each BIU memory bus errors, asserting a second error message to the mesh bus if a memory bus error was detected, and performing a second reconfiguration algorithm if a second error message is asserted on the mesh bus and a step of performing said configuration consistency algorithm according to the results of the second reconfiguration algorithm; and completing the transaction according to the reconfigured configuration vector.
Claim 10
Dependent Claim
48 words
The fault-tolerant computing method of claim 7, wherein said step of detecting further comprises the steps of: reading back said data of the completed transaction if the transaction is a write transaction when only a single CPU channel is active and detecting the read back data for errors.
Claim 11
Dependent Claim
47 words
The fault tolerant computing method of claim 7, wherein said step of detecting further comprises the steps of: reading back said data of the completed transaction if the transaction is a write transaction when only disjoint BIUs are active and detecting the read back data for errors.
Claim 12
Dependent Claim
79 words
The fault-tolerant computing method according to claim 7, wherein said step of isolating and eliminating comprises a step of detecting within each BIU for any CPU bus errors, asserting a third error message to the mesh bus if a CPU bus error was detected, and performing a third reconfiguration algorithm if a third error message is asserted on the mesh bus and a step of performing said configuration consistency algorithm according to the results of the third reconfiguration algorithm.
Claim 13
Dependent Claim
38 words
The fault-tolerant computing method according to claim 7, further comprising the steps of: storing the consensus configuration vector; and regenerating a consensus configuration vector, if the consensus configuration vector does not match a previously stored consensus configuration vector.
Claim 14
Dependent Claim
408 words
A fault-tolerant computer system, including one or more central processing units (CPUs) each connected to a CPU bus and one or more memory units each connected to a memory bus, said CPU bus(es) intersecting said memory bus(es), said system further comprising: bus interface units (BIUs) located at the intersections of the CPU bus(es) and the memory bus(es); a transaction means for transmitting a transaction comprising at least one of address data, read data, write data, and control data; a mesh bus for interconnecting predetermined BIUs; said BIUs further comprising: a means for storing a configuration vector representing a BIU's knowledge of the operating status of the BIUs connected to the mesh bus; an error detecting means for detecting correctable, retryable and non-retryable errors in said data of a transaction; an error correcting means for correcting any detected correctable errors; an error asserting means for asserting to all the BIUs via the mesh bus if a retryable or non-retryable error(s) was detected by said error detecting means; a retry means for sending the data back to said error detecting means a preset number of times, if a retryable error remains asserted on the mesh bus; a fault management means for isolating and eliminating said BIU(s) with any detected error(s) remaining after said retry means by reconfiguring the configuration vector of each BIU connected on the mesh bus according to the type of remaining detected error(s) and generating a consensus configuration vector according to the reconfigured configuration vector of each BIU, said fault management means comprising: a first error means within the fault management means of each BIU for detecting a predetermined first type of error, asserting a first error message to the mesh bus if the first type of error was detected, performing a first reconfiguration algorithm if a first error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the first reconfiguration algorithm; and a second error means within the fault management means of each BIU for detecting a predetermined second type of error, asserting a second error message to the mesh bus if the second type of error was detected, performing a second reconfiguration algorithm if a second error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the second reconfiguration algorithm; and a continuation means for completing the transaction if no error(s) remain asserted on the mesh bus.
Claim 15
Dependent Claim
408 words
A fault-tolerant computer system, including one or more central processing units (CPUs) each connected to a CPU bus and one or more memory units each connected to a memory bus, said CPU bus(es) intersecting said memory bus(es), said system further comprising: bus interface units (BIUs) located at the intersections of the CPU bus(es) and the memory bus(es); a transaction means for transmitting a transaction comprising at least one of address data, read data, write data, and control data; a mesh bus for interconnecting predetermined BIUs; said BIUs further comprising: a means for storing a configuration vector representing a BIU's knowledge of the operating status of the BIUs connected to the mesh bus; an error detecting means for detecting correctable, retryable and non-retryable errors in said data of a transaction; an error correcting means for correcting any detected correctable errors; an error asserting means for asserting to all the BIUs via the mesh bus if a retryable or non-retryable error(s) was detected by said error detecting means; a retry means for sending the data back to said error detecting means a preset number of times, if a retryable error remains asserted on the mesh bus; a fault management means for isolating and eliminating said BIU(s) with any detected error(s) remaining after said retry means by reconfiguring the configuration vector of each BIU connected on the mesh bus according to the type of remaining detected error(s) and generating a consensus configuration vector according to the reconfigured configuration vector of each BIU, said fault management means comprising: a first error means within the fault management means of each BIU for detecting a predetermined first type of error, asserting a first error message to the mesh bus if the first type of error was detected, performing a first reconfiguration algorithm if a first error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the first reconfiguration algorithm; and a second error means within the fault management means of each BIU for detecting a predetermined second type of error, asserting a second error message to the mesh bus if the second type of error was detected, performing a second reconfiguration algorithm if a second error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the second reconfiguration algorithm; and a continuation means for completing the transaction if no error(s) remain asserted on the mesh bus.
Claim 16
Dependent Claim
82 words
The fault-tolerant computer system according to claim 12, wherein said fault management means comprises a third error means within the fault management means of each BIU for detecting a predetermined third type of error, asserting a third error message to the mesh bus if the third type of error was detected, performing a third reconfiguration algorithm if a third error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the third reconfiguration algorithm.
Claim 17
Dependent Claim
36 words
The fault-tolerant computer system according to claim 12, wherein each of the first and second error means detects errors selected from the group consisting of: self-implicating errors, synchronization errors, memory bus errors, and CPU bus errors.
Claim 18
Dependent Claim
34 words
The fault-tolerant computer system according to claim 12, wherein each of the first and second error means detects errors selected from the group consisting of: synchronization errors, memory bus errors and CPU bus errors.
Claim 19
Dependent Claim
355 words
A fault-tolerant computing method, including one or more central processing units (CPUs) each connected to a CPU bus and one or more memory units each connected to a memory bus, each CPU bus intersects each memory bus, said method comprising the steps of: transmitting a transaction comprising at least one of address data, read data, write data, or control data; connecting predetermined BIUs by a mesh bus; detecting within said BIUs correctable, retryable and non-retryable errors in said data of the transaction; correcting any correctable errors detected; asserting an error message to all the BIUs via the mesh bus if a retryable or non-retryable error(s) was detected; generating a configuration vector for each BIU, said configuration vector representing the BIU's knowledge of the operating status of all BIUs connected to the mesh bus; completing the transaction if no error messages are asserted on the mesh bus; sending the data back to said error detecting step a preset number of times if a retryable error(s) remains asserted on the mesh bus; isolating and eliminating within said BIUs any remaining retryable or non-retryable error(s) by reconfiguring the configuration vector of each BIU connected on the mesh bus according to the type of detected error(s) and generating a consensus configuration vector according to the reconfigured configuration vector, said step of isolating and eliminating comprising: a first step of detecting a predetermined first type of error, asserting a first error message to the mesh bus if the first type of error was detected, and performing a first reconfiguration algorithm if the first error message is asserted on the mesh bus and performing a configuration consistency algorithm according to the results of the first reconfiguration algorithm; and a second step of detecting within each BIU a predetermined second type of error, asserting a second error message to the mesh bus if the second type of error was detected, and performing a second reconfiguration algorithm if a second error message is asserted on the mesh bus and performing said configuration consistency algorithm according to the results of the second reconfiguration algorithm; and completing the transaction according to the reconfigured configuration vector.
Claim 20
Dependent Claim
355 words
A fault-tolerant computing method, including one or more central processing units (CPUs) each connected to a CPU bus and one or more memory units each connected to a memory bus, each CPU bus intersects each memory bus, said method comprising the steps of: transmitting a transaction comprising at least one of address data, read data, write data, or control data; connecting predetermined BIUs by a mesh bus; detecting within said BIUs correctable, retryable and non-retryable errors in said data of the transaction; correcting any correctable errors detected; asserting an error message to all the BIUs via the mesh bus if a retryable or non-retryable error(s) was detected; generating a configuration vector for each BIU, said configuration vector representing the BIU's knowledge of the operating status of all BIUs connected to the mesh bus; completing the transaction if no error messages are asserted on the mesh bus; sending the data back to said error detecting step a preset number of times if a retryable error(s) remains asserted on the mesh bus; isolating and eliminating within said BIUs any remaining retryable or non-retryable error(s) by reconfiguring the configuration vector of each BIU connected on the mesh bus according to the type of detected error(s) and generating a consensus configuration vector according to the reconfigured configuration vector, said step of isolating and eliminating comprising: a first step of detecting a predetermined first type of error, asserting a first error message to the mesh bus if the first type of error was detected, and performing a first reconfiguration algorithm if the first error message is asserted on the mesh bus and performing a configuration consistency algorithm according to the results of the first reconfiguration algorithm; and a second step of detecting within each BIU a predetermined second type of error, asserting a second error message to the mesh bus if the second type of error was detected, and performing a second reconfiguration algorithm if a second error message is asserted on the mesh bus and performing said configuration consistency algorithm according to the results of the second reconfiguration algorithm; and completing the transaction according to the reconfigured configuration vector.
Claim 21
Dependent Claim
77 words
The fault-tolerant computer system according to claim 16, wherein isolating and eliminating step further comprises a third step of detecting within each BIU a predetermined third type of error, asserting a third error message to the mesh bus if the third type of error was detected, performing a third reconfiguration algorithm if a third error message is asserted on the mesh bus and generating a consensus configuration vector according to the results of the third reconfiguration algorithm.
Claim 22
Dependent Claim
37 words
The fault-tolerant computing method according to claim 16, wherein each of the first and second error detecting steps detects errors selected from the group consisting of: self-implicating errors, synchronization errors, memory bus errors, and CPU bus errors.
Claim 23
Dependent Claim
35 words
The fault-tolerant computing method according to claim 16, wherein each of the first and second error detecting steps detects errors selected from the group consisting of: synchronization errors, memory bus errors and CPU bus errors.
References Cited (Backward Citations)
US4493081A
Cited
US4438494A
Cited
US4503535A
Cited
US4503534A
Cited
US4570261A
Cited
US4589066A
Cited
US4697344A
Cited
US4914657A
Cited
US5212785A
Cited
US5048816A
Cited
US5477492A
Cited
US5517616A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-04-20 | 2001-10-20 | 2002-04-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-04-20 | 2005-10-20 | 2006-04-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-04-20 | 2009-10-20 | 2010-04-21 | $7700.00 | Window Closed / Lapsed |