Obviousness

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.