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 .
DETAILED ACTION
Claims 1-14 are currently pending and have been examined.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 05/30/2024, 05/19/2026 has been considered. The submission is in compliance with the provisions of 37 CFR 1.97. Form PTO-1449 is signed and attached hereto.
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 of this title, 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.
Claims 1-3, 6-10, 13-14 are rejected under 35 U.S.C. 103 as being unpatentable over Stellwag et al. (U.S. Pub. No. 20110185154 A1) in view of Gong et al. (U.S. Pub. 20160132435 A1).
As per claim 1, Stellwag teaches the invention substantially as claimed including a method for providing, to one or more cores in a multicore system, fair access to a spinlock (par. 0016 a fair and efficient technique for synchronizing multiple processor cores), the method comprising:
the spinlock being acquired by the first core (par. 0005 multiple cores request the lock; [0006] the lock is allocated to exactly one of the cores; par. 0017 allocating the lock to the first core requesting it),
accessing, by the first core and not by the second core, a section of data (par. 0006 the lock is allocated to exactly one of the cores; this core may start processing by using the unlocked resource);
releasing, by the first core, the spinlock after performing one or more operations on the section of the data (par. 0008 the operating core returns the lock after end of operation).
Stellwag does not expressly disclose: setting, by a first core of the one or more cores, a spinlock variable in response to the spinlock being acquired by the first core, the setting of the spinlock variable by the first core including changing a cache state of the spinlock variable in a cache of the first core to MODIFIED based on a cache coherency protocol of the multicore system; setting, by a second core of the one or more cores, a secondary variable based on a set of cores, including the second core, waiting for the spinlock, the setting of the secondary variable by the second core including changing a cache state of the secondary variable in a cache of the second core to MODIFIED based on the cache coherency protocol, wherein the cache state of the secondary variable is set on a cache line that is separate from a cache line associated with the spinlock variable, the second core comprises the spinlock variable as INVALID in the cache of the second core, and the first core comprises the secondary variable as INVALID in the cache of the first core; updating, by the first core, the INVALID secondary variable upon releasing the spinlock, the updating of the secondary variable including performing the updating such that a number of INVALID variables that are to be updated by each of the first core and the set of cores including the second core becomes equal.
However, Gong teaches:
setting, by a first core of the one or more cores, a spinlock variable in response to the spinlock being acquired by the first core, the setting of the spinlock variable by the first core including changing a cache state of the spinlock variable in a cache of the first core to MODIFIED based on a cache coherency protocol of the multicore system (par. 0001 Generally, critical resources may be set in a processing system ... A spinlock may be set when software is designed to prevent the multiple cores from accessing the same critical resource simultaneously; par. 0025 the obtaining module 201 may write the value of the spinlock cache variable into the register and perform the determination at block 303. If the value of the spinlock cache variable is the initial value, the spinlock resource may not be occupied; par. 0026 In block 304, the value of the spinlock cache variable in the register may be updated [modified]; par. 0030 In block 306, the updated value of the spinlock cache variable in the register may be written into the cache);
setting, by a second core of the one or more cores, a secondary variable based on a set of cores, including the second core, waiting for the spinlock, the setting of the secondary variable by the second core including changing a cache state of the secondary variable in a cache of the second core to MODIFIED based on the cache coherency protocol, wherein the cache state of the secondary variable is set on a cache line that is separate from a cache line associated with the spinlock variable, the second core comprises the spinlock variable as INVALID in the cache of the second core, and the first core comprises the secondary variable as INVALID in the cache of the first core (par. 0009 images of globally-shared memory variables are stored in the memory, the L2 cache, and each L1 cache. In addition, when a core operates the spinlock, the memory variables in the L1 cache may be updated, resulting in the memory variables stored in the L1 caches of other cores to become invalid; par. 0029 The updated value of the spinlock cache variable in the register may be written into the cache to inform other cores that the spinlock resource may be occupied);
updating, by the first core, the INVALID secondary variable upon releasing the spinlock, the updating of the secondary variable including performing the updating such that a number of INVALID variables that are to be updated by each of the first core and the set of cores including the second core becomes equal (par. 0031 After the critical resources are accessed, the spinlock resource may be released so that other cores may access the spinlock resource. After the critical resources are accessed, the value of the spinlock cache variable in the register may be set as the initial value and the initial value may be written into the cache; par. 0039 the processor 402 may further include … machine readable instructions. The restoring instruction 416 may be configured to set the value of the spinlock cache variable in the register 404 as the initial value after critical resources are accessed and store the initial value in the cache 405).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the spinlock processing method of Gong with the system and method of Stellwag resulting in a system and method which provides for in response to the spinlock being acquired by a core, updating spinlock cache variable and writing into the cache to inform other core, resulting in the memory variables of the L1 caches of the other cores to be invalidated, and releasing the spinlock after the critical data is accessed by restoring spinlock to the initial value in the cache as in Gong. One of ordinary skill in the art would have been motivated to make this combination for the purpose of enhancing access efficiency of the critical resources and performance of the device (par. 0042).
As per claim 2, Gong further teaches: wherein the cache state of the spinlock variable being changed to the MODIFIED indicates that the cache line associated with the spinlock variable is only present in the cache of the first core, the cache state of the secondary variable being changed to the MODIFIED indicates that the cache line associated with the secondary variable is only present in the cache of the second core, the spinlock variable that is INVALID in the cache of the second core indicates that the cache line associated with the spinlock variable that is present in the cache of the second core is invalid, and the secondary variable that is INVALID in the cache of the first core indicates that the cache line associated with the secondary variable that is present in the cache of the first core is invalid (par. 0009 images of globally-shared memory variables are stored in the memory, the L2 cache, and each L1 cache. In addition, when a core operates the spinlock, the memory variables in the L1 cache may be updated, resulting in the memory variables stored in the L1 caches of other cores to become invalid. More specifically, that globally shared memory variables are stored in memory and multiple levels of caches, and updating a variable in a cache of a core invalidates corresponding variables in the caches of other cores).
As per claim 3, Gong further teaches: upon the releasing of the spinlock by the first core, updating, by the second core the INVALID spinlock variable in the cache of the second core in a case based on the second core waiting to acquire the spinlock (par. 0029 If the value of the spinlock cache variable is accessed by another core, the operation for obtaining the spinlock resource may have failed and block 301 may be re-performed to obtain the spinlock resource again; par. 0034 configured to update the value of the spinlock cache variable in the register 404 if the value of the spinlock cache variable is the initial value).
As per claim 6, Stellwag further teaches: wherein the setting by the first core and the setting by the second core are performed in parallel (par. 0018 The steps of allocating the lock to the first requesting core and of establishing the waiting time indications may be performed in any sequential order or may be performed in parallel to each other).
As per claim 7, Stellwag teaches the invention substantially as claimed including method for providing, to one or more cores in a multicore system, fair access to a spinlock (par. 0016 a fair and efficient technique for synchronizing multiple processor cores), the method comprising:
the spinlock being acquired by the first core (par. 0005 multiple cores request the lock; [0006] the lock is allocated to exactly one of the cores; par. 0017 allocating the lock to the first core requesting it),
accessing, by the first core and not by the second core, a section of data (par. 0006 the lock is allocated to exactly one of the cores; this core may start processing by using the unlocked resource);
releasing, by the first core, the spinlock after performing one or more operations on the section of the data (par. 0008 the operating core returns the lock after end of operation).
Stellwag does not expressly disclose: setting, by a first core of the one or more cores, a spinlock variable in response to the spinlock being acquired by the first core, the setting of the spinlock variable by the first core including changing a cache state of the spinlock variable in a cache of the first core to MODIFIED based on a cache coherency protocol of the multicore system; setting, by a second core of the one or more cores, a contention indication variable in response to the second core waiting for the spinlock, the second core comprises the spinlock variable as INVALID in a cache of the second core; upon releasing the spinlock, cleaning and invalidating, by the first core, spinlock data from the cache of the first core in response to the contention indication variable being set.
However, Gong teaches:
setting, by a first core of the one or more cores, a spinlock variable in response to the spinlock being acquired by the first core, the setting of the spinlock variable by the first core including changing a cache state of the spinlock variable in a cache of the first core to MODIFIED based on a cache coherency protocol of the multicore system (par. 0001 Generally, critical resources may be set in a processing system ... A spinlock may be set when software is designed to prevent the multiple cores from accessing the same critical resource simultaneously; par. 0025 the obtaining module 201 may write the value of the spinlock cache variable into the register and perform the determination at block 303. If the value of the spinlock cache variable is the initial value, the spinlock resource may not be occupied; par. 0026 In block 304, the value of the spinlock cache variable in the register may be updated [modified]; par. 0030 In block 306, the updated value of the spinlock cache variable in the register may be written into the cache);
setting, by a second core of the one or more cores, a contention indication variable in response to the second core waiting for the spinlock, the second core comprises the spinlock variable as INVALID in a cache of the second core (par. 0029 The updated value of the spinlock cache variable in the register may be written into the cache to inform other cores that the spinlock resource may be occupied; par. 0009, when a core operates the spinlock, the memory variables in the L1 cache may be updated, resulting in the memory variables stored in the L1 caches of other cores to become invalid)
upon releasing the spinlock, cleaning and invalidating, by the first core, spinlock data from the cache of the first core in response to the contention indication variable being set (par. 0031 After the critical resources are accessed, the spinlock resource may be released so that other cores may access the spinlock resource. After the critical resources are accessed, the value of the spinlock cache variable in the register may be set as the initial value and the initial value may be written into the cache. That is, the releasing of the spinlock necessarily involves cleaning and invalidating before setting the spinlock variable to an initial value in the register).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the spinlock processing method of Gong with the system and method of Stellwag resulting in a system and method which provides for in response to the spinlock being acquired by a core, updating spinlock cache variable and writing into the cache to inform other core, resulting in the memory variables of the L1 caches of the other cores to be invalidated, and releasing the spinlock after the critical data is accessed by restoring spinlock to the initial value in the cache as in Gong. One of ordinary skill in the art would have been motivated to make this combination for the purpose of enhancing access efficiency of the critical resources and performance of the device (par. 0042).
As per claim 8, Gong further teaches: wherein the contention indication variable is set on a same cache line as the spinlock variable, or the contention indication variable is not stored in a cache memory (par. 0007 an independent high-speed cache area may be specially designed for the spinlock … The physical cache area may be independently accessed and may be shared by all of a plurality of cores).
As per claim 9, Gong further teaches: wherein the contention indication variable indicates that a contention is present for acquiring the spinlock (par. 0027 a determination may be made as to whether the spinlock cache variable is accessed by a core after the value of the spinlock cache variable is written into the register). Further, Stellwag teaches: contention is present for acquiring the spinlock (par. 0007 the other cores continue to request the lock, i.e. they repeatedly and continuously check whether the lock is available ("spinning")).
As per claim 10, Gong further teaches: wherein the cleaning and invalidating the spinlock data includes flushing the spinlock data from the cache of the first core and writing the spinlock variable to a main memory (par. 0030 the updated value of the spinlock cache variable in the register may be written into the cache. It is noted that writing the updated value into the cache necessarily involves flushing the spinlock data).
As per claim 13, Stellwag furth teaches: wherein the setting by the first core and the setting by the second core are performed in parallel (par. 0018 The steps of allocating the lock to the first requesting core and of establishing the waiting time indications may be performed in any sequential order or may be performed in parallel to each other).
As per claim 14, it is a multicore system having similar limitations as claim 1. Thus, claim 14 is rejected for the same rationale as applied to claim 1. Stellwag further teaches: a plurality of cores including a first core and a second core (par. 0036 a multi-core system 100 comprising multiple cores C1, C2, C3),
Claims 4-5 and 11-12 are rejected under 35 U.S.C. 103 as being unpatentable over Stellwag in view of Gong, and further in view of Rajwar et al. “Transactional Lock-Free Execution of Lock-Based Programs”, further in view of Lee et al. (U.S. Pub. No. 20110252258 A1).
As per claim 4, Stellwag and Gong do not expressly disclose: upon releasing the spinlock, adding, by the first core, a delay time in resetting the secondary variable based on the second core waiting to acquire the spinlock, wherein the delay time corresponds to a delay due to power saving optimization in at least one of the second core or the set of cores including the second core
However, Rajwar teaches: upon releasing the spinlock, adding, by the first core, a delay time in resetting the secondary variable based on the second core waiting to acquire the spinlock … (page 12, right column, lines 38-43 To ensure fairness, we introduce [add] delays after a lock release operations. After releasing the lock, the processor waits a minimum random interval before proceeding to ensure another processor has an opportunity to acquire the lock before a successive local lock re-acquire, thus reducing unfairness).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the technique of introducing delays after lock releasing operations of Rajwar with the system and method of Stellwag and Gong resulting in a system and method which provides for setting a minimum delay time for a processor after performing lock release operations as in Rajwar. One of ordinary skill in the art would have been motivated to make this combination for the purpose of ensuring another processor has an opportunity to acquire the lock before a successive local lock re-acquire, thus reducing unfairness (page 12, right column, lines 41-43).
Stellwag, Gong and Rajwar do not expressly describe wherein the delay time corresponds to a delay due to power saving optimization in at least one of the second core or the set of cores including the second core.
However, Lee teaches: a delay due to power saving optimization in at least one of the second core or the set of cores including the second core (par. 0010 A core that fails to acquire the lock waits for a backoff delay and repeatedly attempts to acquire the lock until the lock is acquired; par. 0033 As a result of the competition, the second core 120 may have the exclusive access right to the shared resource by acquiring the lock variable. The first core 110 may wait a predetermined time before reattempting to acquire the lock variable, because of its failure to acquire the lock variable; par. 0034 When the first core 110 fails to acquire the lock variable, the main controller 130 may control the first core 110 to be operated in the low power sleep mode; Abstract, lines 3-5, A processor core that fails to acquire a lock variable may be switched to a low power sleep mode and a waste of power may be reduced. It is noted that when the first core fails to acquire the lock waits for a predetermined time and switches to a sleep mode to reduce waste of power [power saving]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the technique waiting for a backoff delay before reattempting to acquire a lock of Lee with the system and method of Stellwag, Gong and Rajwar resulting in a system and method which provides for setting a delay time for a processor/core upon performing a lock release so as to allow for other contending acquisition of the lock by performing backoff delay operations and reattempting acquisition of the lock. One of ordinary skill in the art would have been motivated to make this combination for the purpose improving performance (par. 0012). Further, this would have provided for ensuring other processor cores which are attempting to acquire the lock via performing backoff delay operations have opportunity to acquire the lock and thereby reduce unfairness
As per claim 5, Gong further teaches: initiating a next iteration spinlock acquisition (par. 0032 *if the t0 does not equal to zero, the spinlock resource may be obtained, the value of the lockkey may be reloaded to perform the determination and subsequent operations may be performed until the value of the lockkey is zero). Rajwar further teaches: such that a probability of at least the first and second cores acquiring the spinlock is equal due to the delay time (page 12, right column, lines 38-43 To ensure fairness, we introduce delays after a lock release operations. After releasing the lock, the processor waits a minimum random interval before proceeding to ensure another processor has an opportunity to acquire the lock before a successive local lock re-acquire, thus reducing unfairnes)
As per claim 11, Rajwar further teaches: upon releasing the spinlock, adding, by the first core, a delay time in the cleaning and the invalidating the spinlock data based on the second core waiting for the spinlock … ((page 12, right column, lines 38-43 To ensure fairness, we introduce delays after a lock release operations. After releasing the lock, the processor waits a minimum random interval before proceeding to ensure another processor has an opportunity to acquire the lock before a successive local lock re-acquire, thus reducing unfairness).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the technique of introducing delays after lock releasing operations of Rajwar with the system and method of Stellwag and Gong resulting in a system and method which provides for setting a minimum delay time for a processor after performing lock release operations as in Rajwar. One of ordinary skill in the art would have been motivated to make this combination for the purpose of ensuring another processor has an opportunity to acquire the lock before a successive local lock re-acquire, thus reducing unfairness (page 12, right column, lines 41-43).
Stellwag, Gong and Rajwar do not expressly describe wherein the delay time corresponds to a delay due to power saving optimization in at least one of the second core or the set of cores including the second core.
However, Lee teaches: a delay due to power saving optimization in at least one of the second core or the set of cores including the second core (par. 0010 A core that fails to acquire the lock waits for a backoff delay and repeatedly attempts to acquire the lock until the lock is acquired; par. 0033 As a result of the competition, the second core 120 may have the exclusive access right to the shared resource by acquiring the lock variable. The first core 110 may wait a predetermined time before reattempting to acquire the lock variable, because of its failure to acquire the lock variable; par. 0034 When the first core 110 fails to acquire the lock variable, the main controller 130 may control the first core 110 to be operated in the low power sleep mode; Abstract, lines 3-5, A processor core that fails to acquire a lock variable may be switched to a low power sleep mode and a waste of power may be reduced. It is noted that when the first core fails to acquire the lock waits for a predetermined time and switches to a sleep mode to reduce waste of power [power saving]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the technique waiting for a backoff delay before reattempting to acquire a lock of Lee with the system and method of Stellwag, Gong and Rajwar resulting in a system and method which provides for setting a delay time for a processor/core upon performing a lock release so as to allow for other contending acquisition of the lock by performing backoff delay operations and reattempting acquisition of the lock. One of ordinary skill in the art would have been motivated to make this combination for the purpose improving performance (par. 0012). Further, this would have provided for ensuring other processor cores which are attempting to acquire the lock via performing backoff delay operations have opportunity to acquire the lock and thereby reduce unfairness.
As per claim 12, Gong further teaches: performing a next iteration spinlock acquisition (par. 0032 *if the t0 does not equal to zero, the spinlock resource may be obtained, the value of the lockkey may be reloaded to perform the determination and subsequent operations may be performed until the value of the lockkey is zero). Rajwar further teaches: such that a probability of at least the first and second cores acquiring the spinlock is equal due to the delay time (page 12, right column, lines 38-43 To ensure fairness, we introduce delays after a lock release operations. After releasing the lock, the processor waits a minimum random interval before proceeding to ensure another processor has an opportunity to acquire the lock before a successive local lock re-acquire, thus reducing unfairnes).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
U.S. Pub. No. 20180373573 A1 teaches a lock manager to manage locks for shared resources.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Willy W. Huaracha whose telephone number is (571)270-5510. The examiner can normally be reached on M-F 8:30-5:00pm.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Bradley Teets can be reached on (571) 272-3338. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/WH/
Examiner, Art Unit 2195
/BRADLEY A TEETS/Supervisory Patent Examiner, Art Unit 2197
Prosecution Insights