US5864657A — Main memory system and checkpointing protocol for…

Claim 1

Independent Claim 197 words

A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor and connected to a main memory system, wherein the processor has means for queuing input/output events between checkpoints; wherein the main memory system includes: i) a primary memory element; ii) a buffer memory element connected to the primary memory element such that data and addresses of write accesses to the primary memory element are captured in the buffer memory element simultaneously with the write access to the primary memory element; iii) a shadow storage element connected to the buffer memory; iv) means for copying data from the buffer memory element to the shadow storage element in response to an instruction to perform such copying from the processor; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the means for copying after flushing of the cache, internal registers and queued input/output events has completed.

Claim 2

Dependent Claim 197 words

A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor and connected to a main memory system, wherein the processor has means for queuing input/output events between checkpoints; wherein the main memory system includes: i) a primary memory element; ii) a buffer memory element connected to the primary memory element such that data and addresses of write accesses to the primary memory element are captured in the buffer memory element simultaneously with the write access to the primary memory element; iii) a shadow storage element connected to the buffer memory; iv) means for copying data from the buffer memory element to the shadow storage element in response to an instruction to perform such copying from the processor; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the means for copying after flushing of the cache, internal registers and queued input/output events has completed.

Claim 3

Dependent Claim 169 words

A memory system for use with at least two processors, each connected to the memory system and having a cache of arbitrary size, internal registers and a queue of input/output events, wherein the cache, internal registers and queue of each processor are periodically flushed by the processors in synchronization, comprising: a primary memory element; a buffer memory physically disjoint from and connected to the primary memory such that data and addresses of write accesses to the primary memory element are captured in the buffer memory element simultaneously with the write access to the primary memory element; a shadow storage element connected to the buffer memory and physically disjoint from the primary memory and the buffer memory; means for copying data in the buffer memory to appropriate locations in the shadow storage element when the processors complete flushing of their caches, internal registers and queues, thereby establishing a consistent checkpoint in the memory system from which processing can resume without loss of data integrity or program continuity following a fault.

Claim 4

Dependent Claim 169 words

A memory system for use with at least two processors, each connected to the memory system and having a cache of arbitrary size, internal registers and a queue of input/output events, wherein the cache, internal registers and queue of each processor are periodically flushed by the processors in synchronization, comprising: a primary memory element; a buffer memory physically disjoint from and connected to the primary memory such that data and addresses of write accesses to the primary memory element are captured in the buffer memory element simultaneously with the write access to the primary memory element; a shadow storage element connected to the buffer memory and physically disjoint from the primary memory and the buffer memory; means for copying data in the buffer memory to appropriate locations in the shadow storage element when the processors complete flushing of their caches, internal registers and queues, thereby establishing a consistent checkpoint in the memory system from which processing can resume without loss of data integrity or program continuity following a fault.

Claim 5

Dependent Claim 209 words

A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor, wherein the processor has means for queuing input/output events between checkpoints; a main memory having a primary memory element connected to the processor; a buffer memory connected to the primary memory element such that the buffer memory captures data and addresses of write accesses to the primary memory element simultaneously with the write access to the primary memory element; a shadow storage element connected to the buffer memory; and a memory control logic circuit, connected to the shadow storage element and the buffer memory and having outputs to control the shadow storage element and the buffer memory to copy data from the buffer memory to the shadow storage element in response to instructions from the processor; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the memory control logic to copy data after flushing of the cache, internal registers and queued input/output events has completed.

Claim 6

Dependent Claim 209 words

A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor, wherein the processor has means for queuing input/output events between checkpoints; a main memory having a primary memory element connected to the processor; a buffer memory connected to the primary memory element such that the buffer memory captures data and addresses of write accesses to the primary memory element simultaneously with the write access to the primary memory element; a shadow storage element connected to the buffer memory; and a memory control logic circuit, connected to the shadow storage element and the buffer memory and having outputs to control the shadow storage element and the buffer memory to copy data from the buffer memory to the shadow storage element in response to instructions from the processor; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the memory control logic to copy data after flushing of the cache, internal registers and queued input/output events has completed.

Claim 7

Dependent Claim 261 words

In a computer system having first processor with a first cache, first internal registers and a first queue of input/output events and a second processor with a second cache, second internal registers and a second queue of input/output events, each cache being connected to a main memory and for caching data from the main memory, the main memory comprising a primary memory, a buffer memory connected to the primary memory such that data and addresses of write accesses to the primary memory are captured in the buffer memory simultaneously with the write access to the primary memory, and a shadow storage element connected to the buffer memory, a method for synchronizing flushing of caches, internal registers and queues to maintain a consistent state of the computer system in the main memory, the method comprising the steps, performed by the first processor, of: setting a lock and suspending normal operations; flushing the first cache, the first internal registers and the first queue to the primary memory such that the buffer memory captures data flushed from the first cache, first internal registers and first queue; waiting until the second processor commences flushing of the second cache, second internal registers and a second queue such that the buffer memory captures data flushed from the second cache and second internal registers; identifying which processor has written the data in the buffer memory; instructing the buffer memory to copy data flushed from each processor having completed flushing and captured in the buffer memory to the shadow storage element; and releasing the lock and resuming normal operations.

Claim 8

Dependent Claim 261 words

In a computer system having first processor with a first cache, first internal registers and a first queue of input/output events and a second processor with a second cache, second internal registers and a second queue of input/output events, each cache being connected to a main memory and for caching data from the main memory, the main memory comprising a primary memory, a buffer memory connected to the primary memory such that data and addresses of write accesses to the primary memory are captured in the buffer memory simultaneously with the write access to the primary memory, and a shadow storage element connected to the buffer memory, a method for synchronizing flushing of caches, internal registers and queues to maintain a consistent state of the computer system in the main memory, the method comprising the steps, performed by the first processor, of: setting a lock and suspending normal operations; flushing the first cache, the first internal registers and the first queue to the primary memory such that the buffer memory captures data flushed from the first cache, first internal registers and first queue; waiting until the second processor commences flushing of the second cache, second internal registers and a second queue such that the buffer memory captures data flushed from the second cache and second internal registers; identifying which processor has written the data in the buffer memory; instructing the buffer memory to copy data flushed from each processor having completed flushing and captured in the buffer memory to the shadow storage element; and releasing the lock and resuming normal operations.

Claim 9

Independent Claim 168 words

A method for maintaining a consistent state of a computer system in main memory to support fault tolerance in the computer system, wherein the computer system includes a first computer having a first cache, internal registers and queue of input/output events, a second computer having a second cache, internal registers and queue of input/output events, wherein the first and second caches hold data accessed from a primary memory by the first and second computers, and wherein the first and second computers may modify said data in the primary memory, the method including the steps of: monitoring the primary memory to detect a write of data to the primary memory; copying the data written to the primary memory into a buffer memory simultaneously with the data written to the primary memory; periodically flushing data from the first cache, internal registers and queue and the second cache, internal registers and queue into the primary memory in synchronization; after flushing, copying data from the buffer memory into a shadow storage element.

Claim 10

Independent Claim 168 words

A method for maintaining a consistent state of a computer system in main memory to support fault tolerance in the computer system, wherein the computer system includes a first computer having a first cache, internal registers and queue of input/output events, a second computer having a second cache, internal registers and queue of input/output events, wherein the first and second caches hold data accessed from a primary memory by the first and second computers, and wherein the first and second computers may modify said data in the primary memory, the method including the steps of: monitoring the primary memory to detect a write of data to the primary memory; copying the data written to the primary memory into a buffer memory simultaneously with the data written to the primary memory; periodically flushing data from the first cache, internal registers and queue and the second cache, internal registers and queue into the primary memory in synchronization; after flushing, copying data from the buffer memory into a shadow storage element.

Claim 11

Dependent Claim 211 words

A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor, wherein the processor has means for queuing input/output events between checkpoints: a main memory system connected to the processor, wherein the processor utilizes data from the main memory system and temporarily stores utilized data in the cache, the main memory system comprising: a primary memory element having an input through which data in the primary memory element is accessed; a second memory element connected to the primary memory element so as to enable the second memory element to capture data and addresses of accesses to the primary memory element simultaneously with the write access; and means for ensuring the existence of a consistent checkpoint state in the primary and second memory elements using the data stored in the second memory element; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the means for ensuring after flushing of the cache, internal registers and queued input/output events has completed.

Claim 12

Dependent Claim 211 words

A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor, wherein the processor has means for queuing input/output events between checkpoints: a main memory system connected to the processor, wherein the processor utilizes data from the main memory system and temporarily stores utilized data in the cache, the main memory system comprising: a primary memory element having an input through which data in the primary memory element is accessed; a second memory element connected to the primary memory element so as to enable the second memory element to capture data and addresses of accesses to the primary memory element simultaneously with the write access; and means for ensuring the existence of a consistent checkpoint state in the primary and second memory elements using the data stored in the second memory element; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the means for ensuring after flushing of the cache, internal registers and queued input/output events has completed.

Claim 13

Dependent Claim 159 words

A computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor, wherein the processor has means for queuing input/output events between checkpoints; a main memory subsystem, coupled to the processor, including: a primary memory element accessible by the processor a buffer that monitors write accesses to the primary memory element and stores data related to the write accesses simultaneously with the write access; and means, using the data from the buffer, for ensuring the existence of a consistent checkpoint state in the main memory subsystem to which processing can resume without loss of data integrity and program continuity following a fault; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the means for ensuring after flushing of the cache, internal registers and queued input/output events has completed.

Claim 14

Dependent Claim 159 words

A computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor, wherein the processor has means for queuing input/output events between checkpoints; a main memory subsystem, coupled to the processor, including: a primary memory element accessible by the processor a buffer that monitors write accesses to the primary memory element and stores data related to the write accesses simultaneously with the write access; and means, using the data from the buffer, for ensuring the existence of a consistent checkpoint state in the main memory subsystem to which processing can resume without loss of data integrity and program continuity following a fault; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the means for ensuring after flushing of the cache, internal registers and queued input/output events has completed.

Claim 15

Dependent Claim 206 words

In a computer system having first processor with a first cache and first queue of input/output events and a second processor with a second cache and second queue of input/output events, each cache being connected to a main memory and for caching data from the main memory and having means for maintaining cache coherency between the first and second caches, wherein the main memory comprises a primary memory, a buffer memory connected to the primary memory, and a shadow storage element connected to the buffer memory, a method for synchronizing flushing of the first and second caches to maintain a consistent state in the main memory, the method comprising the steps, performed by the first processor, of: setting a lock and suspending normal operations; flushing the first cache and first queue to the main memory such that the buffer memory and the primary memory capture data flushed from the first cache; synchronizing with the second processor to flush the second cache and second queue to the main memory such that the buffer memory and the primary memory capture data flushed from the second cache; instructing the buffer memory to copy data captured therein to the shadow storage element; and releasing the lock and resuming normal operations.

Claim 16

Dependent Claim 206 words

In a computer system having first processor with a first cache and first queue of input/output events and a second processor with a second cache and second queue of input/output events, each cache being connected to a main memory and for caching data from the main memory and having means for maintaining cache coherency between the first and second caches, wherein the main memory comprises a primary memory, a buffer memory connected to the primary memory, and a shadow storage element connected to the buffer memory, a method for synchronizing flushing of the first and second caches to maintain a consistent state in the main memory, the method comprising the steps, performed by the first processor, of: setting a lock and suspending normal operations; flushing the first cache and first queue to the main memory such that the buffer memory and the primary memory capture data flushed from the first cache; synchronizing with the second processor to flush the second cache and second queue to the main memory such that the buffer memory and the primary memory capture data flushed from the second cache; instructing the buffer memory to copy data captured therein to the shadow storage element; and releasing the lock and resuming normal operations.

Claim 17

Dependent Claim 51 words

The method of claim 8, wherein the step of synchronizing comprises the step of waiting until the second processor completes flushing of the second cache and second queue to the main memory such that the buffer memory and the primary memory capture data flushed from the second cache and second queue.

Claim 18

Dependent Claim 113 words

The method of claim 8, wherein each cache is connected to a main memory such that the main memory can identify the processor which accesses the main memory, and wherein the step of synchronizing includes the step of waiting until the second processor commences flushing of the second cache and second queue to the main memory such that the buffer memory and the primary memory capture data flushed from the second cache and second queue and wherein the buffer memory identifies which processor has written the data in the buffer memory, and copies only data flushed from each processor having completed flushing and captured in the buffer memory to the shadow storage element.

Claim 19

Dependent Claim 63 words

The method of claim 8, wherein the first and second processors each have first and second sets of internal registers, respectively, and wherein the first processor flushes the first set of internal registers when the first cache and first queue are flushed and wherein the second processor flushes the second set of internal registers when the second cache and second queue are flushed.

Claim 20

Dependent Claim 25 words

The method of claim 8, wherein the first and second processors each have a flush counter which is incremented when a flush operation is completed.

Claim 21

Dependent Claim 215 words

A computer system comprising: a first processor with a first cache and first queue of input/output events, and a second processor with a second cache and second queue of input/output events and having means for maintaining cache coherency between the first and second caches; a main memory connected to the first and second processors and caches and first and second queues and comprising a primary memory, a buffer memory connected to the primary memory, and a shadow storage element connected to the buffer memory; and means for synchronizing flushing of the first and second caches and first and second queues to maintain a consistent state in the main memory, including: means for setting a lock and suspending normal operations; means for flushing the first cache and first queue to the main memory such that the buffer memory and the primary memory capture data flushed from the first cache and first queue; means for synchronizing with the second processor to flush the second cache and second queue to the main memory such that the buffer memory and the primary memory capture data flushed from the second cache and second queue; means for instructing the buffer memory to copy data captured therein to the shadow storage element; and means for releasing the lock and resuming normal operations.

Claim 22

Dependent Claim 215 words

A computer system comprising: a first processor with a first cache and first queue of input/output events, and a second processor with a second cache and second queue of input/output events and having means for maintaining cache coherency between the first and second caches; a main memory connected to the first and second processors and caches and first and second queues and comprising a primary memory, a buffer memory connected to the primary memory, and a shadow storage element connected to the buffer memory; and means for synchronizing flushing of the first and second caches and first and second queues to maintain a consistent state in the main memory, including: means for setting a lock and suspending normal operations; means for flushing the first cache and first queue to the main memory such that the buffer memory and the primary memory capture data flushed from the first cache and first queue; means for synchronizing with the second processor to flush the second cache and second queue to the main memory such that the buffer memory and the primary memory capture data flushed from the second cache and second queue; means for instructing the buffer memory to copy data captured therein to the shadow storage element; and means for releasing the lock and resuming normal operations.

Claim 23

Dependent Claim 51 words

The computer system of claim 13, wherein the means for synchronizing comprises means for waiting until the second processor completes flushing of the second cache and second queue to the main memory such that the buffer memory and the primary memory capture data flushed from the second cache and second queue.

Claim 24

Dependent Claim 113 words

The computer system of claim 13, wherein each cache is connected to a main memory such that the main memory can identify the processor which accesses the main memory, and wherein the means for synchronizing includes means for waiting until the second processor commences flushing of the second cache and second queue to the main memory such that the buffer memory and the primary memory capture data flushed from the second cache and second queue and wherein the buffer memory identifies which processor has written the data in the buffer memory, and copies only data flushed from each processor having completed flushing and captured in the buffer memory to the shadow storage element.

Claim 25

Dependent Claim 64 words

The computer system of claim 13, wherein the first and second processors each have first and second sets of internal registers, respectively, and wherein the first processor flushes the first set of internal registers when the first cache and first queue are flushed and wherein the second processor flushes the second set of internal registers when the second cache and second queue are flushed.

Claim 26

Dependent Claim 26 words

The computer system of claim 13, wherein the first and second processors each have a flush counter which is incremented when a flush operation is completed.

Claim 27

Dependent Claim 226 words

A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor, wherein the processor has means for queuing input/output events between checkpoints; a main memory connected to the processor and comprising: a primary memory element having an input through which data in the primary memory element is accessed; a second memory element connected to the primary memory element so as to enable the second memory element to capture data and addresses of write accesses to the primary memory element simultaneous with the write access to the primary memory element; and a memory control logic circuit, connected to the second memory element for controlling the primary and second memory elements to maintain the existence of a consistent checkpoint state in the primary and second memory elements using the data stored in the second memory element in a manner transparent to the processor; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the memory control logic to establish a consistent checkpoint state after flushing of the cache, internal registers and queued input/output events has completed.

Claim 28

Dependent Claim 226 words

A computer system which periodically establishes a consistent checkpoint of a current state of the computer system for supporting fault-tolerant operation, the computer system comprising: a processor having a cache, internal registers and an input/output subsystem which provides input/output events for the processor, wherein the processor has means for queuing input/output events between checkpoints; a main memory connected to the processor and comprising: a primary memory element having an input through which data in the primary memory element is accessed; a second memory element connected to the primary memory element so as to enable the second memory element to capture data and addresses of write accesses to the primary memory element simultaneous with the write access to the primary memory element; and a memory control logic circuit, connected to the second memory element for controlling the primary and second memory elements to maintain the existence of a consistent checkpoint state in the primary and second memory elements using the data stored in the second memory element in a manner transparent to the processor; and wherein the processor includes means for suspending operations, means for flushing the cache, internal registers and the queued input/output events to the main memory system and means for instructing the memory control logic to establish a consistent checkpoint state after flushing of the cache, internal registers and queued input/output events has completed.

Claim 29

Dependent Claim 65 words

The main memory of claim 18, wherein the second memory element includes a buffer memory connected to capture data and addresses of write accesses to the primary memory element and a shadow storage element connected to the buffer memory and wherein the memory control logic circuit copies data from the buffer memory to the shadow storage element in response to an instruction from the processor.

Claim 30

Dependent Claim 37 words

The main memory of claim 18, wherein the processor includes a cache, internal registers and a queue of input/output events and means for periodically flushing the cache, the internal registers and the queue to the main memory.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-01-25	2002-07-27	2003-01-26	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-01-25	2006-07-27	2007-01-26	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-01-25	2010-07-27	2011-01-26	$7700.00	Window Closed / Lapsed

Main memory system and checkpointing protocol for fault-tolerant computer system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag