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 .
In view of the Appeal Brief filed on 06/18/2026, PROSECUTION IS HEREBY REOPENED. A new prior art rejection under 35 U.S.C. 103 set forth below.
To avoid abandonment of the application, appellant must exercise one of the following two options:
(1) file a reply under 37 CFR 1.111 (if this Office action is non-final) or a reply under 37 CFR 1.113 (if this Office action is final); or,
(2) initiate a new appeal by filing a notice of appeal under 37 CFR 41.31 followed by an appeal brief under 37 CFR 41.37. The previously paid notice of appeal fee and appeal brief fee can be applied to the new appeal. If, however, the appeal fees set forth in 37 CFR 41.20 have been increased since they were previously paid, then appellant must pay the difference between the increased fees and the amount previously paid.
A Supervisory Patent Examiner (SPE) has approved of reopening prosecution by signing below:
[4]
Response to Arguments
Applicant’s arguments, see pages 13-50, filed 06/18/2026, with respect to claims 1, 4-7 and 14-22 have been fully considered and are persuasive. The 35 U.S.C. 103 rejection of 1, 4-7 and 14-22 has been withdrawn.
Applicant’s arguments, see 13-50, filed 06/18/2026, with respect to the rejection(s) of claim(s) 8-13 under 35 U.S.C. 103 have been fully considered and are persuasive. Therefore, the rejection has been withdrawn. However, upon further consideration, a new ground(s) of rejection is made in view of Yang et al (US 20220/0019339). Yang teaches the fall through transitions as seen below.
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.
Claim(s) 8-13is/are rejected under 35 U.S.C. 103 as being unpatentable over Billa et a (US 2021/0097082) in view of Yang et al (2020/0019339).
Regarding claim 8, Billa discloses:
A method comprising:loading an object file into a memory associated with a regular expression (regex) accelerator, wherein the object file includes information related to a deterministic finite automaton (DFA) graph and fall- through information indicative of whether a transition associated with any nodes of the DFA graph comprises a fall-through transition; ([0012] In one example, a system comprises a data source storing data, a data processing unit (DPU) comprising an integrated circuit having programmable processor cores and a hardware-based regular expression (RegEx) engine, and a control node configured to generate a data flow graph for configuring the DPUs to execute the analytical operation to be performed on the data. The analytical operation specifies a query having at least one query predicate. A controller is configured to receive the data flow graph and, in response, configures the DPU to input the data as one or more data streams, and configure the RegEx engine to operate according to one or more deterministic finite automata (DFAs) or non-deterministic finite automata (NFA) to evaluate the query predicate against the data by applying one or more regular expressions to the one or more data streams.); the regex accelerator receiving a payload for processing; ([0149] After compilation, the loader stores data representing the DFA graph initially in external memory 210 or a different computer-readable storage medium for loading when needed for stream processing. In some examples, control block 202 may receive work units including instructions to retrieve at least a portion of a DFA graph from external memory 210 allocated and structurally arranged for buffer memory 204 by the loader following compilation of the regular expression. In response, control block 202 may retrieve the designated portion of the DFA graph from external memory 210 and store the portion of the DFA graph to one or more of buffer memory 204, and in some cases may preload certain nodes into high-speed, on-chip DFA caches 208, which may operate as L1 caches. Likewise, after one or more searches have been conducted, control block 202 may receive work units including instructions to clear one or more of DFA caches 208 and/or unload portions of DFAs from buffer memory 204. Furthermore, control block 202 may receive work units including instructions to initiate a search, e.g., indicating a payload to be searched using a loaded DFA graph. In some examples, a single work unit may represent both a command to load a DFA and to perform a search using the loaded DFA.).
Billa does not explicitly teach and during processing of the payload by the reqex accelerator, based on the fall-through information, executing fall-through transitions associated with the DFA graph without consuming a portion of the payload.
Yang teaches and during processing of the payload by the reqex accelerator, based on the fall-through information, executing fall-through transitions associated with the DFA graph without consuming a portion of the payload.,( [0099] Each of DFA engines 206 correspond to respective, private DFA cache memories 208. DFA cache memories 208 may serve two purposes: cache arc data (e.g., recently traversed arcs from a node for which data is stored in external memory 210), and cache root buffer data (e.g., caching pre-loaded root data from external memory 210 for parallel lookups in response to arc cache misses). An entire one of DFA cache memories 208 may be used as an arc cache, where each cache line holds one node arc. DFA engines 206 may load these node arcs and evict these node arcs dynamically in the arc cache when they are accessed and traversed by a respective DFA thread..)
Accordingly, it would have been obvious to one of ordinary skill in the art before the
effective filing date of the claimed invention to have modified the teachings of Billa to include during processing of the payload by the reqex accelerator, based on the fall-through information, executing fall-through transitions associated with the DFA graph without consuming a portion of the payload as taught by Yang. It wouldbe advantageous reduce the memory requirements for storage as taught by the cited sections of Yang.
Regarding claim 9, Billa in view of Yang teaches The method of claim 8, Billa further teaches wherein the information indicative of whether a transition associated with any nodes of the DFA graph comprises a fall-through transition comprises a fall-through bit. ([0243] In other examples, FINAL instructions push a result (Y/N or 1/0) to the result buffer based upon the results of the previously executed array comparison instructions but, upon a failure, do not empty the instruction stack such that NFA engines 216 execute any instructions previously pushed to a given instruction stack. As such, NFA engines 216 generate output data flow 244 to include an affirmative result upon a match and also a negative indication if the predicate is not satisfied by the current data unit of the input data stream. As such, in this example implementation, NFA engines 216 may output data flow 244 as a bitmap, e.g., where a 1 or Y is reported for a match and 0 or N is reported for mismatch, as shown in FIG. 17.).
Regarding claim 10, Billa in view of Yang teaches The method of claim 8, Billa further teaches wherein a DFA graph with fall-through transitions has fewer transitions than a DFA graph without fall-through transitions ([0158] In some examples, before evaluating payload data, DFA engines 206 may preload at least a portion of a DFA graph into buffer memory 204 from external memory 210 or a different computer-readable medium based on the memory allocation specified by the compiler for each node. Additionally, or alternatively, DFA engines 206 may preload a portion of the DFA graph into memory of a thread of the one of DFA engines 206. In particular, DFA engines 206 may be configured to receive a DFA LOAD work unit, including instructions to direct the DFA engine to load at least a portion of a DFA graph (e.g., a root of the DFA graph, and/or other portions of the DFA graph) into buffer memory 204 and/or memory of one of the threads of the DFA engines 206. The at least portion of the DFA graph may include a root node of the DFA graph and/or data representing one or more nodes and/or arcs of the nodes of the DFA graph. Likewise, DFA engines 206 may be configured to unload a loaded portion of a DFA graph from the thread memory and/or from buffer memory 204, e.g., in response to a DFA UNLOAD work unit. The DFA UNLOAD work unit may include instructions indicating that one or more loaded arcs of a DFA graph are to be removed from thread memory and/or buffer memory 204, and/or to unlock and clear a root buffer for a DFA graph from the thread memory and/or buffer memory 204.).
Regarding claim 11, Billa in view of Yang teaches The method of claim 10, Billa further teaches further comprising caching a larger amount of information for the DFA graph with fall-through transitions relative to the DFA graph without fall-through transitions. ([0156] DFA engines 206 also include respective processing units for comparing a current symbol of the payload data to labels for arcs from the current node of the DFA graph. The threads of each of DFA engines 206 may share a common processing unit, or the threads may each include a corresponding processing unit. In general, the processing unit determines a node to which to transition from the current node (i.e., the node to which the arc having a label matching the current symbol of the payload data points). ).
Regarding claim 12, Billa in view of Yang teaches The method of claim 8, Billa further teaches wherein during compiling, fall-through transitions are added to the DFA graph while reducing a total number of transitions associated with the DFA graph ([0158] In some examples, before evaluating payload data, DFA engines 206 may preload at least a portion of a DFA graph into buffer memory 204 from external memory 210 or a different computer-readable medium based on the memory allocation specified by the compiler for each node. Additionally, or alternatively, DFA engines 206 may preload a portion of the DFA graph into memory of a thread of the one of DFA engines 206. In particular, DFA engines 206 may be configured to receive a DFA LOAD work unit, including instructions to direct the DFA engine to load at least a portion of a DFA graph (e.g., a root of the DFA graph, and/or other portions of the DFA graph) into buffer memory 204 and/or memory of one of the threads of the DFA engines 206. The at least portion of the DFA graph may include a root node of the DFA graph and/or data representing one or more nodes and/or arcs of the nodes of the DFA graph. Likewise, DFA engines 206 may be configured to unload a loaded portion of a DFA graph from the thread memory and/or from buffer memory 204, e.g., in response to a DFA UNLOAD work unit. The DFA UNLOAD work unit may include instructions indicating that one or more loaded arcs of a DFA graph are to be removed from thread memory and/or buffer memory 204, and/or to unlock and clear a root buffer for a DFA graph from the thread memory and/or buffer memory 204.).
Regarding claim 13, Billa in view of Yang teaches The method of claim 8, Billa further teaches further comprising, compiling a set of regular expression patterns to generate the output file. ([0243] In other examples, FINAL instructions push a result (Y/N or 1/0) to the result buffer based upon the results of the previously executed array comparison instructions but, upon a failure, do not empty the instruction stack such that NFA engines 216 execute any instructions previously pushed to a given instruction stack. As such, NFA engines 216 generate output data flow 244 to include an affirmative result upon a match and also a negative indication if the predicate is not satisfied by the current data unit of the input data stream. As such, in this example implementation, NFA engines 216 may output data flow 244 as a bitmap, e.g., where a 1 or Y is reported for a match and 0 or N is reported for mismatch, as shown in FIG. 17.).
Allowable Subject Matter
Claims 1, 4-7 and 14-22 are allowed.
The following is a statement of reasons for the indication of allowable subject matter:
Billa generally teaches a data processing unit (DPU) comprising an integrated circuit having programmable processor cores and a hardware-based regular expression (RegEx) engine, and a control node configured to generate a data flow graph for configuring the DPUs to execute the analytical operation to be performed on the data. The analytical operation specifies a query having at least one query predicate. A controller is configured to receive the data flow graph and, in response, configures the DPU to input the data as one or more data streams, and configure the RegEx engine to operate according to one or more deterministic finite automata (DFAs) or non-deterministic finite automata (NFAs) to evaluate the query predicate against the data by applying one or more regular expressions to the one or more data streams.
Yang generally teaches a discreet finite automata (DFA) buffer configured to store at least a portion of a DFA graph, the DFA graph comprising a plurality of nodes, each of the nodes having zero or more arcs each including a respective label and pointing to a respective subsequent node of the plurality of nodes, at least one of the plurality of nodes comprising a match node, wherein the at least portion of the DFA graph comprises one or more slots of a memory slice, the one or more slots comprising data representing one or more of the arcs for at least one node of the plurality of nodes, and a DFA engine implemented in circuitry, the DFA engine comprising one or more DFA threads implemented in circuitry and configured to evaluate a payload relative to the DFA graph.
The cited prior art when considered individually or in combination does not disclose the claimed invention. An updated prior art search was conducted and no prior anticipates or obviously teaches the claimed invention as recited in the dependent claims.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SAMUEL SHARPLESS whose telephone number is (571)272-1521. The examiner can normally be reached M-F 7:30 AM- 3:30 PM (ET).
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, ALEKSANDR KERZHNER can be reached at 571-270-1760. 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.
/S.C.S./Examiner, Art Unit 2165
/ALEKSANDR KERZHNER/Supervisory Patent Examiner, Art Unit 2165
