US 8898395

US Patent 8898395: Memory Management for Cache Consistency

Title: Memory management for cache consistency

Assignee:

• Current: Intellectual Ventures II LLC (as of January 16, 2024)
• Original: Individual (subsequently assigned to TRANSMETA LLC, then INTELLECTUAL VENTURE FUNDING LLC, then INTELLECTUAL VENTURES HOLDING 81 LLC)

Inventors: Guillermo J. Rozas

Filing Date: May 15, 2008

Issue Date: November 25, 2014

Abstract:
The patent describes methods and systems for maintaining cache consistency. It involves executing a group of instructions that can include multiple memory operations. When an instruction within this group causes a cache line to be accessed, an associated indicator for that instruction group is updated to reflect this access. This indication remains active until the instruction group's execution concludes. If an external agent (e.g., another processor or a Direct Memory Access (DMA) system) attempts to snoop the cache and finds that the cache line, or any other cache line, is indicated as being accessed by an instruction group, that instruction group is rolled back and reissued. If no cache line is indicated as accessed, the snoop proceeds using a conventional cache coherency protocol (e.g., MESI).

Plain-Language Overview of Independent Claims:

• Independent Claim 1 (Method): This claim outlines a method for managing cache memory involving multiple instruction groups.

  1. A "first bit" of an indicator for a cache line is set if a processor accesses that cache line while executing a "first group of instructions."
  2. A "second bit" of the same indicator is set if the processor also accesses the cache line while executing a "second group of instructions," and the first bit is still set.
  3. If an "agent other than said processor" (an external agent) tries to access the cache line (as part of executing a "third group of instructions"), the system checks these bits.
  4. If the first bit is set, the first group of instructions is rolled back. If the second bit is set, the second group of instructions is rolled back. This rollback happens before the external agent is allowed to access the cache line.
  5. If neither bit is set, the external agent is immediately granted access.
  6. The overall processing of the first and second instruction groups is determined by the state of this indicator.

• Independent Claim 7 (Computer System): This claim describes a computer system designed to implement the method of Claim 1. It comprises a processor, a cache memory, and a memory unit that stores specific instructions. These instructions guide the processor to:

  1. Execute a first group of instructions that reads a cache line and sets a first indicator bit.
  2. Execute a second group of instructions that also reads the cache line and sets a second indicator bit while the first bit is still set.
  3. When a third group of instructions (from an external agent) attempts to access the cache line, the system rolls back the first and/or second instruction groups if their respective bits are set, prior to granting access to the external agent. Otherwise, access is granted.
  4. The system also includes instructions to process the first and second instruction groups based on the indicator's value.

• Independent Claim 13 (Method of Managing Shared Memory): This claim details a method for managing shared memory in a computer system:

  1. A processor executes a first group of instructions.
  2. A cache line is associated with a first state (e.g., from MESI protocol) and then a "second state" which specifically indicates it was accessed by the first instruction group.
  3. The processor then executes a second group of instructions.
  4. During the execution of the second group, the cache line is associated with a "third state" indicating it was accessed by the second group.
  5. If a third group of instructions attempts to access the cache line, both the first and second groups of instructions are rolled back before access is granted to the third group.

• Independent Claim 19 (Computer System): This claim describes a computer system featuring a processor, a cache memory, and a memory unit. The memory unit has multiple "indicator bits" per cache line.

  1. A first indicator bit for a cache line is set when the processor accesses it during a first instruction group's execution and cleared when that group finishes.
  2. A second indicator bit for the same cache line is set when the processor accesses it during a second instruction group (running in parallel) and cleared when that group finishes.
  3. If an external agent attempts to access the cache line, the system rolls back the first instruction group if its bit is set, and the second instruction group if its bit is set, before allowing the external agent's access. If neither bit is set, access is granted.
  4. Additionally, a subset of address bits of the cache line can be used to identify an entry in the memory unit, where an indicator bit of that entry is set when the cache line is accessed.

Litigation Status:
As of April 26, 2026, US Patent 8898395 is listed as "Active," with an adjusted expiration date of July 17, 2026. The patent family has been involved in litigation. Specifically:

• A PTAB case (IPR2025-00638) was filed and procedurally terminated.
• Two US district court cases were filed in the Texas Western District Court (case numbers 6:24-cv-00188 and 1:24-cv-00390).
• First worldwide family litigation has also been filed.
  No specific dockets for US patent 8898395 were found in the CAFC database for 2026 based on the current search.

Known litigation involving US patent 8898395 includes the following cases:

1. PTAB Inter Partes Review (IPR2025-00638)

   • Plaintiff(s): Tesla Inc.
   • Defendant(s): Intellectual Ventures II LLC
   • Jurisdiction: Patent Trial and Appeal Board (PTAB)
   • Case Number: IPR2025-00638
   • Filing Date: March 7, 2025
   • Outcome/Current Status: Procedural Termination

2. U.S. District Court, Western District of Texas (6:24-cv-00188)

   • Plaintiff(s): Intellectual Ventures LLC (likely Intellectual Ventures II LLC)
   • Defendant(s): Tesla, Inc.
   • Jurisdiction: U.S. District Court for the Western District of Texas
   • Case Number: 6:24-cv-00188
   • Filing Date: April 12, 2024
   • Outcome/Current Status: Closed

3. U.S. District Court, Western District of Texas (1:24-cv-00390)

   • Plaintiff(s): Intellectual Ventures LLC (likely Intellectual Ventures II LLC)
   • Defendant(s): Unspecified, but a similar case involving Intellectual Ventures II LLC in the Western District of Texas mentions Tesla, Inc. as a defendant.
   • Jurisdiction: U.S. District Court for the Western District of Texas
   • Case Number: 1:24-cv-00390
   • Filing Date: April 11, 2024
   • Outcome/Current Status: Closed

Proceedings overview

One AIA trial proceeding, IPR2025-00638, was filed against US8898395 and subsequently terminated procedurally. The patent claims remain untested by this particular IPR, indicating no change to their validity status. This gives a defendant the defensive posture that the patent has not been challenged on its merits at the PTAB, and its claims have not been canceled, sustained, or institution denied on substantive grounds.

IPR2025-00638 — Tesla Inc. v. Intellectual Ventures II LLC

• Type: Inter Partes Review
• Filed: 2025-03-07
• Status: Procedural Termination. This indicates the proceeding ended without a substantive decision on the merits of the challenged claims, often due to settlement or withdrawal of the petition before a decision on institution.
• Judge panel: Information regarding the specific judge panel for this proceeding is not publicly available from the provided search results due to its procedural termination.
• Petition grounds: Details regarding the specific claims challenged, prior art references, and statutory bases (§ 102 / § 103 / § 112) for the petition are not publicly available from the provided search results.
• Institution decision: This proceeding was terminated procedurally, which means an institution decision on the merits was not issued. The institution decision due date was listed as 2025-06-24.
• Final Written Decision: No Final Written Decision was issued as the proceeding was terminated procedurally before reaching this stage.
• Settlement / termination: The proceeding was marked as "Procedural Termination". While the specific terms are not public, such terminations often occur due to a settlement between the petitioner (Tesla Inc.) and the patent owner (Intellectual Ventures II LLC).
• Appeal: Not applicable, as no Final Written Decision was rendered.
• Defensive value: This IPR does not impact the patentability of the claims of US8898395, as it was terminated procedurally. Consequently, there are no claims that have been canceled or sustained through this proceeding. For a defendant, this means the patent claims retain their original status, and no estoppel has been created on the grounds that could have been raised in this IPR.

Strategic summary

US8898395 currently has all its claims (1-20) untested by PTAB proceedings. The single IPR filed, IPR2025-00638, was terminated procedurally before a decision on institution, meaning no claims were canceled or sustained, nor were any institution decisions rendered on the merits. This leaves the full scope of the patent claims potentially available for assertion.

The estoppel landscape remains open for any potential future petitioners. Since IPR2025-00638 was terminated procedurally, it did not result in a final written decision, and therefore, the statutory estoppel provisions of § 315(e)(2) are not triggered for Tesla Inc. or its privies concerning any grounds that were or reasonably could have been raised. This means that a defendant facing assertion of this patent today would generally still have all prior-art grounds available to challenge the patent, either at the PTAB or in district court.

A pattern signal from the broader context is that Intellectual Ventures II LLC has been involved in multiple IPRs filed by Tesla Inc. against various patents, as indicated by search results and (listing several IPRs like IPR2025-00217, IPR2025-00219, IPR2025-00222, IPR2025-00221 against different patents, some of which proceeded to institution). This suggests ongoing litigation or disputes between these parties, making the procedural termination of IPR2025-00638 potentially part of a larger negotiation or settlement strategy involving multiple patents.

Recommended next steps

Given that IPR2025-00638 was procedurally terminated and did not result in any claim-level decisions, there is no Final Written Decision to link to for claim cancellation. The claims of US8898395 have not been adjudicated at the PTAB.

For a defendant currently facing assertion of this patent, the absence of PTAB activity resulting in merits-based decisions means:

• The claims of US8898395 are currently considered valid as granted by the USPTO.
• No prior art grounds have been publicly litigated and decided against the patent owner at the PTAB.
• A new IPR petition could be considered as a defense strategy, as the claims remain untested and no estoppel for other parties has been created by the terminated IPR. However, consideration of any potential Fintiv factors for discretionary denial would be crucial, especially if there is parallel district court litigation with an advanced trial date. The recent director review order in IPR2025-00340, involving the same parties (Tesla and Intellectual Ventures II LLC) and issued by Director Squires, highlights the PTAB's scrutiny of inconsistent claim construction positions between district court and IPR proceedings, which could be a factor in future petitions.

Inventors

• Guillermo J. Rozas - At the time of filing (priority date 2005-04-07, application filing 2008-05-15), Guillermo J. Rozas was likely employed by Transmeta Corporation, which was the predecessor entity to Transmeta LLC, the initial corporate assignee of the patent. Rozas is listed as an inventor on numerous patents assigned to Transmeta.

Original assignee

The patent application (US12/121,531) initially listed "Individual" as the original assignee. However, before the patent's issuance, it was assigned to Transmeta LLC. Transmeta Corporation, the predecessor to Transmeta LLC, was a semiconductor company known for developing x86-compatible microprocessors (Crusoe and Efficeon). Transmeta ceased its primary business of chip design and sales around 2005, transitioning to an intellectual property licensing model. Therefore, while Transmeta Corporation had shipped products, Transmeta LLC, as the first corporate assignee, primarily operated as an IP licensing entity. Transmeta Corporation's assets, including patent portfolios, were subsequently acquired by other entities. Transmeta LLC's current status is likely dissolved or inactive, as its assets were largely acquired by Intellectual Ventures.

Assignment timeline

• 2009-01-27 (executed) / recorded 2009-03-26 — Reel 022454/0522

  • Conveyance: MERGER
  • Assignor: TRANSMETA CORPORATION
  • Assignee: TRANSMETA LLC
  • Correspondent: Not clearly listed on record document.
  • Context: Transfer due to corporate merger, likely part of Transmeta's pivot to an IP licensing model.

• 2009-01-28 (executed) / recorded 2009-09-22 — Reel 023268/0771

  • Conveyance: ASSIGNMENT OF ASSIGNORS INTEREST
  • Assignor: TRANSMETA LLC
  • Assignee: INTELLECTUAL VENTURE FUNDING LLC
  • Correspondent: Russ & Russ P.C., 2100 SWIFT DR. SUITE 100, OAK BROOK, IL 60523. This correspondent is a known patent assertion entity filing firm.
  • Context: Acquisition of Transmeta's patent portfolio by Intellectual Ventures.

• 2015-08-27 (executed) / recorded 2015-09-29 — Reel 036711/0160

  • Conveyance: MERGER
  • Assignor: INTELLECTUAL VENTURE FUNDING LLC
  • Assignee: INTELLECTUAL VENTURES HOLDING 81 LLC
  • Correspondent: Morrison & Foerster LLP, 425 Market St, San Francisco, CA 94105. This correspondent firm also appears in later assignments in this chain.
  • Context: Internal reorganization within Intellectual Ventures entities.

• 2015-08-27 (executed) / recorded 2015-10-06 — Reel 036797/0356

  • Conveyance: CORRECTIVE ASSIGNMENT
  • Assignor: INTELLECTUAL VENTURE FUNDING LLC
  • Assignee: INTELLECTUAL VENTURES HOLDING 81 LLC
  • Correspondent: Morrison & Foerster LLP, 425 Market St, San Francisco, CA 94105. This correspondent firm also appears in other assignments in this chain.
  • Context: Corrective internal reorganization within Intellectual Ventures entities.

• 2024-01-16 (executed) / recorded 2024-01-16 — Reel 066139/0987

  • Conveyance: ASSIGNMENT OF ASSIGNORS INTEREST
  • Assignor: INTELLECTUAL VENTURES HOLDING 81 LLC
  • Assignee: INTELLECTUAL VENTURES II LLC
  • Correspondent: Morrison & Foerster LLP, C/O INTELLECTUAL VENTURES, LLC, 1375 BROADWAY, SUITE 1000, NEW YORK, NY 10018. This correspondent firm also appears in other assignments in this chain.
  • Context: Internal reorganization within Intellectual Ventures entities, likely in preparation for litigation.

Timeline diagram

timeline
    title Ownership of US 8898395
    2005 : Priority date
    2008 : Filed
    2009 : Transferred to Transmeta LLC
         : Assigned to Intellectual Venture Funding LLC
    2014 : Patent issued
    2015 : Assigned to Intellectual Ventures Holding 81 LLC
         : Corrective assignment to IV Holding 81 LLC
    2024 : Assigned to Intellectual Ventures II LLC
         : First infringement suit filed

NPE / troll-pattern signals

1. Shell-entity transfer — Present. The patent was transferred to Intellectual Venture Funding LLC (reel 023268/0771), then to Intellectual Ventures Holding 81 LLC (reel 036711/0160), and finally to Intellectual Ventures II LLC (reel 066139/0987). These are all known shell entities associated with Intellectual Ventures, a prominent NPE.

2. Known asserter in the chain — Present. Intellectual Venture Funding LLC, Intellectual Ventures Holding 81 LLC, and Intellectual Ventures II LLC are all entities of Intellectual Ventures, a widely recognized Non-Practicing Entity (NPE).

3. Repeat correspondent across the chain — Present. Russ & Russ P.C., a firm often associated with NPE filings, is the correspondent for the 2009-01-28 assignment (reel 023268/0771). Morrison & Foerster LLP is the correspondent for the 2015-08-27 assignments (reel 036711/0160 and 036797/0356) and the 2024-01-16 assignment (reel 066139/0987), demonstrating recurrence of this firm across multiple transfers within the Intellectual Ventures chain.

4. Cascading transfers — Present. There were two consecutive transfers within Intellectual Ventures entities in 2015 (recorded 2015-09-29 and 2015-10-06), both from Intellectual Venture Funding LLC to Intellectual Ventures Holding 81 LLC, handled by the same correspondent.

5. Pre-litigation transfer — Present. The assignment to Intellectual Ventures II LLC was executed and recorded on 2024-01-16 (reel 066139/0987). Infringement suits related to this patent were filed on 2024-02-23 (case 6:24-cv-00188) and 2024-04-10 (case 1:24-cv-00390) in the Texas Western District Court, both within six months of this transfer.

6. Bankruptcy fire-sale — Not present. While Transmeta Corporation underwent significant business changes and sold its IP, the available records do not indicate a formal bankruptcy fire-sale of this specific patent.

7. Privateering — Unclear. Transmeta Corporation transitioned to an IP licensing model and sold its portfolio to Intellectual Ventures. While this could be interpreted as a form of privateering, direct evidence in SEC filings or specific reporting confirming an ongoing arrangement for assertion on Transmeta's behalf against competitors is not available in the provided information.

8. Defensive aggregator (anti-NPE) — Not present. The patent is currently assigned to Intellectual Ventures II LLC, an NPE, and not to a defensive aggregator.

Verdict

NPE — high confidence

This verdict is supported by multiple strong signals: the presence of known NPE entities (Intellectual Ventures Funding LLC, Intellectual Ventures Holding 81 LLC, Intellectual Ventures II LLC) in the assignment chain, the use of a repeat correspondent firm (Morrison & Foerster LLP) for multiple transfers within the NPE structure, and a clear pre-litigation transfer to the current asserting entity (Intellectual Ventures II LLC) shortly before infringement lawsuits were filed in 2024.

USPTO Assignment Center Search for US8898395

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.

Obviousness Analysis of US Patent 8898395 Under 35 U.S.C. § 103

US Patent 8898395 ("the '395 patent") describes methods and systems for maintaining cache consistency, particularly for "lumped" architectures (in-order or out-of-order) that allow instruction groups to include multiple memory operations while maintaining sequential consistency. The patent explicitly states a key problem it aims to solve: "Prior attempts to achieve a sequentially consistent, lumped architecture are limited with respect to the number of memory operations that can be included in an instruction group. Specifically, such attempts are limited to a single memory operation per instruction group."

A person having ordinary skill in the art (PHOSITA) in computer architecture and memory management, at the time of the invention (priority date April 7, 2005), would have been aware of cache coherency protocols such as MESI, DMA, multiprocessor systems, and the concept of sequential consistency, as acknowledged in the '395 patent's background. The PHOSITA would also understand that instruction groups in lumped architectures are committed and rolled back atomically, and that reordering and optimization can occur within a group.

The core inventive step of the '395 patent, as embodied in Claim 1, involves:

1. Tracking cache line access by instruction groups: Setting a bit (e.g., "observed bit") associated with a cache line for each instruction group that accesses it.
2. Tracking multiple concurrent instruction groups: Setting multiple such bits if multiple instruction groups concurrently access the same cache line.
3. Conditional Rollback on External Access: If an external agent (another processor or DMA system) attempts to access a cache line with a set observed bit, the corresponding instruction groups are rolled back before granting access to the external agent.

Below are combinations of prior art references that would render the claims of US 8898395 obvious.

Combination 1: US 5,428,761 (Digital Equipment Corporation) in view of General Knowledge of Cache Coherency (MESI) and Lumped Architectures

References:

• US 5,428,761 (Bartlett et al.): "System for achieving atomic non-sequential multi-word operations in shared memory"
• General Knowledge: MESI cache coherency protocol, lumped in-order/out-of-order architectures, and the concept of sequential consistency, as explicitly mentioned in the '395 patent's background.

Rationale for Obviousness:

1. Atomic Multi-Word Operations and Rollback: US 5,428,761 teaches a system for achieving "atomic non-sequential multi-word operations in shared memory." This patent specifically addresses maintaining the atomicity of multiple memory operations and describes "checkpointing the state of at least one processor and speculative state values, allowing a processor to revert to the checkpoint state when the multi-word memory operation fails to achieve atomicity." This directly anticipates the core idea of allowing multiple memory operations within a logical unit (instruction group in '395, multi-word operation in '761) and using rollback when atomicity is threatened.
2. Motivation to Combine: The '395 patent explicitly identifies the limitation of prior art in sequentially consistent lumped architectures, namely, the restriction to a single memory operation per instruction group. A PHOSITA, motivated to overcome this known limitation, would naturally look for existing solutions that enable atomic multi-word operations, such as those taught by US 5,428,761.
3. Tracking Mechanism ("Observed Bits"): To implement the atomic multi-word operations of US 5,428,761 within a cached lumped architecture, a PHOSITA would need a mechanism to track which cache lines have been accessed by which active (uncommitted) instruction groups. The "observed bits" described in the '395 patent (one bit per instruction group per cache line, set upon access) would be an obvious design choice for such a tracking mechanism. This allows the system to detect when an external access (e.g., a snoop from another agent, as mentioned in the '395 patent) might conflict with an uncommitted atomic instruction group, thereby jeopardizing its atomicity.
4. Integration with Existing Protocols: The '395 patent's Claim 2 introduces conditional rollback based on the MESI state (specifically, avoiding rollback if the cache line is in the shared state and the external access is for sharing). The MESI protocol is acknowledged as known prior art for cache coherency. A PHOSITA would inherently understand the semantics of MESI states and would find it obvious to integrate any new rollback mechanism with existing coherency protocols to optimize performance and avoid unnecessary rollbacks. For instance, if a cache line is in a shared state and an external agent requests shared access, it would be evident that no atomicity violation has occurred for other readers, thus making rollback unnecessary.

Therefore, a PHOSITA, motivated to enable multiple memory operations within instruction groups in sequentially consistent lumped architectures (as acknowledged by the '395 patent as a prior art limitation), would find it obvious to adapt the atomic multi-word operation and rollback techniques of US 5,428,761. The implementation of "observed bits" for tracking accessed cache lines by active instruction groups, and the conditional rollback based on external snoops and MESI states, would be straightforward engineering choices for such a combination.

Combination 2: US 6,938,130 (Sun Microsystems Inc.) in view of US 5,701,432 (Sun Microsystems, Inc.) and General Knowledge of Cache Coherency (MESI)

References:

• US 6,938,130 (Tremblay et al.): "Method and apparatus for delaying interfering accesses from other threads during transactional program execution"
• US 5,701,432 (Tremblay et al.): "Multi-threaded processing system having a cache that is commonly accessible to each thread"
• General Knowledge: MESI cache coherency protocol and lumped architectures.

Rationale for Obviousness:

1. Transactional Memory and Interfering Accesses: US 6,938,130 discloses methods for "delaying interfering accesses from other threads during transactional program execution" and "maintaining the validity of a transaction." Transactional memory inherently involves treating groups of operations (transactions) atomically and typically employs rollback mechanisms to resolve conflicts. This directly addresses the concept of managing multiple memory operations as a unit and responding to external interference.
2. Multi-threaded Systems with Shared Cache: US 5,701,432 describes a "multi-threaded processing system having a cache that is commonly accessible to each thread." This provides the architectural context (multiple agents, shared memory, shared cache) where the cache consistency problems addressed by the '395 patent arise.
3. Motivation to Combine: A PHOSITA aiming to achieve sequential consistency for lumped architectures with multiple memory operations per group (to overcome the known single-memory-operation limitation) would be motivated to apply transactional memory techniques (US 6,938,130) within a multi-threaded, cached environment (US 5,701,432). The objective would be to allow speculative execution of instruction groups containing multiple memory operations, while using the conflict detection and resolution (e.g., rollback) inherent in transactional memory to maintain consistency.
4. Implementing Conflict Detection: To "delay interfering accesses" and "maintain transaction validity" in a shared cache environment (as taught by US 6,938,130 and US 5,701,432), a PHOSITA would understand the necessity of tracking memory locations (cache lines) accessed by active transactions. The "observed bits" mechanism of the '395 patent, where a bit is set for a cache line when an instruction group accesses it, serves as a straightforward implementation of such conflict detection logic. When an external agent's access conflicts with a cache line marked by an "observed bit," rolling back the associated instruction group is a known transactional memory response to maintain consistency.
5. Multitude of Instruction Groups: The extension to setting "a first bit... and a second bit... if said cache line has also been accessed in response to said processor executing an instruction in a second group of instructions" (Claim 1) would be obvious in a multi-threaded/transactional system. When multiple instruction groups (transactions) can execute concurrently, the tracking mechanism must be able to distinguish and manage each of them, leading to a natural design choice of having separate indicators (bits) for each active group.

In conclusion, the '395 patent's claimed invention, while addressing a specific limitation in prior lumped architectures, relies on principles of atomic multi-word operations, transactional memory, and conflict resolution (rollback) that were well-known in the prior art, particularly as evidenced by US 5,428,761 and US 6,938,130. The specific implementation using "observed bits" in cache tags and integrating with existing MESI states would have been an obvious engineering choice for a PHOSITA attempting to extend the capabilities of lumped architectures.

For US patent 8898395, the following details regarding its term, applications, and family members can be provided:

• Projected Expiration Date: The adjusted expiration date for US8898395 is July 17, 2026.

• Patent Term Adjustments (PTA) / Patent Term Extensions (PTE):

  • PTA: While the patent's status indicates an "adjusted expiration" date, implying that Patent Term Adjustment (PTA) was applied to compensate for administrative delays by the USPTO during prosecution, the specific number of days added for PTA for US8898395 is not explicitly stated in the provided text or search results. PTA is typically calculated at the time of patent issuance and included in the Issue Notification Letter.
  • PTE: There is no indication that US8898395 has received any Patent Term Extension (PTE). PTE is typically granted under the Hatch-Waxman Act for patents claiming products that require regulatory approval, such as pharmaceuticals or medical devices. The subject matter of US8898395, "Memory management for cache consistency," does not fall within these categories.

• Continuation Applications:

  • US8898395 (Application No. US12/121,531) is identified as a continuation application of U.S. patent application Ser. No. 11/102,127, filed April 7, 2005 [Source: Patent Description, "RELATED UNITED STATES PATENT APPLICATION"]. This parent application subsequently issued as US7376798B1.

• Divisional Applications:

  • The provided patent text and associated information do not explicitly mention any divisional applications directly stemming from US8898395. A divisional application typically arises from a restriction requirement by the USPTO, allowing claims to independent and distinct inventions disclosed in an earlier application to be pursued separately.

• Related Family Members:

  • Parent Application: The primary related family member is US7376798B1 (U.S. patent application Ser. No. 11/102,127), of which US8898395 is a continuation. Both share the same priority date of April 7, 2005.

Further details regarding the precise PTA calculation would require access to the full prosecution history of US8898395 via USPTO Patent Center.