DETAILED ACTION
Claims 1-20 are presented for examination. This action is made in response to the claims filed June 8, 2023.
Claims 4, 15, and 20 are objected to.
Claim 17 is being interpreted under 35 USC 112(f)
Claims 1-20 are rejected under 35 USC 101 and 35 USC 115 for failing to correctly state inventorship.
Claims 1-20 are rejected under 35 USC 101 as ineligible subject matter.
Claims 1-6, 8-14, and 17-20 are rejected under 35 USC 103 as unpatentable over Shah in view of Lan.
Claim 7 is rejected under 35 USC 103 as unpatentable over Shah in view of Lan and Vielma.
Claims 15-16 are rejected under 35 USC 103 as unpatentable over Shah in view of Lan and Li.
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 Objections
Claims 4, 15, and 20 are objected to because of the following informalities:
Claim 4 recites “and/or.” In its broadest reasonable sense, this is equivalent to “or.” This should be amended for clarity/conciseness.
Claim 15 recites, “sun of demands.” This appears to be a typo. For purposes of examination, this will be interpreted to read “sum of demands.”
Claim 20 recites, “[…] wherein the model is further configured represent […].” This appears to be a typo.
Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: input engine and output engine in claim 17.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 101
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 therefore, subject to the conditions and requirements of this title.
Inventorship
Claims 1-20 are rejected under 35 USC 101 and 35 USC 115 for incorrect inventorship of record. As expressed in 35 USC 101, “[w]hoever invents or discovers,” claims are only valid if asserted by an inventor or discoverer. The Applicant filed a White Paper publication on the subject matter of the application (See the Liu reference of record), and the names on the paper differ from the stated inventors on the Application. Most importantly, the first author (the author typically responsible for most of the research), Liu, has been omitted as an inventor. More specifically, the patent names the following inventors: Arzani, Kakarla, Castro, Kandula, Maleki, Marshall. The paper names the following authors: Liu (Xuting), Arzani, Kakarla, Zhao, Liu (Vincent), Kandula, and Marshall. The Applicant can overcome this by a declaration on the record that Xuting Liu and Vincent Liu did not contribute to any alleged inventive features of the claims 1-20 and that Maleki did contribute to at least one alleged inventive feature of the claims 1-20, signed by someone with evidentiary first-hand/personal knowledge of the alleged inventive contributions of the people listed on the paper and the patent to the claims 1-20.
For example, a demonstration of mapping of independent claim 1 to the Liu white paper is as follows:
1. A method for scheduling a coordinated transfer of data among a plurality of processor nodes on a network, the method comprising: (Liu Page 18, 2.2 Relationship with TE Solutions “Multi-commodity flow problems in TE route specific demands (with a given source and destination) in a way that meets the capacity constraints of the network. Experts usually model TE in one of two forms: a path [13, 15] or edge formulation [4]. We focus on the edge formulation here, but our discussion also applies to the path form. – Method for scheduling a coordinated transfer of data among a plurality of processor nodes on a network.)
operating a multi-commodity flow model subject to a plurality of predetermined constraints, the model being configured to- : (Liu Page 18, 2.2 Relationship with TE Solutions “Multi-commodity _ow problems in TE route specific demands (with a given source and destination) in a way that meets the capacity constraints of the network.” – Operating a multi-commodity flow model subject to a plurality of predetermined constraints.)
receive as input a set of demands defining, for each of the plurality of processor nodes, an amount of data to be transferred to that processor node, (Liu Page 18, 2.2 Relationship with TE Solutions “In its most basic format, the edge formulation takes a set of demands _ (represented as a matrix matching source and destination nodes (B, 3))” - Receive as input a set of demands defining, for each of the plurality of processor nodes, an amount of data to be transferred to that processor node)
assign a plurality of paths linking the plurality of processor nodes, and (Liu Page 18, 2.2 Relationship with TE Solutions “and the topology where each link (i,j) has capacity ) Ti,j as input, and it outputs how much of each demand should go over each link.” – Assign a plurality of paths linking the plurality of processor nodes.)
emit a schedule for transfer of the data along the plurality of paths so as to minimize a predetermined cost function, wherein the schedule comprises at least one store-and-forward operation and at least one copy operation. (Liu Page 18, 2.2 Relationship with TE Solutions “The objective. Our optimization objective is to finish the transfer as quickly as possible. We can encode this as follows:
PNG
media_image1.png
75
549
media_image1.png
Greyscale
The objective gives fewer rewards as k increases: the objective improves if the schedule satisfies the demand as soon as possible. We now have a complete optimization model. – Cost Function optimization to emit a schedule. Page 26, 7 Related Work “Our solution supports unsustained demands, store-and-forward, and copy. Our work builds on prior work both in network tra_c engineering and in collective optimization” – Schedule includes copy and store-and-forward operarions.)
Independent claims 17 and 18 have similar features/mappings to independent claim 1.
Claim 2: Page 31, The objective. “So first, we need to automatically compute this additional payoff. To do this, we add logical edges to the graph that allow nodes to form a clique. We assign a weight to each of these edges,”
Claim 3: Page 19, Figure 3 Description: “Results are for a proprietary topology from a public cloud with 2 chassis, 8 GPUs, and 40 edges, where the " of intra-chassis and GPU-switch links are 0.6 and 0.75 µs, respectively.”
Claim 4: Page 21, Modeling switches “Traffic pays the α delay cost of two links to cross a switch: one from the node to the switch and one from the switch to the node.” - α is an element of the cost function and measures time delay to the cost of completion. Page 21, The objective “The objective gives fewer rewards as k increases: the objective improves if the schedule satisfies the demand as soon as possible. We now have a complete optimization model.” – k is an element of the cost function which represents the number of epochs undergone, which is indicative of the time it takes to optimize. Page 21, The objective “To avoid such silly cases, we can do one of two things: (a) we can either add a term to the objective to discourage unnecessary flows” – The cost function includes a metric of processor disuse.
Claim 5: Page 25, Right Column, Second Paragraph “We use Gurobi’s early-stop for AllGather demands to improve TE-CCL’s ability to scale: this does not materially impact the quality of TE-CCL’s solution — even with an aggressive optimality gap threshold of 30%” – Optimality gap guarantee.
Claim 6: Page 29, A. INITIALIZATION AND TERMINATION CONSTRAINTS “We introduced the main constraints for the MILP and LP formulations in §3 and §4.1. But we need to add a few additional constraints to initialize and terminate them.” MILP formulation
Claim 7: Page 17, Right Column, Second Paragraph “For certain collectives, we can further scale our solution by converting the MILP into an LP by removing all integer variables. In the general case, we improve scalability by partitioning the problem in time, using a technique inspired by the A∗ [12] algorithm from robotics.” Convert MILP to LP by removing integers
Claim 8: Page 21, Modeling switches “Traffic pays the α delay cost of two links to cross a switch: one from the node to the switch and one from the switch to the node.” - α is an element of the cost function and measures time delay to the cost of completion. Page 21, The objective “The objective gives fewer rewards as k increases: the objective improves if the schedule satisfies the demand as soon as possible. We now have a complete optimization model.” – k is an element of the cost function which represents the number of epochs undergone, which is indicative of the time it takes to optimize.
Claim 9: Page 18 “Recent collective communication optimizers seek automation.
To use these libraries, applications specify (1) the “collective,” i.e., a relationship between a set of GPU’s input and output buffers; (2) the “demand matrix,” i.e., the amount of data to be sent between each input buffer and output buffer; (3) the topology, i.e., the connectivity, latency, and capacity of each link; and (4) an objective.” Page 23, Handling stragglers. “We note that our formulation also includes coarse-grained mechanisms that help account for stragglers. For instance, we can manage the latency variations that lead to stragglers” See Also FIG. 2 – Each link has different latency, representing differences in latency of nodes.
Claim 10: Page 27, ALLREDUCE implementation. “TE-CCL supports AllReduce implicitly through the combination of AllToAll and AllGather operations. We can also directly solve for the AllReduce workload by utilizing multiple demand matrices, each representing an intermediate stage of the operation. However, we acknowledge that our model does not account for the compute cost in this case, and we plan to address this in future work.” – ALLREDUCE, ALLTOALL, and ALLGATHER operations supported.
Claim 11: Page 22, 4.1 Scaling by Converting to an LP “TE-CCL supports AllReduce implicitly through the combination of AllToAll and AllGather operations. We can also directly solve for the AllReduce workload by utilizing multiple demand matrices, each representing an intermediate stage of the operation. However, we acknowledge that our model does not account for the compute cost in this case, and we plan to address this in future work.” – Flow conservation and destination constraints. Page 17, Left Column, Third Paragraph “We credit TE-CCL’s formulation, scalability, and performance to our ability to borrow ideas from scalable production TE systems. TE solutions give us a model of the physical problem (i.e., the flow conservation constraints and the capacity constraints) and make it easier to reason about a formulation that is otherwise difficult [23, 33].” – Flow conservation and capacity constraints.
Claim 12: Page 29, B MODELING LIMITED BUFFERS “In the MILP. To model limited buffers in the MILP we need to change the buffer constraints to track which chunks to remove from the buffer and in which epoch. Hence, we introduce a new variable […] which encodes whether we should remove chunk 2 from node B from the buffer […] The buffer constraints become […]” – Flow-conservation constraints include buffer constraints.
Claim 13: Page 21, The objective “To avoid such silly cases, we can do one of two things: (a) we can either add a term to the objective to discourage unnecessary flows” – The cost function includes a metric to discourage unnecessary flows.
Claim 14: Page 29, The A* TECHNIQUE “In the A* based approach, we split the problem into multiple time partitions (or rounds). Our goal in each round is to get the chunks closer to the destination. We solve each of these rounds sequentially
until we satisfy all the demands.” – Problem split into time partitions. Page 31, The objective. “The objective. We now need to motivate the optimization in each round to get the chunks closer to the destination (while making it even more profitable to satisfy the demand fully).” See Also the equations in this section that follow the quote. – Cost function maximizes progress toward completion of the coordinated transfer of data within a current partition.
Claim 15: Page 23, Use in multi-tenant clusters. “we have to change the demand
matrix to the sum of the demands across all collectives.” – The set of demands comprises a sum of demands across a plurality of collectives in a multi-tenant cluster on the network.
Claim 16: Page 17, Right Column, Third Paragraph “As part of TE-CCL, we are also able to algorithmically account for multi-tenant and heterogeneous topologies, which are critical for cloud-scale GPU clusters.” Page 23, Use in multi-tenant clusters. “The formulation can be further updated to support priorities across tenants (i.e., prioritizing one tenant’s completion time over the others) if we add a separate buffer and read variable for each tenant. We can then add the priorities to the objective function. This change increases the number of variables in the MILP. For efficiency, we may have to use A* in this case, but doing so would not impact the quality of the solution compared to when we solve
a single tenant problem at the same scale.” – Cost function in A* accounts for differences in demand prioritization.
Claim 19: Page 27, Conclusion “Many collective demands (e.g., AllGather) consist of sources that send the same data to multiple destinations (multi-cast traffic) and benefit substantially from the ability to copy and send data at intermediate nodes.” – Multicasting to multiple nodes, each of which has a GPU.
Claim 20: Page 27, Handling failures. “This allows the network to naturally adapt to failures of inter-chassis links and switches. We simplify this in our model by replacing the detailed topology with a single big-switch abstraction, ignoring the internal topology of the Clos.” - The model is further configured to represent a plurality of switches configured to connect different blocks of GPUs on the network
Subject Matter Eligibility
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed subject matter is directed to an abstract idea without significantly more. The claims recite mental processes that are capable of being performed in the mind and/or with the aid of pen and paper and mathematical equations. Any computer elements are merely generic computing elements. Further, the process steps recited by the claims neither result in any practical application, nor recite any additional limitations that integrate the abstract idea into a practical application. Also, as demonstrated by the references on record, the elements of the claims are longstanding practices, which were conducted manually prior to the computer becoming a common tool. This illustrates that the specified features of the claims, represent evaluations, mental processes, abstract ideas. Further, the specified features of the claims are also mathematical expressions, mathematical concepts, abstract ideas.
Independent Claims
Claims 1, 17, and 18
Claim 17 (Statutory Category – Machine)
Step 2A – Prong 1: Judicial Exception Recited?
Yes, the claims recite mental processes, which are abstract ideas.
Claim 17 recites:
[…] operate within a plurality of predetermined constraints and configured to- assign a plurality of paths linking the plurality of GPUs, and […] emit a schedule for transfer of the data along the plurality of paths so as to minimize a predetermined cost function, wherein the schedule comprises at least one store-and-forward operation and at least one copy operation; and […] output the schedule, together with an optimality-gap guarantee for the schedule.
(Mental Process – Using a model to determine a schedule for routing elements based on constraints is practically performable in the mind or with the aid of pen and paper, so it is an evaluation, a mental process, an abstract idea.)
Claim 17 recites mental processes, which are abstract ideas.
Claim 17 recites an abstract idea.
Step 2A – Prong 2: Integrated into a Practical Application?
No.
Claim 17 recites the following additional limitations:
furnish a set of demands defining, for each of the plurality of GPUs, an amount of data to be transferred to that GPU;
receive the set of demands as input from the input engine,
This is mere data gathering akin to the MPEP 2106.05(g) examples: “i. Performing clinical tests on individuals to obtain input for an equation” “v. Consulting and updating an activity log, Ultramercial,” “i. Limiting a database index to XML tags” “iii. Selecting information, based on types of information and availability of information in a power-grid environment, for collection, analysis and display.” Accordingly, this is extra-solution activity and fails to integrate the abstract ideas into a practical application.
A communication scheduler for a machine-learning collective of a plurality of graphics processing unit (GPU) clusters arranged on a network, the communication scheduler comprising:
an input engine configured to […]
a multi-commodity flow model formulated to […]
an output engine configured to […]
These are generic computing elements recited at a high level, which, under MPEP 2106.05(f), fail to integrate the abstract idea into a practical application.
Should it be found that emitting and/or outputting is not an element of the abstract idea, these are insignificant extra-solution activity similar to the MPEP 2106.05(g) examples: “a printer that is used to output a report of fraudulent transactions, which is recited in a claim to a computer programmed to analyze and manipulate information about credit card transactions in order to detect whether the transactions were fraudulent.” “iii. Selecting information, based on types of information and availability of information in a power-grid environment, for collection, analysis and display” “ii. Printing or downloading generated menus”
Also, the quantities the data in the claims represent merely limit the abstract idea to a technological environment, which, under MPEP 2106.05(h), fail to integrate the abstract idea into a practical application.
Claim 17 fails to recite any additional limitations that integrate the abstract idea into a practical application.
Claim 17 is directed to the abstract idea.
Step 2B: Claim provides an Inventive Concept?
No.
Claim 17 recites the following additional limitations:
furnish a set of demands defining, for each of the plurality of GPUs, an amount of data to be transferred to that GPU;
receive the set of demands as input from the input engine,
This is well-understood, routine, and conventional (WURC) activity akin to the MPEP 2106.05(d) examples: “iii. Electronic recordkeeping” “iv. Storing and retrieving information in memory” “v. Electronically scanning or extracting data from a physical document” “i. Determining the level of a biomarker in blood by any means “ “v. Analyzing DNA to provide sequence information or detect allelic variants” “vi. Arranging a hierarchy of groups, sorting information, eliminating less restrictive pricing information and determining the price.” Because this limitation is WURC and insignificant extra-solution activity, under MPEP 2106.05(d) and 2106.05(g), the limitation fails to combine with the other elements of the claim to provide significantly more than the abstract idea that would confer an inventive concept.
A communication scheduler for a machine-learning collective of a plurality of graphics processing unit (GPU) clusters arranged on a network, the communication scheduler comprising:
an input engine configured to […]
a multi-commodity flow model formulated to […]
an output engine configured to […]
The are generic computing elements recited at a high level, which, under MPEP 2106.05(f), fail to combine with the other elements of the claim to provide significantly more than the abstract idea that would confer an inventive concept.
Should it be found that emitting and/or outputting is not an element of the abstract idea, these are WURC similar to the MPEP 2106.05(d) examples: “i. Receiving or transmitting data over a network” “iii. Electronic recordkeeping” “iv. Storing and retrieving information in memory” “vi. Arranging a hierarchy of groups, sorting information, eliminating less restrictive pricing information and determining the price”
Also, the quantities the data in the claims represent merely limit the abstract idea to a technological environment, which, under MPEP 2106.05(h), fail to combine with the other elements of the claim to provide significantly more than the abstract idea that would confer an inventive concept.
The additional limitations fail to combine with the other elements of the claim to provide significantly more than the abstract idea that would confer an inventive concept.
Claim 17 is ineligible.
Claim 1 (Statutory Category – Process)
Claim 1 recites the method of claim 17. The method is rejected for at least the same reasons as claim 17.
Accordingly claim 1 is ineligible.
Claim 18 (Statutory Category – Process)
Step 2A – Prong 1: Judicial Exception Recited?
Yes, the claims recite mental processes, which are abstract ideas.
Claim 18 recites:
A method for scheduling a coordinated transfer of a plurality of weighting factors of a machine-learning model among a plurality of graphics processing units (GPUs) on a network, the method comprising: operating a multi-commodity flow model subject to a plurality of predetermined constraints, the model being configured to – receive as input a set of demands defining, for each of the plurality of GPUs, an amount of data to be transferred to that GPU, assign a plurality of paths linking the plurality of GPUs, and emit a schedule for transfer of the data along the plurality of paths so as to minimize a predetermined cost function, wherein the schedule comprises at least one store-and-forward operation and at least one copy operation, each employing cache memory of the plurality of GPUs.
(Mental Process – Using a model to determine a schedule for routing elements is practically performable in the mind or with the aid of pen and paper, so it is an evaluation, a mental process, an abstract idea. Note that this claim does not do anything other than make a schedule.)
Claim 18 recites mental processes, which are abstract ideas.
Claim 18 recites an abstract idea.
Step 2A – Prong 2: Integrated into a Practical Application?
No.
Claim 18 recites the following additional limitations:
receive as input a set of demands defining, for each of the plurality of GPUs, an amount of data to be transferred to that GPU,
This is mere data gathering akin to the MPEP 2106.05(g) examples: “i. Performing clinical tests on individuals to obtain input for an equation” “v. Consulting and updating an activity log, Ultramercial,” “i. Limiting a database index to XML tags” “iii. Selecting information, based on types of information and availability of information in a power-grid environment, for collection, analysis and display.” Accordingly, this is extra-solution activity and fails to integrate the abstract ideas into a practical application.
Should it be found that emitting and/or outputting is not an element of the abstract idea, these are insignificant extra-solution activity similar to the MPEP 2106.05(g) examples: “a printer that is used to output a report of fraudulent transactions, which is recited in a claim to a computer programmed to analyze and manipulate information about credit card transactions in order to detect whether the transactions were fraudulent.” “iii. Selecting information, based on types of information and availability of information in a power-grid environment, for collection, analysis and display” “ii. Printing or downloading generated menus”
Also, the quantities the data in the claims represent merely limit the abstract idea to a technological environment, which, under MPEP 2106.05(h), fail to integrate the abstract idea into a practical application.
Claim 18 fails to recite any additional limitations that integrate the abstract idea into a practical application.
Claim 18 is directed to the abstract idea.
Step 2B: Claim provides an Inventive Concept?
No.
Claim 18 recites the following additional limitations:
receive as input a set of demands defining, for each of the plurality of GPUs, an amount of data to be transferred to that GPU,
This is well-understood, routine, and conventional (WURC) activity akin to the MPEP 2106.05(d) examples: “iii. Electronic recordkeeping” “iv. Storing and retrieving information in memory” “v. Electronically scanning or extracting data from a physical document” “i. Determining the level of a biomarker in blood by any means “ “v. Analyzing DNA to provide sequence information or detect allelic variants” “vi. Arranging a hierarchy of groups, sorting information, eliminating less restrictive pricing information and determining the price.” Because this limitation is WURC and insignificant extra-solution activity, under MPEP 2106.05(d) and 2106.05(g), the limitation fails to combine with the other elements of the claim to provide significantly more than the abstract idea that would confer an inventive concept.
Should it be found that emitting and/or outputting is not an element of the abstract idea, these are WURC similar to the MPEP 2106.05(d) examples: “i. Receiving or transmitting data over a network” “iii. Electronic recordkeeping” “iv. Storing and retrieving information in memory” “vi. Arranging a hierarchy of groups, sorting information, eliminating less restrictive pricing information and determining the price”
Also, the quantities the data in the claims represent merely limit the abstract idea to a technological environment, which, under MPEP 2106.05(h), fail to combine with the other elements of the claim to provide significantly more than the abstract idea that would confer an inventive concept.
The additional limitations fail to combine with the other elements of the claim to provide significantly more than the abstract idea that would confer an inventive concept.
Claim 18 is ineligible.
Dependent Claims
The dependent claims are also ineligible for at least the following reasons.
Claim 2
wherein the data includes a plurality of weighting factors of a machine-learning model, and wherein the weighting factors are computed by the plurality of processor nodes.
This merely describes the data used for determining the schedule, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
This also merely describes and is an element of the insignificant extra-solution activity and WURC from the receive as input step of claim 1.
Claim 2 fails to recite any additional limitations that confer eligibility.
Claim 2 is ineligible.
Claim 3
wherein each of the plurality of processor nodes comprises a graphics processing unit (GPU).
This merely describes the data used for determining the schedule, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
This also merely describes and is an element of the insignificant extra-solution activity and WURC from the receive as input step of claim 1.
Claim 3 fails to recite any additional limitations that confer eligibility.
Claim 3 is ineligible.
Claim 4
wherein the predetermined cost function comprises a length of time for completion of the coordinated transfer of data and/or a metric of processor disuse.
This merely describes the data used for determining the schedule, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
This also merely describes and is an element of the insignificant extra-solution activity and WURC from the receive as input step of claim 1.
Claim 4 fails to recite any additional limitations that confer eligibility.
Claim 4 is ineligible.
Claim 5
further comprising emitting an optimality-gap guarantee for the schedule based on a primal-dual theorem.
This is merely another constraint for the determinations, so it is an aspect of the abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
This also merely describes and is an element of the insignificant extra-solution activity and WURC from the receive as input step of claim 1.
Claim 5 fails to recite any additional limitations that confer eligibility.
Claim 5 is ineligible.
Claim 6
wherein the model is formulated as a mixed-integer linear program (MILP).
This merely describes the manner in which the evaluation is conducted in the determination of the schedule, so it is an element of the abstract idea. Similarly, mixed-integer problem formulations have been conducted since before they were applied on computers, so it is clear that these operations are practically performable in the mind or with aid of pen and paper, so the limitation is an evaluation, mental process, abstract idea. The limitation is an element of the abstract idea and does not provide any additional limitations to confer eligibility.
Should it be found otherwise, this is merely a generic computing element under MPEP 2106.05(f) because mixed-integer linear problems for scheduling multi-processor operations are longstanding practices that fail to confer eligibility.
Claim 6 fails to recite any additional limitations that confer eligibility.
Claim 6 is ineligible.
Claim 7
further comprising converting the MILP into a linear program (LP), wherein said converting includes removing all integer variables.
Conversions of MILPs into LPs by removing all integer variables has been conducted since before they were applied on computers, so it is clear that these operations are practically performable in the mind or with aid of pen and paper, so the limitation is an evaluation, mental process, abstract idea. The limitation is an element of the abstract idea and does not provide any additional limitations to confer eligibility.
Should it be found otherwise, this is merely a generic computing element under MPEP 2106.05(f) because mixed-integer linear problems for scheduling multi-processor operations are longstanding practices that fail to confer eligibility.
Claim 7 fails to recite any additional limitations that confer eligibility.
Claim 7 is ineligible.
Claim 8
wherein the cost function is minimized in dependence on a data-transfer latency for each of the plurality of processor nodes.
Minimizing cost functions based on relevant data has been conducted since before application on computers, so it is clear that these operations are practically performable in the mind or with aid of pen and paper, so the limitation is an evaluation, mental process, abstract idea. The limitation is an element of the abstract idea and does not provide any additional limitations to confer eligibility.
Should it be found otherwise, this merely limits the abstract idea to a particular field, so it fails to confer eligibility under MPEP 2106.05(h)
Claim 8 fails to recite any additional limitations that confer eligibility.
Claim 8 is ineligible.
Claim 9
wherein at least two of the plurality of processors differ in the data-transfer latency.
This merely describes data used in the determinations, so it is an element of the determinations, an abstract ideas.
Should it be found otherwise, this limitation merely identifies the data used in a consideration, to it merely limits the abstract idea to a particular field, so it fails to confer eligibility under MPEP 2106.05(h)
Claim 9 fails to recite any additional limitations that confer eligibility.
Claim 9 is ineligible.
Claim 10
wherein the set of demands comprise an ALLTOALL demand, an ALLGATHER demand, or an ALLREDUCE demand.
This is merely another constraint for the determinations, so it is an aspect of the abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
This also merely describes and is an element of the insignificant extra-solution activity and WURC from the receive as input step of claim 1.
Claim 10 fails to recite any additional limitations that confer eligibility.
Claim 10 is ineligible.
Claim 11
wherein the plurality of predetermined constraints include, for each processor node, a capacity constraint, a flow-conservation constraint, and a destination constraint.
This is merely another constraint for the determinations, so it is an aspect of the abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
This also merely describes and is an element of the insignificant extra-solution activity and WURC from the receive as input step of claim 1.
Claim 11 fails to recite any additional limitations that confer eligibility.
Claim 11 is ineligible.
Claim 12
wherein the flow-conservation constraint includes a buffer constraint.
This is merely another constraint for the determinations, so it is an aspect of the abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
This also merely describes and is an element of the insignificant extra-solution activity and WURC from the receive as input step of claim 1.
Claim 12 fails to recite any additional limitations that confer eligibility.
Claim 12 is ineligible.
Claim 13
wherein the cost function is adapted to discourage unnecessary data transfer during operation of the model.
This limitation is an element of the determinations that are the abstract ideas, so it is an element of the abstract idea. That is, a person can deploy a cost function that discourages unnecessary data transfer mentally or with the aid of pen and paper.
Also, cost functions are mathematical equations, so they are mathematical concepts, abstract ideas.
NOTE: This limitation is functional and only limited to the extent that the result has the effect of reducing unnecessary data transfer, which is practically performable in the mind or with the aid of pen and paper, again, an abstract idea.
Claim 13 fails to recite any additional limitations that confer eligibility.
Claim 13 is ineligible.
Claim 14
wherein the model is configured to operate within successive partitions of time, and wherein minimizing the cost function includes maximizing progress toward completion of the coordinated transfer of data within a current partition.
These all operate as constraints on, and are therefore elements of, the evaluations of claim 1, so they are elements of the evaluations, mental process, abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
Claim 14 fails to recite any additional limitations that confer eligibility.
Claim 14 is ineligible.
Claim 15
wherein the set of demands comprises a sun of demands across a plurality of collectives in a multi-tenant cluster on the network.
These all operate as constraints on, and are therefore elements of, the evaluations of claim 1, so they are elements of the evaluations, mental process, abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
Claim 15 fails to recite any additional limitations that confer eligibility.
Claim 15 is ineligible.
Claim 16
wherein the multi-tenant cluster services demands of first and second tenants, and wherein the predetermined cost function is adapted to prioritize the demands of the first tenant over the demands of the second tenant.
These all operate as constraints on, and are therefore elements of, the evaluations of claim 1, so they are elements of the evaluations, mental process, abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
Claim 16 fails to recite any additional limitations that confer eligibility.
Claim 16 is ineligible.
Claim 19
wherein the copy operation supports multicasting to two or more of the plurality of GPUs.
This operates as constraints on, and is therefore an element of, the evaluations of claim 1, so it is an element of the evaluations, mental process, abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
Claim 19 fails to recite any additional limitations that confer eligibility.
Claim 19 is ineligible.
Claim 20
wherein the model is further configured represent a plurality of switches configured to connect different blocks of GPUs on the network.
This operates as constraints on, and is therefore an element of, the evaluations of claim 1, so it is an element of the evaluations, mental process, abstract ideas.
Should it be found otherwise, this merely describes that which the data used represents, which merely limits the abstract idea to a field of technology and fails to confer eligibility under MPEP 2106.05(h).
Claim 20 fails to recite any additional limitations that confer eligibility.
Claim 20 is ineligible.
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- : Shah and Lan
Claim(s) 1- is/are rejected under 35 U.S.C. 103 as being unpatentable over NPL: “TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches” by Shah et al. (Shah) in view of NPL: “Communication-Efficient Algorithms for Decentralized and Stochastic Optimization” by Lan et al. (Lan).
Regarding claim 17, Shah teaches:
A communication scheduler for a machine-learning collective of a plurality of graphics processing unit (GPU) clusters arranged on a network, the communication scheduler comprising: (Shah Abstract “Machine learning models are increasingly being trained across multiple GPUs and servers. In this setting, data is trans ferred between GPUs using communication collectives such as ALLTOALL and ALLREDUCE, which can become a signifi cant bottleneck in training large models. Thus, it is important to use efficient algorithms for collective communication. We develop TACCL, a tool that enables algorithm designers to guide a synthesizer into automatically generating algorithms for a given hardware configuration and communication collec tive. TACCL uses a novel communication sketch abstraction to get crucial information from the designer to significantly reduce the search space and guide the synthesizer towards better algorithms.” – Teaches a communication scheduler for a collective of a plurality of graphics processing unit (GPU) clusters arranged on a network.)
an input engine configured to furnish a set of demands defining, for each of the plurality of GPUs, an amount of data to be transferred to that GPU; (Shah Page 4, 3 Communication Sketches “Therefore, we ask the algorithm designer (user) for four low-effort inputs as a part of the communication sketch: • Specify the logical topology as a subset of the actual physical topology that the algorithm will operate on. This constrains the routes chosen by the communication algo rithm and alleviates over-subscription of low-bandwidth links. For example, the outgoing links of all but one GPU can be removed in the logical topology to force all data going to remote GPUs to be relayed through one GPU. • The logical topology abstracts away switches (e.g., NVSwitches, IBSwitches) in the GPU network. Users can annotate switches in the topology for the synthesizer to use certain switch-hyperedge policies, enabling it to apply synthesis policies that help algorithms avoid contention. • Provide algorithm symmetry based on the symmetries in the topology and the collective. • Specify the expected input size of the data, which is used as a part of the synthesis engine’s built-in cost model. Weexplain all parts of the communication sketch and provide an example sketch written for TACCL in Appendix A.” – The system includes input elements that furnish a set of demands defining, for each GPU/linked pair of GPUs, an amount of data to be transferred therebetween. )
a multi-commodity flow model formulated to operate within a plurality of predetermined constraints and configured to- receive the set of demands as input from the input engine, (Shah Page 7, 5.1 Problem Formulation “MILP problems in general are NP-hard. Luckily, there are solvers such as Gurobi [20] that apply heuristics to solve MILPs in a feasible way. However, this requires careful con sideration regarding the number of variables and constraints in the formulation. In TACCL’s formulation, transferring chunks over a link cannot overlap and an ordering among them is required. Therefore, potentially a binary decision is needed for every pair of chunks that may traverse a link. If we assume there are C chunks for a collective problem, there are O(C2) such decisions per link. Moreover, as the number of nodes increase, the number of links increase linearly (larger topology) and the number of chunks for a collective increases linearly (ALLGATHER) or even quadratically (ALLTOALL). This large set of variables and constraints leads to infeasible solver time and memory requirements. To solve this problem, we divide the synthesis into three parts. First, the synthesizer solves an optimization problem to determine the path used by every chunk without fixing any ordering among chunks, then it heuristically orders the chunks over every link, and finally, it solves another optimization problem to determine chunk contiguity. Complete formal descriptions of each step are in Appendix B.” – A flow model is used that operates within different specified constraints.)
assign a plurality of paths linking the plurality of GPUs, and (Shah Pages 8-9, Step 1: Routing “Step 1: Routing solves a MILP for finding the path of each chunk independent of other chunks, allowing chunks sent over a link to overlap. The objective of this MILP is to minimize the time, which we constrain to be the maximum of two sets of variables. (1) for each link, the number of chunks that traverse that link multiplied by the transfer time of a chunk over that link. (2) for the path of each chunk, the summation of transfer times of the chunk along every link in the path. Note that this is only a lower bound on the time since we do not consider link contention or chunk ordering. TACCL also con strains each chunk’s path to be via GPU ranks that are on the shortest paths from their sources to their destinations using variable send_time indicates when a chunk is sent over a link. the links the user decided to include in the logical topology. If the communication sketch specifies an algorithm symmetry, TACCL adds the constraints for the symmetric sends. Replacing switches with switch-hyperedges is also applied in this step. For each switch-hyperedge, a user-provided policy on the number of unique connections to/form a switch is applied (see Section 5.2).” – Paths linking the GPUs are assigned.)
emit a schedule for transfer of the data along the plurality of paths minimize a predetermined cost function, wherein the schedule comprises at least one store-and-forward operation and at least one copy operation; and (Shah Page 8, Left Column, Second Paragraph “TACCL uses Gurobi [20] to solve this MILP and the so lution gives every chunk a start_time for each GPU along its path. Clearly this step solves chunk routing, but only partially solves the chunk scheduling and contiguity problem and requires follow-up steps (explained next) to account for ordering the chunks sent over a link as well as minimizing α costs of sends. However, by using this technique, TACCL’s synthesizer is able to reduce binary variables needed from O(C2) to O(C) per link.” – The Gurobi solver is used, which utilizes a cost function (e.g., linear, quadratic, or multi-objective). Page 9, 6.2 Lowering to TACCL runtime “Input and output buffers are preallocated by the user and passed to the collective. Scratch buffers are allocated by the TACCL runtime per TACCL-EF. Chunks are indices in the input, output and scratch buffers. For chunks that are common for both the input and the output buffers (e.g. as in ALLGATHER) a local copy from input to the output buffer is performed at the end.” – Both copy and store-and-forward operations done by scheduler. NOTE: Copy and store-and-forward operations are conducted by all modern schedulers depending on the selected buffering method in the chunk/packet header. For more detail, see the Network Academy.io reference of record.
an output engine configured to output the schedule. (Shah Page 14, Conclusion and Future Work “TACCL is a topology and input-size aware collective communication library for multi-node distributed machine learning training and inference. TACCL uses user-provided communication sketches to guide synthesis of collective algorithms. Using a three-step technique of relaxed routing, heuristic ordering, and contiguity and exact scheduling, TACCL generates efficient collectives for multi-node topologies. […] To conclude, TACCL uses the abstraction of communication sketches and a novel problem formulation to generate efficient algorithms for collectives like ALLGATHER, ALL TOALL, and ALLREDUCE. The algorithms thus generated are up-to 6.7× faster than the state-of-the-art NCCL and result in 11%−2.4× faster end-to-end training time.” - A schedule is output.)
Shah does not appear to explicitly teach, but Shah in view of Lan teaches:
an output engine configured to output the schedule, together with an optimality-gap guarantee for the schedule. (Lan Abstract “We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. We first propose a decentralized primal-dual method which can find an ϵ-solution both in terms of functional optimality gap and feasibility residual in O(1/ ϵ) inter-node communication rounds when the objective functions are convex and the local primal subproblems are solved exactly.” Page 7, Last Paragraph “Our main goals here in this section are to: 1) adapt the primal-dual framework for a decentralized setting; and 2) provide complexity results (number of communication rounds and subgradient computations) separately in terms of primal functional optimality gap and constraint (or consistency) violation.” – Optimality gap is a known, conventional goal to achieve for routing, even if it is not explicitly stated in a reference. Here it is explicitly stated for the sake of completeness.)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claims to modify the flow scheduling in Shah by the flow scheduling optimization of Lan because the person of ordinary skill in the art would be motivated by the aim of Shah to expedite machine learning request routing to look to Lan, which reduces the total number of intern-node communication rounds by orders of magnitude. (Shah Abstract “We demonstrate that the algorithms synthesized by TACCL outperform the Nvidia Collective Communication Library (NCCL) by up to 6.7×. We also show that TACCL can speed up end-to-end training of Transformer-XL and BERT models by 11%–2.3× for different batch sizes.”; Lan Abstract “In comparison with existing results for decentralized nonsmooth and stochastic optimization, we can reduce the total number of inter-node communication rounds by orders of magnitude while still maintaining the optimal complexity bounds on intra-node stochastic subgradient evaluations. The bounds on the (stochastic) subgradient evaluations are actually comparable to those required for centralized nonsmooth and stochastic optimization under certain conditions on the target accuracy.“)
Regarding claim 1, claim 1 recites substantially the operations that claim 17 is configured to execute, so claim 1 is rejected for at least the same reasons as claim 17.
Regarding claim 18, it recites the operation substantially the operations that claim 17 is configured to execute, so the common elements between claim 18 and claim 1 are rejected for at least the same reasons as claim 17. Claim 18 further recites,
wherein the schedule comprises at least one store-and-forward operation and at least one copy operation, each employing cache memory of the plurality of GPUs. (Shah Page 12, Changing number of instances “Figure 9e shows algorithm bandwidth with instances ranging from 1 to 8. The switch hyperedge policy for these algorithms is set to uc-min. In creasing the number of instances improves bandwidth utilization — multiple threadblocks seem to be needed to keep the six NVLinks in a V100 busy. However, a larger number of threadblocks also increases latency, which we suspect is due to unfavorable scheduling of synchronization related memory operations onto the NVLinks at the start of each send.“ – The GPUs use NVLink for transfers, and NVLink still interacts with the GPU's internal memory hierarchy, including the L2 cache. That is, when a GPU reads or writes data residing in peer memory over NVLink, those memory transactions still pass through and utilize the local processing units and L2 cache structures. Even if the bulk of the data need not pass through cache, the instructions for the transfer employ the cache for control of the operations.)
Claim 2
Regarding claim 2, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein the data includes a plurality of weighting factors of a machine-learning model, and wherein the weighting factors are computed by the plurality of processor nodes. (Shah Page 9, 6.1 TACCL runtime “This allows TACCL to dynamically swap in collective algorithms generated for any training/inference workload using torch.distributed.” Page 12, 7.3 End-to-End Training “We evaluate TACCL on distributed training of two large language models, Transformer-XL [4,13] and BERT [3,15], on two (and four) Azure NDv2 nodes, i.e. 16 (and 32) GPUs. Transformer-XL uses data parallelism and whereas BERT uses model parallelism. The typical transfer sizes for ALLRE DUCE in Transformer-XL is in the 20- 40MB range, and for BERT it is about 2MB. Both models communicate with torch.distributed and, as explained in Section 6, using TACCL algorithms in them is quite straightforward.”– Training large language ML models involves determining and transferring data representing weights of ML models.)
Claim 3
Regarding claim 3, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein each of the plurality of processor nodes comprises a graphics processing unit (GPU). (Shah Abstract “We use TACCL to synthesize algorithms for three collectives and two hardware topologies: DGX-2 and NDv2. We demonstrate that the algorithms synthesized by TACCL outperform the Nvidia Collective Communication Library (NCCL) by up to 6.7×. We also show that TACCL can speed up end-to-end training of Transformer-XL and BERT models by 11%–2.3× for different batch sizes.” – The processor nodes include GPUs.)
Claim 4
Regarding claim 4, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein the predetermined cost function comprises a length of time for completion of the coordinated transfer of data and/or a metric of processor disuse. (Shah Page 6, Left Column, Third Paragraph “The profiler empirically derives the α and β parameters of different links in the network by performing peer-to-peer data transfers between GPUs. We send n chunks one after another on a link and measure the time to transfer. As per the α−β cost model, the time to transfer is n·(α+β·s). We then send n chunks all at once on the link and attribute that time to be α+n·β·s. Using several measurements of time to transfer, we solve for α and β.” – The cost function includes a length of time for the completion of the coordinated transfer of data.)
Claim 5
Regarding claim 5, Shah in view of Lan teaches the features of claim 1, and further teaches:
further comprising emitting an optimality-gap guarantee for the schedule based on a primal-dual theorem. (Lan Abstract “We first propose a decentralized primal-dual method which can find an ϵ-solution both in terms of functional optimality gap and feasibility residual in […] inter-node communication rounds when the objective functions are convex and the local primal subproblems are solved exactly. Our major contribution is to present a new class of decentralized primal-dual type algorithms, namely the decentralized communication sliding (DCS) methods, which can skip the inter-node communications while agents solve the primal subproblems iteratively
through linearizations of their local objective functions.” – The optimality gap constraint is determined based on a primal-dual theorem.)
Claim 6
Regarding claim 6, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein the model is formulated as a mixed-integer linear program (MILP). (Shah Page 7, 5.1 Problem Formulation “Step 1: Routing solves a MILP for finding the path of each chunk independent of other chunks, allowing chunks sent over a link to overlap. The objective of this MILP is to minimize the time, which we constrain to be the maximum of two sets of variables. (1) for each link, the number of chunks that traverse that link multiplied by the transfer time of a chunk over that link. (2) for the path of each chunk, the summation of transfer times of the chunk along every link in the path. Note that this is only a lower bound on the time since we do not consider link contention or chunk ordering.” – The model is formulated as a mixed-integer linear program.)
Claim 8
Regarding claim 8, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein the cost function is minimized in dependence on a data-transfer latency for each of the plurality of processor nodes. (Shah Page 6, Left Column, Third Paragraph “The profiler empirically derives the α and β parameters of different links in the network by performing peer-to-peer data transfers between GPUs. We send n chunks one after another on a link and measure the time to transfer. As per the α−β cost model, the time to transfer is n·(α+β·s). We then send n chunks all at once on the link and attribute that time to be α+n·β·s. Using several measurements of time to transfer, we solve for α and β.” – The cost function includes a length of time for the completion of the coordinated transfer of data.)
Claim 9
Regarding claim 9, Shah in view of Lan teaches the features of claim 8, and further teaches:
wherein at least two of the plurality of processors differ in the data-transfer latency. (Shah Page 6, Left Column, Third Paragraph “The profiler empirically derives the α and β parameters of different links in the network by performing peer-to-peer data transfers between GPUs. We send n chunks one after another on a link and measure the time to transfer. As per the α−β cost model, the time to transfer is n·(α+β·s). We then send n chunks all at once on the link and attribute that time to be α+n·β·s. Using several measurements of time to transfer, we solve for α and β.” – The data transfer latency differs between processors, as is demonstrated by the need to record each transfer.)
Claim 10
Regarding claim 10, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein the set of demands comprise an ALLTOALL demand, an ALLGATHER demand, or an ALLREDUCE demand. (Shah Page 2, Results “We use TACCL to synthesize efficient algorithms for a range of collectives like ALLGATHER, ALLTOALL, and ALLREDUCE” – Verbatim.)
Claim 11
Regarding claim 11, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein the plurality of predetermined constraints include, for each processor node, a capacity constraint, a flow-conservation constraint, and a destination constraint. (Shah Pages 17-20, Appendix B – This teaches bandwidth (capacity) constraints, flow-conservation constraints (such as is_together and ordering constraints) and destination constraints (See Table 3 on page 19 for routing constraints that include destination-specific constraints).
Claim 12
Regarding claim 12, Shah in view of Lan teaches the features of claim 11, and further teaches:
wherein the flow-conservation constraint includes a buffer constraint. (Shah Page 8, Synthesizer Hyperparameters “Buffer Size. TACCL needs the size of input/output buffers of a collective for the α-β cost model. In ML workloads the input/output buffer size is a known fixed value.” – Buffer constraints are applied.)
Claim 13
Regarding claim 13, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein the cost function is adapted to discourage unnecessary data transfer during operation of the model. (Shah Page 8, Step 3: Contiguity and Exact Scheduling “The start_time and send_time variables are reassigned in this step by considering both the α and β costs for each transfer. In this step, the synthesizer allows either sending one chunk at a time or sending multiple chunks contiguously. This offers a trade-off between (1) sending the chunks that are available at the same time for a link according to the ordering in step 2 so that the subsequent sends can be scheduled earlier or (2) sending the chunks contiguously in one send instruction to save the latency cost. The objective of this MILP is to minimize the total time by enforcing all constraints which in TACCL solved by Gurobi [20]. The solution gives the exact schedule for each chunk. The details of these constraints and their formulation are in Appendix B.” – The cost function discourages unnecessary data transfers.)
Claim 14
Regarding claim 14, Shah in view of Lan teaches the features of claim 1, and further teaches:
wherein the model is configured to operate within successive partitions of time, and wherein minimizing the cost function includes maximizing progress toward completion of the coordinated transfer of data within a current partition. (Shah Page 8, Step 3: Contiguity and Exact Scheduling “The start_time and send_time variables are reassigned in this step by considering both the α and β costs for each transfer. In this step, the synthesizer allows either sending one chunk at a time or sending multiple chunks contiguously. This offers a trade-off between (1) sending the chunks that are available at the same time for a link according to the ordering in step 2 so that the subsequent sends can be scheduled earlier or (2) sending the chunks contiguously in one send instruction to save the latency cost. The objective of this MILP is to minimize the total time by enforcing all constraints which in TACCL solved by Gurobi [20]. The solution gives the exact schedule for each chunk. The details of these constraints and their formulation are in Appendix B.” – The model operates by transferring chunks over successive periods, and the cost function maximizes progress toward completion of the transfer within each partition to reduce the transfer time.)
Claim 19
Regarding claim 19, Shah in view of Lan teaches the features of claim 18, and further teaches:
wherein the copy operation supports multicasting to two or more of the plurality of GPUs. (Shah Page 3, Collective communication in distributed ML workloads “Multi-GPU ML workloads typically communicate using MPI style collectives like ALLGATHER, ALLTOALL, and ALLRE DUCE shown in Figure 2. These primitives capture the application’s intent behind the communication, thus allowing collective communication libraries to optimize for specific hardware configurations. In ALLGATHER, every GPU receives the data buffers of all other GPUs (left diagram in Figure 2). In ALL TOALL, every GPU receives different parts, or chunks, of the data buffers present on all GPUs. This effectively transposes the data chunk from buffer index to GPU index as can be seen in center diagram in Figure 2. In ALLREDUCE, every GPU ends up with a data buffer that has the results of per forming a point-wise computation (e.g., sum in right diagram in Figure 2) over the same data index of all GPUs. The parallelism strategy for the distributed ML workload determines which collective communication primitive is used. Data parallelism and some tensor model parallelisms [43] make use of the ALLREDUCE collective to aggregate gradi ents and intermediate data respectively from multiple GPUs. Expert parallelism [18,27] and common deep learning recommendation models (DLRM) [32] make use of the ALL TOALL collective to shuffle intermediate data between experts and embedding lookup data between GPUs respectively. DL RMs[32] also make use of the ALLGATHER collective and another REDUCESCATTER collective to perform embedding lookups from embedding tables sharded over multiple GPUs.” – All operations support multicasting to multiple GPUs.)
Claim 20
Regarding claim 20, Shah in view of Lan teaches the features of claim 18, and further teaches:
wherein the model is further configured represent a plurality of switches configured to connect different blocks of GPUs on the network. (Shah Page 4, 3 Communication Sketches “The logical topology abstracts away switches (e.g., NVSwitches, IBSwitches) in the GPU network. Users can annotate switches in the topology for the synthesizer to use certain switch-hyperedge policies, enabling it to apply synthesis policies that help algorithms avoid contention.” - The model is further configured represent a plurality of switches configured to connect different blocks of GPUs on the network.)
Claims 7: Shah, Lan, and Vielma
Claim 7 is rejected under 35 U.S.C. 103 as being unpatentable over NPL: “TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches” by Shah et al. (Shah) in view of NPL: “Communication-Efficient Algorithms for Decentralized and Stochastic Optimization” by Lan et al. (Lan) and NPL: “Mixed Integer Linear Programming Formulation Techniques” by Vielma (Vielma).
Claim 7
Regarding claim 7, Shah in view of Lan teaches the features of claim 6, but does not appear to explicitly teach, but Shah in view of Lan and Vielma teaches:
further comprising converting the MILP into a linear program (LP), wherein said converting includes removing all integer variables. (Vielma Page 4, Second Paragraph “We begin in section 2 with a motivating example that allows us to precisely define the idea of an MIP formulation or model. This same example serves to illustrate one of the most important favorable properties of an MIP formulation: the strength of its LP relaxation. Through this section we also introduce basic MIP concepts and notation that we use in the rest of the paper.” Page 7, 2.2 Stength, Size, and MIP Solvers.” – LP relaxation is a standard method used to reduce the complexity of MILP. The relaxation involves removing integral variables.)
Claims 15-16: Shah, Lan, and Li
Claim(s) 15-16 are rejected under 35 U.S.C. 103 as being unpatentable over NPL: “TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches” by Shah et al. (Shah) in view of NPL: “Communication-Efficient Algorithms for Decentralized and Stochastic Optimization” by Lan et al. (Lan) and NPL: “Priority-Based PCIe Scheduling for Multi-Tenant Multi-GPU Systems” by Li et al. (Li).
Claim 15
Regarding claim 15, Shah in view of Lan teaches the features of claim 1, but fails to explicitly teach, but Shah in view of Lan and Li teaches:
the set of demands comprises a [sum] of demands across a plurality of collectives in a multi-tenant cluster on the network. (Li Page 159, 4 PRELIMINARY EVALUATION “In this work, we run two kinds of tasks, launched by two users to model multi-tenant sharing. For experimental purposes, a task with a larger data size is assumed to be the QoS task, while the task with smaller data size is assumed as a non-QoS task. The deadline of the memory transfer time is set as 3 times the memory transfer time without bandwidth contention. The 8 workloads we used to evaluate the proposed solution are from the AMDAPPSDK [10], Hetero-Mark suite [11] and clCaffe [12] suites, as shown in Table 1. We select the problem size to find a good trade-off between the simulation time and common use-cases of applications.” – This is a sum of demands from a shared multi-GPU cluster.)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claims to modify the flow determinations of Shah by the QoS considerations of Li because the person of ordinary skill in the art would be motivated by the aim of Shah to provide solutions for traffic flow management that are fast, to look to Li, which adds priority-based scheduling that alleviates competing bandwidth demands and satisfies QOS constraints. (Shah Abstract “Thus, it is important to use efficient algorithms for collective communication. We develop TACCL, a tool that enables algorithm designers to guide a synthesizer into automatically generating algorithms for a given hardware configuration and communication collective. TACCL uses a novel communication sketch abstraction to get crucial information from the designer to significantly reduce the search space and guide the synthesizer towards better algorithms. TACCL also uses a novel encoding of the problem that allows it to scale beyond single-node topologies. We use TACCL to synthesize algorithms for three collectives and two hardware topologies: DGX-2 and NDv2. We demonstrate that the algorithms synthesized by TACCL outperform the Nvidia Collective Communication Library (NCCL) by up to 6.7×. We also show that TACCL can speed up end-to-end training of Transformer-XL and BERT models by 11%–2.3× for different batch sizes.” ; Li Abstract “Multi-GPU systems are widely used in data centers to provide significant speedups to compute-intensive workloads such as deep neural network training. However, limited PCIe bandwidth between the CPU and multiple GPUs becomes a major performance bottleneck. We observe that relying on a traditional Round-Robin-based PCIe scheduling policy can result in severe bandwidth competition and stall the execution of multiple GPUs. In this article, we propose a priority-based scheduling policy which aims to overlap the data transfers and GPU execution for different applications to alleviate this bandwidth contention. We also propose a dynamic priority policy for semi-QoS management that can help applications to meet QoS requirements and improve overall multi-GPU system throughput. Experimental results show that the system throughput is improved by 7.6 percent on average using our priority-based PCIe scheduling scheme as compared with a Round-Robin-based PCIe scheduler. Leveraging semi-QoS management can help to meet defined QoS goals, while preserving application throughput.”)
Claim 16
Regarding claim 16, Shah in view of Lan and Li teaches the features of claim 15, and further teaches:
wherein the multi-tenant cluster services demands of first and second tenants, and wherein the predetermined cost function is adapted to prioritize the demands of the first tenant over the demands of the second tenant. (Li Page 159, 4 PRELIMINARY EVALUATION “In this work, we run two kinds of tasks, launched by two users to model multi-tenant sharing. For experimental purposes, a task with a larger data size is assumed to be the QoS task, while the task with smaller data size is assumed as a non-QoS task. The deadline of the memory transfer time is set as 3 times the memory transfer time without bandwidth contention. The 8 workloads we used to evaluate the proposed solution are from the AMDAPPSDK [10], Hetero-Mark suite [11] and clCaffe [12] suites, as shown in Table 1. We select the problem size to find a good trade-off between the simulation time and common use-cases of applications.” – The QOS program restraint/cost function/objective function determines which of the tenants’ demands is prioritized for processing.)
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
NPL: “MISO: exploiting multi-instance GPU capability on multi-tenant GPU clusters” by Li et al. (Teaches flow scheduling for multitenant ML loads in multi-GPU systems)
NPL: “Exactly Solving Hard Permutation Flowshop Scheduling Problems on Peta-Scale GPU-Accelerated Supercomputers” by Gmys. (Teaches flow scheduling for ML loads in multi-GPU systems)
NPL: “Speeding up Collective Communications Through Inter-GPU Re-Routing” by Ranganath et al. Teaches flow scheduling in multi-GPU systems)
NPL: “TopoOpt: Co-optimizing Network Topology and Parallelization Strategy for Distributed Training Jobs.” by Wang et al. (Teaches flow scheduling for ML loads in multi-GPU systems)
NPL: “On scheduling ring-all-reduce learning jobs in multi-tenant GPU clusters with communication contention.” by et al. (Teaches flow scheduling for ML loads in multi-GPU systems)
(Contemporaneous (Not Prior) Art)
NPL: “Rethinking Machine Learning Collective Communication as a Multi-Commodity Flow Problem” by Liu et al. (The White Paper with the technology of the instant application)
NPL: “Optimizing ML Systems without using experts” by Shah (The PhD dissertation of the author, Shah, of the primary prior art reference, the dissertation including features of the primary prior art reference)
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JAY MICHAEL WHITE whose telephone number is (571) 272-7073. The examiner can normally be reached Mon-Fri 11:00-7:00 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, Ryan Pitaro can be reached at (571) 272-4071. 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.
/J.M.W./Examiner, Art Unit 2188
/RYAN F PITARO/Supervisory Patent Examiner, Art Unit 2188
Prosecution Insights