Advanced Micro Devices, Inc.Download PDFPatent Trials and Appeals BoardApr 1, 20212020000303 (P.T.A.B. Apr. 1, 2021) Copy Citation 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 Copy with citationCopy as parenthetical citation