DETAILED ACTION
This action is responsive to the application filed on 11/29/2024. Claims 1-26 are pending and have been examined.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed. The examiner suggests adding details of switching between lock modes in a NUMA multi-core processor.
Claim Objections
Claim 1-26 are objected to because of the following informalities:
In regards to claim 1, line 5 delete “the” before “different processes” as to correct a minor antecedent basis issue (note: this issue does not rise to the level of indefiniteness defined in 35 USC 112(b) and therefore is addressed as an objection).
In regards to claim 1, line 6 delete “the” before “different CPU cores” as to correct a minor antecedent basis issue (note: this issue does not rise to the level of indefiniteness defined in 35 USC 112(b) and therefore is addressed as an objection).
In regards to claim 1, line 17 amend “the same NUMA node” to “[[the]] a same NUMA node” as to correct a minor antecedent basis issue (note: this issue does not rise to the level of indefiniteness defined in 35 USC 112(b) and therefore is addressed as an objection).
In regards to claim 11, line 3 delete “a” before “data” to correct a grammatical issue.
In regards to claim 15, line 2 amend “the number” to “[[the]] a number” as to correct a minor antecedent basis issue (note: this issue does not rise to the level of indefiniteness defined in 35 USC 112(b) and therefore is addressed as an objection).
In regards to claim 23, line 6 delete “the” before “different processes” as to correct a minor antecedent basis issue (note: this issue does not rise to the level of indefiniteness defined in 35 USC 112(b) and therefore is addressed as an objection).
In regards to claim 23, line 7 delete “the” before “different CPU cores” as to correct a minor antecedent basis issue (note: this issue does not rise to the level of indefiniteness defined in 35 USC 112(b) and therefore is addressed as an objection).
Claims 2-22 and 24-26 are dependent upon one or more claims above and therefore are similarly objected to for including the same deficiencies of one or more claims above.
Appropriate correction is required.
Claim Interpretation/Examiner Notes
Claim 23 recites the following contingent limitations: “…in response to the competition-level indicator satisfying a first switching condition, the lock of the shared computing resource is switched from a primitive lock mode to a NUMA lock mode...”
The contingent limitation uses the language “in response to” which is contingent because they are only required to be performed if (e.g. in response to) a condition being met (e.g. switching of the modes is only required if a condition is satisfied). However, if a first switching condition is not satisfied then the mode switch does not occur and the following steps are not required to occur based on the broadest reasonable interpretation given to contingent limitations in method claims (See MPEP 2111.04(II) See Ex parte Schulhauser, Appeal 2013-007847 (PTAB April 28, 2016)).
The examiner suggests amending the claim to remove the contingent limitations stating “in response to” and positively recite each step of the method claim.
The examiner further asserts that claims 25-26 both include contingent limitations that should be removed as well stating “in response to” in claim 25 and “if” in claim 26.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1, 14, 23 and 25 is/are rejected under 35 U.S.C. 103 as being unpatentable over NPL reference “Scalable Adaptive NUMA-Aware Lock” hereby referred to as SANL, and further in view of Nussbaum, USPAT No. 7,945,912.
In regards to claim 1, SANL discloses A multi-core processor comprising: a plurality of central processing unit (CPU) cores configured to form a plurality of non-uniform memory access (NUMA) nodes (page 1754, abstract: “multi-core machines with non-uniform memory access (NUMA) (also see page 1762, section 4 “…We conduct experiments on two NUMA machines. One is a 40-core machine with four 10-core Intel Xeon E7-4850 processors, running Debian 7. The other is a 64-core machine with eight 8-core AMD Opteron 6,274 processors)) the different processes running on the different CPU cores applying for a lock of a shared computing resource are queued to be locked with the shared computing resource to gain access rights to the shared computing resource (page 1755, section 2.1: “propose MCS lock: each thread lets its lock request join a request queue and spins only on its own variable until the previous thread hands over the lock.” Page 1760: section 3.3.2: “maintains a FIFO queue Q, a standard lock-based linked list, to monitor the remote clients”. Wherein the SANL lock includes an in-place mode and a delegation mode and each mode queues running threads on different cores applying for a lock using respective queueing mechanisms of each mode; wherein the threads are queued to be locked with shared memory to gain access rights to shared memory (also see Fig. 2 on page 1757 for details of SANL lock and its in-place mode and delegation mode and page 1762, section 4 “…The critical section includes acquiring lock, changing data in shared cache lines and releasing lock”)) monitoring a competition-level indicator (page 1757: “…In Step 1, if the global contention level is below a threshold (which depends on the architecture), all threads will enter in-place mode; otherwise, they enter delegation mode…In order to determine when to switch, SANL relies on the global contention level Cg”. Wherein global contention indicator is monitored. (also see page 1758 for further details on contention level)) in response to the competition-level indicator satisfying a first switching condition, the lock of the shared computing resource is switched from a primitive lock mode to a NUMA lock mode (page 1757: “We also extend existing delegation locks with an efficient NUMA support to work with SANL… In Step 1, if the global contention level is below a threshold (which depends on the architecture), all threads will enter in-place mode; otherwise, they enter delegation mode” and page 1758: “When the global vote Cg is greater than half of the number of contending threads, threads will enter the delegation mode”. Wherein if a global contention is greater than a threshold a lock is switched from a in place lock mode to a delegation lock mode which is NUMA aware.) in the primitive lock mode, the processes follow a first-in and first-out rule to gain the lock of the shared computing resource, regardless of their NUMA nodes queued (page 1755, section 2.1: “propose MCS lock: each thread lets its lock request join a request queue and spins only on its own variable until the previous thread hands over the lock.” Page 1757: “We craft SANL to combine the benefits of in-place locks…” Wherein an in-place lock is implemented using a MCS lock which follows a FIFO order to gain access to the lock of shared memory regardless of NUMA nodes (see section 4.1 on details regarding selecting MCS lock as in-place mode lock and 4 and 4.2 on pages 1762-1764 for further details on shared cache lines of memory)) and in the NUMA lock mode, the processes on the same NUMA node with the shared computing resource gain the lock of the shared computing resource first. (page 1757: “(Step 3) or not; otherwise, when the contention on the server node is sufficiently high, SANL will enter restrictive-mode (Step 4), where local clients are allowed to send requests while remote clients wait until the server node’s contention level has come down or server re-nomination occurs (Step). A thread can be in the server’s role for only at most a limited number of times Ts, and then it will downgrade to a normal thread to finish its own task. This ensures that the thread will not be occupied for too long, and server nomination can take place fairly among all the NUMA nodes.” Wherein in a restrictive mode of the delegation lock only local threads of a same NUMA node are allowed access to the lock and threads of remote NUMA nodes must wait (see section 4 and 4.2 on pages 1762-1764 for further details on shared cache lines of memory))
SANL does not disclose wherein: by executing a lock-application instruction, the different processes running on the different CPU cores applying for a lock of a shared computing resource are queued, to be locked with the shared computing resource to gain access rights to the shared computing resource. SANL discloses queueing processes running on different CPU cores applying for a lock to gain access to a shared resource. However, SANL does not disclose executing of a lock instruction to queue the processes.
Nussbaum discloses wherein: by executing a lock-application instruction, the different processes running on the different CPUs applying for a lock of a shared computing resource are queued, to be locked with the shared computing resource to gain access rights to the shared computing resource (Column 3, lines 24-31 and Column 5, lines 5-18: wherein a compare and swap operation is executed, different threads running on different processors, applying for a lock of a shared memory are queued to be locked with the shared memory to gain access to the shared memory (See Column 2, lines 24-67 for details of threads running on different processors and accessing a lock of shared memory))
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to modify the multicore processor of SANL, which queues threads waiting to acquire a lock, to execute a lock instruction, such as a compare and swap operation to place the threads in a queue while they wait to gain access to a shared memory as taught in Nussbaum. It would have been obvious to one of ordinary skill in the art because using a compare and swap allows threads to repeatedly retry the operation (by spinning), without being suspended, thus minimizing delays and avoids the overhead of context switching when the lock is only held for short periods. In addition, the queueing in Nussbaum utilizes a minimal number of compare and swap operations in order to minimize cost and provides a fair chance for all threads to acquire a lock (Nussbaum: Column 6, lines 57-60).
Claim 23 is similarly rejected on the same basis as claim 1 above as claim 23 is the method claim corresponding to the processor of claim 1 above.
In regards to claim 14, the combination of SANL and Nussbaum discloses The multi-core processor as claimed in claim 1 (see rejection of claim 1 above) wherein: in response to the competition-level indicator satisfying a second switching condition, the lock of the shared computing resource is switched from the NUMA lock mode to the primitive lock mode. (SANL: page 1757 “Under low contention, in-place locks are more efficient, so SANL switches to the in-place mode”. Thus, when a contention level is low and global contention is less than a threshold delegated NUMA lock mode is switched to in-place mode (see section 3.1 for further details))
Claim 25 is similarly rejected on the same basis as claim 14 above as claim 25 is the method claim corresponding to the processor of claim 14 above.
Allowable Subject Matter
Claims 2-13, 15-22, 24 and 26 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
The prior art of record, alone or in combination, fail to disclose or render obvious claim 2 filed on 11/29/2024. The prior art of record has not taught either individually or in combination and together with all other claimed features “The multi-core processor as claimed in claim 1, wherein: the competition-level indicator includes information about depth data, wherein the depth data shows the number of processes that have applied for the lock and have not been unlocked yet; and in response to depth data exceeding a threshold a predetermined number of times, the lock of the shared computing resource is switched from the primitive lock mode to the NUMA lock mode” as claimed in claim 2.
The closest prior art of record, SANL discloses switching between locking modes based on a global contention level, which is derived from each thread’s local contention level and represents a ratio of time in which threads spend in a critical section. Once a global contention value is greater than a threshold the lock mode switches to a NUMA aware delegation mode. However, SANL does not disclose “…information about depth data, wherein the depth data shows the number of processes that have applied for the lock and have not been unlocked yet; and in response to depth data exceeding a threshold a predetermined number of times, the lock of the shared computing resource is switched from the primitive lock mode to the NUMA lock mode” as claimed.
Furthermore, while NPL reference “Fissile locks” discloses switching from a test-and test lock mode to a Compact NUMA aware mode, based upon arriving threads being unable to acquire the test and test lock. However, Fissile does not disclose “…information about depth data, wherein the depth data shows the number of processes that have applied for the lock and have not been unlocked yet; and in response to depth data exceeding a threshold a predetermined number of times, the lock of the shared computing resource is switched from the primitive lock mode to the NUMA lock mode” as claimed.
Thus, none of the prior art references disclose all limitations of claim 2 above, which includes all limitations of claim 1.
Furthermore, while some limitations may be broadly disclosed in the references above, the specific combination of limitations would not be obvious as claimed absent impermissible hindsight.
Claims 3-10 are dependent upon claim 2, and are thus allowable over the prior art at least based upon their respective dependencies.
The following is a statement of reasons for the indication of allowable subject matter:
The prior art of record, alone or in combination, fail to disclose or render obvious claim 11 filed on 11/29/2024. The prior art of record has not taught either individually or in combination and together with all other claimed features “The multi-core processor as claimed in claim 1, wherein: the competition-level indicator further carries an over-threshold number that shows how many times a data representing a competition level exceeds a threshold; and in response to the over-threshold number showing that the data representing the competition level exceeds a threshold a predetermined number of times, the lock of the shared computing resource is switched from the primitive lock mode to the NUMA lock mode” as claimed in claim 11.
The closest prior art of record, SANL discloses switching between locking modes based on a global contention level, which is derived from each thread’s local contention level and represents a ratio of time in which threads spend in a critical section. Once a global contention value is greater than a threshold the lock mode switches to a NUMA aware delegation mode. However, SANL does not disclose “…the competition-level indicator further carries an over-threshold number that shows how many times a data representing a competition level exceeds a threshold; and in response to the over-threshold number showing that the data representing the competition level exceeds a threshold a predetermined number of times, the lock of the shared computing resource is switched from the primitive lock mode to the NUMA lock mode” as claimed.
Furthermore, while NPL reference “Fissile locks” discloses switching from a test-and test lock mode to a Compact NUMA aware mode, based upon arriving threads being unable to acquire the test and test lock. However, Fissile does not disclose “…the competition-level indicator further carries an over-threshold number that shows how many times a data representing a competition level exceeds a threshold; and in response to the over-threshold number showing that the data representing the competition level exceeds a threshold a predetermined number of times, the lock of the shared computing resource is switched from the primitive lock mode to the NUMA lock mode” as claimed.
Thus, none of the prior art references disclose all limitations of claim 11 above, which includes all limitations of claim 1.
Furthermore, while some limitations may be broadly disclosed in the references above, the specific combination of limitations would not be obvious as claimed absent impermissible hindsight.
The following is a statement of reasons for the indication of allowable subject matter:
The prior art of record, alone or in combination, fail to disclose or render obvious claim 12 filed on 11/29/2024. The prior art of record has not taught either individually or in combination and together with all other claimed features “The multi-core processor as claimed in claim 1, wherein: after the first switching condition is satisfied, through the execution of the lock-application instruction, subsequent processes applying for the lock are not permitted to enter the queue until all processes already queued gain a primitive lock for operations in turn, and then the subsequent processes are queued to gain a NUMA lock” as claimed in claim 12.
The closest prior art of record, SANL discloses switching between locking modes using queues in each mode. However, SANL does not disclose “…wherein: after the first switching condition is satisfied, through the execution of the lock-application instruction, subsequent processes applying for the lock are not permitted to enter the queue until all processes already queued gain a primitive lock for operations in turn, and then the subsequent processes are queued to gain a NUMA lock” as claimed.
Furthermore, while NPL reference “Fissile locks” discloses switching from a test-and test lock mode to a Compact NUMA aware mode, Fissile only queues processes in a NUMA lock mode. Thus, Fissile does not disclose “…wherein: after the first switching condition is satisfied, through the execution of the lock-application instruction, subsequent processes applying for the lock are not permitted to enter the queue until all processes already queued gain a primitive lock for operations in turn, and then the subsequent processes are queued to gain a NUMA lock” as claimed.
Thus, none of the prior art references disclose all limitations of claim 12 above, which includes all limitations of claim 1.
Furthermore, while some limitations may be broadly disclosed in the references above, the specific combination of limitations would not be obvious as claimed absent impermissible hindsight.
Claim 13 is dependent upon claim 12, and are thus allowable over the prior art at least based upon their respective dependencies.
Claim 24 is similarly allowable for the same reasons as claim 12 above.
The following is a statement of reasons for the indication of allowable subject matter:
The prior art of record, alone or in combination, fail to disclose or render obvious claim 15 filed on 11/29/2024. The prior art of record has not taught either individually or in combination and together with all other claimed features “The multi-core processor as claimed in claim 14, wherein: the competition-level indicator shows the number of processes applying for locks on each NUMA node; and when a total number of processes applying for locks on each NUMA node is lower than a threshold, the second switching condition is satisfied” as claimed in claim 15.
The closest prior art of record, SANL discloses switching between locking modes based on a global contention level, which is derived from each thread’s local contention level and represents a ratio of time in which threads spend in a critical section. Once a global contention value is greater than a threshold the lock mode switches to a NUMA aware delegation mode; or alternatively if the global contention value returns to being lower than a threshold the mode switches back to an in-place mode. However, SANL does not disclose “…: the competition-level indicator shows the number of processes applying for locks on each NUMA node; and when a total number of processes applying for locks on each NUMA node is lower than a threshold, the second switching condition is satisfied” as claimed.
Furthermore, while NPL reference “Fissile locks” discloses switching from a test-and test lock mode to a Compact NUMA aware mode, based upon arriving threads being unable to acquire the test and test lock. However, Fissile does not disclose “…: the competition-level indicator shows the number of processes applying for locks on each NUMA node; and when a total number of processes applying for locks on each NUMA node is lower than a threshold, the second switching condition is satisfied” as claimed.
Thus, none of the prior art references disclose all limitations of claim 15 above, which includes all limitations of claim 1 and 14.
The following is a statement of reasons for the indication of allowable subject matter:
The prior art of record, alone or in combination, fail to disclose or render obvious claim 16 filed on 11/29/2024. The prior art of record has not taught either individually or in combination and together with all other claimed features “The multi-core processor as claimed in claim 14, wherein: a NUMA lock data structure includes lock information; and if the lock information matches unique tag information about a primitive lock mapped to a NUMA lock presented in the NUMA lock data structure, the NUMA lock is reliable; otherwise, the NUMA lock is unreliable” as claimed in claim 16.
The closest prior art of record, SANL discloses an in-place lock and a delegation lock that supports NUMA architectures. However, SANL does not disclose “… if the lock information matches unique tag information about a primitive lock mapped to a NUMA lock presented in the NUMA lock data structure, the NUMA lock is reliable; otherwise, the NUMA lock is unreliable” as claimed.
Furthermore, while NPL reference “Fissile locks” discloses a test-and test lock and a Compact NUMA aware lock. However, Fissile does not disclose if the lock information matches unique tag information about a primitive lock mapped to a NUMA lock presented in the NUMA lock data structure, the NUMA lock is reliable; otherwise, the NUMA lock is unreliable” as claimed.
Thus, none of the prior art references disclose all limitations of claim 16 above, which includes all limitations of claim 1 and 14.
Furthermore, while some limitations may be broadly disclosed in the references above, the specific combination of limitations would not be obvious as claimed absent impermissible hindsight.
Claims 17-22 are dependent upon claim 16, and are thus allowable over the prior art at least based upon their respective dependencies.
Claim 26 is similarly allowable for the same reasons as claim 16 above.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Kogan, PGPUB No. 2023/0161641 for teaching the use of compact NUMA aware locks
Dice, PGPUB No. 2022/0100587 for teaching a NUMA aware reader writer lock
McKenny, PGPUB No. 2014/0351231 for teaching low and high overhead contention-based lock mode switching between a ticket lock and a queue lock
Dice, PGPUB No. 2013/0290583 for teaching NUMA aware locks employing lock cohorting which allows lock ownership to remain resident on a single NUMA node longer than under strict FIFO ordering, thus reducing coherence traffic and improving aggregate performance
NPL reference “Fissile Locks” for teaching two underlying locks: a TS lock, which serves as a fast path, and a CNA lock, which serves as a slow path. The key feature of Fissile locks is the ability of threads on the fast path to bypass threads enqueued on the slow path, and acquire the lock with less overhead than CNA.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to COURTNEY P SPANN whose telephone number is (571)431-0692. The examiner can normally be reached M-F, 9am-6pm, EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jyoti Mehta can be reached at 571-270-3995. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/COURTNEY P SPANN/Primary Examiner, Art Unit 2183