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 § 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.
Claims 1-6, 9-15, and 18-20 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Zhao et al., “Distributed hierarchical GPU parameter server for massive scale deep learning ads systems,” arXiv:2003.05622v1 [cs.DC] 12 Mar 2020 (“Zhao”) (cited in an IDS).
As to claim 1, Zhao teaches a model training method, comprising:
obtaining, by a computing core of a first processor, a first target embedding from a second memory of a second processor, wherein the first processor comprises a first memory, the first processor is communicatively connected to the second processor, and wherein the first processor and the second processor are processors of different types; [§ 3, paragraph 2: “The local MEM-PS loads the local parameters stored on local SSD-PS into the memory and requests other nodes for the remote parameters through the network. After all the referenced parameters are loaded in the memory, these parameters are partitioned and transferred to the HBM-PS in GPUs.” That is, the parameters are obtained from the local memory MEM-PS (second memory). This HBM-PS belongs to a CPU (second processor), as disclosed in the abstract: “We propose a hierarchical workflow that utilizes GPU High-Bandwidth Memory, CPU main memory and SSD as 3-layer hierarchical storage.” Furthermore, noting that the instant application defines “embedding” to encompass the model (see paragraph 6 of the instant application’s specification: “embedding layer is also referred to as an embedding.”), the “parameters” here include an embedding model as disclosed in FIG. 1 and described in § 1, paragraph 1: “The high-dimensional sparse input data first go through an embedding layer to get a low-dimensional embedding; then the embedded results are connected by fully-connected layers.” That is, the parameters as described here refers to the neural network which includes embedding layer (see FIG. 1), any part of which corresponds to a first target embedding. (The Examiner notes that the output of this layer can also be regarded as the embeddings of the instant claim). These parameters are loaded into a GPU (first processor), which is communicatively connected to the CPU as shown in FIG. 2 and comprises the HBM-PS (first memory). Furthermore, the GPU’s operations are performed by a computing core, because a computing core implied as a part of the GPU. See abstract: “All the neural network training computations are contained in GPUs” and the footnote on page 17, which teaches CUDA cores.]
training, by the computing core, a to-be-trained model based on the first target embedding, to obtain an updated to-be-trained model and a second target embedding, wherein the second target embedding is an updated first target embedding; [§ 3.2, paragraph 2 (text after Algorithm 1): “Each training worker pulls the required parameters of its corresponding mini-batch from the HBM-PS (line 12), performs forward and backward propagation to update the parameters (line 13), and interacts with the HBM-PS to update the referenced parameters on other GPUs (line 14). The MEM-PS collects the updates from the HBM-PS (line 16) and dumps infrequently used parameters to the SSD-PS when the MEM-PS does not have sufficient memory (line 17- 18).” Here, the post-update parameters of the neural network correspond to a second target embedding and an updated to-be-trained model.] and
writing, by the computing core, the second target embedding to the first memory. [§ 3.2, paragraph 2 (text after Algorithm 1): “Each training worker pulls the required parameters of its corresponding mini-batch from the HBM-PS (line 12), performs forward and backward propagation to update the parameters (line 13), and interacts with the HBM-PS to update the referenced parameters on other GPUs (line 14). The MEM-PS collects the updates from the HBM-PS (line 16) and dumps infrequently used parameters to the SSD-PS when the MEM-PS does not have sufficient memory (line 17- 18).” That is, since the parameters are collected from the HBM-PS, they are considered to be written to the HBM-PS (first memory) during the course of each of the training process in lines 11-14 of the algorithm.]
As to claim 2, Zhao teaches the method according to claim 1, wherein the training, by the computing core, the to-be-trained model based on the first target embedding comprises:
performing, by the computing core, model training of an Mth batch on the to-be-trained model based on the first target embedding, wherein M is a positive integer greater than 1; [Zhao, Algorithm 1, lines 11-15 is a for-loop with index j from 1 to #minibatch, where j is the index of the Mth batch that is being trained in accordance with the model update in line 13. Here, an arbitrary index corresponds to M and the index of a subsequent iteration for a subsequent batch corresponds to M+1.] and
after the writing, by the computing core, the second target embedding to the first memory, the method further comprises:
obtaining, by the computing core, the second target embedding from the first memory; [Zhao, § 3.2, paragraph 2 (text after Algorithm 1): “Each training worker pulls the required parameters of its corresponding mini-batch from the HBM-PS (line 12), performs forward and backward propagation to update the parameters (line 13).] and
performing, by the computing core, model training of an (M+1)th batch on the updated to-be-trained model based on the second target embedding. [Zhao, § 3.2, paragraph 2 (text after Algorithm 1): “Each training worker pulls the required parameters of its corresponding mini-batch from the HBM-PS (line 12), performs forward and backward propagation to update the parameters (line 13). As noted above, lines 11-15 of the algorithm provides for multiple minibatches. For example, Appendix § A teaches an example of 4 minibatches.]
As to claim 3, Zhao teaches the method according to claim 2, wherein the method further comprises:
after the performing, by the computing core, the model training of the (M+1)th batch on the updated to-be-trained model based on the second target embedding, obtaining a third target embedding, wherein the third target embedding is an updated second target embedding; [As noted in the rejections of the parent claims, Zhao, Algorithm 1 teaches that its method is repeated across multiple minibatches. Therefore, a third iteration of the loop in corresponds to the obtaining of a third target embedding.] and
writing, by the computing core, the third target embedding to the first memory. [As noted in the rejections of the parent claims, Zhao trains the models on HBM-PS, i.e., the high bandwidth memory of the GPU. Therefore, each iteration is written onto the HBM-PS.]
As to claim 4, Zhao teaches the method according to claim 2, wherein the obtaining, by the computing core, a first target embedding from the second memory comprises:
when the first target embedding is an embedding required for model training of the Mth batch and the first target embedding is not stored in the first memory, obtaining, by the first memory, the first target embedding from the second memory; [Zhao, § 3, paragraph 2: “The local MEM-PS loads the local parameters stored on local SSD-PS into the memory and requests other nodes for the remote parameters through the network. After all the referenced parameters are loaded in the memory, these parameters are partitioned and transferred to the HBM-PS in GPUs.”] and
obtaining, by the computing core, the first target embedding from the first memory. [Zhao, abstract: “All the neural network training computations are contained in GPUs.” Zhao, § 3.2, paragraph 2 (text after Algorithm 1): “Each training worker pulls the required parameters of its corresponding mini-batch from the HBM-PS (line 12).” Since the parameter updates are on the model and the model is pulled from the HBM, it is understood that the model is obtained from the memory in order to perform the computations.]
As to claim 5, Zhao teaches the method according to claim 4, wherein the obtaining, by the first memory, the first target embedding from the second memory comprises:
in a process during which the computing core performs model training of an (M−1)th batch on the to-be-trained model, obtaining, by the first memory, the first target embedding from the second memory. [Zhao, § 3, paragraph 2: “The local MEM-PS loads the local parameters stored on local SSD-PS into the memory and requests other nodes for the remote parameters through the network. After all the referenced parameters are loaded in the memory, these parameters are partitioned and transferred to the HBM-PS in GPUs.” The examiner notes that the entire process of Algorithm 1 of Zhao is a process during which the computing core performs model training of an (M−1)th batch on the to-be-trained model, and a previous iteration . The instant claim language does not require a more precise timing scheme of performing any specific training operation and the loading of a match. The Examiner also notes that since the M-1, M, M+1, etc. batches are met by a sequence of minibatches starting from the first batch, and that use of a second, third, etc. batch would be based on the original model parameters used with the first batch.]
As to claim 6, Zhao teaches the method according to claim 4, wherein the method further comprises:
before the obtaining, by the computing core, the first target embedding from the first memory, obtaining, by the computing core, a first vector and a target vector that are from the second processor, wherein the first vector indicates embeddings required for model training of the Mth batch, each element in the first vector indicates one embedding, and different elements indicate different embeddings; [Zhao, § 3, paragraph 2: “After all the referenced parameters are loaded in the memory, these parameters are partitioned and transferred to the HBMPS in GPUs. In order to effectively utilize the limited GPU memory, the parameters are partitioned in a non-overlapped fashion—one parameter is stored only in one GPU.” In Algorithm 1, this is represented in line 6, where “partitions” is a mapping of the parameters to the GPU. As explained in appendix § A, this is mapping (labeled as “partition parameters”) identifies specific parameters and is thus a vector. See also § 4.1, paragraph 1: “Multi-GPU distributed hash table manages the GPU HBMs on the same node and provides a unified interface to the GPU worker threads. All referenced parameters of the current training batch are partitioned and inserted into the local hash table of each GPU.” Furthermore, since the model of Zhao (see FIG. 1) has an embedding layer, a parameter of the model teaches an “embedding” in the absence of further limitation on the characteristics of the embeddings recited in the instant claim or what those embeddings represent.] and
the target vector indicates permutations of the embeddings indicated by the elements in the first vector when model training of the Mth batch is performed, and the embedding indicated by each element appears at least once in the permutations; [Zhao, Appendix § A, paragraph 1: “Here we have 2 GPUs on node1. The working parameters are partitioned and transferred to GPU HBMs. In this example, GPU1 obtains the parameters whose keys are less than or equal to 50—4; 5; 11; 50, and GPU2 takes 53; 56; 61; 87; 98.” That is, the “partitions” also correspond to a target vector, since they identify the subset (permutations) of the parameters that are to be used on each GPU worker.] and
the obtaining, by the computing core, the first target embedding from the first memory comprises:
obtaining, by the computing core, based on the first vector, the embeddings required for model training of the Mth batch from the first memory; [Zhao, § 3, paragraph 2: “The local MEM-PS loads the local parameters stored on local SSD-PS into the memory and requests other nodes for the remote parameters through the network. After all the referenced parameters are loaded in the memory, these parameters are partitioned and transferred to the HBM-PS in GPUs.”] and
determining, by the computing core, based on the target vector and the embeddings required for model training of the Mth batch, the permutations of the embeddings required for model training of the Mth batch. [Zhao, § 3, paragraph 2: “The local MEM-PS loads the local parameters stored on local SSD-PS into the memory and requests other nodes for the remote parameters through the network. After all the referenced parameters are loaded in the memory, these parameters are partitioned and transferred to the HBM-PS in GPUs.”]
As to claim 9, Zhao teaches the method according to claim 1, wherein the first processor is a graphics processing unit (GPU), an embedded neural network processing unit (NPU), or a tensor processing unit (TPU), the first memory is a cache, and the second processor is a central processing unit (CPU). [Zhao, abstract: “We propose a hierarchical workflow that utilizes GPU High-Bandwidth Memory, CPU main memory and SSD as 3-layer hierarchical storage.” Zhao § 3, paragraph 2: “The local MEM-PS loads the local parameters stored on local SSD-PS into the memory and requests other nodes for the remote parameters through the network. After all the referenced parameters are loaded in the memory, these parameters are partitioned and transferred to the HBM-PS in GPUs.” That is, a system with a plurality of GPUs and a CPU is taught in this reference. In regards to the imitation of “the first memory is a cache,” paragraph [0120] defines a cache as broadly encompassing a video memory (“a cache (or referred to as a video memory) (which may be referred to as a first memory in subsequent embodiments)”). Therefore, the HBM (high bandwidth memory) of a GPU, which is a form of video memory, meets the limitation of a cache.]
As to claims 10-15, these claims are directed to an apparatus for performing operations that are the same or substantially the same as those of claims 1-6. Therefore, the rejections made to claims 1-6 are applied to claim 10-15.
Furthermore, Zhao teaches “a model training apparatus, comprising: a first processor, communicatively connected to a second processor, the first processor comprising a computing core and a first memory, the second processor comprising a second memory, and the first processor and the second processor are processors of different types” [§ 7, paragraph 2: “System. We execute the distributed hierarchical GPU parameter server experiments on 4 GPU computing nodes. Each node has 8 cutting-edge 32 GB HBM GPUs, server grade CPUs with 48 cores (96 threads), ~1 TB of memory, ~20 TB RAID-0 NVMe SSDs and a 100 Gb RDMA network adaptor. The nodes in the MPI cluster for the baseline comparison are maintained in the same data center.” Note that the elements of the processors, the computing core, and the first memory are taught by the elements discussed in the rejection of claim 1].
As to claim 18, Zhao teaches the apparatus according to claim 15, wherein the first processor is a graphics processing unit (GPU), an embedded neural network processing unit (NPU), or a tensor processing unit (TPU), the first memory is a cache, and the second processor is a central processing unit (CPU). [Zhao, abstract: “We propose a hierarchical workflow that utilizes GPU High-Bandwidth Memory, CPU main memory and SSD as 3-layer hierarchical storage.” Zhao § 3, paragraph 2: “The local MEM-PS loads the local parameters stored on local SSD-PS into the memory and requests other nodes for the remote parameters through the network. After all the referenced parameters are loaded in the memory, these parameters are partitioned and transferred to the HBM-PS in GPUs.” That is, a system with a plurality of GPUs and a CPU is taught in this reference. In regards to the imitation of “the first memory is a cache,” paragraph [0120] defines a cache as broadly encompassing a video memory (“a cache (or referred to as a video memory) (which may be referred to as a first memory in subsequent embodiments)”). Therefore, the HBM (high bandwidth memory) of a GPU, which is a form of video memory, meets the limitation of a cache.]
As to claim 19, Zhao teaches a model training apparatus, wherein the apparatus comprises a memory and a processor, [§ 7, paragraph 2: “System. We execute the distributed hierarchical GPU parameter server experiments on 4 GPU computing nodes. Each node has 8 cutting-edge 32 GB HBM GPUs, server grade CPUs with 48 cores (96 threads), ~1 TB of memory, ~20 TB RAID-0 NVMe SSDs and a 100 Gb RDMA network adaptor. The nodes in the MPI cluster for the baseline comparison are maintained in the same data center.”] code is stored in the memory, and the processor is configured to obtain the code and perform the method according to claim 1. [Since the method taught in Zhao is an automated process performed using computers, the instant limitation of memory comprising code to perform the method of claim 1 is implicitly disclosed by Zhao.]
As to claim 20, Zhao teaches a non-transitory computer storage medium, wherein one or more instructions are stored in the computer storage medium, and when the one or more instructions are executed by one or more computers, [Since the method taught in Zhao is an automated process performed using computers, the instant limitation of a computer storage medium comprising instructions to perform the method of claim 1 is implicitly disclosed by Zhao.] the one or more computers are enabled to perform the method according to claim 1. [§ 7, paragraph 2: “System. We execute the distributed hierarchical GPU parameter server experiments on 4 GPU computing nodes. Each node has 8 cutting-edge 32 GB HBM GPUs, server grade CPUs with 48 cores (96 threads), ~1 TB of memory, ~20 TB RAID-0 NVMe SSDs and a 100 Gb RDMA network adaptor. The nodes in the MPI cluster for the baseline comparison are maintained in the same data center.”]
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 7-8 and 16-17 are rejected under 35 U.S.C. 103 as being unpatentable over Zhao in view of Chapelle et al. (US 2013/0290223 A1) (“Chapelle”).
As to claim 7, Zhao teaches the method according to claim 3, wherein before the training, by the computing core, the to-be-trained model based on the first target embedding, the method further comprises:
obtaining, by the computing core, the third target embedding from a third memory of a third processor, wherein the third target embedding and the first target embedding are embeddings required for model training of the Mth batch, and the first processor and the third processor are processors of a same type; [Zhao, § 3.2, paragraph 2 (text after Algorithm 1): “Each training worker pulls the required parameters of its corresponding mini-batch from the HBM-PS (line 12), performs forward and backward propagation to update the parameters (line 13), and interacts with the HBM-PS to update the referenced parameters on other GPUs (line 14). The MEM-PS collects the updates from the HBM-PS (line 16) and dumps infrequently used parameters to the SSD-PS when the MEM-PS does not have sufficient memory (line 17- 18).” Zhao, § 3.2, paragraph 3: “HBM-PS is distributed in the High-Bandwidth Memory (HBM) across multiple GPUs. Comparing with the conventional distributed parameter servers, workers in GPUs can directly request and update parameters in the HBM without transferring data between GPU memory and CPU memory.”] and
the training, by the computing core, a to-be-trained model based on the first target embedding comprises:
processing, by the computing core, the first target embedding and the third target embedding by using the to-be-trained model, […] [Zhao, § 3.2, paragraph 2 (text after Algorithm 1): “Each training worker pulls the required parameters of its corresponding mini-batch from the HBM-PS (line 12), performs forward and backward propagation to update the parameters (line 13), and interacts with the HBM-PS to update the referenced parameters on other GPUs (line 14). The MEM-PS collects the updates from the HBM-PS (line 16) and dumps infrequently used parameters to the SSD-PS when the MEM-PS does not have sufficient memory (line 17- 18). That is, since the parameters are shared in line 14, lines 12-13 in a subsequent iteration are used in a subsequent iteration to train the model, which includes the embedding layer.] […]
updating, by the computing core, the to-be-trained model and the first target embedding […] [Zhao, § 3.2, paragraph 2 (text after Algorithm 1): “Each training worker pulls the required parameters of its corresponding mini-batch from the HBM-PS (line 12), performs forward and backward propagation to update the parameters (line 13), and interacts with the HBM-PS to update the referenced parameters on other GPUs (line 14).]
Zaho does not teach the limitation of “to obtain a target output, and determining a first gradient based on the target output” and the limitation that the update is “based on the target gradient.”
Li teaches “to obtain a target output, and determining a first gradient based on the target output;” [[0005]-[0006]: “Distributed machine learning is one of the distributed applications where much work focuses on the problem in the form… where xi is the feature vector of the i-th training sample, yi is the label, w is the linear predictor (parameters), l is a loss function, and R is a regularizer.” That is, in this equation, the other argument in the loss function, which is a function of the weights and input, constitutes a target output. Furthermore, in more detail [0060] (“Algorithm 1”) teaches calculating the gradient g. In general, [0060] (Algorithm 1) is extended to an multi-node algorithm in [0061] (Algorithm 2). In this algorithm over T iterations, each node calculates gk, which is “the (local batch) gradient of examples on node k.”] and
updating “based on the first gradient.” [In general, the weights are updated based on the gradient g as shown in Algorithm 1. In the mulita-node context, [0061] teaches: “In this setting, each node performs an online pass over its data, and then weights are averaged according to Equation (2).” This also applies in the multi-node extension. See [0058]: “Concretely, node k maintains a local weight vector wk and a diagonal matrix Gk based on the gradients in the adaptive gradient updates (see Algorithm 1).”]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Zhao with the teachings of Chapelle by implementing the aggregation technique as taught by Chappelle, so as to arrive at the claimed invention. The motivation would have been to provide a method for parallel learning on large datasets (see Chapelle, [0033]: “efficiently and effectively parallel learning very large datasets, including for example, trillions of features, billions of training samples, and millions of parameters, with a good predictive accuracy.”).
As to claim 8, the combination of Zhao and Chapelle teaches the method according to claim 7, as set forth above.
Chapelle further teaches wherein the determining the first gradient based on the target output comprises: determining the first gradient and a second gradient based on the target output; [[0048]: “The AllReducing module 708 is also configured to transmit the local parameter to at least one connected node in accordance with the network topology. In this example, operation nodes B, C transmit their local parameters B, C to operation node A in accordance with the tree network topology. The AllReducing module 708 is also responsible for merging local parameter with one or more local parameters received from one or more connected nodes in accordance with the network topology. In this example, the AllReducing module 708-1 of operation node A sums up the local parameter A calculated by the local machine learning module 706-1 and the local parameters B, C received from operation nodes B, C. The merged local parameter “sum(ABC)” is then transmitted to another connected operation node (not shown) that is higher in the hierarchy. The merged local parameter “sum(ABC)” is then transmitted to another connected operation node (not shown) that is higher in the hierarchy. Eventually, at the end of the reduce stage in each iteration, an aggregated parameter is calculated by merging local parameters calculated by each operation node in accordance with the network topology, as noted above.” Note that the “local parameter” is a gradient, as described in [0041] and [0044]. Therefore, in this case, the local gradient is a first gradient, and a second gradient is the combination of the local parameter and the received gradient.] and
after the determining the first gradient and the second gradient based on the target output, the method further comprises: transferring the second gradient to a computing core of the third processor that updates the third target embedding based on the second gradient. [As noted in the parts cited above, the merged parameter is sent to a further downstream node (analogous to another processor or GPU), and this gradient is used to update the “local weight vector wk” described in [0058].]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of Zhao and Chappelle, including the teachings discussed above, so as to have also arrived at the claimed invention of the instant dependent claim. The motivation for doing so is covered by the motivation given for the teachings of Chappelle in the rejection of the parent dependent claim.
As to claims 16-17, these claims recite further limitations that are the same or substantially the same as those of claims 7-8. Therefore, the rejections made to claim 7-8 are applied to claims 16-17.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. The following documents depict the ordinary skill in the art.
Ma et al. (US20240037378A1) teaches partitioning an embedding table.
Li et al., “Scaling Distributed Machine Learning with the Parameter Server,” Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation, October 6–8, 2014, Broomfield, CO teaches conventional techniques in multi-worker systems.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to YAO DAVID HUANG whose telephone number is (571)270-1764. The examiner can normally be reached Monday - Friday 9:00 am - 5:30 pm.
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, Miranda Huang can be reached at (571) 270-7092. 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.
/Y.D.H./Examiner, Art Unit 2124
/MIRANDA M HUANG/ Supervisory Patent Examiner, Art Unit 2124
Prosecution Insights