Sequoia Systems, Inc.

Texas Micro, Inc.

Raytheon Company

Jack J Stiffler

James M Nolan

Michael J Budwey

David A Wallace

Richard A Karp

James K Mathewes, Jr

Richard B Goud

David Harvey

Jan S Hermam

Stephen C Johnson

Peter Mark

A mechanism for maintaining a consistent, periodically updated state in main memory without constraining normal computer operation is provided, thereby enabling a computer system to recover from faults without loss of data or processing continuity. In this invention, a first computer includes a processor and input/output elements connected to a main memory subsystem including a primary element. A second computer has a remote checkpoint memory element, which may include one or more buffer memories and a shadow memory, which is connected to the main memory subsystem of the first computer. During normal processing, an image of data written to the primary memory element is captured by the remote checkpoint memory element. When a new checkpoint is desired (thereby establishing a consistent state in main memory to which all executing applications can safely return following a fault), the data previously captured is used to establish a new checkpointed state in the second computer. In case of failure of the first computer, the second computer can be restarted to operate from the last checkpoint established for the first computer. This structure and protocol can guarantee a consistent state in main memory, thus enabling fault-tolerant operation.

Remote checkpoint memory system and protocol for fault-tolerant computer

A mechanism for maintaining a consistent, periodically updated state in main memory without constraining normal computer operation is provided, thereby enabling a computer system to recover from faults without loss of data or processing continuity. In a typical computer system, a processor and input/output elements are connected to a main memory subsystem. A checkpoint memory element, which may include one or more buffer memories and a shadow memory, is also appended to this main memory subsystem. During normal processing, an image of data written to primary memory is captured by the checkpoint memory element. When a new checkpoint is desired, thereby establishing a consistent state in main memory to which all executing applications can safely return following a fault, the data previously captured is used to establish that checkpoint. This structure and protocol can guarantee a consistent state in main memory, thus enabling fault-tolerant operation.

Main memory system and checkpointing protocol for fault-tolerant

A mechanism for maintaining a consistent state in main memory without constraining normal computer operation is provided, thereby enabling a computer system to recover from faults without loss of data or processing continuity. In a typical computer system, a processor and input/output elements are connected to a main memory via a memory bus. A shadow memory element, which includes a buffer memory and a main storage element, is also attached to this memory bus. During normal processing, data written to primary memory is also captured by the buffer memory of the shadow memory element. When a checkpoint is desired (thereby establishing a consistent state in main memory to which all executing applications can safely return following a fault), the data previously captured in the buffer memory is then copied to the main storage element of the shadow memory element. This structure and protocol can guarantee a consistent state in main memory, thus enabling fault-tolerant operation.

A mechanism for returning a computer system to a consistent, periodically updated state in main memory without constraining normal computer operation is provided, thereby enabling a computer system to recover from faults without loss of data or processing continuity. In a typical computer system, a processor and input/output elements are connected to a main memory subsystem that includes a primary memory. A checkpoint memory element which may include one or more buffer memories, including a read buffer and a write buffer, and an exclusive-or memory block, is also appended to this main memory subsystem. The exclusive-or memory block is a block of memory corresponding in size to one block of the primary memory that can fail as a unit. The exclusive-or memory block contains an exclusive-or of the contents of the primary memory at a previous checkpoint state. During normal processing, both or either a pre-image and/or a post image of data written to primary memory may be captured by the checkpoint memory element. In one embodiment, a write operation is converted to a read-then-write operation to store pre-image data in a FIFO. An exclusive-or of pre-image and post-image data is exclusive-or'ed into the exclusive-or memory. When a fault occurs in the computer system, the data stored in the buffer memories, along with the contents of the exclusive-or memory block, are used to ensure that the primary memory is restored to a previous checkpointed state from which the computer system can recover. This structure and protocol can guarantee a consistent state in the primary memory, thus enabling fault-tolerant operation.

A mechanism for maintaining a consistent, periodically updated state in main memory without constraining normal computer operation is provided, thereby enabling a computer system to recover from faults without loss of data or processing continuity. In a typical computer system, a processor and input/output elements are connected to a main memory subsystem that includes a primary memory. In embodiments of the present invention, a read buffer is also appended to this main memory subsystem. During normal processing, a pre-image of data written to the primary memory may be captured by the read buffer. Data captured in the read buffer can restore the system to a previous checkpoint. This structure and protocol can guarantee a consistent state in main memory, thus enabling fault-tolerant operation.

Main memory system and checkpointing protocol for a fault-tolerant

Computer system resources shared by several central processing units are allocated by allowing one processing unit to temporarily gain exclusive access to a particular shared resource. Access to a particular resource is controlled by a memory location which contains information representing the current state of the resource and the identity of any processing element currently utilizing the resource. In the case where several resources are interchangeable, the memory location may also contain information regarding the busy/idle states of other interchangeable resources. The memory location can be interrogated by any of the processing elements via command and address information. If the contents of the memory location indicate that the associated resource is not in use, then the interrogating processing element immediately obtains control of the resource. If the resource is in use, the identity of the processing element currently using the resource and any stored resource state information is returned to the interrogating processing element which can then continue processing without the resource or choose another idle resource.

Shared computer resource allocation system having apparatus for

A microprogrammed control unit of an information processing system having a control sequencer with dual microprogram counters for performing microdiagnostics simultaneously with performing macroprograms. The microdiagnostics comprise background and operability tests, the background tests being interleaved with macroinstruction operations under the control of the two independent microprogam counters. The background tests are run during processor idle time and the operability tests are executed at processor turn-on. The organization of the microdiagnostics into a hierarchical structure allows the use of the same microprogrammed test module for both the background and operability microdiagnostic tests. A prediction/residual coding technique provides fault detection for address and data information within the control sequencer.

Control sequencer with dual microprogram counters for microdiagnostics

Apparatus for maintaining duplicate copies of information stored in fault-tolerant computer main memories is disclosed. A non write-through cache memory associated with each of the system's processing elements stores computations generated by that processing element. At a context switch, the stored information is sequentially written to two separate main memory units. A separate status area in main memory is updated by the processing element both before and after each writing operation so that a fault occurring during data processing or during any storage operation leaves the system with sufficient information to be able to reconstruct the data without loss of integrity. To efficiently transfer information between the cache memory and the system main memories without consuming a large amount of processing time at context switches, a block status memory associated with the cache memory contains an entry for each data block in the cache memory. The entry indicates whether the corresponding data block has been modified during data processing or written with computational data from the processing element. The storage operations are carried out by high-speed hardware which stores only the modified data blocks. Additional special-purpose hardware simultaneously invalidates all cache memory entries so that a new task can be loaded and started.

Memory back up system with one cache memory and two physically separated

Encoding/decoding circuitry which processes data and both corrects single errors and detects multiple errors is disclosed. The circuitry is both fail-safe and self-checking in that no internal device failure can alter data without producing improperly encoded outputs and all failures quickly reveal themselves through normal usage even if they do not actually cause any data to be modified. The circuitry can be configured in two identical halves with each half operating on one half of the data so that the circuitry can be advantageously constructed with large scale integrated circuits. Error-detecting information in the form of a syndrome produced by each circuit half is combined with similar syndrome information produced by the other circuit half. The combined syndrome information is then decoded to generate error correction information which is used to modify the data bit outputs to correct detected errors. A failure in either circuit half modifies the combined syndrome information in such a way that the modification can either be detected or else causes no erroneous data bit modification.

Self-checking error correcting encoder/decoder

Memory back-up system

A multi-processor computer system is disclosed in which processing elements, memory elements and peripheral units can be physically added and removed from the system without disrupting its operation or necessitating any reprogramming of software running on the system. The processing units, memory units and peripheral units are all coupled to a common system bus by specialized interface units. The processing elements are organized into partially independent groups each of which has dedicated interface units, but the processing units share system resources including peripherals and the entire memory space. Within each processing element group at any one time, group supervisory tasks are performed by one of the processors, but the supervisor function is passed among the processors in the group in a sequence to prevent a fault in one processor from disabling the entire group. Communication between groups is accomplished via the common memory areas. The transfer of the supervisor function from processor to processor is performed by registering the supervisor's identity in a common area in one of the dedicated interface units which area is accessable to all processors in the associated group and using program interrupts generated in the common interface unit to communicate between group processors. Access to the common system bus by the processing elements is controlled by the associated interface units by means of a combination serial/parallel arbitration scheme which increases arbitration speed without requiring a full complement of request/grant leads.

Modular computer system

Circuitry for a fault-tolerant computer is disclosed which circuitry is constructed in two identical halves. Each half, by itself, is not a functionally-complete circuit, however, the two identical halves can be connected together to provide a functionally-complete circuit. Each of the two circuit halves is considerably less complex than a functionally-complete circuit yet, when connected together, the two halves provide fault detection capabilities equivalent to a computer system in which the outputs of two functionally-complete, redundant circuits are compared to detect faults. In particular, each inventive circuit half contains a complete data processing and control unit but only one half of the memory which is necessary for a functionally-complete unit. The processing units on each circuit half operate simultaneously on identical data and the same address information is provided to the memories on each circuit half. To provide error detection, address information and data sent from each control unit to its associated memory is compared between circuit halves. In addition, information provided to the circuits over an external bus or generated by the control unit is encoded with an error-detecting code.

Growing community of inventors

Hopkinton, MA, United States of America

Jack J Stiffler