Ex Parte Walker et al

Patent Trial and Appeal Board

Dec 9, 2016

13473778 (P.T.A.B. Dec. 9, 2016)

United States Patent and Trademark Office
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O.Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
13/473,778 05/17/2012 William L. Walker 1458-0506 1703
102347 7590 12/13/2016
Polansky & Associates, P.L.L.C.
12600 Hill Country Blvd
Suite R-275
Austin, TX 78738
EXAMINER
MATIN, TASNIMA
ART UNIT PAPER NUMBER
2135
NOTIFICATION DATE DELIVERY MODE
12/13/2016 ELECTRONIC
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the
following e-mail address(es):
ppolansky@patentwerks.net
admin @ patent werks. net
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Ex parte WILLIAM L. WALKER, ROBERT F. KRICK,
TARUN NAKRA, and PRAMOD SUBRAMANYAN1
Appeal 2015-004808
Application 13/473,778
Technology Center 2100
Before ST. JOHN COURTENAY III, KRISTEN L. DROESCH, and
NORMAN H. BEAMER, Administrative Patent Judges.
DROESCH, Administrative Patent Judge.
DECISION ON APPEAL
STATEMENT OF THE CASE
Appellants seek review under 35 U.S.C. § 134(a) from the Examiner’
Final Rejection of claims 1—20, all of the pending claims in the application.
We have jurisdiction under 35 U.S.C. § 6(b).
We AFFIRM-IN-PART.
1 Appellants indicate the real party-in-interest is Advanced Micro Devices,
Inc. App. Br. 3.
Appeal 2015-004808
Application 13/473,778
BACKGROUND
The disclosed invention relates to a method and cache system that
includes a first plurality of caches at a first hierarchy level and a second
cache at a second hierarchy level lower that the first level and coupled to the
first plurality of caches. The second cache enforces a cache line replacement
policy in which the second cache selects a cache line for replacement based
on part on whether the cache line is present in any of the plurality of first
caches and in part on another factor. See Spec. 110, Abstract.
CLAIMED SUBJECT MATTER
Representative claims 1 and 16, reproduced from the Claims
Appendix of the Appeal Brief, read as follows (disputed limitations in
italics)'.
1. A cache system comprising:
a plurality of first caches at a first level of a cache hierarchy; and
a second cache at a second level of the cache hierarchy coupled
to each of the plurality of first caches, the second level lower than the
first level, wherein the second cache enforces a biased cache line
replacement policy in which the second cache selects a valid cache
line for replacement based in part on whether the cache line is present
in one or more of the plurality of first caches and in part on another
factor.
16. A method for biased cache line replacement in a lower level
cache comprising:
selecting a first valid cache line of the lower level cache
as a candidate cache line for replacement;
determining whether the first cache line is present in any
one of a plurality of higher level caches;
if the candidate cache line is not present in any one of the
plurality of higher level caches, replacing the first cache line
with a new cache line; and
2
Appeal 2015-004808
Application 13/473,778
if the candidate cache line is present in at least one of the
plurality of higher level caches, selectively replacing a second
cache line with the new cache line.
REFERENCES AND REJECTIONS ON APPEAL
Claims 1, 4, 6, 11, 12, and 16 stand rejected under 35 U.S.C. § 102(b)
as anticipated by Vishin (US 7,774,549 B2; Aug. 10, 2010).
Claims 2, 3, 13, and 14 stand rejected under 35 U.S.C. § 103(a) as
unpatentable over Vishin and So et al. (US 5,530,832; June 25, 1996)
(“So”).
Claims 5 and 17 stand rejected under 35 U.S.C. § 103(a) as
unpatentable over Vishin and Merrell et al. (US 5,829,038; Oct. 27, 1998)
(“Merrell”).
Claims 7, 15, and 18 stand rejected under 35 U.S.C. § 103(a) as
unpatentable over Vishin and McDermott et al. (US 5,860,105; Jan. 12,
1999) (“McDermott”).
Claims 8—10, and 19-20 stand rejected under 35 U.S.C. § 103(a) as
unpatentable over Vishin and High Performance Cache Replacement
Using Re-Reference Interval Prediction (RRIP), ISCA ’ 10 (2010)
(“Aamer”).
ANALYSIS
We have reviewed the Examiner’s rejections in light of Appellants’
arguments in the Brief, the Answer, and the arguments in the Reply Brief.
We are not persuaded by Appellants’ arguments addressing claims 1—17, and
19-20. We agree with and adopt as our own the Examiner’s findings and
conclusions of law for these claims. However, we are persuaded by
3
Appeal 2015-004808
Application 13/473,778
Appellants’ arguments addressing claim 18. We highlight and address
specific findings and arguments below for emphasis.
Claims 1, 4, and 11
Appellants argue that Vishin does not disclose “wherein the second
cache enforces a biased cache line replacement policy in which the second
cache selects a valid cache line for replacement based in part on whether the
cache line is present in one or more of the plurality of first caches and in part
on another factor,” as recited in independent claims 1 and 11. See App. Br.
7. Appellants contend that Vishin discloses “what to do with cache lines
that have already been selected as victim cache lines, instead of how to
select victim cache lines.” Id. at 8; see id. 7—8 (citing Vishin Fig. 1 A, 5:60—
6:8); Reply Br. 3. Appellants argue that Vishin discusses the selection of
victim cache lines with respect to Figure 2, element 205, and discloses at
column 6, lines 29—35 that victim cache lines are selected by conventional
means. See id. at 8—10; Reply Br. 3^4.
We are not persuaded by Appellants’ arguments because the disputed
claim limitation is not entitled to patentable weight. The “wherein” clause
does not limit the structure of the second cache, but merely recites the use or
function of the second cache of the cache system—“enforces a biased cache
line replacement policy in which the second cache selects a valid cache line
for replacement based in part on whether the cache line is present in one or
more of the plurality of first caches and in part on another factor.”2
Although applicants are free to define something by what it does rather than
by what it is, there is inherent risk in doing so. See In re Swinehart, 439
2 See MPEP § 2111.04, Ninth Ed., Nov. 2015 (regarding “wherein” clauses).
4
Appeal 2015-004808
Application 13/473,778
F.2d 210, 212 (CCPA 1971). One risk is that the recited use will cover any
and all embodiments capable of performing the recited use or function. See
id. at 213; see also In re Schreiber, 128 F.3d 1473, 1477 (Fed. Cir. 1997)
(“Schreiber’s contention that his structure will be used to dispense popcorn
does not have patentable weight if the structure is already known, regardless
of whether it has ever been used in any way in connection with popcorn.”).
Apparatus claims, similar to the system recited in claim 1, and the processor
recited in claim 11, “cover what a device is, not what a device does.”
Hewlett-Packard co. v. Bausch &Lomb, Inc., 909 F.2d 1464, 1468 (Fed.
Cir. 1990); but cf In re Giannelli, 739 F.3d 1375, 1378 (Fed. Cir. 2014)
(“adapted to” clause limited a machine claim where “the written description
makes clear that ‘adapted to,’ as used in the [] [application, has a narrower
meaning, viz., that the claimed machine is designed or constructed to be
used as a rowing machine whereby a pulling force is exerted on the
handles.”)3
We agree with, and adopt as our own, the Examiner’s finding that
Vi shin discloses the claimed structure “a plurality of first caches at a first
level of a cache hierarchy; and a second cache at a second level of the cache
hierarchy coupled to each of the plurality of first caches, the second level
lower than the first level.” See Final Act. 2—3 (citing Vishin Fig. IB: “LI,”
“victim cache”; Fig. 4: “LI cache,” “L2 cache”; 1:47—60, 3:58—60, 4:3—5,
25^42, 9:66—67; 10:1—17). The remaining “wherein” clause recited in
3 Cf. In re Man Mach. Interface Techs. LLC, 822 F.3d 1282, 1286 (Fed. Cir.
2016) (“We have noted that the phrase ‘adapted to’ generally means ‘made
to,’ ‘designed to,’ or ‘configured to,’ though it can also be used more
broadly to mean ‘capable of’ or ‘suitable for.’”) (citations omitted).
5
Appeal 2015-004808
Application 13/473,778
claims 1 and 11 does not patentably distinguish the claimed invention over
the Vishin reference because the “wherein” clause describes the intended use
or function of the second cache, and does not describe or further limit the
structure of the second cache. See MPEP §2111.04.
Accordingly, on this record, we are not persuaded of Examiner error
in the rejection of claims 1 and 11 based on Appellants’ arguments focusing
on the use or function of the second cache of the cache system recited in
claim 1, and the processor recited in claim 11. Appellants do not address
dependent claims 4 and 12 separately. See App. Br. 10. Accordingly, for
the same reason as claims 1 and 11, we are not persuaded of Examiner error
in the rejection of claim 4.
Claims 2, 3, 13
Appellants present arguments addressing dependent claims 2, 3, and
13 under a separate heading. See App. Br. 12—13. Appellants argue that
Vishin does not disclose how to select a cache line for replacement as recited
in claims 1 and 11. See id. at 12. Appellants contend that So does not teach
or suggest these limitations either. See id. at 13. For the same reasons as
those explained above addressing claims 1 and 11, we are not persuaded of
Examiner error in the rejection of claims 2, 3, and 13.
Claims 5—10 and 14—15
Appellants present arguments addressing each of claims 5—10 and 14—
15. See App. Br. 10—11, 13—17; Reply Br. 4—9. Claims 5—8 and 10 further
describe the cache line replacement policy recited in the “wherein” clause of
claim 1. Claims 9 and 14—15 recite additional uses or functions of the
second cache of the cache system recited in claim 1, and the processor
recited in claim 11. Similar to claims 1 and 11, the disputed limitations of
6
Appeal 2015-004808
Application 13/473,778
claims 5—10 and 14—15 are not entitled to patentable weight. The additional
recitations of claims 5—10 and 14—15 do not further limit the structure of the
second cache, but merely recite additional uses or functions of the second
cache, and provide additional description of the biased cache line
replacement policy that is to be enforced by the second cache. Therefore,
we are not persuaded of Examiner error in the rejections of claims 5—10 and
14—15 based on Appellants’ arguments addressing the additional functions
of the second cache and additional descriptions of the biased cache line
replacement policy recited in claims 5—10 and 14—15.
Claim 16
Appellants argue that Vishin does not disclose “the steps of selecting,
determining, replacing the first cache line, and selectively replacing a second
cache line as recited in [independent] claim 16.” App. Br. 10. Appellants
assert that Vishin discloses “what to do with cache lines that have already
been selected as victim cache lines, instead of how to select victim cache
lines.” Id. at 8; see id. 7—8 (citing Vishin Fig. 1A, 5:60-6:8); Reply Br. 3.
Appellants assert that Vishin discusses the selection of victim cache lines
with respect to Figure 2, element 205, and “discloses at col. 6, lines 29-35
that victim cache lines are selected by conventional means and not ‘based in
part on whether the cache line is present in one or more of the plurality of
the first caches and in part on another factor’ as recited in claim 1.” Id. at 9;
see id. at 8—10; Reply Br. 3^4.
Appellants’ arguments are not persuasive of Examiner error because
they are not commensurate in scope with the limitations of claim 16. Claim
16 does not recite that the step of selecting “is based in part on whether the
cache line is present in or more of the plurality of the first caches and in part
7
Appeal 2015-004808
Application 13/473,778
on another factor.” Instead, claim 16 recites “selecting a first valid cache
line of the lower level cache as a candidate cache line for replacement.”
Appellants do not present arguments addressing substantively the remaining
steps of claim 16. Therefore, for this reason, we are not persuaded of
Examiner error in the rejection of claim 16.
Claim 17
Appellants argue that dependent claim 17 relates to using a biased
pseudo least recently used (PLRU) policy for victim selection. See App. Br.
13. Appellants contend that the combination of Vishin and Merrell would
result in a cache that selects victims using a conventional PLRU policy, not
a biased PLRU policy. See id. at 14; Reply Br. 6—7.
Appellants’ arguments are not persuasive of Examiner error because
they are not commensurate in scope with the limitations of claim 17. Claim
17 does not recite a biased PLRU policy. Instead, claim 17 recites “selecting
the candidate cache line comprises selecting the candidate cache line based
on a pseudo least recently used policy.” Likewise, independent claim 16
recites “selecting a first valid cache line of the lower level cache as a
candidate cache line for replacement,” but does not recite a biased cache line
replacement policy. Accordingly, for these reasons we are not persuaded of
Examiner error in the rejection of claim 17.
Claim 18
Dependent claim 18 recites “wherein the selecting the candidate cache
line comprises selecting the candidate cache line based on a skip policy.”
The Examiner finds that Vishin does not disclose a skip policy. See Pinal
Act. 9. The Examiner finds that McDermott reaches a cache line
replacement policy comprising a skip policy. See id. (citing McDermott
8
Appeal 2015-004808
Application 13/473,778
2:34—35 “the next line is skipped if it is clean”); see id. at 10 (“[Cjlaim 18 is
rejected for the same reasons set forth in the respective rejections of claim
7.”). The Examiner determined it would have been obvious to one of
ordinary skill in the art to modify the cache line management policy taught
by Vishin and incorporate the skip policy taught by McDermott, and would
have been motivated to make the modification in order to improve the
performance of the cache management system as suggested by McDermott.
See id. at 10 (citing McDermott 1:39-44).
Appellants argue that Vishin does not disclose victim selection by any
other than conventional means. See App. Br. 14. Appellants further contend
that McDermott also doesn’t disclose victim selection either. See id.
Appellants assert that McDermott discloses skipping cache lines in a search
for cache lines with dirty data. See id. at 15 (citing McDermott 1:32—37,
1:65—2:30); Reply Br. 7 (citing McDermott 2:31—35). We agree with
Appellants’ argument that the combination of Vishin and McDermott does
not teach or suggest, and would not render obvious “the selecting the
candidate cache line comprises selecting the candidate cache line based on a
skip policy,” as recited in claim 18. See App. Br. 15; Reply Br. 7.
Therefore, we are constrained on this record to reverse the Examiner’s
rejection of claim 18.
Claim 19
Appellants argue that dependent claim 19 relates to using a biased re­
reference interval prediction (RRTP) policy. See App. Br. 15. Appellants
contend that the combination of Vishin and Aamer would result in a cache
that selects victims using Aamer’s unbiased RRIP policy, not a biased RRIP
policy. See id. at 16; Reply Br. 8.
9
Appeal 2015-004808
Application 13/473,778
Appellants’ arguments are not persuasive of Examiner error because
they are not commensurate in scope with the limitations of claim 19. Claim
19 does not recite a biased RRIP policy. Instead, claim 19 recites “selecting
the candidate cache line comprises selecting the candidate cache line based
on a re-reference interval prediction policy.” Similarly, independent claim
16 recites “selecting a first valid cache line of the lower level cache as a
candidate cache line for replacement,” but does not recite a biased cache line
replacement policy. Accordingly, for these reasons we are not persuaded of
Examiner error in the rejection of claim 19.
Claim 20
Appellants argue that dependent claim 20 relates to using a biased
cache line replacement policy that is based on the length of time a candidate
cache line has been present in the higher level cache. See App. Br. 16.
Appellants contend that the combination of Vishin and Aamer would result
in a cache that selects victims using Aamer’s unbiased RRIP policy, but not
a biased RRIP policy, and not a policy that is based on a length of time a
candidate cache line has been in the upper level cache. See id. at 16.
Appellants’ arguments are not persuasive of Examiner error because
they are not commensurate in scope with the limitations of claim 20. Claim
20 does not recite a biased cache line replacement policy or a biased RRIP
policy. Appellants’ arguments also are not persuasive because they do not
address sufficiently the Examiner’s following findings:
selecting a ‘stale’ cache block to be replaced based on [a] ‘re­
reference prediction value (RRPV)’ implies selecting based on a
‘length of time.’ An ideal [least recently used] LRU policy looks
at when each cache line was last accessed and evicts the cache
line that has not been accessed for the longest time, i.e. ‘distant
re-reference’ block).
10
Appeal 2015-004808
Application 13/473,778
Final Act. 12. Appellants further contend that the Examiner’s findings are
“irrelevant because the combination of Vishin and Aamer would just result
in a cache that selects victims using Aamer’s unbiased RRPV policy and
decide what action to take based on Vichin’s selective action policy.” Reply
Br. 8 (emphasis omitted). Again, claim 20, and independent claim 16 do not
recite a biased cache line replacement policy. Therefore, for these reasons,
we are not persuaded of Examiner error in the rejection of claim 20.
DECISION
We AFFIRM the rejections of claims 1—17, and 19—20.
We REVERSE the rejection of claim 18.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(l)(iv).
AFFIRMED-IN-PART
11