DETAILED ACTION
Claims 1-20 are pending.
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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 11/09/2025 in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statements are being considered by the examiner.
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 1-2, 4-9, 11-16, and 18-20 are rejected under 35 U.S.C. 103 as being unpatentable over Fine-tuning giant neural networks on commodity hardware with automatic pipeline model parallelism, Saar Eliad et al. (hereinafter “Eliad”) in view of Yang (US 2019/0220321 A1) in further view of Raumann et al. (US 2022/0198117 A1).
Eliad and Raumann were cited previously.
Regarding claim 1, Eliad teaches the invention substantially as claimed including a system comprising:
a processor (Section 5.1: 8 RTX2080-Ti GPUs); and
a memory comprising computer program code (section 5.1 "Experimental setup": "We use a server with 8 RTX2080-Ti GPUs each with 11GB memory’), the memory and the computer program code configured to cause the processor to:
obtain a workload including a graph of operations to be performed on a physical device array, the physical device array having logical processing engine (PE) units associated therewith (section 4 "A computational graph of the DNN model... . The number of stages is determined according to the GPU assignment as discussed in detail below" section 4.1: "We therefore posit that relaxing the DNN topology constraints and allowing smaller, multipole partitions per GPU may improve load balance, while still affording communication computation overlap ... The Mixed-pipe partitioning algorithm receives a computational graph of a neural network ...");
partition the graph of operations into subgraphs by minimizing a quantity of the subgraphs and maximizing resource utilization per subgraph (section 4: "A computational graph of the DNN model is decomposed into topologically sorted subgraphs ..." section 4.1: "We therefore posit that relaxing the DNN topology constraints and allowing smaller, multiple partitions per GPU may improve load balance, while still affording communication computation overlap". section 4.1.1: "Coarsening": "The graph is coarsened by contracting edges and merging their nodes to reduce its size ... L is chosen at a sweet spot of the tradeoff between large L, which enables better load balancing in Step 2, and small. L, which is better staleness-wise’. The coarsening step is considered to minimize the quantity of subgraphs, while still respecting other constraints. section 4.1.2: "Load balancing": "The assignment to GPUs can be seen as a classical multiprocessor scheduling problem [26]. While the original problem does not target the pipeline execution setup, in practice, and when communications do not add overhead (the CCO property), the optimal multiprocessor schedule is the one with a balanced distribution of tasks among the processors, meeting the goal of the pipeline assignment... Therefore ...stages are sorted in a descending order of their computation load, and are assigned to the next least busy GPU with enough memory to run them".);
generate a logical mapping of the subgraphs to the logical PE units using features of the subgraph and the logical PE units associated with a logical structure of the physical device array (section 4: "Profiling. Each basic block is profiled to determine its memory consumption and execution time for each of its computational tasks, i.e., forward pass, recomputation (see Section 4.3) and backward pass. Aggregation of these values determines the block’s memory and computing requirements used in the block-to-GPU assignment step".; section 4.1: "The Mixed-pipe partitioning algorithm receives a computational graph of a neural network, which specifies the (traced) basic computational blocks annotated with their memory, communication, and computing requirements. Then, partitioning proceeds in three steps as follows’.);
assign the logical mapping of the subgraphs to physical PE units of the physical device array at least by minimizing network traffic across the physical PE units (section 1, page 383, left column: "Essentially, FTPipe generalizes the pipeline execution of former approaches to dataflow-aware execution, avoiding unnecessary communications and allowing more parallelism ... We present the fine-grain partitioning scheme which relaxes the model topology constraints when scheduling DNN computations on GPUs, thereby vastly improving load balance across the workers without additional communication overheads"; section 3.2 "Low communication volume" section 4: '"FTPipe employs several partitioning method's ... (d) Metis [24], a general graph partitioning scheme that optimizes communications under load balancing constraints’; section 4.1: "As a result, such partitioning implicitly optimizes for reduced communications across GPUs ...".); and
perform operations of the subgraphs using the physical PE units to which the logical mapping is assigned (The operations are effectively performed on the GPUs according to the optimization/partitioning method, see e.g. figure 6.).
While Eliad teaches graph partitioning, Eliad does not teach using integer linear programming (ILP) to minimize a quantity of subgraphs while maximizing resource utilization under a constraint of resources available per device of the physical device array, wherein each subgraph is sized to be executed using a device of the physical device array; and
tiling factors, of the logical PE units, the tiling factors comprising a block size of data.
However, Yang teaches Abstract: receive a workload provisioning request from a user, wherein the workload provisioning request comprises information associated with a workload, a network topology, and a plurality of potential hardware choices for deploying the workload over the network topology; receive hardware performance information for the plurality of potential hardware choices from one or more hardware providers; generate a task dependency graph associated with the workload; generate a device connectivity graph associated with the network topology…provision a plurality of resources for deploying the workload over the network topology, wherein the plurality of resources are provisioned based on the one or more hardware choices. Further Yang teaches using integer linear programming (ILP) to minimize a quantity of subgraphs while maximizing resource utilization under a constraint of resources available per device of the physical device array, wherein each subgraph is sized to be executed using a device of the physical device array ([0037]; [0041]; [0054] As noted above, the scheduling algorithm 223 uses path selection DAG-to-DAG scheduling to derive the optimal hardware recommendations for the workload. In some embodiments, for example, path selection DAG-to-DAG scheduling may be implemented using integer linear programming (ILP) techniques. For example, the workload scheduling problem can be reduced to the following ILP problem:
minimize: c.sup.Tx (objective term)
subject to: Ax≤b (inequality constraint)
Cx=d (equality constraint)
and: x∈{0,1}.sup.K (binary constraint).
This ILP model can be used to determine an optimal schedule that satisfies a specified objective (e.g., minimizing bandwidth utilization, minimizing hardware costs, maximizing performance), while also adhering to various constraints (e.g., workload resource requirements, device and network resource capacities, mapping constraints). For example, in this ILP model, x represents the collection of possible schedules (e.g., paths in the graphs), K is the length of x, the objective term represents the scheduling objective to be minimized, and the inequality/equality constraints represent the additional constraints on the scheduling objective.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teachings of Eliad with the teachings of Yang to utilize ILP for workload allocation among edge devices. The modification would have been motivated by the desire of ensuring getting optimal graph solutions meeting specific constraints.
Eliad nor Yang explicitly teach tiling factors, of the logical PE units, the tiling factors comprising a block size of data.
However, Raumann teaches a system for executing a graph partitioned across a plurality of reconfigurable computing units includes a processing node that has a first computing unit reconfigurable at a first level of configuration granularity and a second computing unit reconfigurable at a second, finer, level of configuration granularity. Further, Raumann teaches tiling factors of the logical PE units, the tiling factors comprising a block size of data ([0114]; [0117]; [0219] Application 2302 is a dataflow graph with a set of processing modules (e.g., processing modules 1 to 5). Examples of the processing modules include neurons or layers of deep neural networks. The runtime processor 1832 is configured to partition the set of processing modules into a first subset of processing modules 2304a and a second subset of processing modules 2304b. The runtime processor 1832 is configured to execute configuration files 2322a for the first subset of processing modules 2304a on the first reconfigurable processor (e.g., RP N from the RPs 142a on the processing node 1). The runtime processor 1832 is configured to execute configuration files 2322b for the second subset of processing modules 2304b on the second reconfigurable processor (e.g., RP N from the RPs 142n on the processing node n).; [0239] FIG. 28 is a simplified block diagram 2800 of components of a CGRA (Coarse-Grained Reconfigurable Architecture) processor. In this example, the CGRA processor has two tiles (Tile 1, Tile2). The tile comprises an array of configurable units connected to a bus system, including array level networks in this example. An array of configurable units (e.g., 2790, FIG. 27) in the tile includes computation units in hardware or by configuration of reconfigurable components, which are configured with the virtualization logic 2797.; [0120] The host sender buffers 212a and the host receiver buffers 202a can be of size 8 bytes, 16 bytes, 32 bytes, 64 bytes, 128 bytes, 256 bytes, and so on, or any convenient size appropriate for the transfer of data between the host processor, the network interface controllers, and the reconfigurable processors. [0240-43]; [0381]; [0384]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teachings of Raumann with the teachings of Eliad and Yang to select reconfigurable processors/tiles to process partitioned portions of a graph based on their configuration. The modification would have been motivated by the desire of ensuring that the appropriate processor is selected for execution.
Regarding claim 2, Eliad teaches wherein partitioning the graph of operations into subgraphs includes minimizing the quantity of subgraphs while constrained by one or more of the following constraints:
a constraint that every operation of the graph of operations is assigned to one subgraph, a constraint that every subgraph is continuous, a maximum quantity of PEs constraint, a maximum quantity of memory constraint (section 4.1.1: "The graph is coarsened by contracting edges and merging their nodes to reduce its size (typically thousands of nodes) to L non-input stages where each stage fits in GPU memory."), and a maximum quantity of bandwidth constraint.
Regarding claim 4, Raumann teaches wherein assigning the logical mapping of the subgraph to the physical PE units includes minimizing network traffic across the physical PE units while constrained by one or more of the following constraints:
a constraint requiring logical vertices of the logical mapping to be mapped to physical nodes of the physical device array;
a constraint requiring logical inputs of the logical mapping to be mapped to physical inputs of the physical device array;
a constraint requiring logical outputs of the logical mapping to be mapped to physical outputs of the physical device array;
a constraint requiring logical links of the logical mapping to be mapped to physical links of the physical device array; and
a constraint requiring logical cascade links of the logical mapping to be mapped to physical cascade links of the physical device array (Abstract).
Regarding claim 5, Yang teaches wherein a graph profile of the graph of operations, an architecture description describing features of the physical device array, and a latency target are used as input for the partitioning, the generating and the assigning ([0179] In one example embodiment of a system, the processor to select, based on the task dependency graph and the device connectivity graph, the one or more hardware choices from the plurality of potential hardware choices is further to: identify a deployment objective for the workload, wherein the deployment objective comprises minimizing network resource utilization, minimizing hardware resource utilization, minimizing hardware costs, or minimizing workload latency; identify a plurality of deployment constraints for the workload, wherein the plurality of deployment constraints are identified based at least partially on the task dependency graph and the device connectivity graph; and identify the one or more hardware choices that optimize the deployment objective and satisfy the plurality of deployment constraints, wherein the one or more hardware choices are identified from the plurality of potential hardware choices based on the task dependency graph and the device connectivity graph.; [0180-181]).
Regarding claim 6, Eliad teaches wherein assigning the logical mapping of the subgraph to the physical PE units is performed by:
solving a coarse-grained routing problem associated with the logical mapping (4.1.1. The graph is coarsened by contracting edges and merging their nodes to reduce its size (typically thousands of nodes) to L non-input stages where each stage fits in GPU memory; 4.1.2);
applying placement and routing constraints to a fine-grained assignment problem associated with the logical mapping using the solved coarse-grained routing problem (4.1.3 We perform fine-grain tuning of the load balance achieved in Step 2. First, the L stages are un-coarsened into their basic blocks. Then, within each pipeline stage, we greedily find blocks which, if moved to an adjacent stage in the pipeline, can improve the throughput, or lower communication or improve load balance (given also the memory constraints).);
solving the fine-grained assignment problem associated with the logical mapping using the applied placement and routing constraints (4.2 execution of fine-tuning tasks); and
assigning the logical mapping to the physical PE units using a solution of the solved fine-grained assignment problem (Section 5. FTPipe has two main components: (a) an automatic neural network partitioning and assignment which builds a data-flow, and (b) a pipelined data-flow execution runtime that executes the partitioned model on GPUs and automatically handles work scheduling and inter-GPU communications.).
Regarding claim 7, Eliad teaches wherein the workload is a deep learning artificial intelligence (AI) workload (Abstract: neural networks).
Regarding claim 8, it is a method type claim having similar limitations as claim 1 above. Therefore, it is rejected under the same rationale above.
Regarding claim 9, it is a method type claim having similar limitations as claim 2 above. Therefore, it is rejected under the same rationale above.
Regarding claim 11, it is a method type claim having similar limitations as claim 4 above. Therefore, it is rejected under the same rationale above.
Regarding claim 12, it is a method type claim having similar limitations as claim 1 above. Therefore, it is rejected under the same rationale above.
Regarding claim 13, it is a method type claim having similar limitations as claim 6 above. Therefore, it is rejected under the same rationale above.
Regarding claim 14, it is a method type claim having similar limitations as claim 7 above. Therefore, it is rejected under the same rationale above.
Regarding claim 15, it is a media/product type claim having similar limitations as claim 1+7 above. Therefore, it is rejected under the same rationale above.
Regarding claim 16, it is a media/product type claim having similar limitations as claim 2 above. Therefore, it is rejected under the same rationale above.
Regarding claim 18, it is a media/product type claim having similar limitations as claim 4 above. Therefore, it is rejected under the same rationale above.
Regarding claim 19, it is a media/product type claim having similar limitations as claim 5 above. Therefore, it is rejected under the same rationale above.
Regarding claim 20, it is a media/product type claim having similar limitations as claim 6 above. Therefore, it is rejected under the same rationale above.
Allowable Subject Matter
Claims 3, 10, are 17 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.
Response to Arguments
Applicant’s arguments with respect to claims 1-20 have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument.
Conclusion
Applicant's amendment necessitated the new grounds of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JORGE A CHU JOY-DAVILA whose telephone number is (571)270-0692. The examiner can normally be reached Monday-Friday, 6:00am-5:00pm.
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, Aimee J Li can be reached at (571)272-4169. 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.
/JORGE A CHU JOY-DAVILA/Primary Examiner, Art Unit 2195