DETAILED ACTION
Claims 1-20 are pending.
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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 04/24/2024 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
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.
Claims 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over Beckmann et al. (US 2022/0206876 A1).
Regarding claim 1, Beckmann teaches a method comprising:
determining, by a graphics processing unit (GPU) processor, an upper threshold number of concurrent program instances and a lower threshold number of concurrent program instances for the GPU processor based on a number of allocations for program variables, a total number of registers of the GPU, and a total number of memory locations of the GPU ([0026] In one implementation, the control unit manages the dynamic scheduling and descheduling of wavefronts based on resource availability of the processing unit (e.g., GPU). Wherein the Control Unit 240 is shown as part of the GPU; [0031] In one implementation, dynamic register allocation involves sharing registers between the workgroups executing on the same compute unit. In another implementation, dynamic register allocation register involves allocating a fixed pool of registers to each wavefront and allowing unique frames (i.e., function calls) to dynamically manage that pool. However, the register demand of each frame can leave the physical register file underutilized and excessive spilling to memory can lead to performance degradation. As used herein, the term “spill” is defined as storing one or more register values of locations in the physical register file to memory so as to make those physical register file locations available for storing values for other variables. [0075] Turning now to FIG. 14, one implementation of a method 1300 for dynamically adjusting wavefronts executing per epoch based on an amount of register threshing is shown. A control unit (e.g., control unit 310 of FIG. 3) allows a first number of wavefronts to execute on a plurality of compute units (e.g., compute units 255A-N of FIG. 2) during a first interval (block 1405). The duration of the interval can vary according to the implementation. The control unit monitors thrashing of a physical register file during the first interval (block 1410). In one implementation, the control unit maintains a spill counter which is incremented each time a frame of registers is spilled to memory. In other implementations, the control unit uses other techniques for monitoring register thrashing. If the thrashing of the physical register file exceeds a first threshold (conditional block 1415, “yes” leg), then the control unit allows a second number of wavefronts to execute on the plurality of compute units during a second interval, with the second number being less than the first number (block 1420). It is assumed for the purposes of this discussion that the second interval is subsequent to the first interval; upper threshold;[0076] If the thrashing of the physical register file is less than a second threshold (conditional block 1425, “yes” leg), then the control unit allows a third number of wavefronts to execute on the plurality of compute units during the second interval, with the third number being greater than the first number (block 1430). It is assumed for the purposes of this discussion that the second threshold is less than the first threshold… It is noted that method 1400 can be repeated in subsequent intervals to adjust the number of wavefronts that are allowed to execute concurrently on the compute units.; lower threshold));
determining, by the GPU processor, a number of concurrent program instances for the GPU processor between the upper threshold number and the lower threshold number, inclusive, that completes allocations for the program variables with corresponding registers and memory locations for a program instance ([0076] Otherwise, if the thrashing of the physical register file is in between the first and second thresholds (conditional block 1425, “no” leg), then the control unit allows the first number of wavefronts to execute on the plurality of compute units during the second interval (block 1435).)
While Beckmann does not explicitly teach determining, by the GPU processor, a number of concurrent program instances for the GPU processor between the upper threshold number and the lower threshold number that completes allocations for the program variables with corresponding registers and memory locations for a program instance.
Beckmann does teach running a number of wavefronts that are not above the upper threshold or below the lower threshold, while the wavefronts are executing in this range the thrashing number is acceptable meaning that the allocation for program variables with its registers and memory locations used for spilling are optimized for the number of wavefronts executing. See at least [0026-27], [0031], and [0075-76]. Therefore, one of ordinary skill in the art would have understood Beckmann teachings to encompass the claimed limitation as both Beckmann and the claimed limitation are directed to the same technical solution of dynamically finding the optimal amount of wavefronts. For example, Beckmann teaches in [0026] “the control unit manages the dynamic scheduling and descheduling of wavefronts based on resource availability of the processing unit (e.g., GPU). In one implementation, the goal of the control unit is to maximize the performance and/or throughput of the processing unit performing meaningful work while ensuring forward progress is maintained. If the control unit schedules too many wavefronts on the compute units, the wavefronts will be competing for resources and may not make sufficient forward progress. For example, if wavefronts are spilling registers to memory and then having to restore registers from memory, this writing and reading data back and forth from memory does not translate to making forward progress in the execution of a workload. Also, in some cases, if a newer wavefront is brought onto the processing unit to execute while an older wavefront is descheduled, the newer wavefront could eventually be stalled waiting for a result from the older wavefront. This could result in a deadlock where the newer wavefront stalls and prevents the older wavefront from being brought back to execute on the processing unit.”
Regarding claim 2, Beckmann teaches wherein determining the upper threshold number and the lower threshold number comprises:
performing register allocation with unlimited registers to determine the number of allocations for program variables ([0027] In one implementation, in order to prevent excessive thrashing while still ensuring the processing unit's resources are being fully utilized, the control unit tracks the number of wavefront registers that are spilled per epoch. If the number of wavefront registers spilled per epoch exceeds a threshold, then the control unit reduces the number of wavefronts that are allowed to be scheduled and dispatched in the next epoch. This allows the control unit to determine the optimal rate at which wavefronts should be scheduled to take advantage of the available resources while avoiding excessive resource contention. Training may be conducted over a series of epochs in which for each epoch the totality or a subset of the training data set is repeated, often in random order of presentation, and the process of repeated training epochs is continued until the accuracy of the network reaches a satisfactory level. As used herein, an “epoch” refers to a period of time (e.g., a number clock cycles, transactions, etc.).), determining the upper threshold number based, at least in part, on the number of allocations for program variables, the total number of registers, and the total number of memory locations ([0075] Turning now to FIG. 14, one implementation of a method 1300 for dynamically adjusting wavefronts executing per epoch based on an amount of register threshing is shown. A control unit (e.g., control unit 310 of FIG. 3) allows a first number of wavefronts to execute on a plurality of compute units (e.g., compute units 255A-N of FIG. 2) during a first interval (block 1405). The duration of the interval can vary according to the implementation. The control unit monitors thrashing of a physical register file during the first interval (block 1410). In one implementation, the control unit maintains a spill counter which is incremented each time a frame of registers is spilled to memory. In other implementations, the control unit uses other techniques for monitoring register thrashing. If the thrashing of the physical register file exceeds a first threshold (conditional block 1415, “yes” leg), then the control unit allows a second number of wavefronts to execute on the plurality of compute units during a second interval, with the second number being less than the first number (block 1420). It is assumed for the purposes of this discussion that the second interval is subsequent to the first interval.), and determining the lower threshold number based, at least in part, on the number of allocations for program variables and the total number of registers ([0076] If the thrashing of the physical register file is less than a second threshold (conditional block 1425, “yes” leg), then the control unit allows a third number of wavefronts to execute on the plurality of compute units during the second interval, with the third number being greater than the first number (block 1430). It is assumed for the purposes of this discussion that the second threshold is less than the first threshold… It is noted that method 1400 can be repeated in subsequent intervals to adjust the number of wavefronts that are allowed to execute concurrently on the compute units.).
Regarding claim 3, Beckmann teaches wherein determining the number of concurrent program instances comprises:
setting a current number of concurrent program instances to the upper threshold number ([0062] Also, the number of wavefronts that are allowed to execute concurrently is increased after a period in which no thrashing is detected. In one implementation, the detection is based on some threshold, and the threshold for increasing the number of wavefronts allowed to execute concurrently can be different from the threshold for decreasing the number of wavefronts allowed to execute concurrently.; [0064] The threshold can be specified in terms of a number of register/frame spills per epoch, with the threshold amount varying from implementation to implementation.);
determining a first number of registers and a second number of memory locations per program instance of the current number of concurrent program instances ([0031] As used herein, the term “spill” is defined as storing one or more register values of locations in the physical register file to memory so as to make those physical register file locations available for storing values for other variables. [0044] register spill threshold 313.; [0040] In one implementation, when dispatch unit 305 is getting ready to launch a new wavefront, dispatch unit 305 queries control unit 310 to determine an initial number of registers to allocate to the new wavefront. [0057] a device program may have different stages with each using a different number of registers); and decreasing the current number of concurrent program instances to a next number of concurrent program instances and repeating determining and decreasing steps ([0027] in order to prevent excessive thrashing while still ensuring the processing unit's resources are being fully utilized, the control unit tracks the number of wavefront registers that are spilled per epoch. If the number of wavefront registers spilled per epoch exceeds a threshold, then the control unit reduces the number of wavefronts that are allowed to be scheduled and dispatched in the next epoch. This allows the control unit to determine the optimal rate at which wavefronts should be scheduled to take advantage of the available resources while avoiding excessive resource contention. Training may be conducted over a series of epochs in which for each epoch the totality or a subset of the training data set is repeated, often in random order of presentation, and the process of repeated training epochs is continued until the accuracy of the network reaches a satisfactory level. As used herein, an “epoch” refers to a period of time (e.g., a number clock cycles, transactions, etc.).), wherein the current number is greater than the lower threshold number and the number of allocations cannot be performed with the first number of registers and the second number of memory locations ([0075]).
Regarding claim 4, Beckmann teaches wherein determining the number of concurrent program instances comprises:
setting a current number of concurrent program instances to the upper threshold number, determining a first number of registers and a second number of memory locations per program instance of the current number of concurrent program instances, and setting the wave occupancy as the current number of concurrent program instances, wherein the current number is equal to the lower threshold number or the number of allocations can be performed with the first number of registers and the second number of memory locations ([0076] Otherwise, if the thrashing of the physical register file is in between the first and second thresholds (conditional block 1425, “no” leg), then the control unit allows the first number of wavefronts to execute on the plurality of compute units during the second interval (block 1435).).
Regarding claim 5, Beckmann teaches further comprising: determining whether the number of allocations can be performed by performing, for the program variables, register allocation with the first number of registers and moving to the second number of memory locations ([0027]; [0076]).
Regarding claim 6, Beckmann teaches wherein register allocation with unlimited registers and register allocation and moving are performed with different coloring algorithms or a same coloring algorithm ([0027] In one implementation, in order to prevent excessive thrashing while still ensuring the processing unit's resources are being fully utilized, the control unit tracks the number of wavefront registers that are spilled per epoch. If the number of wavefront registers spilled per epoch exceeds a threshold, then the control unit reduces the number of wavefronts that are allowed to be scheduled and dispatched in the next epoch. This allows the control unit to determine the optimal rate at which wavefronts should be scheduled to take advantage of the available resources while avoiding excessive resource contention. Training may be conducted over a series of epochs in which for each epoch the totality or a subset of the training data set is repeated, often in random order of presentation, and the process of repeated training epochs is continued until the accuracy of the network reaches a satisfactory level. As used herein, an “epoch” refers to a period of time (e.g., a number clock cycles, transactions, etc.).; [0075-76]).
Regarding claim 7, Beckmann teaches wherein determining the first number of registers and the second number of memory locations comprises:
determining the first number of registers per program instance based, at least in part, on the total number of registers and the current number of concurrent program instances ([0037] register allocation and deallocate can occur at other points in time which are unrelated to call or return boundaries. Threads within wavefronts executing on compute units 255A-N read and write data to corresponding local memory 230A-N, registers 257A-N, global data share 270, shared L1 cache 265, and L2 cache(s) 260 within GPU 205. It is noted that L1 cache 265 can include separate structures for data and instruction caches. It is also noted that global data share 270, shared L1 cache 265, L2 cache(s) 260, memory controller 220, system memory 225, and local memory 230 can collectively be referred to herein as a “memory subsystem”. It should be understood that when registers 257A-N are described as being spilled to memory, this can refer to the values being written to any location or level within the memory subsystem.; [0043] When the registers from range 00-0F are deallocated, the spill indicator field 347 for entry 338 is set and the values stored by these registers are written back to memory subsystem 365. In one implementation, a pre-reserved memory in a known location is used for storing the register stack frame in memory.); and determining the second number of memory locations per program instance based, at least in part, on the total number of memory locations and the current number of concurrent program instances ([0061] discusses a thrashing threshold that relates to the amount of memory being allocated to receive the spilled data from the registers, as such it reasonably teaches memory locations for concurrent program instances).
Regarding claims 8-14, they are system type claims having similar limitations as claims 1-7 above respectively. Therefore, they are rejected under the same rationale above.
Regarding claims 15-20, they are system type claims having similar limitations as claims 1-5 and 7 above respectively. Therefore, they are rejected under the same rationale above.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Duluk JR et al. (US 2013/0268942 A1) See at least [0091-92].
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JORGE A CHU JOY-DAVILA whose telephone number is (571)270-0692. The examiner can normally be reached Monday-Friday, 6:00am-5:00pm.
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, Aimee J Li can be reached at (571)272-4169. 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.
/JORGE A CHU JOY-DAVILA/Primary Examiner, Art Unit 2195
Prosecution Insights