DETAILED ACTION
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 .
This application claims the benefit of U.S. Provisional Application 63/470,399, filed 06/01/2023. The benefit claim is acknowledged by the Examiner.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 09/13/2024 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Examiner’s Note
The Examiner cites particular columns, paragraphs, figures, and line numbers in the references as applied to the claims below for the convenience of the applicant. Although the specified citations are representative of the teachings in the art and are applied to the specific limitations within the individual claim, other passages and figures may also apply. It is respectfully requested that, in preparing responses, the Applicant fully consider the references in its entirety as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior art or disclosed by the Examiner.
Claim Objections
Claims 1-20 are objected to because of the following informalities:
Regarding claims 1, 11, and 16, each claim recites “...for each sub-graph, executing the one or operations associated with a sub-graph...”. The Examiner suggests adding “more” between “or” and “operations” for clarity.
Regarding claim 9, the claim recites “...if the memory requirement for the data in the partition is exceeds that to be executed...”. The Examiner suggests removing “is” for clarity.
Regarding claim 10, the claim recites “...wherein executing the operations associate with a sub-graph further comprises...”. The Examiner suggests amending “associate” to “associated” for clarity.
Any claim not explicitly mentioned above is objected to due to dependency on an objected claim.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claims 1, 11, and 16, each claim recites “... an operation to have substantially the same size after each operation...”. The instant specification at [0009, 0027, 0044, 0056, and 0067] discloses: “Rebalance the partitions (i.e., a portion or subset of the dataset, such as a subset of rows or documents) in the data sets input to, or output by, an operation (or set of operations in a sub-graph) to have the same size after each operation or set of operations”, and “Rebalance the partitions in the data sets input or output by a set of operations (i.e., input to a sub-graph or output from a previous sub-graph) to have the same size (i.e., the same number of rows and columns in a table, as an example)”. The phrase “substantially the same” as recited by claims 1, 11, and 15 is unclear because the claims and specification fail to provide objective boundaries for determining the allowable degree of variation from “the same size” that is encompassed by the term “substantially”, thereby making the metes and bounds of the claims unclear. For purposes of examination, the Examiner assumes no degree of variation from “the same size” is allowed.
Regarding claim 5, the claim recites “output by an operation to have substantially the same size” and “adjusting the number of rows and columns in a table to be substantially the same”. The instant specification at [0009, 0027, 0044, 0056, and 0067] discloses: “Rebalance the partitions (i.e., a portion or subset of the dataset, such as a subset of rows or documents) in the data sets input to, or output by, an operation (or set of operations in a sub-graph) to have the same size after each operation or set of operations”, and “Rebalance the partitions in the data sets input or output by a set of operations (i.e., input to a sub-graph or output from a previous sub-graph) to have the same size (i.e., the same number of rows and columns in a table, as an example)”. The phrase “substantially the same” is unclear because the claims and specification fail to provide objective boundaries for determining the allowable degree of variation from “the same size” or “same number of rows and columns” that is encompassed by the term “substantially”, thereby making the metes and bounds of the claim unclear. For purposes of examination, the Examiner assumes no degree of variation from “the same size” or “same number of rows and columns” is allowed.
Any claim not explicitly mentioned above is rejected due to dependency on a rejected claim.
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, 3-5, 10-11, 13, 16, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Buniatyan (US 20220121880 A1) in view of Cai (US 20210073625 A1), further in view of Watzke et al. (US 9110947 B1) hereafter Watzke, further in view of El-Khamy et al. (US 20180293707 A1) hereafter El-Khamy, further in view of Englert et al. (US 20200218969 A1) hereafter Englert.
Regarding claim 1, Buniatyan teaches:
A method of pre-processing a set of data for use in training a model or for use as an input to a trained model, comprising:
representing the pre-processing of a dataset as a sequence of one or more data conversion and data transformation operations (Paragraph 28; “data transformation module 110 receives a plurality of transformation functions concatenated together as a dependency directed acyclic graph to transform the plurality of large-scale datasets from one form into another”, where the plurality of transformation functions are arranged as a directed acyclic graph thereby representing an ordered sequence of operations and the transformation functions transform the dataset, corresponding to data conversion and transformation operations performed on the dataset as part of preprocessing.);
representing the sequence of one or more data conversions and data transformations and associated dependencies as a directed acyclic graph (DAG), wherein the nodes of the directed acyclic graph represent a state of the processing of the set of data (Paragraph 28; “data transformation module 110 receives a plurality of transformation functions concatenated together as a dependency directed acyclic graph to transform the plurality of large-scale datasets from one form into another”, and Paragraph 44; “These transformations are defined in directed acyclic graphs where each node is a state of the sample and a directed connection as a transformation from sample state to another state.”);
Buniatyan does not teach an edge connecting two nodes represents a type of processor used to perform a data conversion or transformation, separating the directed acyclic graph into a set of sub-graphs, wherein each sub-graph represents one or more operations executed by a specific type or class of processor, rebalancing one or more partitions in the data input to, or output by an operation to have substantially the same size after each operation executed by a specific type or class of processor, associating each sub-graph with an execution time and memory used to process the data input to a sub-graph using the one or more operations represented by the sub-graph, and for each sub-graph, executing the one or operations associated with a sub-graph with the rebalanced partitions of the datasets using the specific type of or class of processor.
However, Cai teaches:
separating the directed acyclic graph into a set of sub-graphs, wherein each sub-graph represents one or more operations executed by a specific type or class of processor (Paragraph 43; “partition a computation graph into a plurality of subgraphs, consistent with embodiments of the present disclosure. In some embodiments, graph partitioner 320 can be configured to map the plurality of subgraphs onto multiple accelerators (e.g., target devices...", where each resulting subgraph is mapped to a corresponding target device such that each subgraph is executed with specific computing resources, thereby associating operations in the directed acyclic graph with a specific processor. A person of ordinary skill in the art would recognize multiple target devices in modern compute systems as heterogeneous resources, as contemplated by Cai in Paragraph 2, “various types of heterogeneous computing devices or accelerators for machine learning or deep learning have been developed”, in which heterogeneous resources generally differ by architecture and performance characteristics. Therefore, different target devices corresponds to different processor types/classes of processing resources.);
associating each sub-graph with an execution time and memory used to process the data input to a sub-graph using the one or more operations represented by the sub-graph (Paragraph 44; “computation graph is divided into two subgraphs 421 and 422, which are mapped to be executed on two different accelerators such as target devices D1 and D2. While FIG. 4 illustrates only two subgraphs at state 420, it is appreciated that a partitioning process can be performed to divide the computation graph into any number of subgraphs based on available accelerators.”, where “the partitioning process can be performed recursively until each of the subgraphs includes an appropriate number of nodes and edges. In some embodiments, the appropriate number of nodes and edges for a subgraph can be determined based on available accelerators, each accelerator's capacity, time requirements, properties of a data structure, and so on”. Paragraph 46 confirms that the partitioner is performed based on accelerator information, including “computing throughput information and memory bandwidth. The operation profiling information may include execution time or speed information and delay information of an accelerator”.);
for each sub-graph, executing the one or more operations associated with a sub-graph using the specific type of or class of processor (Paragraphs 44-45; “graph partitioner 320 can partition a computation graph into multiple subgraphs that are executed on different accelerators based on the subgraph profiling information to optimize performance in executing the computation graph. For example, a computation graph may include subgraphs that are commonly used in many machine learning models as their components. For example, the commonly used subgraphs can include MobileNets layers, ResNet layers, Region Proposal Network, etc. In some embodiments, prior history of execution, experiments, or simulations of a certain subgraph on accelerators can identify which accelerator is optimal for processing the certain subgraph. In some embodiments, each subgraph can be assigned to a certain accelerator that can optimize performance of executing the subgraph.”, the identification of the specific accelerator is optimal for processing the specific subgraph corresponding to for each subgraph, executing the one or more operations associated with a subgraph using the specific type or class of processor.).
Buniatyan and Cai are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan to incorporate the teachings of Cai and separate the directed acyclic graph into a set of sub-graphs, wherein each sub-graph represents one or more operations executed by a specific type or class of processor, associate each sub-graph with an execution time and memory used to process the data input to a sub-graph using the one or more operations represented by the sub-graph, and for each sub-graph, execute the one or more operations associated with a sub-graph with the rebalanced partitions of the datasets using the specific type of or class of processor. A person of ordinary skill in the art would recognize that doing so would have allowed the transformation operations represented in Buniatyan’s DAG to be assigned to processing resources best suited for executing those operations while taking into account resource utilization characteristics, representing the use of the known method of resource-based task assignment, yielding the predictable result of improved execution efficiency and effective utilization of processing resources in a DAG-based workflow.
Buniatyan in view of Cai does not teach rebalancing one or more partitions in the data input to, or output by an operation to have substantially the same size after each operation executed by a specific type or class of processor; an edge connecting two nodes representing a type of processor,
However, Watzke teaches:
using a partition to execute an operation (Col. 3, lines 17-21; “Based on various considerations, a determination by the database management system to reparation the rows of the column-specific data may result in a processing task being generated for each unique column-oriented task identified in the query. Each processing task may be used to direct retrieval of rows containing column data needed to meet the request, as well as, repartitioning the rows and to process column-specific data in order to generate a results set to the query.”).
Buniatyan, Cai, and Watzke are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan in view of Cai to incorporate the teachings of Watzke and have utilized a partition to execute an operation. A person of ordinary skill in the art would have been motivated to incorporate partition based execution because partitioning data into manageable portions for execution is a known technique for improving scalability and balancing workloads across resources, yielding the predictable result of enabling operations represented by the DAG and associated subgraphs to be executed more efficiently by processing partitions of data rather than requiring execution against the entire graph at once.
Buniatyan in view of Cai, further in view of Watzke does not teach rebalancing the data input or output by an operation to have substantially the same size.
However, El-Khamy teaches:
rebalancing the data input or output by an operation to have substantially the same size (Paragraph 72; “Third, at 304, the super resolution imaging system 100 then modifies a subsequent stage network to perform appropriate resizing at output of each convolutional layer (as stretching or padding) to enforce same input and output sizes.”).
Buniatyan, Cai, Watzke, and El-Khamy are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan in view of Cai, further in view of Watzke to incorporate the teachings of El-Khamy and maintain the same sizes of Watzke based on El-Khamy teaching the preservation of dimension between inputs and outputs. Maintaining dimensional consistency is a known technique for ensuring compatibility between processing stages yielding the predictable result of allowing processed outputs to be consumed by downstream components in an expected format corresponding to the input data. A person of ordinary skill in the art would have been motivated to incorporate such rebalancing techniques into the data processing pipeline because maintaining consistent data sizes through successive operations is a known method for facilitating interoperability between processing stages. Applying this known method would yield the predictable result of input and outputs of data having the same size following execution of an operation, ensuring compatibility of data representations across operations.
Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy does not teach an edge connecting two nodes representing a type of processor.
However, Englert teaches:
an edge connecting two nodes representing a type of processor (Paragraph 41; “An edge in the graph 400 can correspond to a directed edge connecting to a subsequent node corresponding to a subsequent algorithm to be performed on a particular processor.”).
Buniatyan, Cai, Watzke, El-Khamy, and Englert are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy to incorporate the teachings of Englert and have configured an edge in a graph as representative of processor information. Englert discloses that an edge in a graph connects to a subsequent node corresponding to a subsequent algorithm to be executed on a particular processor. Because Englert further teaches that graph edges define execution flow between operations and Cai teaches execution of graph-based operations, a person of ordinary skill in the art would have been motivated to associate edge relationships with processor assignments to facilitate scheduling and execution management within a distributed environment, representative of the known method of allowing a graph structure to encode execution resource information in the edges, yielding the predictable result of more efficient data orchestration conversion and transformation operations.
Claim 11 recites similar limitations as those of claim 1, additionally reciting one or more electronic processors configured to execute a set of computer-executable instructions; and one or more non-transitory computer-readable media containing the set of computer-executable instructions. Cai teaches:
one or more electronic processors configured to execute a set of computer-executable instructions and one or more non-transitory computer-readable media containing the set of computer-executable instructions (Paragraph 64; “Embodiments herein include database systems, methods, and tangible non-transitory computer-readable media. The methods may be executed, for example, by at least one processor that receives instructions from a tangible non-transitory computer-readable storage medium. Similarly, systems consistent with the present disclosure may include at least one processor and memory, and the memory may be a tangible non-transitory computer-readable storage medium.”).
Claim 11 is rejected for similar reasons as those of claim 1.
Claim 16 recites similar limitations as those of claim 1, additionally reciting one or more non-transitory computer-readable media comprising a set of computer-executable instructions that when executed by one or more programmed electronic processors, cause the processors or an apparatus or device in which they are contained to perform actions.
Cai teaches:
one or more non-transitory computer-readable media comprising a set of computer-executable instructions that when executed by one or more programmed electronic processors, cause the processors or an apparatus or device in which they are contained to perform actions (Paragraph 64; “Embodiments herein include database systems, methods, and tangible non-transitory computer-readable media. The methods may be executed, for example, by at least one processor that receives instructions from a tangible non-transitory computer-readable storage medium. Similarly, systems consistent with the present disclosure may include at least one processor and memory, and the memory may be a tangible non-transitory computer-readable storage medium.”).
Claim 16 is rejected for similar reasons as those of claim 1.
Regarding claim 3, Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert teach the method of claim 1. Buniatyan teaches:
wherein each operation in the sequence of one or more data conversion and transformation operations is associated with a data format or structure for an input or an output of a data conversion or data transformation operation (Paragraphs 27-28; “The data transformation module 110 may comprise suitable logic, interfaces, and/or code that may be configured to transform each data element into a set of tensors for each data type.”, and “data transformation module 110 receives a plurality of transformation functions concatenated together as a dependency directed acyclic graph to transform the plurality of large-scale datasets from one form into another.”. Because each transformation function receives data in a tensor or dataset representation and transforms the data from one form into another, each operation in the sequence is associated with a data format or structure corresponding to the input/output belonging to the operation.).
Englert teaches:
association with one or more specific dependencies (Paragraph 51; “framework 260 can analyze code and determine input parameters and output data format corresponding to various algorithms. For example, code be analyzed to determine a function's type, where the type includes an indication of the function's parameter types and return type. Based at least in part on the inputs parameters and output data format, the framework 260 can determine an order of algorithms and/or temporal dependencies between such algorithms.”, corresponding to determining dependencies between operations in a processing workflow.).
It would have been obvious to a person of ordinary skill in the art to incorporate the dependency determination of Englert into the DAG-based transformation pipeline of Buniatyan because doing so would implement the known method of enforcing structured compatibility between successive transformation operations, yielding the predictable result of ensuring that outputs of one operation are properly formatted as inputs to subsequent dependent operations.
Claim 13 recites similar limitations as those of claim 3. Claim 13 is rejected for similar reasons as those of claim 3.
Claim 18 recites similar limitations as those of claim 3. Claim 18 is rejected for similar reasons as those of claim 3.
Regarding claim 4, Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert teach the method of claim 1. Cai teaches:
wherein the specific type or class of processor comprises a CPU, a GPU, a DSP, a FPGA, or an ASIC (Paragraph 28; “accelerators can be, for example, GPU (Graphics Processing Unit), FPGA (Field Programmable Gate Array), ASIC (Application Specific Integrated Circuit)”, explicitly corresponding to the GPU, FPGA, and ASIC elements of the list of elements.).
Regarding claim 5, Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert teach the method of claim 1. Watzke teaches:
processing data including rows and columns in a table (Col. 3, lines 17-21; “Based on various considerations, a determination by the database management system to reparation the rows of the column-specific data may result in a processing task being generated for each unique column-oriented task identified in the query. Each processing task may be used to direct retrieval of rows containing column data needed to meet the request, as well as, repartitioning the rows and to process column-specific data in order to generate a results set to the query.”).
El-Khamy teaches:
rebalancing the data input or output by an operation to have substantially the same size (Paragraph 72; “Third, at 304, the super resolution imaging system 100 then modifies a subsequent stage network to perform appropriate resizing at output of each convolutional layer (as stretching or padding) to enforce same input and output sizes.”).
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have maintained the same row and column dimensions of Watzke based on El-Khamy teaching preserving input/output sizes. A person of ordinary skill in the art would have been motivated to utilize the known resizing technique of El-Khamy in the tabular data processing environment of Watzke to maintain dimensional consistency between the inputs and outputs of processing operations thereby facilitating compatibility between successive operations and simplifying downstream processing, yielding the predictable result of adjusting the number of rows and columns in a table such that the input and output data have the same dimensions.
Claims 2, 12, and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Rodriguez et al. (US 20200159820 A1) hereafter Rodriguez.
Regarding claim 2, Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert teach the method of claim 1. Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert does not teach wherein the one or more data conversion and data transformation operations comprise executing an optical character recognition model on a PDF document to extract text content, sanitizing raw text fields to remove unexpected characters, or executing a machine learning model on text data to compute an embedding representation.
However, Rodriguez teaches:
wherein the one or more data conversion and data transformation operations comprise executing an optical character recognition model on a PDF document to extract text content, sanitizing raw text fields to remove unexpected characters, or executing a machine learning model on text data to compute an embedding representation (Paragraph 51; “Structural Elements Extractor (SEE) module was designed to extract the text of almost any type of scanned document so as its structure (i.e., the frame). The SEE is not restrained to form understanding (FU) and can also be used for the extraction of textual content from any pdf document”, and Paragraph 77; “program module extracts Regions of Interests (RoIs) from the form. A RoI represents a text region or a group of words close to each other. The sub-section assumes that a group of words close topologically speaking are also close semantically speaking. This assumption is usually respected in forms where each field is separated by a blank space or by a line with the next one. Each RoI will then be fed to the OCR for content extraction. A text region corresponds to maximum one full line of text”, corresponding to the element of executing an optical character recognition model on a PDF document to extract text content.).
Buniatyan, Cai, Watzke, El-Khamy, Englert, and Rodriguez are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert to incorporate the teachings of Rodriguez and have the one or more data conversion and data transformation operations comprise executing an optical character recognition model on a PDF document to extract text content. A person of ordinary skill in the art would have been motivated to include OCR processing as one of the transformation operations because doing so enables text information within PDFs to be converted into a structured format that can be processed by subsequent operations. Applying the known method of OCR to the transformation pipeline would have yielded the predictable result of extracting text content from PDF documents for use in downstream processing operations.
Claim 12 recites similar limitations as those of claim 2. Claim 12 is rejected for similar reasons as those of claim 2.
Claim 17 recites similar limitations as those of claim 2. Claim 17 is rejected for similar reasons as those of claim 2.
Claims 6, 14, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Steinburger et al. (US 20230123634 A1) hereafter Steinburger, further in view of Chandra et al. (US 20190266015 A1) hereafter Chandra.
Regarding claim 6, Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert teach the method of claim 1. Cai teaches:
wherein associating each sub-graph with an execution time and memory used to process the data input to a sub-graph using the one or more operations represented by the sub-graph (Paragraph 44; “graph partitioner 320 may consider. the execution specialty, if any, of each of the available accelerators” when partitioning or mapping the computation graph. the appropriate number of nodes and edges for a subgraph can be determined based on available accelerators, each accelerator's capacity, time requirements, properties of a data structure.) further comprises:
using an estimation mechanism of the operations or functions associated with a sub-graph (Paragraph 46; "The accelerator information may include computing throughput information and memory bandwidth operation profiling information may include execution time or speed information and delay information of an accelerator for executing a certain operation such as a convolution, matrix multiplication, etc. The operation profiling information can be estimated by simulations or obtained by previous experiments”).
Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert does not teach sampling, or a value for the peak memory used to process the sampled data.
However, Steinburger teaches:
sampling (Paragraph 44; “For example, the scheduling of the processing of the data samples (which may be done on a set of data samples-by-set of data samples basis) may consider priority or execution deadlines of the data samples (individually, as groups, or collectively) as well as required resources (e.g., a number of threads, registers, local shared memory, number of required synchronization barriers, and execution time) for the processing thereof”).
Buniatyan, Cai, Watzke, El-Khamy, Englert, and Steinburger are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert to incorporate the teachings of Steinburger and incorporate a sampling mechanism. A person of ordinary skill in the art would have been motivated to incorporate the sampling mechanism into the system because sampling is a known method that reduces computational overhead associated with full processing while providing representative estimates of resource usage and execution time. Such a modification would yield the predictable result of determining execution time and memory requirements of subgraphs based on sampled data, thereby improving efficiency of performance estimation.
Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Steinburger does not teach a value for the peak memory.
However, Chandra teaches:
a value for the peak memory (Paragraph 47; “the performance model predicts the time taken and peak RAM usage of a DNN workload”.).
Buniatyan, Cai, Watzke, El-Khamy, Englert, Steinburger, and Chandra are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Steinburger to incorporate the teachings of Chandra and determine peak memory usage values. A person of ordinary skill in the art would have been motivated to incorporate the peak memory determination because memory usage is a known critical constraint in execution planning and resource management, and estimating memory usage based on sample data provides an efficient alternative to full workload evaluation, yielding the predictable result of determining a value for the peak memory used to process sampled data and improving the efficiency of resource determination.
Claim 14 recites similar limitations as those of claim 6. Claim 14 is rejected for similar reasons as those of claim 6.
Claim 19 recites similar limitations as those of claim 6. Claim 19 is rejected for similar reasons as those of claim 6.
Claims 7-8, 15, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Steinburger, further in view of Chandra, further in view of Wong et al. (US 20190065241 A1) hereafter Wong.
Regarding claim 7, Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Steinburger, further in view of Chandra teach the method of claim 6. Cai teaches:
a set of data used as an input to the sub-graph (Paragraph 39; “A node representing a computation operation can consume input data flowing in along an incoming edge to the node, while output data produced by the computation operation can flow out along an outgoing edge from the node.”, the incoming data to the node corresponding to the set of data used as input to the subgraph because the node is contained within the subgraph and receives data through the incoming edge.).
Chandra teaches:
a value for the peak memory (Paragraph 47; “the performance model predicts the time taken and peak RAM usage of a DNN workload”.).
Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Steinburger, further in view of Chandra does not teach interpolating or extrapolating the execution time for an entire set of data.
However, Wong teaches:
interpolating or extrapolating the execution time (Paragraph 189; “The expected execution times may be extrapolated on a per step basis and presented to an end user for both the individual stages and the global stages. The estimate may allow a user to more efficiently schedule and execute recipes.”, explicitly teaches extrapolation of an execution time of a set of data).
Buniatyan, Cai, Watzke, El-Khamy, Englert, Steinburger, Chandra, and Wong are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Steinburger, further in view of Chandra to incorporate the teachings of Wong and have interpolated or extrapolated the execution time. A person of ordinary skill in the art would have been motivated to incorporate the extrapolation techniques of Wong because estimating execution time from representative measurements reduces profiling overhead and enables performance prediction for workloads. Such a modification would have yielded the predictable result of extrapolating execution time for a larger set of operations based on execution characteristics.
Regarding claim 8, Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Steinburger, further in view of Chandra, further in view of Wong teach the method of claim 7. Cai teaches:
using a specific type or class of processor (Paragraphs 44-45; “graph partitioner 320 can partition a computation graph into multiple subgraphs that are executed on different accelerators based on the subgraph profiling information to optimize performance in executing the computation graph. For example, a computation graph may include subgraphs that are commonly used in many machine learning models as their components. For example, the commonly used subgraphs can include MobileNets layers, ResNet layers, Region Proposal Network, etc. In some embodiments, prior history of execution, experiments, or simulations of a certain subgraph on accelerators can identify which accelerator is optimal for processing the certain subgraph. In some embodiments, each subgraph can be assigned to a certain accelerator that can optimize performance of executing the subgraph.”, the identification of the specific accelerator is optimal for processing the specific subgraph corresponding to for each subgraph, executing the one or more operations associated with a subgraph using the specific type or class of processor.).
Chandra teaches:
a value for the peak memory (Paragraph 47; “the performance model predicts the time taken and peak RAM usage of a DNN workload”.).
Wong teaches:
using the interpolated or extrapolated execution time (Paragraph 189; “The expected execution times may be extrapolated on a per step basis and presented to an end user for both the individual stages and the global stages. The estimate may allow a user to more efficiently schedule and execute recipes.”, explicitly teaches extrapolation of an execution time of a set of data).
It would have been obvious to a person of ordinary skill in the art to utilize the extrapolated execution time information of Wong together with the peak memory values of Chandra in the processor selection and execution framework of Cai. A person of ordinary skill in the art would have been motivated to use both estimated execution time and peak memory consumption when selecting, assigning, or executing workloads on a particular processor type because execution time and memory usage are known metrics for analyzing processor suitability and scheduling decisions. Combining these known techniques would have yielded the predictable result of utilizing known metrics to improve workload placement and resource allocation.
Claim 15 recites similar limitations as those of claims 7 and 8 in combination. Claim 15 is rejected for similar reasons as those of claims 7 and 8.
Claim 20 recites similar limitations as those of claims 7 and 8 in combination. Claim 20 is rejected for similar reasons as those of claims 7 and 8.
Claim 9 is rejected under 35 U.S.C. 103 as being unpatentable over Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert, further in view of Bolanowski et al. (US 20120278532 A1) hereafter Bolanowski.
Regarding claim 9, Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert teach the method of claim 1. Cai teaches:
the memory requirement for the data in the partition exceeds that to be executed by a single processor or device (Paragraphs 45, 58; “the computation graph can be divided into any number of subgraphs based on available accelerators”, “computing resources available in each of the available accelerators, the execution specialty, if any, of each of the available accelerators, among other things can be considered when partitioning or mapping the computation graph.”, and “each subgraph can be assigned to a certain accelerator that can optimize performance of executing the subgraph”. Partitioning decisions are made in view of available resources on a single processor or device and a graph may be divided into additional subgraphs when the existing partition is unsuitable for execution, memory being part of the computing resources available in the accelerator as evidenced in Paragraph 46, “accelerator information may include computing throughput information and memory bandwidth.”.).
Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert does not teach dynamically reducing a partition size.
However, Bolanowski teaches:
dynamically reducing a partition size (Paragraph 27; “determining if write activity for each monitored address exceeds a threshold for the address and, if so, consider each address with write activity that exceeds the threshold for the address as an active address; and reducing a size of the dynamic enhanced partition”, which expressly discloses dynamically reducing the size of a partition in response to a detected condition exceeding a threshold.).
Buniatyan, Cai, Watzke, El-Khamy, Englert, and Bolanowski are considered to be analogous to the claimed invention because they are in the same field of distributed system load balancing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Buniatyan in view of Cai, further in view of Watzke, further in view of El-Khamy, further in view of Englert to incorporate the teachings of Bolanowski and apply dynamic partition size reduction. A person of ordinary skill in the art would have been motivated to reduce the size of a partition when resource requirements associated with the partition exceed those suitable for execution on a single processor because doing so would allow the workload to fit within the available processing resources, thus implementing the known method of facilitating the assignment of partitions to appropriate accelerators via dynamic partition size reduction, yielding the predictable result of improved workload distribution and optimized execution performance.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Holm et al. (US 20240248764 A1) discloses handling task data, the task data describing a task to be executed as a directed acyclic graph of operations, wherein each operation maps to a corresponding execution unit, and wherein each connection between operations in the acyclic graph maps to a corresponding storage element of the execution unit. The task data defines an operation space representing the dimensions of a multi-dimensional arrangement of the connected operations to be executed represented by the data blocks.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to KENNETH P TRAN whose telephone number is (571)272-6926. The examiner can normally be reached M-TH 4:30 a.m. - 12:30 p.m. PT, F 4:30 a.m. - 8:30 a.m. PT, or at Kenneth.Tran@uspto.gov.
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, April Blair can be reached at (571) 270-1014. 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.
/KENNETH P TRAN/Examiner, Art Unit 2196 /APRIL Y BLAIR/Supervisory Patent Examiner, Art Unit 2196
Prosecution Insights