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 .
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 16-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. Paragraphs 0040, 0052, 0101 and 0123 in the specification fails to explicitly define the claimed "computer-readable medium" to exclude a signal or wave. Therefore, said “computer-readable medium” can also be in a signal/wave form. A signal/wave fails to fall within a statutory category of invention. It is not a process occurring as a result of executing the program, a machine programmed to operate in accordance with the program nor a manufacture structurally and functionally interconnected with program in a manner which enables the program to act as a computer component and realize functionality. It's also clearly not directed to a composition of matter. Therefore, it is non-statutory under 35 USC 101.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
Claim(s) 1, 2, 6-10, 14-16, 18 and 20 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by intel (“oneAPI GPU Optimization Guide,” URL: https://www.intel.com/content/www/us/en/docs/oneapi/optimization-guide-gpu/2023-2/overview.html).
Regarding claim 1, oneAPI teaches an apparatus for graphics processing, comprising:
A memory; and a processor coupled to the memory and, based at least in part on information stored in the memory, the processor is configured to (the guide by oneAPI pertains GPUs comprising memory (oneAPI: pg.4, Performance Considerations)):
Receive a representation of source code comprising a group of operations that write to a shared dataset (“a user starts with a serial program, identifies the parts of the code that take a long time to execute…and converts them into parallel kernels that can be offloaded to an accelerator for execution.” (oneAPI: pg.7, Programming Language and APIs, para 1). The kernels utilize a “buffer [which] is a container for data that can be accessed from a device and the host.” (oneAPI: pg.117, Performance Impact of USM and Buffers, para 3)),
Wherein the group of operations comprises a first subgroup of operations and a second subgroup of operations (“the iterations of a parallel loop…offloaded onto the GPU are divided into work-groups, sub-groups, and work-items” (oneAPI: pg.164, Terminology, para 2));
Execute the first subgroup of operations as a first concurrent plurality of threads (“multiple work-items are packed into a sub-group by vectorization so the generated SIMD instruction stream can perform tasks of multiple work-items simultaneously” (oneAPI: pg.33, Sub-Groups and SIMD Vectorization, para 2))
That write disjointly to a set of memory locations of the shared dataset (“Memory loads/stores are vectorized. Each lane of a vector load/store instruction has its own address and data” (oneAPI: pg.50, Using Sub-group Block Load/Store, para 1). This ensures “every work-item reads from and writes to different addresses” (oneAPI: pg.55, Bank Conflicts, para 3)) during a first set of time periods (“The actual time that a kernel is launched can be substantially later than when it was submitted…The implementation decides the time to launch the kernels” (oneAPI: pg.141, Overlapping Compute on Various Devices, para 4));
And execute the second subgroup of operations (oneAPI teaches different stages of a parallel task where the work is split up so that threads don’t clash while writing to the same memory. Such subgroups correspond to distinct phases of a multi-stage reduction (oneAPI: pg.82-83) or parallel loop (oneAPI: pg.164, Terminology, para 1-2). Therefore, stage1 corresponds to the first subgroup and stage2 corresponds to the second subgroup as presently recited (oneAPI: pg.83))
As a second concurrent plurality of threads that write disjointly to a subset of the set of memory locations during a second set of time periods, wherein the first set of time periods and the second set of time periods do not overlap (Barriers are used to synchronize sets of work-items within individual groups (oneAPI: pg.66, Synchronization among Threads in a Kernel). As such oneAPI teaches “a work-group barrier is again called…to make sure all work-items have completed their work” in one stage (i.e. stage1) before the threads in the next stage (i.e. stage2) are allowed to begin writing to the shared dataset)
Regarding claim 2, oneAPI teaches the apparatus of claim 1, wherein the first subgroup of operations comprises
A plurality of iterations of a write command configured to write to the shared dataset (each turn of the loop saves one piece of data to the shared dataset (oneAPI: pg.62, Pointer Aliasing and the Restrict Directive, para 1)),
Wherein each iteration of the plurality of iterations corresponds with one thread of the first concurrent plurality of threads (“to be executed simultaneously within a given hardware thread” (oneAPI: pg.19, para 5)),
Wherein each write command for each thread of the first concurrent plurality of threads writes to a disjoint memory location of the shared dataset with respect to every other write command of the first concurrent plurality of threads during the execution of the first subgroup of operations for each time period of the first set of time periods (“each vector lane has its own address” (oneAPI: pg.50, Using Sub-group Block Load/Store)).
Regarding claim 6, oneAPI teaches the apparatus of claim 1, wherein the group of operations comprises an iterative loop (“the iterations of a parallel loop (execution range) offloaded onto the GPU are divided into work-groups, sub-groups, and work-items.” (oneAPI: Terminology, para 2))
Having a write function to a shared array of elements (“a buffer provides an abstract view of memory that can be accessed by the host or a device” (oneAPI: pg.129, Buffer Accessor Modes, para 1), wherein example code “sum_acc[i] = a_acc[i] + b_acc[i];” uses “sum_acc” to write operation to the shared array “sum_buf” (oneAPI: pg.26, see second block of code)),
Wherein the iterative loop iterates the write function through the shared array of elements (the for loop executing code “sum_acc[i] = a_acc[i] + b_acc[i];” (oneAPI: pg.26, see second block of code)).
Regarding claim 7, oneAPI teaches the apparatus of claim 1, wherein the group of operations comprises an atomic function that writes to the shared dataset (“Atomics allow multiple work-items in the kernel to work on shared resources” (oneAPI: pg.73, Local Barriers vs Global Atomics, para 1).
Regarding claim 8, oneAPI teaches the apparatus of claim 7, wherein the processor is further configured to:
Determine that the group of operations comprises the atomic function that writes to the shared dataset (determining that inefficient atomics are present (oneAPI: pg.71, Advisor Recommendation Pane));
And replace the atomic function with a non-atomic function before the execution of the first subgroup of operations and the execution of the second subgroup of operations (“Barriers allow synchronization among the work-items in a work-group. It is possible to achieve the functionality of global atomics through judicious use of kernel launches and local barriers.” (oneAPI: pg.73, Local Barriers vs Global Atomics). “This kernel will perform poorly because the threads are atomically updating a single memory location and getting significant contention. A better approach is to split the array into small chunks, let each thread compute a local sum for each chunk, and then do a sequential/tree reduction of the local sums.” (oneAPI: pg.81, para 1)),
Wherein, during the execution of the first concurrent plurality of threads, the non-atomic function writes disjointly to the set of memory locations of the shared dataset during the first set of time periods (As seen in example codes in pg.81, “accum_acc[glob_id] = sum” stores the final local sum at the work items index),
Wherein, during the execution of the second concurrent plurality of threads, the non-atomic function writes disjointly to at least the subset of the set of memory locations during the second set of time periods (as stated above “all work-items…do a tree reduction using barriers to synchronize among themselves”, wherein the code provided below at pg.74 uses “scratch[loc_id] += scratch[loc_id + i];” to ensure disjoint writes to memory).
Claim(s) 9, 10, 14 and 15 are corresponding method claim(s) of claim(s) 1, 2, 7 and 8. The limitations of claim(s) 9, 10, 14 and 15 are substantially similar to the limitations of claim(s) 1, 2, 7 and 8. Therefore, it has been analyzed and rejected substantially similar to claim(s) 9, 10, 14 and 15.
Claim(s) 16, 18 and 20 are corresponding computer-readable medium claim(s) of claim(s) 1, 2 and 8. The limitations of claim(s) 16 and 20 are substantially similar to the limitations of claim(s) 1, 2 and 8. Therefore, it has been analyzed and rejected substantially similar to claim(s) 16, 18 and 20.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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) 3-5, 11-13, 17 and 19 is/are rejected under 35 U.S.C. 103 as being unpatentable over oneAPI as applied to the claim(s) above, and further in view of Chen et al. (US Patent No. 9799089).
Regarding claim 3, oneAPI teaches the apparatus of claim 1, wherein, to execute the first subgroup of operations as the first concurrent plurality of threads that write disjointly to the set of memory locations of the shared dataset during the first set of time periods, the processor is configured to:
Output a first indication of the first concurrent plurality of threads to a vector engine (VE) (“The host interacts with these kernels through a command queue… when a command is submitted into the command queue, the command is checked for dependencies and then executed on a VE” (oneAPI: pg.18, Execution Model Overview, para 2))
For parallel execution of the first concurrent plurality of threads during the first set of time periods (“the work-items within a single workgroup execute concurrently” (oneAPI, pg.19, para 2)),
Wherein, to execute the second subgroup of operations as the second concurrent plurality of threads that write disjointly to at least the subset of the set of memory locations during the second set of time periods, the processor is configured to:
Output a second indication of the second concurrent plurality of threads to the SP for parallel execution of the second concurrent plurality of threads during the second set of time periods (subsequent kernels in an “in-order queue” executing sequentially once the prior stage completes (oneAPI: pg.88, Executing Multiple Kernels on the Device at the Same Time)).
However, oneAPI does not teach but Chen teaches applying the above to a shader processor (SP) (similar to oneAPI, Chen teaches receiving an indication in a per-shader preamble to execute a first set of instructions (Chen: col.7, line 51-58) in a parallel manner (Chen: col.13, line 57-58)).
Therefore, before the effective filing date of the claimed invention, it would have been obvious to one of an ordinary skill in the art to implement the subgroup instruction submission and execution method of oneAPI on the hardware architecture of the “shader processor” taught by Chen, because this enables maximizing the hardware’s ability and speed by avoiding high-contention memory access.
Regarding claim 4, the combined teachings teach the apparatus of claim 3, wherein a graphics processing unit (GPU) comprises a plurality of SPs, wherein the plurality of SPs comprises the SP (“Although only one shader core 24 is illustrated, in some examples, GPU 14 may include two or more shader cores similar to shader core 24” (Chen: col.8, line 45-47)).
Therefore, before the effective filing date of the claimed invention, it would have been obvious to one of an ordinary skill in the art to modify the combined teachings above to implement a plurality shader core processors as taught by Chen, because this enables increasing computational throughput and efficiency.
Regarding claim 5, oneAPI teaches the apparatus of claim 1, wherein the processor is further configured to:
Assign the first subgroup of operations and the second subgroup of operations to a common workgroup (“the iterations of a parallel loop (execution range) offloaded onto the GPU are divided into work-groups, sub-groups, and work-items.” (oneAPI: pg.164, Terminology, para 2). “a collection of sub-groups form a work-group” (oneAPI: pg.33, Sub-Groups and SIMD Vectorization, para 1)),
Wherein, to execute the first subgroup of operations as the first concurrent plurality of threads and to execute the second subgroup of operations as the second concurrent plurality of threads, the processor is configured to:
Output an indication of the common workgroup to a shader processor (SP) (“a SYCL work-group is typically dispatched to an Xe-core” (oneAPI: pg.32, Intel® GPU Occupancy Calculator, para 1))
for serial execution of each subgroup of operations of the common workgroup (“all work-items of the work-group do a tree reduction using barriers to synchronize among themselves to reduce intermediate results in shared memory to the final result.” (oneAPI: pg.74, para 4) “Barriers are used to synchronize sets of work-items within individual groups” (oneAPI: pg.66, Synchronization among Threads in a Kernel). The teachings of oneAPI ensures that the parallel phase completes its writes before the next group begins) and parallel execution of each thread of each subgroup of operations of the common workgroup (“the work-items within a single workgroup execute concurrently” (oneAPI: pg.19, para 2)).
However, oneAPI does not expressly teach but Chen teaches output an indication of the common workgroup to a shader processor (SP) (similar to oneAPI, Chen teaches receiving an indication in a per-shader preamble to execute a first set of instructions (Chen: col.7, line 51-58) in a parallel manner (Chen: col.13, line 57-58)).
Therefore, before the effective filing date of the claimed invention, it would have been obvious to one of an ordinary skill in the art to implement the subgroup instruction submission and execution method of oneAPI on the hardware architecture of the “shader processor” taught by Chen, because this enables maximizing the hardware’s ability and speed by avoiding high-contention memory access.
Claims 11-13 are similar in scope to claims 3-5. Therefore, the rejection to claims 3-5 above similarly applies to claims 11-13.
Claims 19 and 17 are similar in scope to claims 3 and 5. Therefore, the rejection to claims 3 and 5 above similarly applies to claims 19 and 17.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to David H Chu whose telephone number is (571)272-8079. The examiner can normally be reached M-F: 9:30 - 1:30pm, 3:30-8: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, Daniel F Hajnik can be reached at (571) 272-7642. 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.
/DAVID H CHU/Primary Examiner, Art Unit 2616
Prosecution Insights