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 .
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 § 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-20 are rejected under 35 U.S.C. 103 as being unpatentable over Naumov et al. (“Deep-Learning Recommendation Model for Personalization and Recommendation Systems”, published 05/31/2019), hereinafter Naumov; in view of Jangda et al. (“Breaking the Computation and Communication Abstraction Barrier in Distributed Machine Learning Workloads”, published 02/22/2022), hereinafter Jangda; in further view of Georganas et al. (“Communication Avoiding and Overlapping for Numerial Linear Algebra”, published 02/25/2013), hereinafter Georganas. Naumov and Georganas were cited in previous Office Actions.
Regarding Claim 1, Naumov teaches An electronic device, comprising:
one or more data producing nodes and one or more data-consuming nodes communicatively coupled by a communication interface, the one or more data producing nodes and the one or more data consuming nodes each comprising circuitry configured to process instances of input data through a model (Naumov: “The experiments are performed on the Big Basin platform with Dual Socket Intel Xeon 6138 CPU@2.00GHzand eight Nvidia Tesla V100 16GB GPUs” [Section 5. Experiments]; “The size of the embeddings makes it prohibitive to use data parallelism since it requires replicating large embeddings on every device. In many cases, this memory constraint necessitates the distribution of the model across multiple devices to be able satisfy memory capacity requirements.” [Section 3. Parallelism]; “In particular, DLRM consists of both a bottom MLP for processing dense features consisting of three hidden layers with 512, 256 and 64 nodes, respectively, and a top MLP consisting of two hidden layers with 512 and 256 nodes.” [Section 5.1 Model Accuracy on Public Data Sets]), wherein each data-producing node is configured to:
generate a respective block of data for use by one or more of the data-consuming nodes in processing the instances of input data through the model (Naumov: “Recall that DLRM accepts continuous and categorical features as inputs. The former can be modeled by generating a vector of random numbers using either a uniform or normal (Gaussian) distributions with the numpy.random package rand or randn calls with default parameters. Then a mini-batch of inputs can be obtained by generating a matrix where each row corresponds to an element in the mini-batch.” [Section 4.1 Random]); and
communicate a block of data to at least one of the data-consuming nodes via the communication interface (Naumov: “At the end of the embedding lookup, each device has a vector for the embedding tables resident on those devices for all the samples in the mini-batch, which needs to be split along the mini-batch dimension and communicated to the appropriate devices, as shown in Fig. 2. Neither PyTorch nor Caffe2 provide native support for model parallelism; therefore, we have implemented it by explicitly mapping the embedding operators (nn.EmbeddingBag for PyTorch, SparseLengthSum for Caffe2) to different devices. Then personalized all-to-all communication is implemented using the butterfly shuffle operator, which appropriately slices the resulting embedding vectors and transfers them to the target devices.” [Section 3. Parallelism]); and
wherein each data consuming node comprises circuitry configured to:
receive, via the communication interface, the corresponding respective blocks of data from the one or more data-producing nodes, the respective blocks corresponding to the same subset of the instances of input data (Naumov: “Neither PyTorch nor Caffe2 provide native support for model parallelism; therefore, we have implemented it by explicitly mapping the embedding operators (nn.EmbeddingBag for PyTorch, SparseLengthSum for Caffe2) to different devices. Then personalized all-to-all communication is implemented using the butterfly shuffle operator, which appropriately slices the resulting embedding vectors and transfers them to the target devices. In the current version, these transfers are explicit copies, but we intend to further optimize this using the available communication primitives (such as all-gather and send-recv).” [Section 3. Parallelism]); and
perform one or more model operations using the received block of data (Georganas: “We note that for the data parallel MLPs, the parameter updates in the backward pass are accu mulated with an allreduce3 and applied to the replicated parameters on each device [12] in a synchronous fashion, ensuring the updated parameters on each device are consistent before every iteration.” [Section 3. Parallelism]).
However, Naumov fails to expressly disclose to generate a respective block of data, the respective block of data being logically divided into a plurality of portions; communicate a first portion of the respective block of data to at least one of the data-consuming nodes; before communication of all remaining portions of the respective block of data to the at least one data-consuming node is complete, generate and communicate one or more additional portions of the respective block of data; receive corresponding portions of respective blocks of data from one or more data producing nodes, the corresponding portions corresponding to the same subset of the instances of input data; and before all portions of the respective blocks of data have been received by the data-consuming node, perform one or more model operations using the received corresponding portions for the same subset of the instances of input data, while the one or more data producing nodes continue to generate and communicate the one or more additional portions of the respective blocks of data.
In the same field of endeavor, Jangda teaches to generate a respective block of data, the respective block of data being logically divided into a plurality of portions (Jangda: “Figure 9 shows how the fine-grained overlapping of CoCoNet addresses this issue using the example of a MatMul followed by a ring AllReduce. First, it schedules the MatMul kernel (based on CUTLASS [4]) to produce chunks in the same order as the AllReduce consumes them. Here, the nth rank sends chunks in the order starting from the nth chunk. Hence, the MatMul kernel on nth rank produces chunks in the same order.” [Section 5.3 Overlapping of Communication and Computation];
communicate a first portion of the respective block of data to at least one of the data-consuming nodes (Jangda: “Second, CoCoNet invokes both kernels only once on different streams and synchronizes the AllReduce with the MatMul using an efficient fine-grained spin-lock on a memory buffer to ensure that the AllReduce wakes up as soon as the MatMul produces a chunk.” [Section 5.3 Overlapping of Communication and Computation]);
before communication of all remaining portions of the respective block of data to the at least one data-consuming node is complete, generate and communicate one or more additional portions of the respective block of data (Jangda: “The example in Figure 9 works as follows. At T = 1, all ranks invoke MatMul and AllReduce kernels. On rank 0, after computing chunk 0, the MatMul kernel wakes the AllReduce kernel at T = 2 , which starts communicating chunk 0. While on rank 1, at T = 2 the MatMul kernel wakes the AllReduce kernel to communicate chunk 1. Concurrently, both MatMul kernels compute their corresponding next chunk. At T = 3, MatMul kernels finished computing chunk 1 on rank 0 and chunk 2 on rank 1 and wakes up corresponding AllReduce kernels to communicate these chunks. This process continues until all chunks are processed.” [Section 5.3 Overlapping of Communication and Computation]); and
perform model operations while the one or more data producing nodes continue to generate and communicate the one or more additional portions of the respective blocks of data (Jangda: “” []).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have incorporated to generate a respective block of data, the respective block of data being logically divided into a plurality of portions; communicate a first portion of the respective block of data to at least one of the data-consuming nodes; and before communication of all remaining portions of the respective block of data to the at least one data-consuming node is complete, generate and communicate one or more additional portions of the respective block of data, as taught by Jangda to the device of Naumov because both of these systems are directed towards communication and computation within a distributed machine learning system. In making this combination and overlapping multiple communication operations such that they are running concurrently with each other and model computation, it would allow for the system of Naumov to “decrease memory bandwidth usage” and “fully utilize both network and compute resources”, allowing for the model to speed up training and/or inference time (Jangda: [Section 1. Introduction]).
Naumov and Jangda still fail to expressly disclose to receive corresponding portions of respective blocks of data from one or more data producing nodes, the corresponding portions corresponding to the same subset of the instances of input data; and before all portions of the respective blocks of data have been received by the data-consuming node, perform one or more model operations using the received corresponding portions for the same subset of the instances of input data.
In the same field of endeavor, Georganas teaches to receive corresponding portions of respective blocks of data from one or more data producing nodes, the corresponding portions corresponding to the same subset of the instances of input data (Georganas: “Performing computation by blocks reduces the amount of data that must be moved between processors, as well as in a memory hierarchy. 2D algorithms distribute matrices in blocks among processes and communicate on a 2D grid of p processors. SUMMA performs communication with row and column broadcasts on this 2D grid.” [Section II.A. Matrix Multiplication]; “As in the triangular solve, the bottleneck of the 2D Cholesky factorization is the update of the trailing matrix A22 =A22−L21⋅LT21 (described in Section II-C). This update can be decomposed in two phases: first, the required subblocks of L21 and LT21 are received via two consecutive broadcasts and then dgemm operations follow to update the corresponding blocks of A22.” [Section VII.A. Overlapping communication and computation in Cholesky]); and
before all portions of the respective blocks of data have been received by the data-consuming node, perform one or more model operations using the received corresponding portions for the same subset of the instances of input data (Georganas: “As explained in Section II-A, the SUMMA algorithm performs the matrix product based on broadcasts and outer products. The main part of the 2D and 2.5D algorithm consists of a loop where each thread takes part in two broadcasts (related to the grid row and column, respectively) and performs one BLAS matrix product (dgemm) per iteration. We develop new versions of both the 2D and 2.5D algorithms that overlap communication and computation by starting the broadcast of the next iteration while the dgemm of the current iteration is being performed.” [Section IV.A. Overlapping communication and computation]; “Initially we factorize the first column of blocks and we execute two back to back broadcasts to transfer it to the involved UPC threads. Note that we store the received blocks in auxiliary buffers. Then, instead of updating the whole trailing matrix, we update only the second column of blocks with dgemms and continue with its factorization. This slight modification creates a pipeline and provides an overlapping opportunity at the next step. While we broadcast the second column of factorized blocks, we can simultaneously update the rest of the trailing matrix using the buffered first column of factorized blocks. This part of the trailing matrix is depicted with yellow color in Figure 7 and the two back to back broadcasts are depicted with blue arrows. As soon as the two overlapped operations synchronize, we update with dgemms only the third column of blocks in respect to the second factorized column (which is just received), then we factorize it and the same overlapping schedule remains active until the whole matrix is factorized.” [Section VII.A. Overlapping communication and computation in Cholesky]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have incorporated to receive corresponding portions of respective blocks of data from one or more data producing nodes, the corresponding portions corresponding to the same subset of the instances of input data; and before all portions of the respective blocks of data have been received by the data-consuming node, perform one or more model operations using the received corresponding portions for the same subset of the instances of input data, as taught by Georganas to the device of Naumov and Jangda because both of these systems are directed towards minimizing communication cost through communication and computation overlapping. In making this combination and receiving portions of data sent by the data producing nodes and performing model operations concurrently with the communication of additional portions of data, it would allow the system of Naumov and Jangda to “minimize communication cost” by “lower[ing] the per-message cost” while “chang[ing] neither volume nor the number of messages” (Georganas: [Section I. Introduction]).
Regarding Claim 2, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein the data consuming node is configured to perform the one or more model operations after receiving, from each of the plurality of data producing nodes, a portion of a respective block of data for processing the given part of the input data and before receiving all portions of the respective blocks of data for processing the given part of the input data (Georganas: “As explained in Section II-A, the SUMMA algorithm performs the matrix product based on broadcasts and outer products. The main part of the 2D and 2.5D algorithm consists of a loop where each thread takes part in two broadcasts (related to the grid row and column, respectively) and performs one BLAS matrix product (dgemm) per iteration. We develop new versions of both the 2D and 2.5D algorithms that overlap communication and computation by starting the broadcast of the next iteration while the dgemm of the current iteration is being performed.” [Section IV.A. Overlapping communication and computation]; “Initially we factorize the first column of blocks and we execute two back to back broadcasts to transfer it to the involved UPC threads. Note that we store the received blocks in auxiliary buffers. Then, instead of updating the whole trailing matrix, we update only the second column of blocks with dgemms and continue with its factorization. This slight modification creates a pipeline and provides an overlapping opportunity at the next step. While we broadcast the second column of factorized blocks, we can simultaneously update the rest of the trailing matrix using the buffered first column of factorized blocks. This part of the trailing matrix is depicted with yellow color in Figure 7 and the two back to back broadcasts are depicted with blue arrows. As soon as the two overlapped operations synchronize, we update with dgemms only the third column of blocks in respect to the second factorized column (which is just received), then we factorize it and the same overlapping schedule remains active until the whole matrix is factorized.” [Section VII.A. Overlapping communication and computation in Cholesky]).
Regarding Claim 3, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein the one or more model operations include matrix multiplication performed using data contained in the received portions without requiring other portions of the respective blocks of data (Georganas: “As explained in Section II-A, the SUMMA algorithm performs the matrix product based on broadcasts and outer products. The main part of the 2D and 2.5D algorithm consists of a loop where each thread takes part in two broadcasts (related to the grid row and column, respectively) and performs one BLAS matrix product (dgemm) per iteration. We develop new versions of both the 2D and 2.5D algorithms that overlap communication and computation by starting the broadcast of the next iteration while the dgemm of the current iteration is being performed.” [Section IV.A. Overlapping communication and computation]; “We study classical matrix multiplication, which computes all n3 multiplications, though the reduced-complexity Strassen's algorithm can also minimize communication and outperform the classical algorithm in a high-performance setting. Since each of the n3 multiplications can be done independently, parallelization is very simple to load balance and schedule.” [Section II.A. Matrix Multiplication]).
Regarding Claim 4, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein each data producing node is configured to initiate communication of the first portion and, while communication of the first portion is ongoing, obtain the next portion of the respective block of data (Jangda: “The example in Figure 9 works as follows. At T = 1, all ranks invoke MatMul and AllReduce kernels. On rank 0, after computing chunk 0, the MatMul kernel wakes the AllReduce kernel at T = 2 , which starts communicating chunk 0. While on rank 1, at T = 2 the MatMul kernel wakes the AllReduce kernel to communicate chunk 1. Concurrently, both MatMul kernels compute their corresponding next chunk. At T = 3, MatMul kernels finished computing chunk 1 on rank 0 and chunk 2 on rank 1 and wakes up corresponding AllReduce kernels to communicate these chunks. This process continues until all chunks are processed.” [Section 5.3 Overlapping of Communication and Computation]).
Regarding Claim 5, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein a number of portions in each block of data is set based on one or more properties of the respective blocks of data, the data consuming node, or the data producing nodes (Georganas: “Performing computation by blocks reduces the amount of data that must be moved between processors, as well as in a memory hierarchy. 2D algorithms distribute matrices in blocks among processes and communicate on a 2D grid of p processors. SUMMA performs communication with row and column broadcasts on this 2D grid. While SUMMA can flexibly be formulated in terms of rank-1 updates, to minimize messages it is best to block these updates into bundles of up to n/√p.” [Section II.A. Matrix multiplication]; “The memory requirements of each algorithm and the overheads included by their optimizations should be taken into account in order to find the most suitable option for each scenario. In 2D SUMMA, each UPC thread must keep one square block of size n/√p-by-n/√p per matrix.” [Section IV.B. Implementation Details]).
Regarding Claim 6, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein the model is a deep learning recommendation model (DLRM), and each data producing node stores a subset of embedding tables for the model in a local memory of that node (Naumov: “we develop a state-of-the-art deep learning recommendation model (DLRM) and provide its implementation in both PyTorch and Caffe2 frameworks.” [Abstract]; “At the end of the embedding lookup, each device has a vector for the embedding tables resident on those devices for all the samples in the mini-batch, which needs to be split along the mini-batch dimension and communicated to the appropriate devices, as shown in Fig. 2.” [Section 3. Parallelism]).
Regarding Claim 7, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein the data consuming node is configured to combine lookup data received in the portions with results from a bottom multilayer perceptron to generate inputs for a top multilayer perceptron of a deep learning recommendation model (DLRM) (Naumov: Naumov: “we develop a state-of-the-art deep learning recommendation model (DLRM) and provide its implementation in both PyTorch and Caffe2 frameworks.” [Abstract]; “At the end of the embedding lookup, each device has a vector for the embedding tables resident on those devices for all the samples in the mini-batch, which needs to be split along the mini-batch dimension and communicated to the appropriate devices, as shown in Fig. 2.” [Section 3. Parallelism]; “This is done by taking the dot product between all pairs of embedding vectors and processed dense features. These dot products are concatenated with the original processed dense features and post-processed with another MLP (the top or output MLP) (5), and fed into a sigmoid function to give a probability.” [Section 2.2. DLRM Architecture]).
Regarding Claim 8, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein the received portions are independently usable for the one or more operations without requiring other portions of the respective blocks of data (Georganas: “We study classical matrix multiplication, which computes all n3 multiplications, though the reduced-complexity Strassen's algorithm can also minimize communication and outperform the classical algorithm in a high-performance setting. Since each of the n3 multiplications can be done independently, parallelization is very simple to load balance and schedule.” [Section II.A. Matrix Multiplication]).
Regarding Claim 9, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein the blocks of data include lookup data communicated in an all-to-all exchange from the data producing nodes to the data consuming node (Naumov: “Since model parallelism has been used to distribute the embeddings across devices, this requires a personalized all-to-all communication [12]. At the end of the embedding lookup, each device has a vector for the embedding tables resident on those devices for all the samples in the mini-batch, which needs to be split along the mini-batch dimension and communicated to the appropriate devices, as shown in Fig. 2.” [Section 3. Parallelism]).
Regarding Claim 10, Naumov, Jangda, and Georganas teach the device of Claim 1, wherein the operations include training the model, and the communicated data is communicated using an all-reduce communication (Naumov: “We note that for the data parallel MLPs, the parameter updates in the backward pass are accumulated with an allreduce and applied to the replicated parameters on each device [12] in a synchronous fashion, ensuring the updated parameters on each device are consistent before every iteration.” [Section 3. Parallelism]; Jangda: “In data parallelism, communication involves an AllReduce of gradients among all ranks. The output is used by the optimizer to update the model parameters.” [Section 6.1 Data Parallel Training]).
Regarding Claims 11-13 and 15-20, they are method claims that correspond with the device of Claims 1-3 and 5-10. Therefore, they are rejected for the same reasons as Claims 1-3 and 5-10 above.
Regarding Claim 14, Naumov, Jangda, and Georganas teach the method of Claim 11, further comprising allocating computational resources including workgroups for performing one or more of: obtaining the respective block of data, communicating the first portion, or performing the one or more model operations (Jangda: “CoCoNet extends the concept of a tensor in machine learning frameworks from a single device data into distributed forms. Be sides item datatype, like FP32 and FP16, and shape, a CoCoNet tensor also includes a layout that describes the distributed allocation of tensor’s data across a set of ranks.” [Section 2.1 Tensor Layout]; “Overlapping of computation and communication has been studied in the context of executing stencil computations in a distributed system. These works use non-blocking MPI operations to communicate data and simultaneously perform computations on CPUs. A similar approach for overlapping of computation and communication operations for a GPU workload would involve dividing all operations into sub-operations and ensuring dependency between sub-operations using CUDA streams.” [Section 5.3 Overlapping of Communication and Computation]).
Response to Arguments
The Examiner acknowledges the Applicant’s amendments to Claims 1-4, 8-14, and 17-19
Applicant's arguments, filed 05/18/2026, regarding the rejection of Claims 1-20 under 35 U.S.C. § 112(b) have been fully considered and are persuasive. The rejection has been withdrawn.
Applicant's arguments, filed 05/18/2026, regarding the rejection of Claims 1-20 under 35 U.S.C. § 101 have been fully considered and are persuasive. The rejection has been withdrawn.
Applicant's arguments, filed 05/18/2026, regarding the rejection of Claims 1-20 under 35 U.S.C. § 103 have been fully considered and are found moot in light of the new grounds of rejection (see rejection above).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Kalamkar et al. (“Optimizing Deep Learning Recommender Systems Training on CPU Cluster Architectures”) discusses and analyzes novel optimization and parallelization techniques for the various operators in DLRM.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MEGAN E HWANG whose telephone number is (703)756-1377. The examiner can normally be reached Monday-Thursday 10:00AM-7:30PM ET.
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, Jennifer Welch can be reached at (571) 272-7212. 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.
/M.E.H./Examiner, Art Unit 2143
/JENNIFER N WELCH/Supervisory Patent Examiner, Art Unit 2143
Prosecution Insights