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
The present application, 17862435 filed 07/12/2022 claims foreign priority to JP2021-183015, filed 11/10/2021.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 07/12/2022 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Drawings
Figures 2, 5A and 5B should be designated by a legend such as --Prior Art-- because only that which is old is illustrated. See paragraphs [0083, 0098, 0100 and 0104] which discloses that the contents of figures 2, 5A and 5B were disclosed in various prior art references. See MPEP § 608.02(g). Corrected drawings in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. The replacement sheet(s) should be labeled “Replacement Sheet” in the page header (as per 37 CFR 1.84(c)) so as not to obstruct any portion of the drawing figures. If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Specification
The disclosure is objected to because at least paragraphs [0005, 0098, 0100 and 0104] contains an embedded hyperlink and/or other form of browser-executable code. Applicant is required to delete the embedded hyperlink and/or other form of browser-executable code; references to websites should be limited to the top-level domain name without any prefix such as http:// or other browser-executable code. See MPEP § 608.01.
Claim Interpretation
The broadest reasonable interpretation of a method (or process) claim having contingent limitations requires only those steps that must be performed and does not include steps that are not required to be performed because the condition(s) precedent are not met. For example, assume a method claim requires step A if a first condition happens and step B if a second condition happens. If the claimed invention may be practiced without either the first or second condition happening, then neither step A or B is required by the broadest reasonable interpretation of the claim. If the claimed invention requires the first condition to occur, then the broadest reasonable interpretation of the claim requires step A. If the claimed invention requires both the first and second conditions to occur, then the broadest reasonable interpretation of the claim requires both steps A and B. See MPEP 2111.04 for more information.
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.
Claims 1, 5, 7, 11 and 13-17 are rejected under 35 U.S.C. 103 as being unpatentable over Collier (US 2021/0374208 A1), in view of Itou (US 2014/0026138 A1).
Regarding claim 7, Collier teaches an apparatus comprising:
a memory (Collier claim 16; memory – memory); and
a processor coupled to the memory and configured to (Collier claim 16; processor - at least one hardware processor):
(Collier paragraph [0025] “different processing threads may be assigned different parts of the processing workload of the matrix-matrix multiplication”; paragraph [0033] “each NUMA node 114 has sixteen CPUs 120 (not depicted in FIG. 5B) and therefore, sixteen processing threads (not depicted in FIG. 5B); paragraph [0046] “After distributing the matrix-matrix multiplication workload according to the processor sockets 110 and NUMA nodes 114, the engine 140 then proceeds to phase three and distributes the workload across the processing threads. In accordance with some implementations, the number of the threads per NUMA node 114 corresponds to the number of CPU cores 120 per NUMA node 114”; paragraph [0049] “the possible thread-level decompositions, assuming 16 cores per NUMA node 114, are 1x16, 2x8, 4x4, 8x2 and 16x1”; first process – threads in one NUMA node; second process – threads in another NUMA node or threads in a different socket; one or a plurality of processing units that process elements of a first portion of a matrix – cores in the one NUMA node; of one or a plurality of processing units that process elements of a second portion of the matrix – cores in the other NUMA node or cores in the other socket);
execute the first process by using the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel (Collier paragraph [0025] “As part of this execution, the computations are performed in a parallel fashion by the processing threads”; paragraph [0031] “At the end of the three phases, the engine 140 communicates (block 216) the composite workload distribution to the GEMM engine 134, which then assigns the processing tasks based on this workload distribution and performs the matrix-matrix multiplication”);
execute a synchronization process on the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel by using a synchronization method (Collier paragraph [0051] “the GEMM engine 34 includes processing thread synchronization barriers … In accordance with example implementations, the synchronization barriers may be a derived data type that is equal in size to a cache line to avoid false sharing”; paragraph [0023]; claim 14); and
execute the second process by using the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel (Collier Figs. 5A and 7; paragraphs [0036 and 0042-0044] the other NUMA nodes/socket process their own assigned matrix partition).
Collier does not explicitly teach determine, by using each of a plurality of processes included in a matrix process as a first process and using a process next to the first process as a second process, a synchronization method for one or a plurality of processing units that process elements of a first portion of a matrix in parallel, based on the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel in the first process and the number of one or a plurality of processing units that process elements of a second portion of the matrix in parallel in the second process; and execute a synchronization process on the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel by using the synchronization method.
However, on the same field of endeavor, Itou discloses a synchronization method based on a number of processing cores executing threads/processes (Itou Figs. 1A-1C, 3-4C and 21A-21B; paragraphs [0408-0418, 0426]).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective
filling date of the claimed invention, to modify Collier using Itou and configure the apparatus to determine a synchronization method based on the number of processing cores processing the matrix multiplication operation to determine whether an intra-bank synchronization (i.e., within each NUMA node) is to be performed or whether an inter-bank (i.e., with each socket or between the sockets) is to be performed in order to reduce the processing time to complete the matrix multiplication operation by having a two-level hierarchy for performing synchronization as compared to having a single centralized synchronization method (Itou paragraph [0113]).
Therefore, the combination of Collier as modified in view of Itou teaches determine, by using each of a plurality of processes included in a matrix process as a first process and using a process next to the first process as a second process, a synchronization method for one or a plurality of processing units that process elements of a first portion of a matrix in parallel, based on the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel in the first process and the number of one or a plurality of processing units that process elements of a second portion of the matrix in parallel in the second process; and execute a synchronization process on the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel by using the synchronization method.
Regarding claim 11, Collier as modified in view of Itou teaches all the limitations of claim 7 as stated above. Further, Collier as modified in view of Itou teaches wherein the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel process one or a plurality of columns or rows included in the first portion of the matrix in parallel, and the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel process one or a plurality of columns or rows included in the second portion of the matrix in parallel (Collier Figs. 5A and 7 and paragraphs [0042-0044]).
Regarding claims 1 and 5, they are directed to a non-transitory computer-readable recording medium storing an information processing program for causing a computer to function like the apparatus of claims 7 and 11 respectively. All steps in the non-transitory computer-readable recording medium claims 1 and 5 would be practiced by the apparatus of claims 7 and 11 respectively. Claims 7 and 11 analysis applies equally to claims 1 and 5 respectively.
Regarding claims 13 and 17, they are directed to a method practiced by the apparatus of claims 7 and 11. All steps performed by the method of claims 13 and 17 would be practiced by the apparatus of claims 7 and 11 respectively. Claims 7 and 11 analysis applies equally to claims 13 and 17 respectively.
Regarding claim 14, Collier as modified in view of Itou teaches all the limitations of claim 13 as stated above. Further, Collier as modified in view of Itou teaches wherein the determining of the synchronization method includes determining stream synchronization as the synchronization method in a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a group size and the other number is larger than the group size (The step of “determining stream synchronization as the synchronization method” is contingent upon “a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a group size and the other number is larger than the group size” and is not required when required when both the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a group size or larger than the group size. See also claim interpretation section above).
Regarding claim 15, Collier as modified in view of Itou teaches all the limitations of claim 14 as stated above. Further, Collier as modified in view of Itou teaches wherein the executing of the synchronization process by using the synchronization method includes applying inter-group synchronization as the synchronization method in a case where the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel is larger than the group size and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is larger than the group size (The step of “applying inter-group synchronization as the synchronization method” is contingent upon “a case where the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel is larger than the group size and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is larger than the group size” and is not required when the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel is smaller than or equal than the group size and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is smaller than or equal than the group size. See also claim interpretation section above; Itou Figs. 3-4C and 21B and paragraphs [0111, 0418 and 0426]).
Regarding claim 16, Collier as modified in view of Itou teaches all the limitations of claim 14 as stated above. Further, Collier as modified in view of Itou teaches wherein the executing of the synchronization process by using the synchronization method includes applying intra-group synchronization as the synchronization method in a case where the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel is equal to or smaller than the group size and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than the group size (The step of “applying intra-group synchronization as the synchronization method” is contingent upon “a case where the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel is equal to or smaller than the group size and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than the group size” and is not required when the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel is larger than the group size and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is larger than the group size. See also claim interpretation section above; Itou Figs. 1A-1CC and 21A and paragraphs [0018-0019, 0410-0415]).
Claims 6, 12 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Collier in view of Itou as applied to claims 1, 7 and 13 above respectively, and further in view of Kaasschieter et al. (NPL – “Preconditioned conjugate gradients for solving singular systems”), hereinafter Kaasschieter. Kaasschieter is cited in the IDS submitted on 07/12/2022.
Regarding claim 12, Collier as modified in view of Itou teaches all the limitations of claim 7 as stated above. Collier does not explicitly teach wherein the matrix is an upper triangular matrix or a lower triangular matrix representing coefficients of simultaneous linear equations, and the matrix process is included in a precondition in a solution of the simultaneous linear equations.
However, on the same field of endeavor, Kaasschieter discloses calculating a solution of a simultaneous linear equation which includes a matrix representing coefficients of the simultaneous linear equation and is a lower triangular matrix and a matrix process that is included in a precondition in a solution of the simultaneous linear equations (Kaasschieter page 265-268; see also Applicant’s specification paragraphs [0079-0084] which describes Kaasschieter).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention, to modify Collier in view of Itou using Kaasschieter and configure the system to solve simultaneous linear equations by using the matrix to represent coefficients of the simultaneous linear equations, and including the matrix process as a precondition in a solution of the simultaneous linear equation to accelerate the convergence rate by replacing the system of linear equations with the preconditioned system (Kaasschieter page 265 Introduction).
Therefore, the combination of Collier as modified in view of Itou and Kaasschieter teaches wherein the matrix is an upper triangular matrix or a lower triangular matrix representing coefficients of simultaneous linear equations, and the matrix process is included in a precondition in a solution of the simultaneous linear equations.
Regarding claim 6, it is directed to a non-transitory computer-readable recording medium storing an information processing program for causing a computer to function like the apparatus of claim 12. All steps in the non-transitory computer-readable recording medium claim 6 would be practiced by the apparatus of claim 12. Claim 12 analysis applies equally to claim 6.
Regarding clam 18, it is directed to a method practiced by the apparatus of claim 12. All steps performed by the method of claim 18 would be practiced by the apparatus of claim 12. Claim 12 analysis applies equally to claim 18.
Allowable Subject Matter
Claims 2-4 and 8-10 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
Claim 2 is directed to a non-transitory computer-readable recording medium storing an information processing program for causing a computer to execute a process comprising: among other things, determining a synchronization method, wherein the determining of the synchronization method includes determining stream synchronization as the synchronization method in a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a group size and the other number is larger than the group size. Claim 8 is directed to an information processing apparatus comprising, among other things, a processor configured to determine a synchronization method wherein the processor determines stream synchronization as the synchronization method in a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a group size and the other number is larger than the group size.
Collier (US 20210374208 A1) discloses partitioning, assigning and distributing a matrix multiplication to a plurality of processing cores in a parallel processing system. The system includes a plurality of sockets, each including a plurality of non-uniform memory access (NUMA) nodes, each NUMA node comprising a plurality of processing cores, each core executing a processing thread in parallel with other cores processing other processing threads. Further, Collier discloses performing thread synchronization during execution of the a matrix multiplication and using shared data structures that are explicitly local to a given NUMA node to help further improve data locality and reduce contention. However, Collier fails to explicitly teach or suggest determining stream synchronization as the synchronization method in a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a NUMA node size and the other number is larger than the NUMA node size as required by claim 2.
Itou (US 20140026138 A1) discloses a barrier synchronization mechanisms for an information processing device that includes a plurality of barrier banks where each bank includes one or more processor cores. The barrier synchronization mechanism includes a shared unit that includes a barrier type which indicates a type of barrier synchronization to be perform. Examples of the barrier type includes “intra-bank” indicating that synchronization within a barrier bank is performed, or “inter-bank”, indicating that synchronization among barrier banks is performed. However, Itou fails to explicitly teach or suggest determining stream synchronization as the synchronization method in a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a bank size and the other number is larger than the bank size as required by claim 2.
Sakurai (US 20160161981 A1) discloses a parallel operation system that includes a first NUMA node including a first processor configured to execute a first process, a second processor configured to execute a second process, and a first memory, and a NUMA second node including a third processor configured to execute a third process, a fourth processor configured to execute a fourth process, and a second memory, and a first signal line that transfers synchronization information between at least one of the first and second processors and at least one of the third and fourth processors, wherein when the first process is to be synchronized with the third process, at least one of the first and the third processors using the first signal line to execute a first synchronization process. By using an exclusive signal line to synchronize processes executed by processors in different nodes, the system performance is increased as compared to using a memory synchronization process which is used to synchronize processes executed by processors in the same node. However, Sakurai fails to explicitly teach or suggest determining stream synchronization as the synchronization method in a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a node size and the other number is larger than the node size as required by claim 2.
Nickolls et al. (US 7788468 B1) discloses synchronizing some or all threads at certain points during execution of a CTA program, for instance, if one thread produces an intermediate result that will be consumed by another thread, the two threads are synchronized at least to the extent that the producing thread is guaranteed to write the intermediate result to the designated location in shared memory before the consuming thread attempts to read it using barrier synchronization technique where a thread executes a barrier instruction to indicate that it has arrived at a barrier point and waits at that point until all other participating threads have also arrived at that point, thus synchronizing the participating threads before resuming execution. Further, Nickolls discloses the barrier synchronization technique can be applied to data processing algorithm that uses data-parallel decomposition such as matrix multiplication as well as more complex matrix operations such as linear equation solving which generally requires inverting a matrix and transposing a matrix. However, Nickolls fails to explicitly teach or suggest determining stream synchronization as the synchronization method in a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a group size and the other number is larger than the group size as recited in claim 2.
Venkataramani et al. (US 20180157471 A1) discloses that stream synchronization is the default synchronization method in CUDA operations where no operation in the default stream may begin until all previously issued operations in any stream on the device have completed, and an operation in the default stream must complete before any other operation (in any stream on the device) may begin and that the “CudaStreamSynchronize(stream)” API may be used to synchronize the host with respect to a specific stream which block the host until all issued CUDA calls in the identified stream are complete. However, Venkataramani fails to explicitly teach or suggest determining stream synchronization as the synchronization method in a case where any one of the number of the one or the plurality of processing units that process the elements of the first portion of the matrix in parallel and the number of the one or the plurality of processing units that process the elements of the second portion of the matrix in parallel is equal to or smaller than a group size and the other number is larger than the group size as recited in claim 2.
Claim 8 recites substantially the same limitation as claim 2 and would be allowable for the same reasons. Claims 3-4 and 9-10 would also be allowable for the same reasons as claims 2 and 9 by reason of dependence.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Carlo Waje whose telephone number is (571)272-5767. The examiner can normally be reached 9:00-6:00 M-F.
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, James Trujillo can be reached at (571) 272-3677. 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.
/Carlo Waje/Examiner, Art Unit 2151 (571)272-5767