DETAILED ACTION
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 .
Priority
Applicant’s claim for the benefit of a prior-filed application under 35 U.S.C. 119(e) or under 35 U.S.C. 120, 121, 365(c), or 386(c) is acknowledged.
Specification
The lengthy specification has not been checked to the extent necessary to determine the presence of all possible minor errors. Applicant’s cooperation is requested in correcting any errors of which applicant may become aware in the 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.
Claim Objections
Claims 4, 8-14, and 16 are objected to because of the following informalities:
Claim 4, last line: The wording of the last line is unclear and should be improved. Examiner recommends the following: “until completion of the exchange, and wherein the circuitry is further configured to clear the stored indication after completion of the exchange”.
Claim 8, line 4: The “and” at the end is not necessary and should be removed.
Claim 11, last line: The wording of the last line is unclear and should be improved. Examiner recommends the following: “until completion of the exchange, and wherein the circuitry is further configured to clear the stored indication after completion of the exchange”.
Claim 16: The limitation “a register file of one of the plurality of processing circuits” lacks basis and should instead read as “a register file of the processing circuit”
Claims 9-14 are objected to for inheriting the objection of claim 8.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 4-7, 10-14, and 19-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 4 recites the limitation "the indication" in line 3. There is insufficient antecedent basis for this limitation in the claim. It’s unclear if the limitation is referring to the “indication” in claim 4, line 2, or referring to one of the “indications” in claim 1, line 6. For the sake of examination, Examiner will interpret this limitation to be referring to the “indication” in claim 4, line 2.
Claim 11 is rejected for the same reasons as claim 4.
Claim 5 recites the limitation "the next instruction" in line 3. There is insufficient antecedent basis for this limitation in the claim. There was no prior recitation of “a next instruction” within the claim or the claim it depends on. For the sake of examination, Examiner will interpret this limitation to be “a next instruction”.
Claims 12 and 19 are rejected for the same reasons as claim 5.
Claims 6-7, 13-14, and 20 are rejected for inheriting the rejection of claims 5, 12, and 19, respectively.
Claim 10 recites the limitation "the circuitry" in line 1. There is insufficient antecedent basis for this limitation in the claim. It’s unclear if the limitation refers to “circuitry” in claim 8, line 2, or “circuitry” in claim 8, line 6. For the sake of examination, Examiner will interpret this limitation to be referring to “circuitry” in claim 8, line 6.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1, 3, 8, 10, 15, and 17 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Rogers et al. (US 20140149710 A1).
Regarding claim 1, Rogers teaches an apparatus (Fig. 1 and [0023]: Accelerated Processing Device (APD) 104 as the apparatus) comprising:
a plurality of processing circuits (Fig. 1 and [0023, 0025]: The APD consists of SIMD arrays. SIMD arrays as the plurality of vector processing circuits), each comprising a plurality of lanes for executing instructions of a plurality of waves (Fig. 1 and [0023]: Each SIMD array consists of 16 lanes and are capable of executing a single instruction across the 16 lanes, where each lane processes a work item. Each work item within the SIMD array make up a subset of the work items, which is considered a wavefront (i.e., a wave). Therefore, each SIMD array executes instructions of a wavefront, which makes up a plurality of wavefronts); and
circuitry configured to:
responsive to a first lane executing a wave reordering instruction (Figs. 3 and 4 and [0053, 0055]: A conditional statement is executed by the SIMD array, where each lane processes the conditional instruction. The conditional instruction may initiate wave reordering; therefore any conditional statement is a wave reordering instruction. The APD to contain the circuitry to perform the conditional statements which may initiate wave reordering): generate indications of a path of execution for at least a subset of the plurality of lanes (The indications of a path of execution would be whether the lane takes or does not take the if-branch of a conditional statement); and
responsive to a number of lanes that have a same path of execution exceeding a threshold (Fig. 4 and [0055]: “the criteria may include a threshold value of threads active in the wavefront (i.e., only reform the wavefront if more than X work items are diverging”; in other words, when the wavefront is significantly diverged because more lanes took a first branch more over a second branch and the number of lanes that took the first branch reach a certain threshold), exchange active state information between one or more pairs of lanes from at least two waves of the plurality of waves (Figs. 2 and 4, [0048, 0056-0057]: Conditional statement operation results are stored in memory 210. Then, state pointers are sorted before packed into newer wavefronts. Given that each lane corresponds to a state pointer, it must be that at least one lane from the initiating wave that does (or does not) take the conditional statement will exchange the state pointer of a lane from a different wave that does not (or does) take the conditional statement. The register states and the state pointers as the active state information for the plurality of lanes), wherein the one or more pairs are identified prior to the exchange (Figs. 2-4, [0048, 0051-0052]: The processor would have identified the exchanging pairs prior to the exchange by storing their state pointers in the state pointer stack in their respective wave as they’re being allocated).
Regarding claim 3, Rogers teaches the apparatus as recited in claim 1, wherein the circuitry is configured to exchange the active state information using a data structure that stores, for each of the one or more pairs, identifiers for each pair of the one or more pairs (Figs. 2 and 4 [0046, 0057]: The state pointer stack stores state pointers for each lane of each wave, including each pair that gets exchanged between waves. The state pointer stack as the data structure and state pointers as the identifiers of each lane of one or more pairs identified).
Regarding claims 8 and 10, the claims recite a method similar to the apparatus of claims 1 and 3. Therefore the claims are rejected on the same premises.
Regarding claims 15, the claim is mostly rejected for the same reasons as claim 1. Rogers also teaches a computing system (Fig. 1 and [0018]: Computing system 100) comprising: a processing circuit (Fig. 1 and [0018]: Accelerated processing device 104).
Regarding claim 17, Rogers teaches the computing system as recited in claim 15, wherein the circuitry is configured to exchange the active state information within a data structure (Figs. 2 and 4 [0046, 0057]: The state pointers are exchanged and moved around within workgroup memory 210. Workgroup memory as the data structure).
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) 2, 9, and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Rogers et al. (US 20140149710 A1) in view of Hong et al. (US 20210264560 A1).
Regarding claim 2, Rogers teaches the apparatus as recited in claim 1, wherein the circuitry is configured to exchange the active state information within a workgroup memory of one of the plurality of processing circuits (Figs. 2 and 4 [0023, 0046, 0057]: The state pointers are exchanged and moved around within workgroup memory 210. Workgroup memory 210 is memory accessibly by all lanes of the SIMD array) without storing the exchanged active state information to a shared memory or local data store memory (Fig. 2 and [0046]: Workgroup memory may be any other memory as long as it comprises of the state pointer stack 230 and register states 220. Therefore, the workgroup memory is not segmented into multiple parts such that it can be stored into shared memory or local data store memory).
Rogers does not teach that the active state information is exchanged within a register file.
Hong teaches to store state information within a register file ([0051]: State information associated to each thread may be maintained in a local register file, which isn’t a shared memory or local data store memory).
It would have been obvious to one of ordinary skill in the art before the effective filing date to have combined the teachings of Rogers with the teachings of Hong to have stored the active state information in a register file. One of ordinary skill may appreciate storing the state information within a register file as register files are much more specialized compared to regular memory such as cache memory, making it easier to reference the data located within the register file. Additionally, a register file is faster to access than memory, therefore one of ordinary skill would be inclined to choose a register file over other types of memory.
Regarding claim 9, the claim recites a method similar to the apparatus of claim 2. Therefore, the claim is rejected on the same premises.
Regarding claim 16, Rogers teaches the computing system as recited in claim 15, wherein the circuitry is configured to exchange the active state information within a workgroup memory of one of the plurality of processing circuits (Figs. 2 and 4 [0023, 0046, 0057]: The state pointers are exchanged and moved around within workgroup memory 210. Workgroup memory 210 is memory accessibly by all lanes of the SIMD array).
Rogers does not teach that the active state information is exchanged within a register file.
Note that Rogers did indicate that the workgroup memory can be any other memory that all lanes of a workgroup can access (see [0046]).
Hong teaches to store state information within a register file ([0051]: State information associated to each thread may be maintained in a local register file).
It would have been obvious to one of ordinary skill in the art before the effective filing date to have combined the teachings of Rogers with the teachings of Hong to have stored the active state information in a register file. One of ordinary skill may appreciate storing the state information within a register file as register files are much more specialized compared to regular memory such as cache memory, making it easier to reference the data located within the register file. Additionally, a register file is faster to access than memory, therefore one of ordinary skill would be inclined to choose a register file over other types of memory.
Claims 4 and 11 are rejected under 35 U.S.C. 103 as being unpatentable over Rogers et al. (US 20140149710 A1) in view of Mandler (WO 2005086004 A2) and Melvin et al. (US 7257814 B1).
Regarding claim 4, Rogers teaches the apparatus as recited in claim 1. Rogers does not teach that the circuitry is configured to store an indication with the active state information that specifies no eviction until completion of the exchange and clear the indication thereafter.
Note that Rogers did indicate that the workgroup memory can be a cache, which stores the state register information and state pointers (see Fig. 2 and [0046]).
Mandler teaches to store an indication with the cache way or group of ways that specifies no eviction of the data (Page 4, lines 3-7: A lock bit is used to prevent replacing (i.e., evicting) the data within the cache)
It would have been obvious to one of ordinary skill in the art before the effective filing date to have combined the teachings of Rogers with the teachings of Mandler to have provided an indicator to prevent state register data from being evicted. One of ordinary skill would have realized that keeping state data within a cache may be problematic if the cache were to eject the state register data, causing a major fault in the system. Therefore, it would be pertinent to implement a system in place to avoid a pre-mature eviction, such as implementing a bit on the cache memory to indicate that the data stored in the cache line should not be evicted for as long as the bit is set.
Rogers, in view of Mandler, does not teach to store an indication with the active state information that specifies no eviction until completion of the exchange and clear the indication thereafter.
Melvin teaches to clear a lock bit after completion of an operation (Col 4. Lines 33-53: After performing an atomic sequence (i.e., the operation), a lock bit of the address associated with the operation is cleared).
It would have been obvious to one of ordinary skill in the art before the effective filing date to have combined the teachings of Rogers, in view of Mandler, with the teachings and techniques of Melvin to have cleared the lock bit after the completion of the exchange of active state information. One of ordinary skill would recognize that by clearing the lock bit associated to the active state information after completing the exchange, new data can be cached.
Regarding claim 11, the claim recites a method similar to the apparatus of claim 4. Therefore, the claim is rejected on the same premises.
Claim(s) 5-6, 12-13, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Rogers et al. (US 20140149710 A1) in view of Koneru et al. (US 20170365237 A1).
Wikipedia “Program Counter” (see Non-Final Office Action mailed December 5, 2025) is cited as extrinsic evidence to explain what the program counter indicates.
Regarding claim 5, Rogers teaches the apparatus as recited in claim 1, wherein the circuitry is configured to generate, as the indications of the path of execution, a plurality of keys ([0057]: State pointers are sorted depending on if the state registers correlating to the lanes that took the conditional statement or not. This must mean that an indicator must exist to indicate the branch direction (i.e., the path of execution) of the lane and to be able to group the work items of the lanes into different wavefronts. The indicator as the key for each lane, therefore a plurality of keys exist).
Rogers does not that each key comprising at least a subset of an instruction pointer indicating the next instruction to execute.
Koneru teaches that the instruction pointer indicates a path of execution ([0112]: When a thread diverges from an execution code path, the instruction pointer of the thread is set to where it needs to point, which would indicate a new path of execution. The instruction pointer points to the next instruction to be executed (see Wikipedia, “Program counter”, second paragraph)).
It would have been obvious to one of ordinary skill in the art before the effective filing date to have combined the teachings of Rogers with the teachings of Koneru to have the indicator be an instruction pointer. One of ordinary skill may want to use the instruction pointer (IP) to indicate which lane will be executing which instruction as the IP gives the clearest direction in which the lane working on the work item may be working towards. A generic indicator would be confusing to use if multiple lanes diverge in more than two directions (ex., back-to-back conditional statements) without the IP, which would result in ineffective reordering of the work items.
Regarding claim 6, Rogers, in view of Koneru, teaches the apparatus as recited in claim 5, wherein the circuitry is configured to compare keys of the plurality of keys corresponding to lanes of the plurality of lanes that have executed the wave reordering instructions (Rogers, [0057]: The work items of each lane are compared depending on if they take the conditional statement or do not take the conditional statement and are grouped into a wavefront. The comparisons would be done for the plurality of lanes that execute the conditional statement. Given the current embodiment, the instruction pointer would be used to compare the work item of each lane with one another and group them as stated previously. Therefore, the current embodiment would compare keys of the plurality of keys corresponding to lanes of the plurality of lanes that have executed the wave reordering instruction).
Regarding claims 12-13, the claims recite a method similar to the apparatus of claims 5-6. Therefore, the claims are rejected on the same premises.
Regarding claim 19, the claim recites a computing system similar to the apparatus of claim 5. Therefore, the claim is rejected on the same premises.
Claims 7, 14, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Rogers et al. (US 20140149710 A1) in view of Koneru et al. (US 20170365237 A1) and NVIDIA (“Shader Execution Reordering Whitepaper”).
Regarding claim 7, Rogers, in view of Koneru, teaches the apparatus as recited in claim 5, wherein to exchange the active state information between the one or more pairs of lanes (see claim 6 rejection).
Rogers, in view of Koneru, does not teach that the circuitry is configured to exchange active state information of each lane of an emitting wave with a key of the plurality of keys that does not match a first key of the first lane and active state information of each lane of a contributing wave with a key of the plurality of keys that matches the first key.
NVIDIA teaches a function to exchange active state information of an emitting wave with a key of the plurality of keys that does not match a first key of the first lane and active state information of each lane of a contributing wave with a key of the plurality of keys that matches the first key (Section “API overview”, subsection “ReorderThread”: When a thread calls the ReorderThread function, a key is provided to the function to search for threads that have the same key. When the function returns, it’s assumed that the warp where the thread first called the function is more coherent (i.e., more threads have the same key). For the warp to be more coherent, it must have swapped threads that don’t have the same key as the calling thread with other warp(s). Each thread are associated with state information and are processed through a lane within a streaming multiprocessor. The warp with the calling thread as the emitting wave. The key provided to the function by the calling thread as the first key, where each thread in general carry a key. The other warp(s) that contribute to the warp with the calling thread as the contributing warp(s)).
It would have been obvious to one of ordinary skill in the art before the effective filing date to have combined the teachings of Rogers, in view of Koneru, with the teachings of NVIDIA to have the circuitry exchange active state information of each lane of an emitting wave with a key of the plurality of keys that does not match a first key of the first lane and active state information of each lane of a contributing wave with a key of the plurality of keys that matches the first key. One of ordinary skill would appreciate re-using the wavefront from the initiating thread as it would save resources compared to creating/initiating new wavefronts for the work items that do/don’t take the conditional statement.
Regarding claim 14, the claim recites a method similar to the apparatus of claim 7. Therefore, the claim is rejected on the same premises.
Regarding claim 20, the claim recites a computing system similar to the apparatus of claim 7. Therefore, the claim is rejected on the same premises.
Claim 18 is rejected under 35 U.S.C. 103 as being unpatentable over Rogers et al. (US 20140149710 A1) in view of Mandler (WO 2005086004 A2).
Regarding claim 18, Rogers teaches the computing system as recited in claim 17.
Rogers does not teach that the circuitry is configured to store an indication with the active state information that specifies no eviction of the active state information.
Note that Rogers did indicate that the workgroup memory can be a cache, which stores the state register information and state pointers (see Fig. 2 and [0046]).
Mandler teaches to store an indication with the cache way or group of ways that specifies no eviction of the data (Page 4, lines 3-7: A lock bit is used to prevent replacing (i.e., evicting) the data within the cache)
It would have been obvious to one of ordinary skill in the art before the effective filing date to have combined the teachings of Rogers with the teachings of Mandler to have provided an indicator to prevent state register data from being evicted. One of ordinary skill would have realized that keeping state data within a cache may be problematic if the cache were to eject the state register data, causing a major fault in the system. Therefore, it would be pertinent to implement a system in place to avoid a pre-mature eviction, such as implementing a bit on the cache memory to indicate that the data stored in the cache line should not be evicted for as long as the bit is set.
Response to Arguments/Amendments
Applicant's arguments, filed March 5, 2026, with respect to the 102 rejection of claim 1 have been fully considered but they are not persuasive.
Regarding arguments on page 7, paragraph 2, Applicant argues that Rogers does not recite “wherein the one or more pairs are identified prior to the exchange”.
Examiner respectfully disagrees with this argument. Rogers does “identify” the lanes corresponding to the pair at the beginning of startup when the processor begins organizing each lane’s state pointers into waves as seen in Figs. 2-3 of Rogers, in which multiple lanes are “identified” and organized into their respective wave prior to an exchange occurring. See 102 mapping above. Therefore, Applicant’s arguments regarding that Rogers does not teach the specific limitation is considered not persuasive.
Applicant's arguments, filed March 5, 2026, with respect to the 103 rejection of claim 2 have been fully considered but they are not persuasive.
Regarding arguments on page 7, paragraph 4 to page 8, paragraph 1, Applicant argues that combination of Rogers and Hong does not teach to not store exchanged active state information to shared/LDS memory.
Examiner respectfully disagrees with this argument. Rogers indicates that the workgroup memory can be “a portion of the LDS memory 123, a cache memory, the memory 130, or any other memory that all lanes of a workgroup can access” (see [0046]), which does not indicate that the memory is “split” into multiple memories or that there is multiple workgroup memories. Furthermore, Fig. 2 shows that workgroup memory 210 is a “complete” segment of the active state information. Hence, the active state information needs to be stored in its entirety, whether it’s to be stored in LDS memory, cache memory, or any other memory (in which Examiner selects this option as part of the 103 rejection). See 103 mapping above. Therefore, Applicant’s arguments regarding that Rogers, in view of Hong, does not teach the specific limitation is considered not persuasive.
Applicant's arguments, filed March 5, 2026, with respect to the 102 rejection of claim 3 have been fully considered but they are not persuasive.
Regarding arguments on page 8, paragraph 3, Applicant argues that Rogers does not recite “data structure that stores… identifiers for each pair”.
Examiner respectfully disagrees with this argument. Rogers uses a stack, i.e., a data structure, to store state pointers, which is an identifier of each lane. Note that prior art must at least meet the broadest reasonable interpretation of the claim limitations. For example, Examiner may point to a “generic” data structure or to a specific data structure, such as a stack data structure (in which Examiner has mapped above), to satisfy the limitation “data structure”. See 102 mapping above. Therefore, Applicant’s arguments regarding that Rogers does not teach the specific limitation is considered not persuasive.
Applicant’s arguments, see page 8, paragraph 4, filed March 5, 2025, with respect to the rejection(s) of claim(s) 4 under 35 U.S.C. 103 have been fully considered and are persuasive. Therefore, the rejection has been withdrawn. However, upon further consideration, a new ground(s) of rejection is made in view of newly found prior art. See 103 rejection above.
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to EMILIO ALCANTARA-RAMOS whose telephone number is (571)272-4211. The examiner can normally be reached Mon-Fri 8:30-5:00 PST.
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.
/E.A./Examiner, Art Unit 2183
Prosecution Insights