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 .
No claims have been amended. No claims have been canceled. No new claims have been added. Claims 1-20 are currently pending for examination.
Response to Arguments
In response to the applicant’s arguments, pgs. 7-11, that Arvo does not disclose "...executing a first batch of a first kernel on a first processing device ... executing a first batch of a second kernel on a second processing device ... wherein executing the first batch of the second kernel does not overlap in time with executing the first batch of the first kernel.", the examiner has carefully considered these arguments and respectfully disagrees. To begin with, Arvo was not mapped to the limitation "...executing a first batch of a first kernel on a first processing device ... executing a first batch of a second kernel on a second processing device”. This limitation, which it is argued that Arvo does not disclose, is explicitly taught by Gangani.
Furthermore, the limitation of “wherein executing the first batch of the second kernel does not overlap in time with executing the first batch of the first kernel” is both necessitated and implied by the former limitation of “executing a first batch of a second kernel on a second processing device to generate a first output of the second kernel based on the first output of the first kernel”. Thus, although it is conceded that Gangani cannot be explicitly mapped to the limitation of “wherein executing the first batch of the second kernel does not overlap in time with executing the first batch of the first kernel”, this is necessarily taught by the primary reference implicitly.
Regardless of the teachings of Gangani, Arvo fully discloses the limitation "...executing a first batch of a first kernel on a first processing device ... executing a first batch of a second kernel on a second processing device ... wherein executing the first batch of the second kernel does not overlap in time with executing the first batch of the first kernel." Fig. 7 is indeed one embodiment of the invention of Arvo wherein the first batches of the first two kernels are executed in series on the same shader processor. However, as illustrated in fig. 5, the first batches of the first two kernels may also be distributed, in sequence, between shader processors; see [0078-0079]:
“Sequencer module 140 distributes workgroups of kernels 142-146 in a fixed distribution pattern, without controlling the specific destination of the workgroups of different kernels. For example, sequencer module 140 distributes workgroups of the first kernel 142 by sequentially distributing a first workgroup WG0 to SP 152A (as represented by line 160), a second workgroup WG1 to SP 152B (as represented by line 161), a third workgroup WG2 to SP 152C (as represented by line 162), and so on until the first kernel 142 has been distributed and executed. Sequencer module 140 then moves on to the second kernel 144 and the third kernel 146 and distributes those workgroups to the SPs 152. For example, the sequencer module 140 may continue in the fixed distribution pattern and may distribute all of the workgroups of the second kernel 144 among the SPs 152. Sequencer module 140 then may proceed to the third kernel 146 and distribute all of the workgroups of the third kernel 146 among the SPs 152…. Without the ability to control which SP 152 executes a particular workgroup, the data associated with workgroups may be required to be loaded into more than one of the SP memories 156. As shown in the example of FIG. 5, in following the fixed distribution pattern, after processing the entire first kernel 142, sequencer module 140 distributes workgroup WG0 of the second kernel 144 to SP 152B (line 161). Accordingly, the input data associated with WG0 must be loaded into SP memory 156B.”
Fig. 5 and supporting paragraphs 0078-0079 clearly describe a scenario in which the first workgroup of the first kernel is executed, in series, before the first workgroup of the second kernel is executed on a different shader processor (152B), or device.
The combination of Gangani with Arvo would not render Arvo unsatisfactory for its intended purpose. Sharing of data between the local SP memories and Global GPU memory of Arvo allows for parallelization (Arvo, [0066]). In situations wherein the input data for the first workgroup of a first and second kernel is not the same, it would not be advantageous to execute the first workgroup of a first and second kernel on the same shader processor (Arvo, [0022]). Thus, one of ordinary skill in the art would be motivated to combine Gangani’s pipeline fusion with Arvo’s execution order- thereby reducing memory bandwidth consumption when the input data of the first workgroup of a first and second kernel are similar. As such, the 35 USC 103 rejection of claims 1 and 11 under Gangani in view of Arvo is maintained.
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, 2, 4, 5, 11, 12, 14, and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Gangani (US 20210200608 A1) in view of Arvo (US 20120320070 A1).
As per claim 1, Gangani discloses:
A method for pipeline fusion of a plurality of kernels (“GPUs execute a graphics processing pipeline that includes one or more processing stages that operate together to execute graphics processing commands and output a frame. A central processing unit (CPU) may control the operation of the GPU by issuing one or more graphics processing commands to the GPU. Modern day CPUs are typically capable of concurrently executing multiple applications, each of which may need to utilize the GPU during execution.”, abstract ; Examiner Note: a graphics processing pipeline equates to a method for pipeline fusion of kernels.) the method comprising:
executing a first batch of a first kernel on a first processing device to generate a first output of the first kernel based on an input (“For example, a fused shader kernel may facilitate executing the tasks or functions associated with a first ML primitive (e.g., a convolution primitive)", 0046 ; “For example, executing the first node 310A of FIG. 3 may include the graphics processor receiving input data 320A, performing the one or more operations associated with a respective shader kernel, and generating output data 330A.", 0065 ; see fig.3- Node A is the first device ; Examiner Note: an ML primitive running on a node equates to a kernel)
executing a first batch of a second kernel on a second processing device to generate a first output of the second kernel based on the first output of the first kernel (“For example, intermediate results generated by execution of the tasks or functions associated with the first ML primitive may be stored in the local memory and then read from the local memory for execution of the tasks or functions associated with the second ML primitive.", 0046 ; “As shown in FIG. 3, each of the nodes 310A to 310E receives respective input data 320A to 320E and generates respective output data 330A to 330E.”, 0064; Examiner Note: the intermediary results of the execution of the first ML primitive equate to the output of the first batch of the first kernel, and node 310B equates to a second device)
executing a second batch of the first kernel on the first processing device to generate a second output of the first kernel based on the input (“For example, executing the first node 310A of FIG. 3 may include the graphics processor receiving input data 320A, performing the one or more operations associated with a respective shader kernel, and generating output data 330A.", 0065 ; see fig.3- Node A is the first device ; Examiner Note: performing one or more operations corresponds to executing a second batch.)
wherein executing the second batch of the first kernel overlaps at least partially in time with executing the first batch of the second kernel. (“It should be appreciated that the processing elements 244 allow for parallelization, which is why executing ML primitives via the graphics processor 240 may be useful. For example, each processing element 244 of the graphics processor 240 may be configured to execute the same operations, but on different data. In this way, the parallel-processing structure of the processing elements 244 allows the graphics processor 240 to perform many operations in parallel (e.g., at the same time), which may be useful in accelerating an ML primitive”, 0059 ; “The processing unit 520 may be configured to perform graphics processing, such as in a graphics processing pipeline 507”, 0082 ; see fig.3- node 310A runs a first kernel, 310B runs a second kernel in parallel with each other ; Examiner Note: after the first ML primitive, or kernel, (running on 310A) passes its output to the second ML primitive (310B), the graphics processing pipeline will necessarily continue running at 330A as further ML primitives are processed)
Gangani discloses the above limitations of claim 1, but does not explicitly disclose the amended limitation of the execution of the first batch of the first kernel and the first batch of the second kernel not overlapping in time.
However, Arvo explicitly discloses:
executing the first batch of the second kernel does not overlap in time with executing the first batch of the first kernel (“After executing Workgroup 0 of kernel 56, and instead of fetching new data for SP memory 78A, sequencer module 82 directs SP 76A to execute Workgroup 0 of kernel 57, followed by Workgroup 0 of kernel 58.”, 0071 ; “For example, without the ability to control which SP of the GPU executes a particular workgroup of a particular kernel, a workgroup of a first kernel having the same input data as a workgroup of a second kernel may be processed by different SPs of the GPU.”, 0021 ; Examiner Note: a workgroup equates to a batch)
Arvo discloses both sequential workgroup/batch execution and kernels being run in parallel (“Once stored in SP memories 78, SPs 76 operate in parallel to access and process the data stored in the separate SP memories 78.”, 0066). It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the teachings of Gangani with those of Arvo in order to provide an execution order to batches/workgroups, thereby reducing memory bandwidth consumption as well as SP ALU operations (Arvo, [0022]).
As per claim 2, Gangani in view of Arvo teaches all of the limitations of claim 1.
Furthermore, Gangani discloses:
executing a first batch of a third kernel to generate a first output of the third kernel based on the first output of the second kernel (“For example, referring to the graph structure 100 of FIG. 1, the output data 130B generated by executing the shader kernel associated with the second node 110B may be used as the input data 120C used for the execution of the shader kernel associated with the third node 110C.”, 0020 ; see fig.1- node 3 generates output data 130C.)
wherein executing the first batch of the third kernel overlaps at least partially in time with executing the second batch of the second kernel (“the parallel-processing structure of the processing elements 244 allows the graphics processor 240 to perform many operations in parallel (e.g., at the same time), which may be useful in accelerating an ML primitive”, 0059 ; see fig.1- node 110B runs a second kernel, 110C runs a third kernel in parallel with the second kernel ; Examiner Note: after the second ML primitive, or kernel, (running on 110B) passes its output to the third ML primitive (110C), the graphics processing pipeline will necessarily continue running at 110B as further ML primitives are processed)
As per claim 4, Gangani in view of Arvo teaches all of the limitations of claim 1.
Furthermore, Gangani discloses:
the first output of the first kernel is written to a scratch memory of the first processing device by the first processing device (“In some such examples in which the graphics processor 240 includes the local memory, one or more shader kernels may be configured to read input data from the local memory and/or store output data to the local memory", 0045 ; Examiner Note: local memory equates to scratch memory).
As per claim 5, Gangani in view of Arvo teaches all of the limitations of claim 4.
Furthermore, Gangani discloses:
the first output of the first kernel is read from the scratch memory of the first processing device by the second processing device (“intermediate results generated by execution of the tasks or functions associated with the first ML primitive may be stored in the local memory and then read from the local memory for execution of the tasks or functions associated with the second ML primitive.", 0046 ; see fig.1- nodes 110A and 110B equate to first and second processing devices)
As per claim 11, Gangani discloses:
A processor configured for pipeline fusion of a plurality of kernels, the processor comprising: a first processing device… a second processing device (“GPUs execute a graphics processing pipeline that includes one or more processing stages that operate together to execute graphics processing commands and output a frame”, abstract ; “It should be appreciated that the processing elements 244 allow for parallelization, which is why executing ML primitives via the graphics processor 240 may be useful. For example, each processing element 244 of the graphics processor 240 may be configured to execute the same operations, but on different data”, 0059 ; Examiner Note: a graphics processing pipeline equates to a method for pipeline fusion of kernels. A graphics processor (240) equates to a processor, and the processing elements (244) of the processor equate to the first and second processing device; more clearly illustrated by fig.1 and nodes A-E (each representing a shader kernel, [0018]).)
execute a first batch of a first kernel on a first processing device to generate a first output of the first kernel based on an input (“For example, a fused shader kernel may facilitate executing the tasks or functions associated with a first ML primitive (e.g., a convolution primitive)", 0046 ; “For example, executing the first node 310A of FIG. 3 may include the graphics processor receiving input data 320A, performing the one or more operations associated with a respective shader kernel, and generating output data 330A.", 0065 ; see fig.3- Node A is the first device ; Examiner Note: an ML primitive running on a node equates to a kernel)
execute a first batch of a second kernel on a second processing device to generate a first output of the second kernel based on the first output of the first kernel (“For example, intermediate results generated by execution of the tasks or functions associated with the first ML primitive may be stored in the local memory and then read from the local memory for execution of the tasks or functions associated with the second ML primitive.", 0046 ; “As shown in FIG. 3, each of the nodes 310A to 310E receives respective input data 320A to 320E and generates respective output data 330A to 330E.”, 0064; Examiner Note: the intermediary results of the execution of the first ML primitive equate to the output of the first batch of the first kernel, and node 310B equates to a second device)
execute a second batch of the first kernel on the first processing device to generate a second output of the first kernel based on the input (“For example, executing the first node 310A of FIG. 3 may include the graphics processor receiving input data 320A, performing the one or more operations associated with a respective shader kernel, and generating output data 330A.", 0065 ; see fig.3- Node A is the first device ; Examiner Note: performing one or more operations corresponds to executing a second batch.)
execute the second batch of the first kernel overlapping in time at least partially with the second processing device executing the first batch of the second kernel. (“It should be appreciated that the processing elements 244 allow for parallelization, which is why executing ML primitives via the graphics processor 240 may be useful. For example, each processing element 244 of the graphics processor 240 may be configured to execute the same operations, but on different data. In this way, the parallel-processing structure of the processing elements 244 allows the graphics processor 240 to perform many operations in parallel (e.g., at the same time), which may be useful in accelerating an ML primitive”, 0059 ; “The processing unit 520 may be configured to perform graphics processing, such as in a graphics processing pipeline 507”, 0082 ; see fig.3- node 310A runs a first kernel, 310B runs a second kernel in parallel with each other ; Examiner Note: after the first ML primitive, or kernel, (running on 310A) passes its output to the second ML primitive (310B), the graphics processing pipeline will necessarily continue running at 330A as further ML primitives are processed)
Gangani discloses the above limitations of claim 1, but does not explicitly disclose the amended limitation of the execution of the first batch of the first kernel and the first batch of the second kernel not overlapping in time.
However, Arvo explicitly discloses:
execute the first batch of the second kernel does not overlap in time with executing the first batch of the first kernel (“After executing Workgroup 0 of kernel 56, and instead of fetching new data for SP memory 78A, sequencer module 82 directs SP 76A to execute Workgroup 0 of kernel 57, followed by Workgroup 0 of kernel 58.”, 0071 ; “For example, without the ability to control which SP of the GPU executes a particular workgroup of a particular kernel, a workgroup of a first kernel having the same input data as a workgroup of a second kernel may be processed by different SPs of the GPU.”, 0021 ; Examiner Note: a workgroup equates to a batch)
As per claim 12, it is a system claim with substantially the same limitations as claim 2, and as such, it is rejected for substantially the same reasons as claim 2.
As per claim 14, it is a system claim with substantially the same limitations as claim 4, and as such, it is rejected for substantially the same reasons as claim 4.
As per claim 15, it is a system claim with substantially the same limitations as claim 5, and as such, it is rejected for substantially the same reasons as claim 5.
Claims 6-10 and 16-20 are rejected under 35 U.S.C. 103 as being unpatentable over Gangani (US 20210200608 A1) in view of Arvo (US 20120320070 A1) in further view of Andrei (US 20200293367 A1).
As per claim 6, Gangani in view of Arvo fully discloses the limitations of claim 1, but does not discloses writing kernel outputs to a register file.
However, Andrei discloses:
the first output of the first kernel is written to a register file of the first processing device by the first processing device (“The register file 258 provides a set of registers for the functional units of the graphics multiprocessor 234. The register file 258 provides temporary storage for operands connected to the data paths of the functional units (e.g., GPGPU cores 262, load/store units 266) of the graphics multiprocessor 234.”, 0073 ; Examiner Note: operands equate to kernels)
Gangani teaches a system wherein the outputs of the ML primitives, or kernels, are saved to local memory of the device; and Andrei discloses a system wherein operands, or kernels, may use a register file to store data. It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the pipeline fusion system of Gangani with the register files of Andrei in order to provide the system with a smaller, and more quickly accessible memory location which may be used by the kernels- thereby increasing the overall processing speed of the system.
As per claim 7, Gangani in view of Arvo in further view of Andrei fully discloses the limitations of claim 6.
Furthermore, Gangani discloses:
the first output of the first kernel is read from the register file of the first processing device by the second processing device. (“For example, intermediate results generated by execution of the tasks or functions associated with the first ML primitive may be stored in the local memory and then read from the local memory for execution of the tasks or functions associated with the second ML primitive.", 0046)
Gangani in view of Arvo does not disclose the second processing device reading the output of the first processing device from the register file,
However, Andrei discloses:
“The register file 258 provides a set of registers for the functional units of the graphics multiprocessor 234. The register file 258 provides temporary storage for operands connected to the data paths of the functional units (e.g., GPGPU cores 262, load/store units 266) of the graphics multiprocessor 234.”, 0073 ; Examiner Note: the multiple GPGPU cores equate to first and second processing devices.
As per claim 8, Gangani in view of Arvo fully discloses the limitations of claim 1.
Furthermore, Andrei discloses:
the first processing device comprises an arithmetic logic unit (ALU) (“The GPGPU cores 262 can each include floating point units (FPUs) and/or integer arithmetic logic units (ALUs) that are used to execute instructions of the graphics multiprocessor 234.”, 0074)
As per claim 9, Gangani in view of Arvo fully discloses the limitations of claim 1.
Furthermore, Andrei discloses:
the second processing device comprises a compute unit (CU) (“In one embodiment the GPGPU 1420 additionally includes a matrix accelerator 1423, which can include one or more special function compute units that are designed to accelerate a subset of matrix operations (e.g., dot product, etc.).", 0214 ; Examiner Note: GPGPU 1420 equates to a second processing device)
As per claim 10, Gangani in view of Arvo fully discloses the limitations of claim 1.
Furthermore, Andrei discloses:
the first kernel performs a matrix multiply operation and the second kernel does not perform a matrix multiply operation (“The MPUs 1517A-1517N can also be configured for mixed precision matrix operations, including half-precision floating point and 16-bit integer operations. The MPUs 1517-1517N can perform a variety of matrix operations to accelerate machine learning application frameworks, including enabling support for accelerated general matrix to matrix multiplication (GEMM). The AFUs 1512A-1512N can perform additional logic operations not supported by the floating-point or integer units, including trigonometric operations (e.g., Sine, Cosine, etc.).", 0218 ; Examiner Note: an operand, or kernel, running on MPUs 1517A-1517N equates to a first kernel which may perform matrix multiply operations, an operand running on AFUs 1512A-1512N equates to a second kernel which does not perform matrix multiply operations- as it is purposed for logic operations.)
As per claim 16, it is a system claim with substantially the same limitations as claim 6, and as such, it is rejected for substantially the same reasons as claim 6.
As per claim 17, it is a system claim with substantially the same limitations as claim 7, and as such, it is rejected for substantially the same reasons as claim 7.
As per claim 18, it is a system claim with substantially the same limitations as claim 8, and as such, it is rejected for substantially the same reasons as claim 8.
As per claim 19, it is a system claim with substantially the same limitations as claim 9, and as such, it is rejected for substantially the same reasons as claim 9.
As per claim 20, it is a system claim with substantially the same limitations as claim 10, and as such, it is rejected for substantially the same reasons as claim 10.
Claims 3 and 13 are rejected under 35 U.S.C. 103 as being unpatentable over Gangani (US 20210200608 A1) in view of Arvo (US 20120320070 A1) in view of Kappel (US 20220246244 A1).
As per claim 3, Gangani in view of Arvo teaches all of the limitations of claim 2.
Furthermore, Gangani discloses:
executing a second batch of the third kernel to generate a second output of the third kernel based on the second output of the second kernel (“For example, referring to the graph structure 100 of FIG. 1, the output data 130B generated by executing the shader kernel associated with the second node 110B may be used as the input data 120C used for the execution of the shader kernel associated with the third node 110C.”, 0020 ; see fig.1- node 3 generates output data 130C. ; “The processing unit 520 may be configured to perform graphics processing, such as in a graphics processing pipeline 507”, 0082 ; Examiner Note: within a processing pipeline model, it is inherent that the third kernel will be again executed based off of a second kernels output)
Gangani teaches the iterative execution of a third kernel, or ML primitive, based off of the output of a second kernel, but does not teach the concatenation of the multiple outputs of the third kernel.
However, Kappel discloses:
concatenating the first output of the third kernel with the second output of the third kernel to generate an output of the plurality of kernels (“For example, the visual recognition neural network may comprise at least a first batch normalization operation 410 followed by a first ReLu operation 420 followed by a first convolution operation 430 (e.g. kernel size 1×1) followed by a second batch normalization operation 410 followed by a second ReLu operation 420 followed by a second convolution operation 430 (e.g. kernel size 3×3) followed by a GlobalAveragePooling operation 510 in parallel to a Global-MaxPooling operation 520 followed by a first concatenation operation 530”, 0076 ; Examiner Note: the output of the first round of batch normalization, ReLU operation, and convolution operation equates to the first output of the third kernel, the output of the second round of batch normalization, ReLU operation, and convolution operation equate to the second output of the third kernel.)
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the pipeline fusion method of Gangani with the concatenation of Kappel, in order to provide a system benefitting from the efficiency of pipeline fusion with the ability to generate feature vectors from the separate single column outputs of kernels; thereby allowing the intermediary outputs to be processed by a linear regression or clustering operand-which increases the capabilities of the whole system.
As per claim 13, it is a system claim with substantially the same limitations as claim 3, and as such, it is rejected for substantially the same reasons as claim 3.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Gupta (US 9916162 B2)- discloses a method for synchronizing workloads across local thread groups. Method involves using a global barrier between each executing thread to monitor threads.
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 ROSS MICHAEL VINCENT whose telephone number is (703)756-1408. The examiner can normally be reached Mon-Fri 8:30AM-5:30PM.
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, April Blair can be reached on (571) 270-1014. 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.
/R.M.V./
Examiner, Art Unit 2196
/APRIL Y BLAIR/Supervisory Patent Examiner, Art Unit 2196
Prosecution Insights