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 .
Detailed Action
This action is in response to the claims filed 12/28/2023:
Claims 1 – 6 are pending.
Claim 1 is independent.
Specification
The disclosure is objected to because of the following informalities:
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-6 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claim 1, "the entire layers of a model" lacks antecedent basis. Claim 1 does not introduce layers or a model before reciting "the entire layers of a model". "The entire layers" is also grammatically unclear. "partitioning an entire model including a plurality of layers into segments" is recommended.
Regarding claim 1, "the last layers" lacks antecedent basis. "Last layers" is not recommended in isolation to overcome the antecedent basis issue because "last" is a relative term without a relative basis for comparison. Examiner recommends explicitly defining "last layers".
Regarding claim 1, "the last segments of the first segments" is indefinite. "The last segments" lacks antecedent basis and "last segments of the first segments" appears directly contradictory. It's unclear if this is a typo intended to be "the last layers of the first segments", however, "last layers of first segments" is similarly indefinite because "last" is a relative term without a relative basis for comparison. In the interest of further examination this is interpreted as "removes, from the memory, output values of at least one of the first segments".
Regarding claim 1, "the assigned rank immediately follows the rank of the first segments" is indefinite. This is non-standard language with multiple contradictory interpretations. The most obvious interpretation would be that a highest rank is the highest numerical rank and lower ranks follow in descending order. However, the instant specification directly contradicts this in a particular embodiment ([¶0043] "according to an embodiment of the present disclosure [...] Ranks are assigned in ascending order, starting from 1, where 1 is the highest rank"). Examiner asserts that there are an infinite number of alternate interpretations of "immediately follows" making the scope of the claim indefinite. In the interest of further examination "immediately follows" is interpreted as following in ascending or descending order.
Regarding claim 1, “changing the values stored in memory, […], in the memory simultaneously” is grammatically indefinite. The phrase “which removes […] and stores” has an unstable antecedent and subject. Grammatically, “which” could refer to at least three things: “changing”, “the values stored in the memory” (nonsensical but grammatically possible because “which” immediately follows the noun phrase), or “the memory”. “In the memory simultaneously” is also grammatically ambiguous. The phrase “in the memory simultaneously” sits at the end of a long clause, it could modify: “stores output values of the last layers of second segments”, “both removing and storing”, “changing the values stored in the memory”, or the condition that the second-segment outputs, among themselves, are stored simultaneously. In the interest of further examination “in the memory simultaneously” is interpreted as modifying “changing the values stored in the memory”.
Regarding claim 3, "all possible cases of subsets" is indefinite. Neither the claims or instant specification limit the space of "possible cases" such that one of ordinary skill in the art would readily recognize the scope of "all possible cases of subsets". In the interest of further examination the claim is interpreted as "all possible subsets".
Regarding claim 5, "adjusts their ranks to come after the ranks assigned" is indefinite. First, neither the claims or instant specification specify what is meant by "come after": ascending, descending, or something else altogether. Second, the claim appears to use two different orderings simultaneously: Reverse segment traversal order and rank numbering order, either of which would satisfy the claim language while being contradictory to the other. In the interest of further examination reverse segment traversal is interpreted as adjusting ranks to come after ranks assigned earlier.
Claim Rejections - 35 USC § 101
101 Rejection
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.
Claim 6 is rejected under 35 USC § 101 because the claimed invention is directed to non-statutory subject matter.
Regarding claim 6, claim 6 is directed towards non-statutory subject matter, “signal per se”. Claim 6 recites “a recording medium readable by a digital processing device” however, there is no indication that the recording medium cannot be transitory. Therefore, claim 6 is rejected as signal-per-se.
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 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, 2, 3, and 6 are rejected under U.S.C. §103 as being anticipated by Zhao (“VPIPE: A Virtualized Acceleration System for Achieving Efficient and Scalable Pipeline Parallel DNN Training”, 2021).
PNG
media_image1.png
608
1270
media_image1.png
Greyscale
FIG. 5 of Zhao
Regarding claim 1, Zhao teaches A recalculation method of backpropagation for selecting layers to store outputs in a memory, the method comprising: ([p. 1] "a pipeline parallel system injects multiple batches of inputs and overlaps their forward and backward pass executions, forming a pipeline" [p. 2] "(GPipe [19] and PipeMare [59]) discards all activation tensors in the forward passes and recomputes them in the backward passes [...] To achieve G1, instead of GPipe’s all-recompute strategy, VPIPE computes a hybrid plan of both swap and recompute for all layers on each stage" [p. 10] "VPIPE’s recompute leverages PyTorch’s checkpoint library, which is a builtin library for recomputing activations. A major implementation obstacle for on-demand recompute is to change the training statement at runtime. In VPIPE, we used python’s builtin feature exec stmt, which takes a piece of statement as input and executes the statement, to modify a stage’s execution statement at runtime and on demand decide whether to recompute a layer’s activation" Zhao teaches that when R=1 the tensor is dropped and recomputed/recalculated by the backward pass. vPipe chooses default, swap, or recompute for each layer's dependent tensor and recompute means the activation is not kept in memory)
partitioning the entire layers of a model including a plurality of layers into segments; ([p. 1] "Pipeline parallelism is a promising approach to train large DNNs with lots of layers on multiple GPUs, where the DNN is partitioned into multiple stages, each containing a number of layers" See also FIG. 5)
assigning ranks to the segments; ([p. 7] "Vpipe's swap and recompute algorithm (Algorithm 2) works as follows. For each stage, the algorithm takes a set of layers, a memory limit M, PCIe bandwidth P, stage rank (p-k), tfwd and tbwd of this stage as input" See also Algorithm 2 Input)
storing outputs of the last layers of first segments with the highest assigned rank among the segments in the memory simultaneously; ([p. 7] "Vpipe's swap and recompute algorithm (Algorithm 2) works as follows. For each stage, the algorithm takes a set of layers, a memory limit M, PCIe bandwidth P, stage rank (p-k), tfwd and tbwd of this stage as input" [p. 9] "Given a new input batch k, for q layers {l1,l2,…,l1} in stage n of a training pipeline (0 ≤ n < p, where p is the number of stages and the number of simultaneously injected input batches)" Zhao teaches simultaneous activation storage in ranked stages where the "highest assigned rank" maps to the stage-rank endpoint in the pipeline where the algorithm uses stage rank (p-k) and different stages maintain different numbers of dependent activation copies)
changing the values stored in the memory, which removes, from the memory, output values of the last segments of the first segments stored in the memory after recalculation of backpropagation is performed on the first segments and stores output values of the last layers of second segments, of which the assigned rank immediately follows the rank of the first segments, in the memory simultaneously; and ([p. 5] "R = 1 means the tensor will be dropped and recomputed by the backward pass" [p. 10] "In VPIPE, we used python’s builtin feature exec stmt, which takes a piece of statement as input and executes the statement, to modify a stage’s execution statement at runtime and on demand decide whether to recompute a layer’s activation" [p. 5] "S=1 means the tensor will be proactively swapped to CPU memory and swapped back to GPU before usage" [p. 7 Algorithm 2] "space = space - rank * m^activation" Zhao changes memory contents by applying per-layer tensor policies. For example, a tensor may stay in GPU memory, be swapped to CPU and layer swapped back, or be dropped and recomputed by the backward pass. These policies rely on rank * mactivation, meaning the ranked stage position directly affects how many activation copies must be accommodated or removed from GPU memory.)
repeating the changing of the values stored in the memory until output values of the last layers of third segments with the lowest assigned rank are stored in the memory simultaneously. ([p. 7] " Input: layers In a stage […] foreach l in layers do: […] l.op=Recompute […] l.op=Swap […] space=space−rank∗mactivation" Zhao explicitly iterates all layers and ranks. The "lowest assigned rank" maps to the endpoint of the ordered p-stage pipeline).
Regarding claim 2, Zhao teaches The method of claim 1, wherein the partitioning of the entire layers of the model into segments partitions the entire layers of the model into segments (Zhao [p. 1] "Pipeline parallelism is a promising approach to train large DNNs with lots of layers on multiple GPUs, where the DNN is partitioned into multiple stages, each containing a number of layers" See also FIG. 5)
so that recalculation cost is minimized based on the number of floating-point operations per second (FLOPs) of each of the entire layers of the model. (Zhao [p. 6] "For the recompute, our goal is to select the cheapest layer with maximized memory saving to recompute" In Zhao the recompute/swap framework is explicitly designed to avoid GPU memory pressure by deciding whether to keep activations on GPU, swap them, or recompute them. To evaluate that tradeoff Zhao explicitly models compute time, the compute side driven by the amount of floating-point work associated with the layer. For a GPU resident DNN layer, the cost is fundamentally driven by the amount of floating-point operations required by that layer.).
Regarding claim 3, Zhao teaches The method of claim 2, wherein the partitioning of the entire layers of the model into segments generates all possible cases of subsets for the entire layers of the model (Zhao [p. 1] "Pipeline parallelism is a promising approach to train large DNNs with lots of layers on multiple GPUs, where the DNN is partitioned into multiple stages, each containing a number of layers" See also FIG. 5)
and partitions the entire layers of the model into segments so that recalculation cost calculated for each subset is minimized.(Zhao [p. 6] "For the recompute, our goal is to select the cheapest layer with maximized memory saving to recompute").
Regarding claim 6, Zhao teaches A recording medium readable by a digital processing device, in which a program of commands executed by the digital processing device to provide recalculation of backpropagation for selecting layers to store outputs in memory is implemented, recording a program for executing a method of claim 1 in a computer.(Zhao [p. 9] "VPIPE’s design leverages the imperative features from Py Torch. The current popular deep learning frameworks are typically based on either imperative or declarative program ming. The imperative programs are similar to Python or C++ programs, which perform computations during the execution. PyTorch adopts it as the default and only execution mode. Overall, VPIPE is currently implemented by modifying 2782 LoC to PyTorch").
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 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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 4 and 5 are rejected under U.S.C. §103 as being unpatentable over the combination of Zhao and Steiner (“OLLA: Optimizing the Lifetime and Location of Arrays to Reduce the Memory Usage of Neural Networks”, 2022).
Regarding claim 4, Zhao teaches and, if the memory allocation is successful, retains the ranks of the segments.(Zhao [p. 7] "For the rest of the layers, vPipe keeps them by default" [p. 5] "D=1 means the tensor by default resides in the GPU memory" [p. 7 Algorithm 2] "while memConsume(layers) > M do").
However, Zhao doesn't explicitly teach The method of claim 1, wherein the assigning of the ranks to the segments repeats the last layers of the respective segments in reverse order when recalculation of backpropagation is performed, allocates memory in reverse order of the output values of the last layers of the respective segments at each repetition, .
Steiner, in the same field of endeavor, teaches The method of claim 1, wherein the assigning of the ranks to the segments repeats the last layers of the respective segments in reverse order when recalculation of backpropagation is performed, allocates memory in reverse order of the output values of the last layers of the respective segments at each repetition, ([p. 7] "DNN gradients are computed in reverse order of the activations. Since an activation is preserved in memory until the corresponding gradient computation takes place, the earlier an activation tensor is allocated the later it is freed. We place these tensors in memory in a manner that maximizes the usability of the unallocated memory").
Zhao as well as Steiner are directed towards [...]. Therefore, Zhao as well as Steiner are analogous art in the same field of endeavor. It would have been obvious before the effective filing date of the claimed invention to combine the teachings of Zhao with the teachings of Steiner by [...]. Steiner provides as additional motivation for combination [...].
Regarding claim 5, the combination of Zhao, and Steiner teaches The method of claim 4, wherein, if memory allocation fails, (Zhao [p. 7] "Until the PCIe is full, VPIPE selects tensors according to their memory saving gains to be asynchronously swapped (line 13-16). After that, if the memory limit is still reached, VPIPE chooses whether to swap or recompute an activation based on their swap/recompute cost and memory saving gain (line 17-19)." Zhao explicitly models per-GPU training memory must not exceed physical memory limit M and Algorithm 2 enters a memory pressure loop when memConsume(layers)>M. That is the operational equivalent of a failed attempt to keep the relevant tensors allocated in GPU memory)
the assigning of the ranks to the segments removes all memory allocations for output values of the last layers of the individual segments which have succeeded in the memory allocation, (Zhao [p. 5] "R = 1 means the tensor will be dropped and recomputed by the backward pass" [p. 10] "In VPIPE, we used python’s builtin feature exec stmt, which takes a piece of statement as input and executes the statement, to modify a stage’s execution statement at runtime and on demand decide whether to recompute a layer’s activation" [p. 5] "S=1 means the tensor will be proactively swapped to CPU memory and swapped back to GPU before usage" [p. 7 Algorithm 2] "Input: layers In a stage […] foreach l in layers do: […] l.op=Recompute […] l.op=Swap […] space = space - rank * m^activation" Zhao gives each stage a rank input (p-k) and uses that rank in Algorithm 2's memory-management logic. When the stage exceeds memory M, Zhao changes layer tensor states from default GPU residence to swap or recompute. That functionally removes the allocation from GPU memory (swap moves it to CPU and recompute drops it so it can be recreated later))
allocates memory again to the output values of the last layers of the individual segments in reverse order, starting from the output value of the last layer of the segment which has encountered a memory allocation failure,(Steiner [p. 7] "DNN gradients are computed in reverse order of the activations. Since an activation is preserved in memory until the corresponding gradient computation takes place, the earlier an activation tensor is allocated the later it is freed. We place these tensors in memory in a manner that maximizes the usability of the unallocated memory")
and for those segments which have encountered a memory allocation failure, adjusts their ranks to come after the ranks assigned to the segments which have succeeded in memory allocation.(Zhao [p. 6] "We decompose the master problem into two subproblems. First, we assume that Varp is constant, and each stage locally finds a swap and recompute plan (Varsr) depending on its GPU resource to minimize the objective function (3). Second, we assume that Varsr is constant, and stages should be repartitioned (i.e., find an optimal VarP) to minimize (3). Algorithm 1 shows out decomposed algorithm by iteratively resolve these two sub-problems").
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Huang (“GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism”, 2019) is directed towards a hierarchical pipeline parallelism method for neural networks.
Shen (“NASPipe: High Performance and Reproducible Pipeline Parallel Supernet Training via Causal Synchronous Parallelism”, 2022) is also directed towards a hierarchical pipeline parallelism method for neural networks.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SIDNEY VINCENT BOSTWICK whose telephone number is (571)272-4720. The examiner can normally be reached M-F 7:30am-5:00pm EST.
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 on (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.
/SIDNEY VINCENT BOSTWICK/Examiner, Art Unit 2124
Prosecution Insights