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 .
Priority
Acknowledgment is made of applicant's claim for foreign priority based on European Patent Application EP23306940.0, filed 11/09/2023. However, priority documents have not been received. See Failure Status Report receipt on 04/09/2025.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 11/07/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.
Specification
The abstract of the disclosure is objected to because the abstract recites: “an application executed by a node of a High-Performance Computing system while said node is running an application”. “The form and legal phraseology often used in patent claims, such as "means" and "said," should be avoided.” (MPEP 608.01(b)(I)(C)).
A corrected abstract of the disclosure is required and must be presented on a separate sheet, apart from any other text. See MPEP § 608.01(b).
Claim Objections
Claim 4 is objected to because of the following informalities: the claim recites “adding the directred edge in the graph from the first vertex to the second vertex;”. “directred” is misspelled. The Examiner suggests “directed”.
Appropriate correction is required.
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, 13-15 are rejected under 35 U.S.C. 103 as being unpatentable over Yoo et al. (US 20190179752 A1) hereafter Yoo, in view of Fleming et al. (US 20190004945 A1) hereafter Fleming, further in view of Zhai et al. (US 20230244588 A1) hereafter Zhai.
Regarding claim 1, Yoo teaches:
predicting data to be used for execution (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”, which describes the prediction of data likely to be used to execute queries.);
predicting an Input/Output request to be required, corresponding to the data that is predicted, the Input/Output request at least defining the data to be prefetched (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”. The query corresponds to the input/output request because a query can be both a request for data results and an action on the data. It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to predict data required by a request from an application. Yoo teaches predicting data that is likely to be used on a subsequent graph query request based on an access frequency and caching the predicted data in anticipation of the request. A modification of Yoo’s predictive caching technique to predict and separately cache data required for servicing a request, rather than merely data that may be required, would have been a predictable application of Yoo’s identifying data expected to be accessed by a request, yielding the predictable result of ensuring that data necessary for servicing the request is available when the request is received, involving the use of Yoo’s access predictive techniques for their known purpose of anticipating data requirements of a request, with a reasonable expectation of success.);
wherein said predicting the data is carried out based on the first data associated with the first vertex (Paragraph 35; “multi-level caching system may assign a weight to data based on a pattern of a frequently used subgraph and may cache the data in a first cache memory (for example, a used data cache). Also, the multi-level caching system may cache, in a second cache memory (for example, a prefetched cache), neighboring data determined to be highly likely to be connected to and used together with recently used data although not used.”, teaching determining data likely to be connected to and used together with recently used data, and Paragraph 95 teaches predicting data likely to be used on a graph query request, thereby teaching prediction based on recently used graph-related information, the sub-graph information corresponding to a portion of the graph, which includes the first vertex as claimed.);
and first data corresponding to a lastly received request (Paragraph 35; “multi-level caching system may cache, in a second cache memory (for example, a prefetched cache), neighboring data determined to be highly likely to be connected to and used together with recently used data although not used.”, which teaches using recently used data as a basis for determining neighboring data that is likely to be connected to and used together with the recently used data for subsequent activity. The lastly received aspect is an obvious selection of the most recently received request from the request history, utilizing Yoo’s teaching that a recent usage is relevant to predicting subsequent usage. ).
Yoo does not explicitly teach prefetching data related to an application executed by a node of a High-Performance Computing system; prefetching the data that is predicted.
However, Fleming teaches:
A computer implemented method for prefetching data related to an application (Paragraphs 214-215, 286-288; “Prefetching modes”, “prefetch configuration information”) executed by a node of a High-Performance Computing system (Paragraphs 72-74; “configurable spatial accelerator (CSA) that targets high performance computing”, “directly (e.g., without using a table of work) execute existing high performance computing (HPC) code”, and “Depicted accelerator tile 100 is a heterogeneous array comprised of several kinds of PEs coupled together via an interconnect network 104. Accelerator tile 100 may include one or more of integer arithmetic PEs, floating point arithmetic PEs, communication circuitry, and in-fabric storage.”, in which given a generic HPC system containing a plurality of different CSA processing elements, a person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized a HPC node as an option for execution), the computer implemented method comprising:
prefetching the data that is predicted (Paragraph 214; “A configuration path is augmented with a new command, ConfigurationCachePrefetch. Instead of programming the fabric, this command simply causes a load of the relevant program configuration into a configuration cache”, and Paragraph 215; “A global configuration controller may maintain a prefetch predictor, and use this to initiate the explicit prefetching to a configuration cache, e.g., in an automated fashion.”).
Yoo and Fleming are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo and Fleming and implement a method for prefetching data related to an application on a node of an HPC and prefetching predicted data. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that applying the known technique of predicting data likely to be subsequently requested and prefetching the predicted data would therefore allow the HPC node to retrieve the data before the application requests it, yielding the predictable result of reduced latency associated with subsequent data accesses that are correctly predicted, and improving application performance, involving an implementation of the predictive-prefetching technique for its known purpose of anticipating future data accesses without requiring changes to the underlying operation of the HPC node or application.
Yoo in view of Fleming does not teach a graph comprising one or more vertices, each vertex of the one or more vertices being associated with one call-stack corresponding to one Input/Output request previously required by the application, the one or more vertices comprising at least a first vertex associated with a first call-stack corresponding to a lastly required Input/Output request, wherein said predicting the call-stack is carried out based on the first call-stack associated with the first vertex.
However, Zhai teaches:
a graph comprising one or more vertices, each vertex of the one or more vertices being associated with one call-stack corresponding to one request previously required by the application (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime… and associate performance data with the corresponding program structure graph vertex, according to the program call stack information. In addition to hardware counter performance data, the performance data of the vertex can also be user-defined performance data in software, for example, user manual timing, or manual statistics of a certain variable.”, which explicitly discloses a program structure graph comprising multiple vertices which, during runtime, has its “program call stack and related performance data… recorded” and “associate[d]… with the corresponding program structure graph vertex, according to the program call stack information”, establishing an association between the graph vertex and the call stack info used to identify/correspond the runtime execution represented by the vertex to its related vertex dependencies. This can be used for applications as evidenced in Paragraph 64; “several causal paths that connect a set of problematic vertices are obtained. Further analysis of these identified paths will help application developers to locate the root cause.”);
the one or more vertices comprising at least a first vertex associated with a first call-stack corresponding to a lastly required request (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime”, thereby teaching a graph having one or more vertices, including a first vertex, and “program call stack and related performance data are recorded”, according to program call stack info, thus associating call stack info with corresponding graph vertices.).
Yoo, Fleming, and Zhai are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming and Zhai to have a graph comprising one or more vertices, each vertex of the one or more vertices being associated with one call-stack corresponding to one Input/Output request previously required by the application, the one or more vertices comprising at least a first vertex associated with a first call-stack corresponding to a lastly required Input/Output request, wherein said predicting the call-stack is carried out based on the first call-stack associated with the first vertex. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that identifying the context associated with graph activity is a known method in the art whose implementation would yield the predictable result of allowing the prediction system to use relevant information to infer the execution path of the application, yielding the predictable result of providing more accurate predictions of required data for execution, and thus, faster execution. Further, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have the requests of Zhai be substituted as an I/O request as taught by Yoo. A person of ordinary skill in the art would have recognized that requests may come in many different forms, an I/O request is well known in the art, and would have been motivated to substitute such a request for the requests of Zhai with a reasonable expectation of success.
Claim 13 recites similar limitations as those of claim 1, additionally reciting a circuit and a processor. Fleming teaches:
a circuit (Paragraph 95; “Moreover, because embodiments of the architecture are extremely parallel, a number of powerful circuit and device level optimizations are possible without seriously impacting throughput”);
and a processor (Paragraph 378; “Thus, different implementations of the processor 4100 may include: 1) a CPU with the special purpose logic 4108 being integrated graphics and/or scientific (throughput) logic”).
Yoo, Fleming, and Zhai are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, and Zhai to have utilized a circuit and a processor. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized circuitry and processors to be well known computing parts for processing information, whose implementation would yield the predictable result of execution of the claimed invention.
Claim 13 is rejected for similar reasons as those of claim 1.
Claim 15 recites similar limitations as those of claim 1, additionally reciting a non-transitory computer program product. Fleming teaches:
A non-transitory computer program product (Paragraph 403; “embodiments of the disclosure also include non-transitory, tangible machine-readable media containing instructions or containing design data, such as Hardware Description Language (HDL), which defines structures, circuits, apparatuses, processors and/or system features described herein. Such embodiments may also be referred to as program products.”).
Yoo, Fleming, and Zhai are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, and Zhai to have utilized a non-transitory computer program product. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized non-transitory mediums storing the program product of instructions to be a well-known method for storing executable code, yielding the predictable result of storage of code for executing the claimed invention.
Claim 15 is rejected for similar reasons as those of claim 1.
Regarding claim 3, Yoo in view of Fleming, further in view of Zhai teach the method of claim 1. Yoo teaches:
Input/Output request (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”, the query corresponding to an I/O request because a query can be used for a request for data results and for action on the data.).
wherein the predicting is carried out when a request is currently required (Paragraph 48; “when a query requesting a subgraph 801 is received, the searcher 110 may search for three vertices, for example, vertices V.sub.1, V.sub.3 and V.sub.n+1 included in the subgraph 801 from a first cache memory 151, 810 in which vertices of a subgraph used in a previous query request are cached.”, the query being the request that is required to be executed.).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have performed the prediction when the request is currently required because initiating the prediction upon identification of a currently required request would allow the system to use the request as the basis for determining the data or execution information needed to service the request, yielding the predictable result of providing the information in anticipation of processing the request and reducing delay time.
Zhai teaches:
the first vertex associated with the first call-stack corresponding to the lastly required request before the request that is currently required by the application (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime”, thereby teaching a graph having one or more vertices, including a first vertex, and “program call stack and related performance data are recorded”, according to program call stack info, thus associating call stack info with corresponding graph vertices. The selection of the first vertex associated with the first call stack which is the last request before the current one would be understood by a person of ordinary skill in the art as corresponding to the first vertex of the program structure graph while traversing through the graph, and Paragraph 64; “several causal paths that connect a set of problematic vertices are obtained. Further analysis of these identified paths will help application developers to locate the root cause” discloses the use of an application.).
Regarding claim 14, Yoo in view of Fleming, further in view of Zhai teach the system of claim 13. Fleming teaches:
wherein said system is comprised in a High-Performance Computing system (Paragraphs 72-74; “configurable spatial accelerator (CSA) that targets high performance computing”, explicitly disclosing a processing device targeted towards HPC. A person of ordinary skill in the art before the effective filing date of the claimed invention would recognize this would involve the use of a HPC system.).
Claim 2 is rejected under 35 U.S.C. 103 as being unpatentable over Yoo in view of Fleming, further in view of Zhai, further in view of Yang et al. (US 20260172473 A1) hereafter Yang.
Regarding claim 2, Yoo in view of Fleming, further in view of Zhai teach the method of claim 1. Yoo teaches:
Input/Output request (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”, the query corresponding to an I/O request because a query can be used for a request for data results and for action on the data.).
Fleming teaches:
wherein the graph is initiated with a vertex associated with the data corresponding to an initial request (Paragraph 174; “Another important class of CFGs in dataflow conversion are CFGs for single-entry-single-exit loops, a common form of loop generated in (LLVM) IR. These loops may be almost acyclic, except for a single back edge from the end of the loop back to a loop header block. The dataflow conversion pass may use same high-level strategy to convert loops as for branches, e.g., it inserts switches at the end of the loop to direct values out of the loop (either out the loop exit or around the back-edge to the beginning of the loop), and inserts picks at the beginning of the loop to choose between initial values entering the loop and values coming through the back edge.”. Since the CFG of Fleming has a single designated entry, a person of ordinary skill in the art would have found it obvious to initiate graph processing at the entry vertex, corresponding to the initial request.);
Zhai teaches:
call-stack information (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime… and associate performance data with the corresponding program structure graph vertex, according to the program call stack information”).
Yoo in view of Fleming, further in view of Zhai does not teach said initial request being required by the application when initializing said application.
However, Yang teaches:
said initial request being required by the application when initializing said application (Paragraph 70; “a method for creating the user-mode memory region includes that the RDMA application may initiate an RDMA resource initialization request to the user-mode event management instance, where the RDMA resource initialization request is used to request various resources needed to create an RDMA application”, where the RDMA initialization request corresponds to the initial request for the application, which requests the resources needed to create said application.).
Yoo, Fleming, Zhai, and Yang are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, and Yang and have the graph be associated with an initial I/O request required by the application during initialization. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that applications commonly perform I/O operations during initialization to obtain/load info needed to establish application initial operating state. Providing the required I/O request during initialization would therefore ensure that info needed to initialize the application is obtained before subsequent application processing begins, which, when applied to the graph of Yoo, Fleming, and Zhai, yields the predictable result of graph operations using known I/O operations to obtain initialization data for its intended purpose with a reasonable expectation of success.
Claim 4 is rejected under 35 U.S.C. 103 as being unpatentable over Yoo in view of Fleming, further in view of Zhai, further in view of Yang, further in view of Hunter et al. (US 20210073285 A1) hereafter Hunter, further in view of Oka et al. (US 20190391902 A1) hereafter Oka.
Regarding claim 4, Yoo in view of Fleming, further in view of Zhai teach the method of claim 3. Yoo teaches:
Input/Output request (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”, the query corresponding to an I/O request because a query can be used for a request for data results and for action on the data.).
Zhai teaches:
retrieving a current call-stack (Paragraph 44; “hardware counter interface is configured to sample and collect hardware performance data, wherein, the program is interrupted at regular clock cycles and program call stack and related performance data are recorded”).
Yoo in view of Fleming, further in view of Zhai does not teach the currently required request; or detecting that the Input/Output request is currently required by the application.
However, Yang teaches:
detecting that the Input/Output request is currently required by the application (Paragraph 70; “a method for creating the user-mode memory region includes that the RDMA application may initiate an RDMA resource initialization request to the user-mode event management instance, where the RDMA resource initialization request is used to request various resources needed to create an RDMA application”, in which the initialization request for resources, thereby being an output request, is currently required by the RDMA application.);
and the currently required request (Paragraph 70; “a method for creating the user-mode memory region includes that the RDMA application may initiate an RDMA resource initialization request to the user-mode event management instance, where the RDMA resource initialization request is used to request various resources needed to create an RDMA application”).
Yoo, Fleming, Zhai, and Yang are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, and Yang and have the graph be associated with an initial I/O request required by the application. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that applications commonly perform I/O operations to obtain/load info needed for the application. Providing the required I/O request during initialization would therefore ensure that info needed for the application is obtained before processing continues, which, when applied to the graph of Yoo, Fleming, and Zhai, yields the predictable result of graph operations using known I/O operations to obtain execution data for its intended purpose with a reasonable expectation of success.
Yoo in view of Fleming, further in view of Zhai, further in view of Yang does not teach when the current call-stack is not similar to a previous call-stack corresponding to a previous Input/Output request required by the application; adding a second vertex in the graph associated with said current call-stack; adding a directed edge in the graph from the first vertex to the second vertex; when the current call-stack is similar to the previous call-stack corresponding to the previous Input/Output request required by the application but no edge in the graph connects the first vertex to the second vertex corresponding to the current call-stack; adding the directed edge in the graph from the first vertex to the second vertex; the current call-stack becoming the first call-stack for predicting the call-stack.
However, Hunter teaches:
no edge in the graph connects the first vertex to the second vertex corresponding to the current state (Paragraph 77; explicitly contemplates “other vertices are not directly connected to the triggered vertex.”, where a person of ordinary skill in the art before the effective filing date of the claimed invention would have found it obvious that an unconnected edge connecting a first vertex to the current state vertex would be a graph structure that is different from the current state and would necessitate performing corrective actions thereof.);
adding a second vertex in the graph associated with said current data, and adding a directed edge in the graph from the first vertex to the second vertex (Embodiment C-8; “in response to a determination that the first graph structure is different from the second graph structure with respect to a number of vertices or number of edges, adding a new vertex to the set of vertices based on the request in persistent memory.”, explicitly disclosing revising the graph to add new vertices/edges in response to a difference determination. Since a new vertex was added, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have additionally added a directed edge in the graph connecting the edge to its dependent vertex.);
adding the directed edge in the graph from the first vertex to the second vertex (Embodiment C-8; “in response to a determination that the first graph structure is different from the second graph structure with respect to a number of vertices or number of edges, adding a new vertex to the set of vertices based on the request in persistent memory.”, explicitly disclosing revising the graph to add new vertices/edges in response to a difference determination.);
the current status becoming the first status for predicting the status (Paragraph 106; “the system may perform one or more iterations of operations to modify the statuses of a first set of vertices and then update the program state data based on the modified statuses in order to acquire a plurality of outcomes. The program state data or a portion of the program state data may be in a same state at the start each iteration, where two states of program state data are identical if both states have the same set of values. For example, if a first state of program state data is [1,2,3], and if a second state of program state data is [1,2,4], and if the program state data is reverted to [1,2,3], the reverted program state data may be described as being in the first state.”, which explicitly describes updating the program state data in which the current state is used for status prediction.).
Yoo, Fleming, Zhai, Yang, and Hunter are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, Yang, and Hunter, to have revised the graph to add vertices and directed edges when necessary. A person of ordinary skill in the art would recognize that as program execution traverses the graph, updating the graph to include dependencies that were not previously included would allow the graph to have up to date information, yielding the predictable result of providing faster prefetch information by utilizing the up-to-date graph. Further, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have had the vertices of the graph correspond to the call stack of Zhai. A person of ordinary skill in the art would have recognized that correlating the execution context represented by the call stack with the corresponding portion of the program structure graph would allow the behavior and performance information to be analyzed in the context of the application execution path, corresponding to a modification of the known call stack information technique associated with graph vertices with the graph of the claimed system, with a reasonable expectation of success.
Yoo in view of Fleming, further in view of Zhai, further in view of Yang, further in view of Hunter does not teach when the current state is not similar to a previous state corresponding to a previous required request; when the current state is similar to the previous state corresponding to the previous required request but no edge in the graph connects the first vertex to the second vertex corresponding to the current state.
However, Oka teaches:
when the current state is not similar to a previous state corresponding to a previous required request (Paragraph 75; “This is accomplished by selecting a method which is the closest from the previous most important frame in the first step when there are multiple methods which are the same as the user-selected frame in the same call stack or selecting a method which has a similar pattern of callers and callees as that of the user-selected frame when there are multiple methods which are the same as the user-selected frame in the same call stack. If a call stack does not include the user-selected frame, the call stack is placed as another set of frames based on the previous important frame in the first step. A call stack which does not include the user-selected frame is placed next to the updated visualization result.”, where if the call stack is not similar, a particular action is taken.);
when the current state is similar to the previous state corresponding to the previous required request (Paragraph 75; “This is accomplished by selecting a method which is the closest from the previous most important frame in the first step when there are multiple methods which are the same as the user-selected frame in the same call stack or selecting a method which has a similar pattern of callers and callees as that of the user-selected frame when there are multiple methods which are the same as the user-selected frame in the same call stack. If a call stack does not include the user-selected frame, the call stack is placed as another set of frames based on the previous important frame in the first step. A call stack which does not include the user-selected frame is placed next to the updated visualization result.”, where if the call stack is similar, a different particular action is taken.).
Yoo, Fleming, Zhai, Yang, Hunter, and Oka are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, Yang, Hunter, and Oka to have performed actions when the current call stack of Zhai is/is not similar to the state of the previous I/O request of Yoo as required by the application of Yang. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that using a call stack as the state associated with a previously required I/O request and performing actions based on whether the current call stack state is similar or not to a previous state is a known method in the art because Zhai explicitly records the program call stack during runtime and associates information with a corresponding vertex according to the call stack info, and Yoo explicitly uses recently used data to predict information for a subsequent request, whose implementation would yield the predictable result of using the current call stack to determine whether the current execution state of the application corresponds to a state associated with a previous I/O request and performing corresponding actions based on that determination.
Claims 5 and 7 are rejected under 35 U.S.C. 103 as being unpatentable over Yoo in view of Fleming, further in view of Zhai, further in view of Maeda et al. (US 20170255577 A1) hereafter Maeda.
Regarding claim 5, Yoo in view of Fleming, further in view of Zhai teach the method of claim 1. Yoo teaches:
Input/Output request (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”, the query corresponding to an I/O request because a query can be used for a request for data results and for action on the data.).
Zhai teaches:
the call-stack (Paragraph 44; “hardware counter interface is configured to sample and collect hardware performance data, wherein, the program is interrupted at regular clock cycles and program call stack and related performance data are recorded”).
Yoo in view of Fleming, further in view of Zhai does not teach a hash table.
However, Maeda teaches:
a hash table (Paragraph 24; “If the provided hash value is not registered in the hash table 7, the DMAC 6 transfers the data from the main memory 4 to the main memory 10 and updates the hash table 7 using the transferred data and an address of a destination of the transfer.”).
Yoo, Fleming, Zhai, and Maeda are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, and Maeda to have utilized a hash table to store the correspondence between the call stack of Zhai and the I/O request of Yoo. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized the use of a hash table to store/retrieve information is a known method in the art because hash tables are a well-known mechanism for storing information and efficiently retrieving information, whose implementation would yield the predictable result of efficiently associating and retrieving relevant information.
Regarding claim 7, Yoo in view of Fleming, further in view of Zhai, further in view of Maeda teach the method of claim 5. Yoo teaches:
Input/Output request (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”, the query corresponding to an I/O request because a query can be used for a request for data results and for action on the data.).
Zhai teaches:
the call-stack (Paragraph 44; “hardware counter interface is configured to sample and collect hardware performance data, wherein, the program is interrupted at regular clock cycles and program call stack and related performance data are recorded”);
vertices in the graph (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime… and associate performance data with the corresponding program structure graph vertex, according to the program call stack information.).
Maeda teaches:
An identifier (ID) of the data with which it is associated, being comprised within the hash table (Paragraph 20; “The tag table (second hash table) 51 retains hash values of data inputted from the I/O apparatus 3. The tag table 51 includes one or more tag entries. Each tag entry includes two fields that are an address tag and a hash value. The address tag is a tag for identifying an address of a destination in which data is to be stored in the main memory 4.”).
Claim 6 is rejected under 35 U.S.C. 103 as being unpatentable over Yoo in view of Fleming, further in view of Zhai, further in view of Maeda, further in view of Oka.
Regarding claim 6, Yoo in view of Fleming, further in view of Zhai, further in view of Maeda teach the method of claim 5. Zhai teaches:
association with one or more vertices (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime… and associate performance data with the corresponding program structure graph vertex, according to the program call stack information.”).
Maeda teaches:
the hash table is updated when there is no match (Paragraph 24; “If the provided hash value is not registered in the hash table 7, the DMAC 6 transfers the data from the main memory 4 to the main memory 10 and updates the hash table 7 using the transferred data and an address of a destination of the transfer.”).
Yoo in view of Fleming, further in view of Zhai, further in view of Maeda does not teach performing actions when a current state is not similar to a previous state.
However, Oka teaches:
performing actions when a current state is not similar to a previous state (Paragraph 75; “This is accomplished by selecting a method which is the closest from the previous most important frame in the first step when there are multiple methods which are the same as the user-selected frame in the same call stack or selecting a method which has a similar pattern of callers and callees as that of the user-selected frame when there are multiple methods which are the same as the user-selected frame in the same call stack. If a call stack does not include the user-selected frame, the call stack is placed as another set of frames based on the previous important frame in the first step. A call stack which does not include the user-selected frame is placed next to the updated visualization result.”, where if the call stack is not similar, a particular action is taken).
Yoo, Fleming, Zhai, Maeda, and Oka are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, Maeda, and Oka to have performed actions when the current call stack of Zhai is/is not similar to the state of the previous I/O request of Yoo. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that using a call stack as the state associated with a previously required I/O request and performing actions based on whether the current call stack state is similar or not to a previous state is a known method in the art because Zhai explicitly records the program call stack during runtime and associates information with a corresponding vertex according to the call stack info, and Yoo explicitly uses recently used data to predict information for a subsequent request, whose implementation would yield the predictable result of using the current call stack to determine whether the current execution state of the application corresponds to a state associated with a previous I/O request and performing corresponding actions based on that determination.
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over Yoo in view of Fleming, further in view of Zhai, further in view of Maeda, further in view of Copty et al. (US 20180232518 A1) hereafter Copty, further in view of Sahasrabudhe et al. (US 20170046359 A1) hereafter Sahasrabudhe.
Regarding claim 8, Yoo in view of Fleming, further in view of Zhai, further in view of Maeda teach the method of claim 7. Maeda teaches:
An identifier (ID) (Paragraph 20; “The tag table (second hash table) 51 retains hash values of data inputted from the I/O apparatus 3. The tag table 51 includes one or more tag entries. Each tag entry includes two fields that are an address tag and a hash value. The address tag is a tag for identifying an address of a destination in which data is to be stored in the main memory 4.”).
Yoo in view of Fleming, further in view of Zhai, further in view of Maeda does not teach a number M of frames of the call stack.
However, Copty teaches:
a number M of frames of the call stack (Paragraph 14; “The stack, generally referenced 100 comprises a number of stack frames 104, 108, each associated with a function or a method call, and arranged such that the latest call is at the top of the stack.”).
Yoo, Fleming, Zhai, Maeda, and Copty are considered to be analogous to the claimed invention because they are in the same field of data processing. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, Maeda, and Copty, to have the number of frames be utilized to determine the identifier. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized determining an identifier based on number of frames to be a known method because the number of frames in a call stack provides a characteristic of the call stack that can be used to distinguish the call stack, yielding the predictable result of generating an identifier based on the frame count of the stack.
Yoo in view of Fleming, further in view of Zhai, further in view of Maeda, further in view of Copty does not teach a limit at 124.
However, Sahasrabudhe teaches:
a limit at 124 (Paragraph 18; “As one example, B1 and B2 may both be set to 128 kilobytes, whereas the N, data blocks, K parity blocks, and R reserve blocks for the respective files may be set to N1=6, K1=2, R1=2, and N2=8, K2=4, and R2=4.”, disclosing an explicit limit as 128 and a reserve section example of 4.).
Yoo, Fleming, Zhai, Maeda, Copty, and Sahasrabudhe are considered to be analogous to the claimed invention because they are in the same field of data processing. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, Maeda, Copty, and Sahasrabudhe to have set an integer limit between 1 and 124. A person of ordinary skill in the art before the effective filing date of the claimed invention would have been motivated by the desire to limit the amount of space required for identifiers, and would thus limit the number of frames identified to 128 (2^7). A person of ordinary skill in the art would also recognize the use of reserved ranges required for system processing as a known method in the art, and utilizing the teachings of Sahasrabudhe of setting a reserved section of 4, and with a number of stack frames in order to be identified necessarily being non-zero, as it is not possible to contain a zero, negative, or decimal positive stack frame value, would have been motivated to utilize a range comprising an integer between 1 and 124.
Claims 9-10 are rejected under 35 U.S.C. 103 as being unpatentable over Yoo in view of Fleming, further in view of Zhai, further in view of Linda (US 20140002467 A1).
Regarding claim 9, Yoo in view of Fleming, further in view of Zhai teach the method of claim 1. Zhai teaches:
when at least one edge connects the first vertex to another vertex of the one or more vertices in the graph (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime”, thereby teaching a graph having one or more vertices, including a first vertex, and “program call stack and related performance data are recorded”, according to program call stack info, thus associating call stack info with corresponding graph vertices. The selection of the first vertex associated with the first call stack which is the last request before the current one would be understood by a person of ordinary skill in the art as corresponding to the first vertex of the program structure graph while traversing through the graph, containing edges that show dependency across the vertices, as evidenced in Paragraph 58; “problematic vertices are detected from the program performance graph, and starting from some or all of the problematic vertices, backtracking is performed through data/control dependence edges within a process and communication dependence edges”.);
call-stack (Paragraph 44; “program call stack and related performance data are recorded”).
Yoo in view of Fleming, further in view of Zhai does not teach choosing among the first data or second data, wherein said data that is predicted is chosen based on a metric value assigned to the at least one edge.
However, Linda teaches:
choosing among the first or second state, wherein said data that is predicted is chosen based on a metric value (Paragraph 30; “a full frame may be modeled as a state diagram with state transition probabilities (e.g., based on a Markov model, observed and unobserved processes) and state transition path at a coarse-level to use for learning/training”, where the implementation of this method effectively acts like an implementation of a Markov chain that selects from a plurality of states in which a next state is predicted based on the current state and the state transition probabilities to the next state(s), corresponding to the metric value.).
Yoo, Fleming, Zhai, and Linda are considered to be analogous to the claimed invention because they are in the same field of data optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, and Linda, to have applied the concept of a Markov chain of Linda to the system of Yoo, Fleming, and Zhai. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized assigning the state transition probabilities to the edges connecting the graph vertices is a known concept in the art because Markov chains are commonly used to determine probabilities for transitions between states (Linda, Paragraph 30), whose implementation would yield the predictable result of associating transition probabilities with the corresponding edges between the vertices representing respective states. A person of ordinary skill in the art before the effective filing date of the claimed invention would have further recognized selecting a predicted call stack based on the metric associated with an edge as a known method in the art because Markov chains are used to predict subsequent states with state transition probabilities, whose implementation would yield the predictable result of selecting the call stack associated with the graph vertex corresponding to the predicted state.
Regarding claim 10, Yoo in view of Fleming, further in view of Zhai, further in view of Linda teach the method of claim 9. Linda teaches:
wherein the metric value is a most recently used path, a most frequently used path, or any combination thereof (Paragraph 37; “a workload (for example, a drawcall or a full frame) may be modeled as a state diagram with state transition probabilities (e.g., Bayesian model or Markov model) and a state transition path at a coarse-level to use for learning/training. This may in turn detect which states never occur and which states occur most frequently for optimization”, explicitly disclosing the contemplating of which states occur most frequently for optimization.).
A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized determining the most frequently used path from the frequency of occurrence of the states forming the path as a known method in the art because Linda explicitly discloses contemplating which states occur most frequently, therefore implementation of the metric value as a most frequently used path would yield the predictable result of identifying the most frequently used path and enabling the system to prioritize and predict the most likely execution path.
Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over Yoo in view of Fleming, further in view of Zhai, further in view of Linda, further in view of Hakewill et al. (US 10642618 B1) hereafter Hakewill, further in view of Hunter.
Regarding claim 11, Yoo in view of Fleming, further in view of Zhai teach the method of claim 1. Yoo teaches:
an input/output request (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”. The query corresponds to the input/output request because a query can be both a request for data results and an action on the data.).
Zhai teaches:
the graph containing vertices and edges (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime”, thereby teaching a graph having one or more vertices, including a first vertex, and “program call stack and related performance data are recorded”, according to program call stack info, thus associating call stack info with corresponding graph vertices. The selection of the first vertex associated with the first call stack which is the last request before the current one would be understood by a person of ordinary skill in the art as corresponding to the first vertex of the program structure graph while traversing through the graph, containing edges that show dependency across the vertices, as evidenced in Paragraph 58; “problematic vertices are detected from the program performance graph, and starting from some or all of the problematic vertices, backtracking is performed through data/control dependence edges within a process and communication dependence edges”.);
an application (Paragraph 64; “several causal paths that connect a set of problematic vertices are obtained. Further analysis of these identified paths will help application developers to locate the root cause.”);
call-stack (Paragraph 44; “program call stack and related performance data are recorded”).
Yoo in view of Fleming, further in view of Zhai, further in view of Linda does not teach detecting an error comprising that said prediction is erroneous when a next request is not similar to the request that is predicted; performing corrections based on said error that is detected.
However, Hakewill teaches:
detecting an error comprising that said prediction is erroneous when a next request is not similar to the request that is predicted (Col. 10, lines 20-28; “As a result, when an instruction cache miss occurs, a halt in execution may result. When such a instruction cache miss occurs, an error in the predicted program path may be detected and corrected, allowing instructions from the old path to be discarded and instruction fetching to be redirected down a new program path. A previously issued cache miss should not block instruction fetch if the new path does not require the contents of the previously issued cache miss.”, explicitly detecting error in a predicted program path.);
performing corrections based on said error that is detected (Col. 10, lines 20-28; “As a result, when an instruction cache miss occurs, a halt in execution may result. When such a instruction cache miss occurs, an error in the predicted program path may be detected and corrected, allowing instructions from the old path to be discarded and instruction fetching to be redirected down a new program path. A previously issued cache miss should not block instruction fetch if the new path does not require the contents of the previously issued cache miss.”, in which the system performs corrections based on the error that is detected.).
Yoo, Fleming, Zhai, Linda, and Hakewill are considered to be analogous to the claimed invention because they are in the same field of data optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, Linda, and Hakewill to have detected a prediction error in the graph and performed corrections thereof, applied on the call stack graph of Yoo, Fleming, Zhai, and Linda. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized error detection and error handling to be known concepts in the art whose implementation in view of the call stack graph of Yoo, Fleming, Zhai, and Linda would yield the predictable result of remedying prediction errors as they occur, thus lowering the possibility of future similar executions causing the same error and improving data access speeds.
Yoo, Fleming, Zhai, Linda, and Hakewill does not teach wherein a correction of the error comprises one or more of adding one or more of: a second vertex in the graph, an edge in the graph from the first vertex to the second vertex; modifying the metric value assigned to one or more of: the edge connecting the first vertex to another vertex associated with the call-stack that is predicted, the edge connecting the first vertex to the second vertex.
However, Hunter teaches:
wherein a correction of the error comprises one or more of:
adding one or more of:
a second vertex in the graph, an edge in the graph from the first vertex to the second vertex (Embodiment C-8; “in response to a determination that the first graph structure is different from the second graph structure with respect to a number of vertices or number of edges, adding a new vertex to the set of vertices based on the request in persistent memory.”, explicitly disclosing revising the graph to add new vertices/edges in response to a difference determination. This fulfills the ”correction of the error comprises one or more of: adding one or more of: a second vertex in the graph, an edge in the graph from the first vertex to the second vertex,” element of the one or more list of elements.).
Yoo, Fleming, Zhai, Linda, Hakewill, and Hunter are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, Linda, Hakewill, and Hunter, to have revised the graph to add vertices and directed edges when errors are detected. A person of ordinary skill in the art would recognize that as program execution traverses the graph, updating the graph to include dependencies that were not previously included would allow the graph to have up to date information, yielding the predictable result of providing faster prefetch information by utilizing the up-to-date graph for future executions.
Claim 12 is rejected under 35 U.S.C. 103 as being unpatentable over Yoo in view of Fleming, further in view of Zhai, further in view of Hunter, further in view of Harris et al. (US 11526502 B1) hereafter Harris.
Regarding claim 12, Yoo in view of Fleming, further in view of Zhai teach the method of claim 1. Yoo teaches:
an input/output request (Paragraph 95; “it is possible to predict and separately cache data that is highly likely to be used in a subsequent graph query request based on an access frequency to each subgraph, instead of merely loading data of each subgraph used in a query history into an existing single-layer cache memory.”. The query corresponds to the input/output request because a query can be both a request for data results and an action on the data.).
Zhai teaches:
the graph containing vertices and edges (Paragraph 44; “collecting performance data of each vertex of the program structure graph during runtime”, thereby teaching a graph having one or more vertices, including a first vertex, and “program call stack and related performance data are recorded”, according to program call stack info, thus associating call stack info with corresponding graph vertices. The selection of the first vertex associated with the first call stack which is the last request before the current one would be understood by a person of ordinary skill in the art as corresponding to the first vertex of the program structure graph while traversing through the graph, containing edges that show dependency across the vertices, as evidenced in Paragraph 58; “problematic vertices are detected from the program performance graph, and starting from some or all of the problematic vertices, backtracking is performed through data/control dependence edges within a process and communication dependence edges”.);
an application (Paragraph 64; “several causal paths that connect a set of problematic vertices are obtained. Further analysis of these identified paths will help application developers to locate the root cause.”);
call-stack (Paragraph 44; “program call stack and related performance data are recorded”).
Yoo in view of Fleming, further in view of Zhai, does not teach the sequence of requests comprising a number N of previous requests when the each vertex has been added to the graph, N being an integer and being comprised between 1 and 100.
However, Hunter teaches:
adding a vertex to the graph (Embodiment C-8; “in response to a determination that the first graph structure is different from the second graph structure with respect to a number of vertices or number of edges, adding a new vertex to the set of vertices based on the request in persistent memory.”, explicitly disclosing revising the graph to add new vertices/edges in response to a difference determination. This fulfills the ”correction of the error comprises one or more of: adding one or more of: a second vertex in the graph, an edge in the graph from the first vertex to the second vertex,” element of the one or more list of elements).
Yoo, Fleming, Zhai, and Hunter are considered to be analogous to the claimed invention because they are in the same field of data access optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, and Hunter, to have revised the graph to add vertices to the graph. A person of ordinary skill in the art would recognize that as program execution traverses the graph, updating the graph to include dependencies that were not previously included would allow the graph to have up to date information, yielding the predictable result of providing faster prefetch information by utilizing the up-to-date graph for future executions.
Yoo in view of Fleming, further in view of Zhai, further in view of Hunter does not teach a number N of previous requests, N being an integer and being comprised between 1 and 100.
However, Harris teaches:
a number N of previous information, N being an integer and being comprised between 1 and 100 (Col. 14, lines 11-22; “The disjoint subset descriptor 561 may indicate sub-range identifiers (e.g., integers in a selected range, such as [1-45] from a range of 1-100, or discrete integers such as [3, 7, 9, 18] from such a range) that can be used to unambiguously identify specific records from the results obtained using the logical filtering criteria 560.”, which identifies specific records in a range, corresponding to identification of previous information based on a range of integers, of which 1-100 is explicitly contemplated.).
Yoo, Fleming, Zhai, Hunter, and Harris are considered to be analogous to the claimed invention because they are in the same field of data optimization. Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Yoo, Fleming, Zhai, Hunter, and Harris to have included a number N of previous information, using the I/O requests of Yoo as the information, when each vertex has been added to the graph as taught by Hunter, bound between integers 1-100. A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized including a number of previous I/O requests when each vertex is added to the graph as a known method in the art because Hunter’s adding vertices to the graph and Yoo’s sequence of I/O requests in combination with an integer describing the range at which previous information should be pulled would yield the predictable result of associating each newly added vertex with a number of preceding I/O requests. Further, a person of ordinary skill in the art would have recognized bounding N between [1, 100] to be a known method in the art because Harris explicitly teaches specifying a range of integers from 1-100 to identify specific records, whose implementation would yield the predictable result of representing a selected number of the previous I/O requests using an integer within the range defined by the user, limited to the options disclosed by the prior art (i.e. 1-45, 1-100, or discrete integers such as [3, 7, 9, 18] (Col. 14, lines 11-22)).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Guven Kaya et al. (US 20210174189 A1) discusses a directed graph which is updated based on operation for multi-dimensional analysis and processing (see Paragraph 43).
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