Ex Parte Averill et al

Board of Patent Appeals and Interferences

Jan 21, 2010

10760431 (B.P.A.I. Jan. 21, 2010)

UNITED STATES PATENT AND TRADEMARK OFFICE
____________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________

Ex parte DUANE ARLYN AVERILL, RUSSELL DEAN HOOVER,
DAVID ALAN SHEDIVY, and MARTHA ELLEN VOYTOVICH
____________

Appeal 2009-002615
Application 10/760,431
Technology Center 2100
____________

Decided: January 22, 2010
____________

Before JOSEPH L. DIXON, THU A. DANG, and
CAROLYN D. THOMAS, Administrative Patent Judges.

DIXON, Administrative Patent Judge.

DECISION ON APPEAL

Appeal 2009-002615
Application 10/760,431

The Appellants appeal under 35 U.S.C. § 134(a) from a Final
Rejection of claims 1-22. We have jurisdiction under 35 U.S.C. § 6(b).
We affirm-in-part.

I. STATEMENT OF THE CASE
The Invention
The invention at issue on appeal relates to a method and apparatus for
selectively determining whether to send cache line invalidation messages to
a particular device cache (Spec. 6-7).

The Illustrative Claim
Claim 1, an illustrative claim, reads as follows:
1. A digital data processing system, comprising:

a memory;

at least one processor having at least one associated cache for
temporarily caching data from said memory;

at least one device having a device cache, said device cache
having a fixed number of slots for caching data, said fixed
number being greater than one, each slot caching a cache line of
data; and

a cache coherency mechanism, said cache coherency
mechanism including a cache line state directory structure, said
cache coherency mechanism selectively determining whether to
send cache line invalidation messages to said at least one device
using state information in said cache line state directory
structure, wherein at least a portion of said cache line state
directory structure associated with said at least one device
contains exactly said fixed number of cache line entries, each
entry having a fixed correspondence to a unique respective one
Appeal 2009-002615
Application 10/760,431

3
of said fixed number of slots for caching data of said device
cache.

The References
The Examiner relies on the following references as evidence:
Baumgartner US 6,108,764 Aug. 22, 2000
Carpenter US 6,115,804 Sept. 5, 2000
Arimilli US 2003/0009643 A1 Jan. 9, 2003

The Rejections
The following rejections are before us for review:
Claims 1, 2, and 5-8 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Baumgartner in view of Arimilli.
Claims 3, 4, and 9-22 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Baumgartner in view of Arimilli, and further in
view of Carpenter.

II. ISSUES
Have the Appellants shown that the Examiner erred in identifying that
the combination of Baumgartner and Arimilli teaches and fairly suggests a
cache coherency mechanism “selectively determining whether to send cache
line invalidation messages to said at least one device using state information
in said cache line state directory structure,” as recited in independent claim
1?
Have the Appellants shown that the Examiner erred in identifying that
the combination of Baumgartner and Arimilli teaches and fairly suggests the
limitations recited in claim 14?

Appeal 2009-002615
Application 10/760,431

4
III. PRINCIPLES OF LAW
Prima Facie Case of Unpatentability
The allocation of burden requires that the United States Patent and
Trademark Office (USPTO) produce the factual basis for its rejection of an
application under 35 U.S.C. §§ 102 and 103. In re Piasecki, 745 F.2d 1468,
1472 (Fed. Cir. 1984) (citing In re Warner, 379 F.2d 1011, 1016 (CCPA
1967)). The Appellants have the burden on appeal to the Board of Patent
Appeals and Interferences (BPAI) to demonstrate error in the Examiner’s
position. See In re Kahn, 441 F.3d 977, 985-86 (Fed. Cir. 2006) (citing In re
Rouffet, 149 F.3d 1350, 1355 (Fed. Cir. 1998).

Obviousness
The question of obviousness is resolved on the basis of underlying
factual determinations including (1) the scope and content of the prior art;
(2) any differences between the claimed subject matter and the prior art; and
(3) the level of skill in the art. Graham v. John Deere Co., 383 U.S. 1, 17
(1966).

IV. FINDINGS OF FACT
The following findings of fact (FFs) are supported by a preponderance
of the evidence.
Baumgartner
1. Baumgartner discloses a cache directory structure for storing
the information relating to the cache coherency:
Coherence directory 50 stores indications of the system
memory addresses of data (e.g., cache lines) checked out to
caches in remote nodes for which the local processing node is
Appeal 2009-002615
Application 10/760,431

5
the home node. The address indication for each cache line is
stored in association with an identifier of each remote
processing node having a copy of the cache line and the
coherency status of the cache line at each such remote
processing node. Possible coherency states for entries in
coherency directory 50 are summarized in Table VI.
(Col. 7, ll. 59-67.)
2. Baumgartner only mentions once “invalidation” in TABLE VI,
but does not teach how to determine whether to send cache line invalidation
messages using the cache line directory. (Col. 8, Table VI, ll. 27-51.)
Arimilli
3. Arimilli discloses a method and system of a Non-Uniform
Memory Access (NUMA) computer system for improving node controller
queue by implementing a reissue protocol for request of remote data
(¶[0013], fig. 1). Arimilli also discloses that a structure of cache directory
includes a Local Memory Directory (LMD) storing an indication regarding
whether the data, resided in an associated system memory, are cached in one
or more remote nodes, and a Remote Memory Directory (RMD) storing an
indication regarding whether the data from the system memories in other
nodes is cached in the associated RMD (¶[0037]). Arimilli further discloses
the details of the cache directory 140 includes a number of sets (row) 142.
Each set 142 contains a number of directory entries 144 for storing the
address tag and coherency state of a corresponding cache lines (¶¶[0056] &
[0057], Fig. 4).
4. Arimilli further teaches in certain circumstances such that the
data is still being actively used in the remote node, or the cache line’s snoop
queues are all busy, or if the target cache lines are held in the associated L2
or L1 caches, the Flush query may be ignored (¶¶[0091] & [0099]).
Appeal 2009-002615
Application 10/760,431

6
Carpenter
5. Carpenter discloses a NUMA computer system for plural cache
hierarchies coupled by a local interconnection that can hold concurrently an
unmodified copy of a particular cache line (col. 2, l. 56 to col. 3, l. 10).
6. Carpenter also discloses how the node controllers will operate
according to the Table X (col. 12, ll.1-45, Table X).

V. ANALYSIS
“[T]he examiner bears the initial burden, on review of the prior art or
on any other ground, of presenting a prima facie case of unpatentability. . . .
If that burden is met, the burden of coming forward with evidence or
argument shifts to the applicant.” In re Oetiker, 977 F.2d 1443, 1445
(1992).
The Examiner sets forth a detailed explanation of a prima facie case of
unpatentability in the Examiner’s Answer. Therefore, we look to
Appellant’s Briefs to show error in the proffered prima facie case.

The Common Feature in Claims
Independent claim 1, recites, inter alia, “cache coherency mechanism
selectively determining whether to send cache line invalidation messages to
said at least one device using state information in said cache line state
directory structure”. Independent claims 9 and 19 contain those similar
limitations recited in claim 1. The recited limitations have the same scope of
selectively determining whether to send cache line invalidation messages a
device by using the information in the cache line state directory.
Appeal 2009-002615
Application 10/760,431

7
35 U.S.C. § 103(a) rejections
With respect to independent claim 1, Appellants contend that neither
Baumgartner nor Arimilli (nor Carpenter) discloses the feature of
“selectively determining whether to send cache line invalidation messages to
said at least one device” (App. Br. 12-13).
The Examiner states that Baumgartner teaches the argued limitation
(Ans. 4 and Ans. 15). The Examiner also states that “Arimilli clearly
discloses such limitation in at least paragraph [0056]. . . .” (Ans. 12), and
“Arimilli similarly discloses the cache coherency mechanism of Appellant’s
claimed invention.” (Ans. 15.)
We disagree with the Examiner’s reading of the references. We find
that the Baumgartner reference relied upon by the Examiner only discloses
that a cache directory stores the memory addresses of data and each cache
line with an identifier relating to the remote nodes and the corresponding
coherency status (FF 1). However, the Baumgartner reference does not
teach how to send invalidation messages using the cache line directory, let
alone selectively sending invalidation messages (FF 2).
We next look to the teachings of Arimilli. The Examiner in the Final
Rejection has merely relied upon Arimilli for the limitation of the cache line
state directory associated with at least one device containing a fixed number
of cache line entries (Ans. 4). Furthermore, the Examiner has only provided
a limited discussion of the teachings of the Arimilli reference (id. at 15)
which is not sufficient to teach or fairly suggest the specific limitations
recited in claim 1. We also note that the Arimilli reference additionally
teaches that the cache flush queue may be ignored in certain circumstances
(FF 4), however the Examiner does not address those teachings and how the
Appeal 2009-002615
Application 10/760,431

8
merits of the teachings relates to the claimed invention. Thus, we are left to
speculate how the teachings may apply to the claimed limitations. We,
therefore, find the Examiner’s position in reliance upon the teachings of
Arimilli to be untenable.
Because we agree with at least one of the Appellants’ contentions, we
find that the Examiner has not made a requisite showing of obviousness as
required to teach or fairly suggest the invention as recited in claim 1 by the
combination of Baumgartner and Arimilli. The rejection of dependent
claims 2 and 5-8 contains the same deficiency. The Appellants, thus, have
demonstrated error in the Examiner’s prima facie case for obviousness of the
subject matter of claims 1, 2, and 5-8.
The independent claims 9 and 19 contain the similar limitations to
those found in independent claim 1. The Appellants present similar
arguments as set forth with respect to independent claim 1 in response to the
rejections of independent claims 9 and 19 (App. Br. 13-14).
The Examiner states that Carpenter discloses the argued limitation in
the Final Rejection (Ans. 7).
We disagree with the Examiner’s reading of the reference. We find
that Carpenter teaches a NUMA computer system can store concurrently a
cache line of data in different cache hierarchies (FF 5). However, we find
Carpenter does not teach the argued limitation as the Examiner found. We
find the portion relied upon by the Examiner only discloses how the node
controller changes the coherence directory according to the Table X (FF 6)
and does not mention sending invalidation messages.
As in our discussion with respect to independent claim 1, we similarly
find that the Appellants have demonstrated error in the Examiner’s prima
Appeal 2009-002615
Application 10/760,431

9
facie case for obviousness of the subject matter of independent claims 9 and
19. The rejection of dependent claims 3, 4, 10-13, and 20-22 also contains
the same deficiency. Hence, the Appellants’ argument persuades us that the
Examiner erred in rejecting claims 1-13, and 19-22.
We, therefore, cannot sustain the rejection of claims 1-13, and 19-22
under 35 U.S.C. § 103.
With respect to claims 14-18, we note that claims 14-18 do not
contain the limitation “cache coherency mechanism selectively determining
whether to send cache line invalidation messages to said at least one device
using state information in said cache line state directory structure,” as recited
in claim 1. We also note that the Appellants do not specifically argue claims
14-18, but instead argue claims 14-18 with the group of claims 3, 4, 12-18,
and 21 (App. Br. 15-16). Claim 14 recites:
[W]herein said first portion of said cache line state directory
structure contains a plurality of cache entries, each entry having
a fixed correspondence to a respective set of real addresses;
wherein said second portion of said cache line state directory
structure contains exactly said fixed number of cache line
entries, each entry having a fixed correspondence to a unique
respective one of said fixed number of slots for caching data of
said device cache.

(App. Br. 23.)

The Appellants contend that “the cache line directory structure
contains multiple portions, one of which is organized having the one-to-one
correspondence with cache slots discussed above, and the other of which has
entries corresponding to real addresses.” (App. Br. 15).
We disagree with the Appellants’ contention. We find Baumgartner
teaches that one cache line directory contains indications of the cache line
Appeal 2009-002615
Application 10/760,431

10
addresses checked out to caches in remote nodes (FF 1). We also find
Arimilli teaches that a cache line directory structure includes two portions of
cache line directory: LMD and RMD. The address tag and coherency state
of a corresponding cache line (slot) are stored in the directory entries 144 in
the LMD or RMD (FF 3). We thus find that combining the well-known
element of cache line directory of Baumgartner with the well-known
technique of separate cache line directory for addresses and corresponding
entries of cache lines taught by Arimilli is nothing more than a “predictable
use of prior art elements according to their established functions.” KSR Int’l
Co., 550 U.S. at 417.
Accordingly, we sustain the Examiner’s obviousness rejection of the
dependent claim 14. We also sustain the Examiner’s obviousness
rejections of dependent claims 15-18, which have analogous wording and
are not separately argued and fall with their respective base claims. 37
C.F.R. § 41.37 (c)(1)(vii). See In re Nielson, 816 F.2d 1567, 1572 (Fed.
Cir. 1987).
VI. CONCLUSION
We conclude that the Appellants have shown that the Examiner erred
by failing to identify that the combination of Baumgartner and Arimilli
teaches and fairly suggests “cache coherency mechanism selectively
determining whether to send cache line invalidation messages to said at least
one device using state information in said cache line state directory
structure,” as recited in independent claim 1.
Appeal 2009-002615
Application 10/760,431

11
We also conclude that the Appellants have not shown that the
Examiner erred in identifying that the combination of Baumgartner and
Arimilli teaches and fairly suggests the limitations recited in claim 14.

VII. ORDER
We reverse the obviousness rejections of claims 1-13 and 19-22 under
35 U.S.C. § 103(a).
We affirm the obviousness rejections of claim 14-18 under 35 U.S.C.
§ 103(a).
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136 (a). See 37 C.F.R.
§ 1.136(a)(1)(iv).
AFFIRMED-in-PART

erc

ROBERT R. WILLIAMS
IBM CORPORATION, DEPT. 917
3605 HIGHWAY 52 NORTH
ROCHESTER, MN 55901-7829