Ex Parte Pong

Patent Trial and Appeal Board

Sep 18, 2012

11228163 (P.T.A.B. Sep. 18, 2012)

UNITED STATES PATENT AND TRADEMARK OFFICE
________________

BEFORE THE PATENT TRIAL AND APPEAL BOARD
________________

Ex parte FONG PONG

________________

Appeal 2010-005767
Application 11/228,163
Technology Center 2100
________________

Before ROBERT E. NAPPI, ERIC S. FRAHM, and JOHN G. NEW,
Administrative Patent Judges.

NEW, Administrative Patent Judge.

DECISION ON APPEAL

Appeal 2010-005767
Application 11/228,163

2
SUMMARY
Appellant files this appeal under 35 U.S.C. § 134(a) from the
Examiner’s final rejection of claims 1-4, 6-8, 10-17, 19-21, and 23-26
which stand rejected as unpatentable under 35 U.S.C. § 102(b) as being
anticipated by Emma et al. (US 5,584,002, December 10, 1996) (“Emma”),
and 5, 9, 18, and 22 which stand rejected as unpatentable under 35 U.S.C.
§ 103(a) as obvious over Emma. We have jurisdiction under 35 U.S.C.
§ 6(b).
We affirm.

STATEMENT OF THE CASE
The claimed invention is directed to a method and system for
supporting large caches with split and canonicalization tags. Abstract.
Because the Examiner rejected claims 1-4, 10-17, and 23-26 for
substantially the same reasons, we select claim 1 as representative.
Appellant argues that the Examiner erred in determining that claim 1 was
unpatentable under 35 U.S.C. § 102(b) as being anticipated by Emma.
Claim 1 recites:
1. A method for accessing stored data, the method
comprising:

generating a tag signature based on a current portion of a
tag field of an address;

retrieving a cache line based on one or both of said tag
signature and a subsequent portion of said tag field; and

determining whether a cache hit occurs based on said
current portion of said tag field.

Appeal 2010-005767
Application 11/228,163

3
App. Br. 24.
Appellant also argues that the Examiner also erred for substantially
the same reason with respect to determining that claims 6 and 19 are
unpatentable under 35 U.S.C. § 102(b) as being anticipated by Emma. We
therefore select claim 6 as being representative. Claim 6 recites:
6. The method according to claim 1, comprising
determining that a potential cache hit occurs when at least a
portion of a retrieved tag set is equal to a comparison value.

App. Br. 24.
Appellant argues further that the Examiner erred for substantially the
same reason with respect to determining that claims 7 and 20 are
unpatentable under 35 U.S.C. § 102(b) as being anticipated by Emma. We
therefore select claim 7 as being representative. Claim 7 recites:
7. The method according to claim 6, comprising
retrieving said cache line based on said determined potential
cache hit.

App. Br. 25.
Appellant also contends that the Examiner erred for substantially the
same reason with respect to determining that claims 8 and 21 are
unpatentable under 35 U.S.C. § 102(b) as being anticipated by Emma. We
therefore select claim 8 as being representative. Claim 8 recites:
8. The method according to claim 13, comprising
determining that a cache miss occurs when each of said
plurality of tag set values is not equal to said comparison value.

App. Br. 25.
Finally, Appellant argues that the Examiner erred for substantially
the same reason in concluding that claims 5, 9, 18, and 22 are unpatentable
Appeal 2010-005767
Application 11/228,163

4
under 35 U.S.C. § 103(a) as being obvious over Emma. We therefore select
claim 5 as representative of this group. Claim 5 recites:
5. The method according to claim 4, comprising
retrieving stored data from main memory based on said
determined cache miss.

App. Br. 24.

ANALYSIS
Claim 1
Issue 1: Whether the Examiner erred in finding that Emma does not
teach the limitation of claim 1 reciting “a tag field.”

Appellant argues that the Examiner erred in concluding that claim 1
is unpatentable under 35 U.S.C. § 102(b) as being anticipated by Emma.
App. Br. 6. Specifically, Appellant contends that the Examiner erred
because Emma does not teach, suggest or disclose that its AHIGH 322
field, the AMID 324 field or any combination of AHIGH 322 and AMID
324 fields constitute “a tag field” as recited in the limitation of claim 1.
App. Br. 8. Appellant contends that, to the contrary, Emma instead
discloses only that address tags are contained within the cache directory
310, and not in the AHIGH 322 and AMID 324 fields as found by the
Examiner. Id.
The Examiner answers that the Examiner indeed considers the “tag
field” of the address 320 to be comprised of the AHIGH and AMID fields.
Ans. 10. The Examiner points out that, in cache architecture, the “tag”
portion of an incoming address often consists of the most significant bits,
and is used in a comparison step to affirm a “cache-hit.” Id. Consequently,
the Examiner finds that since the “tag field” is the AHIGH and AMID
Appeal 2010-005767
Application 11/228,163

5
fields, the limitation reciting a “current portion of a tag field” is the AMID
field, or more accurately, the bit fields/location that correspond to the
AMID portion –i.e., the bit locations/positions 12 and 13 of the incoming
address as defined above. Id.
The Examiner further answers that the Examiner considers the “tag
signature” to be the value of the bit locations/fields of bits 12 and 13 of the
incoming address. Ans. 10. Therefore, the Examiner finds that the “current
portion of the tag field” corresponds to the bit locations of the incoming
address. Those bit locations contain values of the AMID bits. This value is
being considered by the Examiner to be the “tag signature.” Id.
Consequently, the Examiner concludes that the portion of the limitation of
claim 1 reciting “a tag field” is anticipated by Emma’s teaching of the
AHIGH and AMID fields of the incoming address.
We find the Examiner’s reasoning to be persuasive. Appellant’s Fig.
5a illustrates “a tag field 502” as a portion of the incoming address
containing bit address vectors n1 and n2. See also Spec. 16. Appellant’s
tag field 502 corresponds directly to the teaching of Emma that discloses
portions of the AMID field in the incoming address containing the bit
address vectors that are compared to the addresses in the cache directory, as
the Examiner finds. See Emma, Fig. 5. Consequently, we conclude that the
Examiner did not err in finding that Emma anticipates the portion of the
limitation of claim 1 reciting “a tag field.”

Appeal 2010-005767
Application 11/228,163

6
Issue 2: Whether the Examiner erred in finding that Emma teaches the
“generating” step recited in the limitation of claim 1.

Appellant also argues that the Examiner erred with respect to the
portion of the limitation of claim 1 reciting “generating a tag signature.”
App. Br. 9 (emphasis added). App. Br. 9. Specifically, Appellant contends
Emma teaches that “the above mentioned 14 bits 14 are assigned to the
AMID 324 and ALOW 326 fields, so that the least 12 significant bits are in
ALOW 326 and the 2 most significant bits are in AMID 324.” Id. (footnote
omitted). In other words, according to the Appellant, Emma teaches
assigning of bits of the AMID field of the incoming address, but does not
teach the generating of bits. Id.
The Examiner responds that the Examiner finds that the portion of
the limitation of claim 1 reciting “generating of the tag signature” to be the
parsing, or extraction, of the value of those AMID bits from the bit
locations so designated. Ans. 10. Referring to figure 5 of Emma, the
Examiner finds that the value of the AMID bits are sent to the comparator
and that, Emma therefore teaches “generating a tag signature” because the
value of the bit locations corresponding to the AMID bits of an incoming
address is being employed in a comparison. Moreover, in order for that
comparison to be made, the values of the AMID field bits must be
generated or “brought into existence” from the bits that comprise the entire
32-bit address. Ans. 10-11.
We are persuaded by the Examiner’s reasoning. As discussed supra,
we agree with the Examiner that the specific bit values contained within the
AMID tag field of the address constitute the tag signature. We further
agree with the Examiner’s finding that the message that is being sent to the
Appeal 2010-005767
Application 11/228,163

7
comparator in the cache directory is extracted or generated from the bit
values contained within the AMID tag field. We therefore conclude that the
Examiner did not err in finding that Emma teaches the portion of the
limitation of claim 1 reciting “generating a tag signature.” Consequently,
we conclude that the Examiner did not err in concluding that claim 1 is
unpatentable under 35 U.S.C. § 102(b) as being anticipated by Emma.

Claim 6
Issue 1: Whether the Examiner erred in finding that a “congruence class”
as taught by Emma is synonymous with an entry 380i in the cache directory
310 that is also a “tag set.”

Appellant argues that the Examiner misapprehended the meaning of a
“congruence class” as disclosed in Emma. App. Br. 13. Appellant argues
that Emma teaches that congruence classes are contained within the cache
memory 312 and not the cache directory 310. Id. Specifically, Appellant
contends that Emma teaches that “each congruence class also
contains two associated data lines 314a-n and 316a-n.” Id. (citing Emma,
col. 8, ll. 30-32; Fig. 5). Furthermore, according to Appellant, Emma, also
discloses a definition of a “congruence class” which teaches “a datum with
a given address may be stored in one of a limited group of locations in a
cache, known as a congruence class.” App. Br. 13 (citing Emma, col. 1, ll.
40-42). Thus, Appellant argues that Emma teaches that a “congruence
class” refers to a data storage location in a cache. App. Br. 13.
The Examiner answers that Emma defines a “congruence class” as
constituting the line of data elements in the cache directory in addition to
the associated data lines in the cache memory. Ans. 14. The Examiner
Appeal 2010-005767
Application 11/228,163

8
finds that the language of Emma explicitly defines the congruence class
thus:
In the exemplary embodiment, each congruence class includes
two sets. That is, there are address tags 307a-n and 311a-n and
two valid bits 305a-n and 309a-n in the directory 310. Each
congruence class also contains two associated data lines 314a-n
and 316a-n.

Ans. 14 (quoting Emma, col. 8, ll. 28-31) (emphases added). The Examiner
further answers that Emma teaches that a congruence class is
the entire ith entry across both the cache arrays 314/316 and cache directory
310. Ans. 15 (citing Emma, col. 1, ll. 43-44).
We find the Examiner’s reasoning persuasive and adopt it as our
own. Consequently, we conclude that the Examiner did not err in finding
that Emma teaches that a congruence class comprises the entire ith entry
across both the cache arrays and cache directory.

Issue 2: Whether the Examiner erred in finding that Emma teaches
the limitation of claim 1 reciting a potential cache hit occurs when at least
a portion of a retrieved tag set is equal to a comparison value.

Appellant next argues that the Examiner has “misapprehended the
teachings of Emma with respect to the conditions under which
Emma teaches that there may be a cache hit versus the conditions under
which Emma teaches that there is a cache hit.” App. Br. 14 (emphasis in
original). Appellant contends that Emma teaches that “if SCi-1 and RM
303i (or 308i) have the same value, the output value 337a (or 337b) from
gate 336a (or 336b) is 1, and there may be a cache hit in the storage element
314i (or 316i).” Id. (quoting Emma, col. 10, ll. 28-32). Thus, according to
Appeal 2010-005767
Application 11/228,163

9
Appellant, Emma teaches that the conditions under which “‘there may be a
cache hit’ are determined based on the SC and RM bits [hit]” and do not
depend upon AMID and/or AHIGH values as asserted by the Examiner.
App Br. 14.
The Examiner does not dispute that the citations of Emma provided
by Appellant teach a potential cache hit. Ans. 15. However, the Examiner
answers that in order for a true cache hit, four elements need to occur (i.e.,
be logically “l” as evidenced by AND gate 338b), and without all of those
elements, any elements that positively occur without the others in
combination is considered by the Examiner to be a “potential cache hit,”
including both AHIGHib and AMIDi matching the AHIGH and AMID
fields of the incoming request address, respectively, through the use of
comparators 332b and 334b. Ans. 15-16. Moreover, the Examiner answers
that, since the scope of claim 6 does not set forth a definition of “potential
cache hit,” the Examiner has broadly interpreted the term “potential cache
hit” as the situation occurring when at least one of the four conditions
mentioned supra produces a logic “l” for AND gate 338b. Ans. 16. The
Examiner finds that Appellant’s citation of Emma does indeed point to one
of those four conditions; however, the Examiner argues that any of those
four conditions that may occur (including both AHIGHib and AMIDi
matching the AHIGH and AMID fields of the incoming request address)
yields a “potential cache hit,” since each must occur for an actual cache hit.
Id.
We are persuaded by the Examiner’s reasoning and adopt it as our
own. Consequently, we find that the Examiner did not err in finding that
Emma teaches the limitation of claim 6 reciting “a potential cache hit
Appeal 2010-005767
Application 11/228,163

10
occurs when at least a portion of a retrieved tag set is equal to a comparison
value.”

Claim 7
Issue: Whether the Examiner erred in finding that Emma teaches
“retrieving said cache line based on said determined potential cache hit”
as is recited in claim 7.

Appellant next argues that the Examiner erred by inconsistently
applying the teachings of Emma with respect to the limitation of claim 7
reciting “retrieving said cache line based on said determined potential cache
hit.” App. Br. 16. Specifically, Appellant argues that the Examiner has
utilized an inconsistent interpretation of the meaning of a “cache line” in
support of the rejection of claim 7. Id. According to Appellant, the
Examiner has reasoned that “the potential cache hit” is determined based on
fields within the line 380i and that, based on fields within the line 380i, the
line 380i itself is retrieved. Id. Appellant argues that any such comparison
based on fields within the line 380i cannot be performed prior to the
retrieval of the line 380i. Id.
The Examiner answers that Emma explicitly teaches retrieving the
cache line (Fig. 4, step 408) based on a determined potential cache hit.
Ans. 17. The Examiner finds that a potential cache hit is determined when
a portion (e.g., bit SCi) of a retrieved tag set (i.e., the congruence set that
corresponds to the set of SCi, RMi, Vi, AHIGHi, and AMIDi (See Emma,
FIG. 2) or the set of SCi, RMia, Via, AHIGHia, RMib, Vib, AHIGHib, and
AMIDi (See Emma, Fig. 5)) that is retrieved when processing an access
request in step 402, is equal to a comparison value. Ans. 16-17. Put more
Appeal 2010-005767
Application 11/228,163

11
simply, the Examiner finds that if the SCi field for a corresponding
congruence class is set to logic “0,” the data may be in the cache. Id. The
data (i.e., the cache line) is then retrieved in accordance with step 408 of
figure 4. Ans. 17-18. The actual hit determination occurs in step 411 as
shown after the retrieval of the cache line. Ans. 18.
We find the Examiner’s reasoning persuasive and adopt it as our
own. Consequently, we do find that the Examiner did not err in finding that
Emma teaches the portion of the limitation of claim 7 reciting “retrieving
said cache line based on said determined potential cache hit.”

Claim 8
Issue: Whether the Examiner erred in finding that Emma teaches the
limitation of claim 8 reciting “determining that a cache miss occurs when
each of said plurality of tag set values is not equal to said comparison
value.”

Appellant argues that the Examiner failed to cite any disclosure from
Emma supporting the assertion that Emma teaches “determining that a
cache miss occurs when each of said plurality of tag set values is not equal
to said comparison value,” as recited in claim 8. App. Br. 18. Appellant
argues that that Emma merely discloses conditions under which “there is a
cache hit.” Id. (citing Emma, col. 10, ll. 30-39).
The Examiner answers that, in the caching arts, it is very well
established that anytime a cache hit does not occur, the situation is known
as a “cache miss.” Ans. 18. Moreover, the Examiner finds that Figure 5 of
Emma explicitly depicts an instance with the output of OR gate 342a
resulting in either a hit or miss result. Id.
Appeal 2010-005767
Application 11/228,163

12
We are persuaded by the Examiner. Figure 5 of Emma depicts the
output of OR gate 342a as either a “hit” or a “miss”. Moreover, it is well
known in the art that when the conditions required for a cache hit do not
occur, the result is a cache miss. We therefore find that the Examiner did
not err in finding that Emma teaches the limitation of claim 8 reciting
“determining that a cache miss occurs when each of said plurality of tag set
values is not equal to said comparison value.”

Claim 5
Issue: Whether the Examiner erred in taking Official Notice that it would
have been obvious to one having ordinary skill in the art to have modified
the system of Emma to have retrieved the desired data from the main
storage/memory upon a cache miss.

Appellant argues that the Examiner erred in taking Official Notice,
without supporting references, that it would have been obvious to one
having ordinary skill in the art to have modified the system of Emma to
have retrieved the desired data from the main storage/memory upon a cache
miss, as such a routine is very well known in the art of caching. App. Br.
20. According to Appellant, the assertions of the Official Notice are not
well-known in the art, as indicated by the prior art searched and cited by the
Examiner. Id. Consequently, Appellant contends that the Examiner’s
thorough and detailed search of the relevant prior art revealed no prior art
that taught or suggested the subject matter of the Official Notice with
regard to any of claim 5.
The Examiner answers that retrieving data stored in main memory
based on a cache miss is extremely well established in the art of caching
Appeal 2010-005767
Application 11/228,163

13
and hierarchical memories. Ans. 19. In addition, the Examiner supplies to
the record excerpts from two textbooks (John L. Hennessy and David A.
Patterson, Computer Organization and Design: The Hardware/Software
Interface, 542-43 (Morgan Kaufman Publishers, Inc., 1998); Andrew S.
Tanenbaum, Modern Operating Systems, 23-24 (Prentice Hall, 2d ed.
2001)). Id. The Examiner finds that Hennessy teaches operations of
accessing the next level of memory in the memory hierarchy, i.e. main
memory, when a cache miss occurs. Id. The Examiner finds further that
Tanenbaum discloses cache misses requiring a [main] memory access in
order to retrieve the requested data that caused a miss in the cache. Id.
We agree with the Examiner’s reasoning and adopt it as our own.
Consequently, we conclude that the Examiner did not err in finding that it
would have been obvious to a person of ordinary skill in the contemporary
art to have modified the system of Emma to have retrieved the desired data
from the main storage/memory upon a cache miss.

CONCLUSION
Appellant has not shown that the Examiner erred in rejecting claims
1-4, 6-8, 10-17, 19-21, and 23-26 as unpatentable under 35 U.S.C. § 102(b)
as being anticipated by Emma and claims 5, 9, 18, and 22 as unpatentable
under 35 U.S.C. § 103(a) as obvious over Emma.

DECISION
The Examiner’s rejection of claims 1-4, 6-8, 10-17, 19-21, and 23-26
as unpatentable under 35 U.S.C. § 102(b) as being anticipated by Emma is
affirmed.
Appeal 2010-005767
Application 11/228,163

14
The Examiner’s rejection of claims claims 5, 9, 18, and 22 as
unpatentable under 35 U.S.C. § 103(a) as obvious over Emma is affirmed.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(1). See 37 C.F.R.
§ 1.136(a)(1)(iv) (2010).

AFFIRMED

msc