Advanced Micro Devices, Inc.

Patent Trials and Appeals Board

Apr 1, 2021

2020000303 (P.T.A.B. Apr. 1, 2021)

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.
15/268,798 09/19/2016 John M. King AMD-160223-US-NP 1459
25310 7590 04/01/2021
Volpe Koenig
DEPT. AMD
30 SOUTH 17TH STREET -18TH FLOOR
PHILADELPHIA, PA 19103
EXAMINER
GEBRIL, MOHAMED M
ART UNIT PAPER NUMBER
2135
NOTIFICATION DATE DELIVERY MODE
04/01/2021 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):
eoffice@volpe-koenig.com
PTOL-90A (Rev. 04/07)

UNITED STATES PATENT AND TRADEMARK OFFICE

BEFORE THE PATENT TRIAL AND APPEAL BOARD

Ex parte JOHN M. KING and GREGORY W. SMAUS

Appeal 2020-000303
Application 15/268,798
Technology Center 2100

Before MAHSHID D. SAADAT, SCOTT E. BAIN, and
MICHAEL T. CYGAN, Administrative Patent Judges.

CYGAN, Administrative Patent Judge.

DECISION ON APPEAL
STATEMENT OF THE CASE
Pursuant to 35 U.S.C. § 134(a), Appellant1 appeals from the
Examiner’s decision to reject claims 1–20. Appeal Br. 7. We have
jurisdiction under 35 U.S.C. § 6(b).
We AFFIRM IN PART.

1 We use the word “Appellant” to refer to “applicant” as defined in
37 C.F.R. § 1.42. Appellant identifies the real party in interest as Advanced
Micro Devices, Inc. Appeal Br. 3.
Appeal 2020-000303
Application 15/268,798

2
CLAIMED SUBJECT MATTER
The claimed subject matter relates to handling multiple threads in
concurrent programming. Spec. ¶ 1. A semaphore is used to “guarantee that
only one thread accesses shared memory . . . that should only be performed
by a single thread at a time.” Id. In use, a thread acquires a semaphore,
performs the work, and then releases the semaphore for use by other threads.
Id. In certain situations, multiple threads may contest for the same
semaphore, such that traffic results in the process of ensuring an orderly
succession of semaphore holders. Id. In Appellant’s claimed invention, a
processing core recognizes that a load by the core in a spin-loop has
obtained a semaphore in an exclusive state, and then responds to incoming
requests for access to the semaphore with negative acknowledgements. Id.
¶ 9. Appellant distinguishes the negative acknowledgement from prior
cache traffic after one of the cores obtains the cache line in an exclusive
state, including sending the cache lines to other cores in response to the
request of the cache line. Id. ¶ 36.
Independent claim 1 is illustrative:
1. A method for handling cache coherency traffic for a
contended semaphore, the method comprising:
a first detection, comprising detecting a non-lock load to an
address associated with the contended semaphore;
a second detection, comprising detecting that a cache line
associated with the contended semaphore is evicted;
a third detection, comprising detecting a fill of the cache line in
an exclusive state; and
responsive to the first detection, the second detection, and the
third detection, entering a semaphore cache line protection
mode in which requests for access to the cache line associated
with the contended semaphore are responded to with negative
Appeal 2020-000303
Application 15/268,798

3
acknowledgments that prevent access to the cache line
associated with the contended semaphore.
Appeal Br. 19 (Claims App.). Independent claims 10 and 19 recite a
processing unit and a processor, respectively, having limitations similar to
those recited in claim 1. Id. at 20–23. Dependent claims 2–9, 11–18, and 20
each incorporate the limitations of claim 1. Id. at 19–23.

REFERENCES
Name Reference Date
Akkary et al.
(“Akkary”)
US 5,526,510 June 11, 1996
Saha et al.
(“Saha”)
US 2006/0005197 A1 Jan. 5, 2006
Gunna et al.
(“Gunna”)
US 2008/0307166 A1 Dec. 11, 2008

REJECTIONS
Claims 1–3, 6–12, and 15–20 are rejected under 35 U.S.C. § 102(a)(1)
and § 102(a)(2) as being anticipated by Saha.
Claims 4 and 13 are rejected under 35 U.S.C. § 103(a) as being
obvious over the combined teachings and suggestions of Saha and Gunna.
Claims 5 and 14 are rejected under 35 U.S.C. § 103(a) as being
obvious over the combined teachings and suggestions of Saha, Gunna, and
Akkary.

Appeal 2020-000303
Application 15/268,798

4
OPINION
A. Anticipation by Saha
1. Claim 1
Appellant argues that Saha does not disclose each and every
limitation, including performing the latter two claimed detections and,
responsive to those detections, entering a semaphore cache line protection
mode that uses negative acknowledgements to respond to requests for access
to the contended semaphore line. Appeal Br. 7. We address each limitation
in turn.
We begin with the limitation, “a first detection, comprising detecting a
non-lock load to an address associated with the contended semaphore.” The
Examiner finds this disclosed by Saha’s description of “Saha teaches where
the lock value at processing block 708 detects the non-lock load in spin-lock
for the ‘while’ loop.” Ans. 22 (citing Saha ¶¶ 7–9, 53–54; Figs. 2, 4).
Appellant does not argue against this limitation with particularity. See
Appeal Br. 8–9.
We turn to the next limitation, “a second detection, comprising
detecting that a cache line associated with the contended semaphore is
evicted.” The Examiner finds this disclosed by Saha’s description of a cycle
as an action that results in exclusive ownership of the cache line, and
“thread/processor partitionable resources 560 may ensure that execution of
instructions from each thread concludes properly and that the appropriate
state for that thread is appropriately updated,” by “using the retirement
resources and alternating between threads in a fair manner.” Final Act. 4–5
(citing Saha ¶¶ 6–9, 32, 47, 52–54, Figs. 2–4). The Examiner further finds
Appeal 2020-000303
Application 15/268,798

5
Saha to describe that the lock, i.e., the semaphore, becomes available as part
of the semaphore acquisition process. Ans. 24 (citing Saha ¶ 51).
Appellant argues, “Saha never mentions anything about detecting that
a cache line associated with a contended semaphore is evicted . . . [t]he word
‘evict’ is simply never used in Saha.” Appeal Br. 9. Appellant admits that
Saha does disclose that the lock may be obtained in an exclusive state, but
argues that Saha does not explicitly state that the cache line is later evicted.
Id. Appellant further argues, it “is by no means clear” that “something that
results in exclusive ownership of a cache line is something that results in
eviction of such cache line.” Reply Br. 7.
We are not persuaded by Appellant’s argument that Saha does not
disclose the claimed “second detection.” Appellant argues that Saha does
not explicitly use the terms “evict” or “evicted.” We note that the
Specification describes “evicted” as “an indication that the thread holding
the semaphore has just asked to write to that semaphore to release that
semaphore, indicating that that the thread has completed its critical work.”
Spec. ¶ 39. However, although Saha does not use the same terms, we agree
with the Examiner that Saha’s description of handling cache transitions from
exclusive ownership of a cache line to its availability and transfer to another
cache line, while properly concluding the execution of instructions from
each thread by using retirement resources and alternating between threads,
describes a process similar to detecting an eviction of a cache line.
We next turn to the limitation, “a third detection, comprising
detecting a fill of the cache line in an exclusive state.” The Examiner finds
this disclosed by Saha’s description of
Appeal 2020-000303
Application 15/268,798

6
the lock acquiring processor obtains the cache line of the lock
in ‘exclusive’ state, during the acquisition process, forcing it
out of all other caches. When it is done writing the lock, the
other processors attempt a read, which causes the acquiring
processor to write its modified lock value back to memory and
forward the now shared data to the other processors in a
sequence of bus transactions to correspond to the claimed
limitation.
Final Act. 13.
Appellant argues that although Saha describes the lock is obtained in
an exclusive state, Saha does not explicitly state that a cache line is filled in
an exclusive state, or any detecting of such. Appeal Br. 9. Appellant
distinguishes filling a cache line in an exclusive state as being different from
a thread or processor obtaining exclusive access to a cache line, because in
some instances the cache line would already be in the cache of that thread or
processor. Reply Br. 8. Appellant further argues that the cited sections do
not clearly state that the cache line has anything to do with a semaphore. Id.
We are not persuaded by Appellant’s argument that Saha does not
disclose the claimed “third detection.” We first note that Saha uses the term
“lock” interchangeably with “semaphore,” such that Saha’s description of a
processor obtaining the cache line of the lock in an exclusive state is a
description of the processor obtaining the cache line of the semaphore in an
exclusive state. Saha ¶ 5 (“a semaphore or lock (which refers to the data
structure often used to allow a single processor exclusive access to other
data structures)”). Thus, we are not persuaded that Saha’s cache line is
unrelated to the semaphore.
We further note that a fill of a cache line in an exclusive state is
described in the Specification through the example of multiple caches
holding a cache line, wherein one of the caches transmits the cache line to
Appeal 2020-000303
Application 15/268,798

7
the requesting core, which fills its cache with that cache line and marks the
cache line shared. Spec. ¶ 28. Because the Specification permits a “fill”
where multiple caches already hold a cache line, we are unpersuaded that
Saha is inapplicable because “in some instances” a cache line would already
be in the cache of a processor. Furthermore, Saha describes the processor’s
action as “processor obtains the cache line of the lock in ‘exclusive’ state,”
not that the processor already has a cache line and then obtains exclusive
access, as argued by Appellant. Thus, we are not persuaded by Appellant’s
allegation that Saha does not teach the claimed “third detection.”
We turn next to the limitation, “semaphore cache line protection mode
in which requests for access to the cache line associated with the contended
semaphore are responded to with negative acknowledgments that prevent
access to the cache line associated with the contended semaphore.” The
Examiner finds this limitation to be disclosed by Saha’s description of a
semaphore acquisition process in which a processor “attempts for the lock
634 [semaphore] that is not free, the CMPXCHG_SW instruction 610-612 at
the processor 604-606 is put to sleep.” Final Act. 5 (emphasis omitted). The
Examiner further characterizes this process as
when the processor 604 seeks to obtain the acquired lock 634, a
value is returned from the memory 632 which indicates the lock
634 is being used by the processor 602, and, in one
embodiment, instead of putting the processor 604 in a
continuous “while” loop until the lock 634 becomes available,
the CMPXCHG_SW instruction 610 at the processor 604 is put
to sleep.
Id. at 5–6. The Examiner finds that preventing other actions while being in
the exclusive state corresponds to the claimed protection mode. Ans. 26.
Appeal 2020-000303
Application 15/268,798

8
Appellant argues that Saha does not prevent accesses to the cache line
associated with the contended semaphore. Appeal Br. 10; Reply Br. 10.
Appellant characterizes Saha as directed to a smpexchg instruction that is
used to acquire a lock and has the ability to be put to sleep. Appeal Br. 8.
(citing Saha ¶¶ 32, 50). Appellant further characterizes Saha’s cmpxchg
instruction as being put to sleep if it is executed while the lock is not
available, and then monitored while asleep such that when the lock is
available, the instruction is woken up. Id. (citing Saha ¶¶ 34, 51, 54).
However, Appellant argues that although the lock is prevented from being
acquired by another processor, the lock is actually read to determine that the
lock is held. Id. at 10 (citing Saha ¶ 51). Appellant points to Saha’s
statement that “when a processor seeks to obtain the acquired lock, a value is
returned from the memory which indicates the lock is being used by the
processor.” Id. Appellant argues that Saha thus does not teach preventing
access to the cache line. Id. Further, Appellant argues that Saha responds to
requests for access with the requested value of the lock and not negative
acknowledgements as claimed. Id. Appellant points to its Specification in
support of its interpretation of its protection mode and negative
acknowledgements. Id. at 14 (citing Figs. 3A–3D, 5A–5B, 6; Spec. ¶¶ 20–
36, 48–51).
We are not persuaded by Appellant’s arguments because they do not
show that the Examiner erred in finding Saha to disclose the limitation at
issue under its broadest reasonable interpretation consistent with Appellant’s
Specification. Claim 1 recites, “requests for access . . . are responded to
with negative acknowledgements that prevent access to the cache line
associated with the contended semaphore.” Appellant admits that Saha’s
Appeal 2020-000303
Application 15/268,798

9
process responds to requests for access with the requested value of the lock,
which causes the cmpxchg instruction to be put to sleep. Appeal Br. 8, 10.
When asleep, the cmpxchg is prevented access to the cache line associated
with the contended semaphore, and does not make a further request for the
semaphore until after its wake-up conditions are satisfied. Saha ¶ 54.
Although Saha does not use the term “negative acknowledgement,”
Appellant has not pointed to any specific definition or evidence showing
error in the Examiner’s reliance on Saha’s response of the value of the
semaphore lock, triggering the sleep cycle of the cmpxchg instruction.
Consequently, we are not persuaded by Appellant’s argument.
We further note that the claim does not, as Appellant argues, require
that any and all access to the cache line be prevented to a cache line holding
a cache line in an exclusive state. The broadest reasonable interpretation of
the claim is understood by reference to the Specification, for which
Appellant points to, inter alia, Figures 5A and 5B as illustrating the
protection mode. Appeal Br. 14. Figure 5A shows read requests accessing
the cache line holding the semaphore in an exclusive state. Only after the
negative acknowledgement is issued, in Figure 5B, are further accesses to
the cache line holding the semaphore prevented. Similarly, Saha shows a
read request to the cache line holding the semaphore in an exclusive state,
but the cache line response of the value of the semaphore lock cause the
cmpxchg to enter a sleep mode, thus preventing the cmpxchg from further
accessing the cache line associated with the semaphore. Thus, Appellant’s
argument that Saha permits a read request to the cache line holding the
semaphore lock does not reflect the language of the claim as read in light of
the Specification, which only requires that access be prevented to the cache
Appeal 2020-000303
Application 15/268,798

10
line after the cache line initially responds. Accordingly, Appellant has not
persuasively distinguished the above-described sleep-wake mode of Saha
from the claimed “requests for access . . . are responded to with negative
acknowledgements that prevent access to the cache line associated with the
contended semaphore.”
Finally, Appellant argues in the Reply Brief that the cache line
protection mode is not “responsive to” the first, second, and third detections.
Reply Br. 11–12. Appellant argues that the Examiner maps the second and
third detection to Saha’s activity of a processor getting exclusive ownership
of a cache line; however, Appellant argues that such exclusive ownership
causes an instruction to be put to sleep in Saha, not awakened. Id. (citing to
the Examiner’s reliance on Saha ¶¶ 48–49 for the second and third
detections of claim 1).
We do not consider the merits of this argument because it was not
raised in the Appeal Brief, nor was it alleged to be responsive to any new
reliance on Saha in the Answer. Good cause for this new argument not
having been shown, we do not consider this argument. 37 C.F.R. § 41.41(b)
(stating “Any argument raised in the reply brief which was not raised in the
appeal brief, or is not responsive to an argument raised in the examiner’s
answer, including any designated new ground of rejection, will not be
considered by the Board for purposes of the present appeal, unless good
cause is shown”).
For the above-described reasons, we are not persuaded the Examiner
erred in finding claim 1 to be anticipated by Saha. Appellant provides no
separate argument for independent claims 10 and 19, or for dependent
Appeal 2020-000303
Application 15/268,798

11
claims 7–9 and 16–18. Consequently, we affirm the Examiner’s anticipation
rejection of claims 1, 7–10, and 16–19.
2. Claims 2, 11, 20
Claim 2 recites the additional limitation of “the address associated
with the contended semaphore is stored in a lock address contention table.”
Appellant argues that the Examiner maps this limitation to Saha’s “memory
order buffer,” and that the memory order buffer does not meet that limitation
because it is “a much more general structure than the lock address
contention table and is not directly concerned with locks.” Appeal Br. 16.
Appellant characterizes Saha’s memory order buffer as an entity that “keeps
track[] of outstanding loads and stores and ensures that they complete in
order.” Id.
We interpret the term “lock address contention table” in accordance
with its broadest reasonable interpretation consistent with the Specification.
In re Am. Acad. of Sci. Tech. Ctr., 367 F.3d 1359, 1364 (Fed. Cir. 2004).
Appellant does not point us to any particular definition or description in the
Specification. The Specification describes the lock address contention table
as “hold[ing] addresses corresponding to contended lock instructions.”
Spec. ¶ 9. The table also “includes a state value that indicates progress
through a series of states meant to track whether a load by the core in a spin-
loop associated with semaphore acquisition has obtained the semaphore in
an exclusive state.” Id.
The Examiner maps the lock address contention table to the memory
order buffer; specifically, to the monitor location information register 512
within the buffer. Final Act. 7, 14–15. The Examiner characterizes the
memory order buffer as tracking the “reasons [that] loads did not complete
Appeal 2020-000303
Application 15/268,798

12
and wakes them up after the condition that prevented completion has been
handled.” Id. The Examiner characterizes the monitor location information
register as containing “details specifying the type of cycle and/or the address
which may trigger the resumption or awakening of the instruction.” Id. The
Examiner further finds that the described “cycle” may be a “write cycle, . . .
a read for ownership (e.g., [an] action that results in exclusive ownership of
the cache line), or an invalidating cycle by another agent attempting to take
exclusive ownership of a cacheable line.” Id.
We are not persuaded that Saha’s memory order buffer containing a
monitor location information register, as explained by the Examiner and
described in Saha, does not disclose the claimed lock address contention
table. Saha’s register, like the claimed table, contains addresses
corresponding to contended lock instructions; i.e., those instructions put to
sleep until the lock is free. Final Act. 7. Saha’s buffer, like the claimed
table, keeps track of outstanding loads and reasons why loads did not
complete. Id. Appellant has not persuaded us of error in the Examiner’s
finding that these features of Saha disclose the claimed lock address
contention table storing the address associated with the contended
semaphore. Accordingly, we are not persuaded of error in the Examiner’s
rejection of claim 2, and affirm the Examiner’s anticipation rejection of
claim 2. Because claims 11 and 20 have similar scope, and are not argued
separately from claim 2, we also affirm the Examiner’s rejection of claims
11 and 20.
3. Claims 3, 12
Claim 3 depends from claim 2, and additionally recites
Appeal 2020-000303
Application 15/268,798

13
responsive to the first detection, associating a first state value
with the address in the lock address contention table;
responsive to the second detection, associating a second state
value with the address in the lock address contention table; and
responsive to the third detection, associating a third state value
with the address in the lock address contention table.
Appellant argues that these limitations of claim 3 are mapped to
features of the cmpschg_sw mechanism, but that nothing in Saha describes
any state values, let alone as being stored in a lock address contention table.
Appeal Br. 16–17. Appellant argues that the smpxchg_sw instruction
operates by sleeping the instruction until being notified that the lock is
available. Id.
The Examiner finds that the acquiring processor may need to reset the
lock so that another processor can gain control to access the shared memory
space. Final Act. 8. The Examiner finds that how the system releases
control may be a design choice as dictated by the system architecture. Id.
The Examiner further cites to the monitor location information register for
containing details specifying the type of cycle and/or the address that may
trigger the awakening of the instruction.
We are persuaded of error in the Examiner’s rejection of claim 3. The
Examiner’s citation to the monitor location information register, while
describing the subject matter of claim 3, does not explain how state values
responsive to each of the three claimed detections are associated with the
address in the register. Nor can we agree with the Examiner’s conclusory
statement that it would be a mere design choice as to how the system
releases control is unavailing. An Examiner may not rely solely on common
knowledge, common sense, or the level of skill in the art as a “wholesale
substitute for reasoned analysis and evidentiary support.” In re Nuvasive
Appeal 2020-000303
Application 15/268,798

14
Inc., 842 F.3d 1376, 1383 (Fed. Cir. 2016). Here, the Examiner does not
explain how the claimed first, second, and third values would be associated
with the address in the monitor location information register in a manner that
is responsive to their respective detections. Consequently, we reverse the
Examiner’s rejection of claim 3. Because claim 12 is rejected under the
identical erroneous ground, we also reverse the Examiner’s rejection of
claim 12.
4. Claims 6, 15
Claim 6 depends from claim 1, and recites the additional limitation of
“wherein entering the semaphore cache line protection mode comprises
entering the semaphore cache line protection mode for a first number of
cycles, and, after the first number of cycles, leaving the semaphore cache
line protection mode.”
Appellant argues that the Examiner maps the additional limitations of
claim 6 to Saha’s disclosure at paragraphs 6 and 15. Appeal Br. 17.
Appellant argues that Saha describes a cmpxchg_sw instruction that is
waiting to get access to the cache line itself, and that such a wait is not a
mode in which the processor nacks, i.e., responds with negative
acknowledgments to, incoming requests for access to the cache line, because
the processor itself does not have access to the cache line. Id.
The Examiner finds Saha’s monitor location information register to
have a timeout counter that triggers the resumption or awakening of the
cmpxchg_sw instruction. Final Act. 8. As discussed, supra, the Examiner
has found the sleep mode of the cmpxchg_sw instruction to correspond to
the claimed semaphore cache line protection mode.
Appeal 2020-000303
Application 15/268,798

15
To the extent that Appellant’s arguments against the rejection of claim
6 rely on Appellant’s arguments against the rejection of claim 1, in that the
cmpxchg_sw instruction does not correspond to the claimed semaphore
cache line protection mode in which requests for access to the cache line
associated with the contended semaphore are responded to with negative
acknowledgments, we are not persuaded by such argument for the same
reasons as discussed with respect to the rejection of claim 1. Because
Appellant does not otherwise explain why Saha’s timeout counter
controlling the sleep period of the cmpxchg_sw instruction does not describe
the additional limitation of claim 6, we are not persuaded. Consequently, we
affirm the Examiner’s rejection of claim 6. Because claim 15 contains
similar limitations and is not argued separately, we also affirm the
Examiner’s rejection of claim 15.

B. Obviousness
Appellant does not separately argue claims 4 and 13, rejected over the
combination of Saha and Gunna, or claims 5 and 14, rejected over the
combination of Saha, Gunna, and Akkary, for any reason apart from that
presented with respect to the rejection of claim 1. For the reasons expressed
above with respect to claim 1, we sustain the Examiner’s obviousness
rejections of claims 4, 5, 13, and 14.

CONCLUSION
For the above-described reasons, we affirm the Examiner’s
anticipation rejections of claims 1, 2, 6–11, and 15–20, reverse the
Examiner’s anticipation rejection of claims 3 and 12, and affirm the
Appeal 2020-000303
Application 15/268,798

16
Examiner’s obviousness rejections of claims 4, 5, 13, and 14 as being
obvious over the applied references under 35 U.S.C. § 103(a), as detailed
below.
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).
DECISION SUMMARY
In summary:
Claims
Rejected
35 U.S.C. § Reference(s)/Basis Affirmed Reversed
1–3, 6–
12, 15–20
102(a)(1),
102(a)(2)
Saha 1, 2, 6–11,
15–20
3, 12
4, 13 103 Saha, Gunna 4, 13
5, 14 103 Saha, Gunna, Akkary 5, 14
Overall
Outcome
1, 2, 4–11,
13–20
3, 12

AFFIRMED IN PART