Prior art

The US patent 8898395, titled "Memory management for cache consistency," was filed on May 15, 2008, and published on November 25, 2014. It is currently assigned to Intellectual Ventures II LLC and has an adjusted expiration date of July 17, 2026.

The patent describes methods and systems for maintaining sequential consistency in computer architectures that execute instruction groups containing multiple memory operations. A key aspect is the use of "observed bits" associated with cache lines and specific instruction groups. These bits indicate when a cache line has been accessed by an instruction group. If an external agent attempts to access such a cache line, the instruction groups associated with the set observed bits are rolled back before the external agent's access is granted (unless the cache line is in a shared state and the access is for sharing). This mechanism allows instruction groups to perform multiple memory operations while maintaining sequential consistency, a feature claimed to overcome limitations of prior art that typically restricted instruction groups to a single memory operation for this purpose.

Here is an analysis of the most relevant prior art cited in US8898395, including full citations, dates, brief descriptions, and potential anticipation under 35 U.S.C. § 102. The priority date of US8898395 is April 7, 2005.

Cited Prior Art for US8898395:

1. US5086429A

   • Full Citation: US5086429A, Honeywell Inc., "Fault-tolerant digital computing system with reduced memory redundancy".
   • Publication Date: 1992-02-04 (Filing Date: 1990-04-10).
   • Brief Description: This patent describes a fault-tolerant computer system that uses redundant processors and shared memory with cache memories. It focuses on maintaining cache coherency in such a system, particularly in the context of fault detection and recovery. While it addresses cache coherency in multiprocessor systems, its primary focus is on fault tolerance rather than the specific instruction group and rollback mechanisms for memory consistency as described in US8898395.
   • Potential Anticipation: Less likely to anticipate the core claims of US8898395 (Claims 1, 7, 13, 19) directly, as it does not appear to teach the "observed bits" tied to instruction groups with multiple memory operations, or the specific rollback logic in response to external snoops for maintaining sequential consistency in lumped architectures. Its relevance is primarily in the general field of cache coherency.

2. US5428761A

   • Full Citation: US5428761A, Digital Equipment Corporation, "System for achieving atomic non-sequential multi-word operations in shared memory".
   • Publication Date: 1995-06-27 (Filing Date: 1992-03-12).
   • Brief Description: This patent pertains to atomic operations on multiple memory words in shared memory systems. It aims to ensure that a sequence of memory operations appears to occur instantaneously with respect to other processors. This aligns with the concept of atomicity and sequential consistency which US8898395 seeks to maintain for instruction groups with multiple memory operations. This patent's focus on "non-sequential multi-word operations" suggests an awareness of reordering, which US8898395 also addresses.
   • Potential Anticipation: This patent is highly relevant. It potentially anticipates elements of Claims 1, 7, 13, and 19 related to achieving atomic multi-memory operations and sequential consistency. However, it would need to explicitly teach the "observed bit" mechanism per cache line per instruction group and the specific conditional rollback of speculative instruction groups upon external snoop requests as defined in US8898395. The abstract suggests a software-assisted approach rather than the specific hardware-level observed bit and rollback mechanism of US8898395.

3. US5701432A

   • Full Citation: US5701432A, Sun Microsystems, Inc., "Multi-threaded processing system having a cache that is commonly accessible to each thread".
   • Publication Date: 1997-12-23 (Filing Date: 1995-10-13).
   • Brief Description: This patent describes a multi-threaded processor with a cache accessible to multiple threads, and techniques for handling cache coherency. It involves tagging cache entries to distinguish between different threads accessing data. The use of "tags" and handling of multiple threads could be seen as broadly related to the concept of observed bits and instruction groups.
   • Potential Anticipation: Less directly anticipatory of the specific observed bit and rollback logic for instruction groups. While it deals with multi-threaded cache access and coherency, it does not explicitly disclose the mechanism of setting observed bits for entire instruction groups containing multiple memory operations and initiating a rollback of those groups upon an external snoop.

4. US5974438A

   • Full Citation: US5974438A, Compaq Computer Corporation, "Scoreboard for cached multi-thread processes".
   • Publication Date: 1999-10-26 (Filing Date: 1996-12-31).
   • Brief Description: This patent describes a scoreboard mechanism used in multi-threaded processors to manage cache access and ensure data consistency. Scoreboards track outstanding memory operations and dependencies, which can be related to ensuring correct ordering and preventing hazards in a multi-processor environment.
   • Potential Anticipation: This is a relevant reference. Scoreboards are used to track instructions and their data accesses, which conceptually overlaps with the role of "observed bits" in US8898395. However, it would need to teach the specific implementation where a "scoreboard" (or similar structure) is tied to instruction groups with multiple memory operations, where its state (like an observed bit) causes a rollback of the entire group in response to an external agent's snoop request to maintain sequential consistency. This patent might anticipate the general idea of tracking memory accesses, but not the specific rollback consequences tied to observed bits for instruction groups.

5. US6006299A

   • Full Citation: US6006299A, Intel Corporation, "Apparatus and method for caching lock conditions in a multi-processor system".
   • Publication Date: 1999-12-21 (Filing Date: 1994-03-01).
   • Brief Description: This patent describes caching lock conditions (e.g., for mutexes) in a multiprocessor system to improve performance. It involves managing the coherence of lock states, which are a form of memory operation. While related to memory consistency in multiprocessors, its focus on locks is narrower than the general memory operation consistency of US8898395.
   • Potential Anticipation: Unlikely to directly anticipate the core claims of US8898395, as it addresses a specific type of memory operation (locks) and does not describe the general "observed bit" and instruction group rollback mechanism for arbitrary memory operations and external snoops.

6. US6189074B1

   • Full Citation: US6189074B1, Advanced Micro Devices, Inc., "Mechanism for storing system level attributes in a translation lookaside buffer".
   • Publication Date: 2001-02-13 (Filing Date: 1997-03-19).
   • Brief Description: This patent describes storing system-level attributes (like caching policy or memory type) in a Translation Lookaside Buffer (TLB). This is related to memory management and access permissions/characteristics, but not directly to cache coherency protocols or the specific transactional memory aspects of US8898395.
   • Potential Anticipation: Unlikely to anticipate the core claims of US8898395, as its subject matter is TLB attributes rather than cache coherency through instruction group rollback.

7. US6263407B1

   • Full Citation: US6263407B1, International Business Machines Corporation, "Cache coherency protocol including a hovering (H) state having a precise mode and an imprecise mode".
   • Publication Date: 2001-07-17 (Filing Date: 1998-02-17).
   • Brief Description: This patent introduces a "hovering" (H) state into a cache coherency protocol. This state allows for more flexible handling of cache line transitions, particularly during read and write operations, distinguishing between precise and imprecise modes for coherency. This is a direct cache coherency protocol enhancement.
   • Potential Anticipation: This is a relevant reference as it modifies a cache coherency protocol (like MESI/MOESI mentioned in US8898395). It teaches novel cache states and transitions, which US8898395 also deals with by adding "observed" states (bits). However, US8898395's innovation lies in linking these states to speculative instruction groups with multiple memory operations and using them to trigger rollback upon external snoops, which is not explicitly taught by US6263407B1's hovering state. It might anticipate the idea of adding states to a cache line to manage coherence more finely, but not the specific instruction group rollback.

8. US6625694B2

   • Full Citation: US6625694B2, Fujitsu Ltd., "System and method for allocating a directory entry for use in multiprocessor-node data processing systems".
   • Publication Date: 2003-09-23 (Filing Date: 1998-05-08).
   • Brief Description: This patent describes a directory-based cache coherence system, focusing on efficient allocation of directory entries in multiprocessor systems. Directory-based protocols are alternatives or complements to snooping protocols like MESI.
   • Potential Anticipation: While generally related to cache coherency in multiprocessors, its focus on directory entry allocation is different from the specific observed bit and instruction group rollback mechanism of US8898395. It does not appear to anticipate the core claims.

9. US6658536B1

   • Full Citation: US6658536B1, International Business Machines Corporation, "Cache-coherency protocol with recently read state for extending cache horizontally".
   • Publication Date: 2003-12-02 (Filing Date: 1997-04-14).
   • Brief Description: This patent introduces a "recently read" state to a cache coherency protocol to improve performance in systems with horizontally extended caches (e.g., shared between processors). This is another example of extending cache coherency protocols with new states.
   • Potential Anticipation: Similar to US6263407B1, this is relevant as it proposes a modification to a cache coherency protocol by adding a new state. It could be argued to anticipate the general concept of augmenting cache line state information. However, the specific function of the "recently read" state is different from the "observed bit" of US8898395, which is tied to speculative instruction groups and triggers rollback. It does not appear to teach the full scope of Claims 1, 7, 13, or 19.

10. US6738864B2

    • Full Citation: US6738864B2, Texas Instruments Incorporated, "Level 2 cache architecture for multiprocessor with task—ID and resource—ID".
    • Publication Date: 2004-05-18 (Filing Date: 2000-08-21).
    • Brief Description: This patent describes an L2 cache architecture that incorporates task-IDs and resource-IDs. This allows for finer-grained control over cache access and coherency based on the task or resource accessing the data. The use of IDs associated with access could be seen as related to associating observed bits with instruction groups.
    • Potential Anticipation: This is quite relevant. The use of "task-IDs" or "resource-IDs" to control or manage cache access/coherency on a per-task basis shares a conceptual link with US8898395's "observed bits" being associated with "instruction groups" (which are effectively tasks/threads). If the task-ID was used to mark cache lines accessed by a speculative task and trigger a rollback mechanism when an external agent interfered, this would be highly anticipatory. Claims 1, 7, 13, and 19 relate to associating an indicator (like a bit) with a cache line and a group of instructions. The task-ID could serve as such an indicator. However, the exact mechanism of rollback of speculative instruction groups with multiple memory operations in response to an external snoop and conditional on MESI state needs to be present to fully anticipate.

11. US6779085B2

    • Full Citation: US6779085B2, Texas Instruments Incorporated, "TLB operation based on task-ID".
    • Publication Date: 2004-08-17 (Filing Date: 2000-08-21).
    • Brief Description: This patent describes managing TLB operations using task-IDs, similar to the L2 cache in US6738864B2. It allows different tasks to have distinct TLB entries or access permissions.
    • Potential Anticipation: Less directly anticipatory than US6738864B2, as its primary focus is TLB management, not direct cache coherency or rollback of instruction groups for speculative execution.

12. US6839813B2

    • Full Citation: US6839813B2, Texas Instruments Incorporated, "TLB operations based on shared bit".
    • Publication Date: 2005-01-04 (Filing Date: 2000-08-21).
    • Brief Description: This patent describes TLB operations that use a "shared bit" to manage virtual memory access in a multiprocessor environment. The shared bit indicates whether a page mapping is shared among multiple tasks.
    • Potential Anticipation: Similar to the previous Texas Instruments patents, this relates to memory management using special bits/IDs. While a "shared bit" is used, its function in TLB management is different from the "observed bits" of US8898395 which trigger instruction group rollback for cache consistency. It does not appear to anticipate the core claims.

13. US6938130B2

    • Full Citation: US6938130B2, Sun Microsystems Inc., "Method and apparatus for delaying interfering accesses from other threads during transactional program execution".
    • Publication Date: 2005-08-30 (Filing Date: 2003-02-13).
    • Brief Description: This patent is highly relevant as it explicitly deals with "transactional program execution" and "delaying interfering accesses from other threads." Transactional memory systems are designed to provide atomic execution of instruction sequences, often involving speculation and rollback on conflicts, similar to the "lumped instruction groups" in US8898395. The priority date (Feb 13, 2003) is before US8898395's priority date (Apr 7, 2005).
    • Potential Anticipation: This patent is highly relevant and potentially anticipates many aspects of Claims 1, 7, 13, and 19. If this patent teaches the use of "tags" or "bits" associated with cache lines to track access by a speculative transaction (equivalent to an instruction group with multiple memory operations) and explicitly teaches rolling back the transaction upon an interfering access from another agent (snoop), it would be very strong prior art. The key differentiator for US8898395 would then be the specific implementation details (e.g., "observed bits" per instruction group mapped to each cache line, and the conditional rollback based on MESI state for shared accesses). Claims 3, 4, 9, 10, 16, and 17 (rollback counting and group reduction) and Claim 6, 12 (cache line replacement) might offer more distinctiveness if not taught here.

14. US20060112226A1

    • Full Citation: US20060112226A1, Hady Frank T, "Heterogeneous processors sharing a common cache".
    • Publication Date: 2006-05-25 (Filing Date: 2004-11-19).
    • Brief Description: This patent application describes heterogeneous processors sharing a common cache and the mechanisms to manage coherency in such a system. The priority date (Nov 19, 2004) is also before US8898395's priority date (Apr 7, 2005).
    • Potential Anticipation: While generally related to cache sharing and coherency in multi-processor systems, the abstract does not suggest the specific "observed bit" mechanism or instruction group rollback of US8898395. It might be relevant for the context of shared caches but less so for the specific claimed invention.

Most Relevant Prior Art:

Based on the titles and general understanding, US6938130B2 (Sun Microsystems Inc.) stands out as the most relevant prior art. Its explicit mention of "transactional program execution" and "delaying interfering accesses from other threads" directly addresses the problem space and potential solutions involving speculative execution and conflict resolution through rollback, which are central to US8898395.

US5428761A (Digital Equipment Corporation) on "atomic non-sequential multi-word operations" is also highly relevant due to its focus on achieving atomicity for multiple memory operations, which is a core problem US8898395 aims to solve for instruction groups.

US6738864B2 (Texas Instruments Incorporated) regarding "task-ID" in L2 cache architecture is also significant because it describes associating identifiers with tasks/resources to manage cache state, which is conceptually similar to associating "observed bits" with "instruction groups" in US8898395.

To definitively determine anticipation under 35 U.S.C. § 102, a detailed claim-by-claim comparison against the full specification of these highly relevant prior art documents would be necessary. However, based on the provided information, these three patents demonstrate the closest conceptual and technical overlap with the invention of US8898395.