DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA . The amendment filed 01/12/2026 has been received and considered. Claims 2, 8, 9, 15, and 16 are cancelled. Claims 1, 3-7, 10-14, and 17-20 are pending.
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 3, 4, 10, 11, 17, and 18 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 applicant regards as the invention.
Claim 3 recites the limitation "the strongly connected subgraph" in line(s) 6. There is insufficient antecedent basis for this limitation in the claim. There are two different strongly connected subgraphs anteceding this limitation: "for each strongly connected subgraph” (claim 3, line 5) and "a strongly connected subgraph" (claim 3, line(s) 1-2). The recitation of “the strongly connected subgraph” is unclear because it is uncertain which of the two was intended.
As to claims 10 and 17, they are objected for the same deficiency.
Claim 3 recites the limitation "the strongly connected subgraph" in line(s) 8. There is insufficient antecedent basis for this limitation in the claim. There are three different strongly connected subgraphs anteceding this limitation: "for each strongly connected subgraph” (claim 3, line 5), "a strongly connected subgraph" (claim 3, line(s) 1-2), and "a strongly connected subgraph" (claim 3, line 7). The recitation of “the strongly connected subgraph” is unclear because it is uncertain which of the three was intended.
As to claims 10, 11, 17, and 18, they are objected for the same deficiency.
As to claim 4, the limitation “that strongly connected subgraph" in line(s) 5-6 of the claim renders the claim indefinite, because it is unclear what the limitation refers to. There are three different strongly connected subgraphs anteceding this limitation: "for each strongly connected subgraph” (claim 4, line 3), "a strongly connected subgraph" (claim 4, line(s) 1-2), and "a strongly connected subgraph" (claim 4, line 4). The recitation of “that strongly connected subgraph” is unclear because it is uncertain which of the three was intended.
Appropriate correction or clarification is required.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1, 3-7, 10-14, and 17-20 are rejected because the claimed invention is directed to a judicial exception without significantly more.
Independent claim 1, Step 1: a method (process = 2019 PEG Step 1 = yes).
Independent claim 1, Step 2A, Prong One: claim 1 recites:
… selecting a first vertex from the set of vertices with a state of void, wherein the states of the vertices are initially assigned as void…
marking the states of vertices traversed by the depth first search as processed once the depth first search started from the first vertex is completed, wherein the depth first search skips vertices with states previously marked as processed…
filtering out one or more candidate SCCs from the set of candidate SCCs…
wherein filtering out one or more candidate SCCs from the set of candidate SCCs comprises: marking a strongly connected subgraph that is a subset of another strongly connected subgraph as an incomplete SCC; and removing the incomplete SCC from the set of candidate SCCs
The limitations are substantially drawn to mental concepts. The limitations, as drafted and under their broadest reasonable interpretation, cover performance of the limitations in the mind but for the recitation of generic computer components. That is, other than reciting “a processor” nothing precludes the claimed limitations from practically being performed in the mind. As to these limitations, mathematical graph operations are activities that can be performed in the human mind or by a human using a pen and paper (mental processes including an observation, evaluation, judgment, opinion). They entail a user deciding which information (assigning, selecting, marking, and skipping vertices; determining and filtering out strongly connected components – SCCs) to add or subtract out of a mathematical graph. Information and/or data also fall within the realm of abstract ideas because information and data are intangible. See Electric Power Group1 (Electric Power hereinafter): “Information… is an intangible”.
If a claim limitation, under its broadest reasonable interpretation, covers mental processes, then it falls within the "(c) Mental processes" grouping of abstract ideas (2019 PEG Step 2A, Prong One: Abstract Idea Grouping? = Yes, (c) Mental processes—concepts performed in the human mind (including an observation, evaluation, judgment, opinion).
Independent claim 1, Step 2A, Prong two: The claim recites the additional elements processor and storing remaining candidate SCCs as SCCs of the graph.
The claim recites “receiving a circuit design represented as a graph comprising a set of vertices and a set of edges”, these limitations describe the concept of “mere data gathering”, which corresponds to the concepts identified as abstract ideas by the courts. Data gathering, including when limited to particular content does not change its character as information, is also within the realm of abstract ideas. Data gathering has not been held by the courts to be enough to qualify as “significantly more”. See Electric Power.
As to the limitations "for determining strongly connected components (SCCs) of a circuit design in parallel… determining a set of candidate SCCs comprising, by each thread from a plurality of threads executing concurrently on a processor… performing a depth first search starting from the first vertex… determining a candidate SCC within the set of candidate SCCs based on the vertices traversed by the depth first search", these limitations represent no more than just “apply it” limitations, because the limitations invoke computers or other machinery merely as a tool to perform an existing process.
This judicial exception is not integrated into a practical application (2019 PEG Step 2A, Prong Two: Additional elements that integrate the Judicial exception/Abstract idea into a practical application? = NO).
Independent claim 1, Step 2B: As discussed with respect to Step 2A, Prong two, the claim recites the additional elements processor and storing remaining candidate SCCs as SCCs of the graph as performing generic computer functions routinely used in computer applications. Generic computer components recited as performing generic computer functions that are well-understood, routine and conventional activities amount to no more than implementing the abstract idea with a computerized system. The use of a computer to implement the abstract idea of a mathematical or mental algorithm has not been held by the courts to be enough to qualify as “significantly more”. The implementation on a computing system is described in the specification (underline emphasis added):
“[0067] Processing device 802 represents one or more processors such as a microprocessor, a central processing unit, or the like".
As discussed with respect to Step 2A, claim 1 recites data gathering, these limitations are recited at a high level of generality; and therefore, remain insignificant extra-solution activity even upon reconsideration.
As discussed with respect to Step 2A, Prong two, limitations invoking computers or other machinery merely as a tool to perform an existing process are just “apply it” limitations. See MPEP 2106.05(f)(2). In combination, these limitations amount to implementation of mathematical concepts.
As to the limitations "for determining strongly connected components (SCCs) of a circuit design in parallel… determining a set of candidate SCCs comprising, by each thread from a plurality of threads executing concurrently on a processor… determining a candidate SCC within the set of candidate SCCs based on the vertices traversed by the depth first search", see for example in the Specification (underline emphasis added):
"[0019]… The system identifies and filters out the incomplete SCCs from the set of SCCs determined and returns the filtered set of SCCs. Accordingly, the system is able to determine strongly connected components faster than other techniques by using multiple processors. For example, the techniques disclosed were experimentally measured to reduce SCC computation that takes one hour or more on large netlists to a couple of minutes using a 20 cores machine…
[0035] The system adds 330 the vertices to a queue structure. The system starts 340 multiple threads for parallel execution of the steps for determining 350A, 350B, ..., 350N SCC components… Each thread performs the steps for determining 350 candidate SCCs. The process executed by each thread for identifying a candidate SCC is referred to as SCC discovery. The SCC discovery procedure computes non-trivial strongly connected subgraphs (SCS), i.e., SCSs with more than a single node".
As to the limitations "performing a depth first search starting from the first vertex", see for example in the Specification (underline emphasis added):
"[0038]… system performs a DFS from some unindexed vertex and iterates that process until all vertices have received a DFS index. As the system performs the DFS and indexing, the system maintains v.lowlink as the smallest DFS number (including v.dfsNum) observed when performing the DFS from v. The DFS performed from vertex v is included in TFI(v), but may not encounter the full TFI(v) as DFS indexes are assigned only once. Any vertex that has v.dfsNum is equal to v.lowlink defines a SCC. The system performs this computation using multiple threads".
Taken alone the individual additional elements do not amount to significantly more than the above-identified judicial exception (the abstract idea). Looking at the additional elements as an ordered combination adds nothing that is not already present when looking at the additional elements taken individually. There is no indication that their combination improves the functioning of a computer itself or improves any other technology (underline emphasis added). Therefore, the claim does not amount to significantly more than the abstract idea itself (2019 PEG Step 2B: NO).
Claims 7 and 14 recite substantially the same elements as claim 1 and are rejected for the same reasons above.
Independent claims 7 and 14, Step 2A Prong two and 2B: As to the further additional elements computer readable medium and computer processors, they are interpreted as drawn to a generic computer. (See Independent claim 1, Step 2B above). See for example in the Specification (underline emphasis added):
"[0069] The data storage device 818 may include a machine-readable storage medium 824 (also known as a non-transitory computer-readable medium) on which is stored one or more sets of instructions 826 or software".
Dependent claims, Prong One: The claim limitations further the mental concepts of their independent claims. The limitations, as drafted and under their broadest reasonable interpretation, cover performance of the limitations in the mind but for the recitation of generic computer components. That is, other than reciting computer readable medium and computer processors nothing precludes the claimed limitations from practically being performed in the mind. As to these limitations, mathematical graph operations are activities that can be performed in the human mind or by a human using a pen and paper (mental processes including an observation, evaluation, judgment, opinion). They entail a user deciding which information (identifying, marking, and processing vertices; marking, sorting, filtering out, and removing subgraphs or strongly connected components – SCCs) to add or subtract out of a mathematical graph.
If a claim limitation, under its broadest reasonable interpretation, covers mental processes, then it falls within the "(c) Mental processes" grouping of abstract ideas (2019 PEG Step 2A, Prong One: Abstract Idea Grouping? = Yes, (c) Mental processes—concepts performed in the human mind (including an observation, evaluation, judgment, opinion).
Dependent claims, Step 2A, Prong two: As to the limitations "5/12/19… wherein marking the states of vertices as processed is performed using an atomic write operation" and "6/13/20… wherein two or more threads process vertices of the same strongly connected components", these limitations represent no more than just “apply it” limitations, because the limitations invoke computers or other machinery merely as a tool to perform an existing process. This judicial exception is not integrated into a practical application of the exception (2019 PEG Step 2A, Prong Two: Additional elements that integrate the Judicial exception/Abstract idea into a practical application? = NO).
Dependent claims, Step 2B: As discussed with respect to Step 2A, Prong two, the limitations identified as just “apply it” merely invoke computers as a tool to perform an existing process. (See Independent claim 1, Step 2B above). The claims do not amount to significantly more than the abstract idea itself (2019 PEG Step 2B: NO).
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.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied for establishing a background for determining obviousness under 35 U.S.C. 103(a) are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Examiner would like to point out that any reference to specific figures, columns and lines should not be considered limiting in any way, the entire reference is considered to provide disclosure relating to the claimed invention.
Claims 1, 3-7, 10-14, and 17-20 are rejected under 35 U.S.C. 103(a) as being unpatentable over Gavin Lowe, (Lowe hereinafter), "Concurrent depth-first search algorithms based on Tarjan's Algorithm" (see IDS dated 10/06/2023), taken in view of David Ward, (Ward hereinafter), U.S. Patent, 7246331.
As to claim 1, Lowe discloses a method for determining strongly connected components (SCCs)… in parallel (see "concurrent versions of algorithms based on depth-first search, all variants of Tarjan’s Algorithm [24]. We consider algorithms for three closely related problems: 1. To find the strongly connected components (SCCs) of a graph" in page 129, col. 1, last paragraph), the method comprising… determining a set of candidate SCCs (see "Rooted search. A search starts at the root of the graph, and explores out from there. Only the reachable part of the state space is explored. New searches can be started from any new node seen by another search, i.e. from any successor of an expanded node" in page 136, col. 1, 5th paragraph; "candidate" as "SCCs that are reachable from the root node", "The algorithm in rooted mode produces precisely the SCCs that are reachable from the root node" in page 136, col. 2, 6th paragraph) comprising, by each thread from a plurality of threads executing concurrently on a processor (see "concurrent versions of algorithms based on depth-first search" in page 129, col. 1, last paragraph), selecting a first vertex from the set of vertices with a state of void (see "void" as "unseen", "if (node has an unexplored edge to child){ else if (child . status == unseen)" in page 132, Fig. 4, lines 19-20), wherein the states of the vertices are initially assigned as void (see "void" as "unseen", "var status : {unseen… each node has a status, one of: unseen when it has not yet been encountered" in page 130, last paragraph to page 131, 1st paragraph), performing a depth first search (see "Abstract… concurrent algorithms, based on depth-first search" in page 129, lines 1-2) starting from the first vertex, marking the states of vertices traversed by the depth first search as processed (see "Other operations on nodes require atomicity. In particular, a single operation on a node, using a synchronized block, corresponds to most of the operations of lines 20–28 of Fig. 4, obtaining the node’s status, search and index, and also (a) if the node’s status is unseen, its search and status are updated" in page 137, 2nd paragraph) once the depth first search started from the first vertex is completed, wherein the depth first search skips vertices with states previously marked as processed (see "otherwise, child is complete, nothing to do" in page 132, Fig. 4, line 30), and determining a candidate SCC within the set of candidate SCCs based on the vertices traversed by the depth first search (see "if (node.lowlink == node.index){ start new SCC… until (w == node)" in page 132, Fig. 4, lines 36-42)…
Lowe does not disclose, but Ward discloses of a circuit design (see "sorting of the nodes of an individual SCC is based on identifying a starting node, and then enumerating the elementary circuits of the SCC. As enumerate elementary circuits are enumerated from the designated start node, nodes are added to the total order as they appear in some elementary circuit" in col. 8, lines 44-49)… receiving (see “Parse input source and create CFG” in col. 9, line 19) a circuit design represented as a graph comprising a set of vertices and a set of edges (see "Preparation of a CFG… A control flow graph CFG of a program P with statements S is a directed graph G=(V, E), where: V=S U {exit,entry,junction} is a finite set of nodes, where {entry, exit, junction} are distinguished entry, exit, and junction nodes, respectively, and E C VxV is a control flow relation, whose elements are directed edges" in col. 4, lines 8-26)… filtering out one or more candidate SCCs from the set of candidate SCCs, and storing remaining candidate SCCs as SCCs of the graph (see "Generate hints from remaining SCCs using the decision sets of each SCC following the partial ordering on the subprogram SCCs. During the determination of hints, a goal is to retrieve pertinent information (valid paths, over-approximate reachable states, etc.) from the original program text by utilizing the smallest subset of the original program text during the analysis while achieving the same results. Program slicing allows efficient and effective achievement of this goal… The statements selected constitute a subprogram with respect to the variable occurrence. For a statement Si in a PDG, the static program slice with respect to Si is the set of statements S1, S2, S3, . . . in the PDG that can reach Si via a path of flow or control dependence edges. The program slice for a set of statements S is simply the union of each statement Si program slice… Program slicing or parsing is employed during infeasible path analysis and valid computational paths to minimize the size of the original source used to verify these properties" in col. 9, lines 40-63), wherein filtering out one or more candidate SCCs from the set of candidate SCCs comprises: marking a strongly connected subgraph that is a subset of another strongly connected subgraph as an incomplete SCC; and removing the incomplete SCC from the set of candidate SCCs (see "Parse input source and create CFG; Perform control and data dependence analysis on CFG; Generate PDG; Eliminate infeasible data dependency paths from PDG using abstract interpretation (integer interval abstract domain) if model checking of subprogram reachability property timeouts; Extract data dependency SCCs from the PDG… Perform abstract interpretation (integer interval abstract domain) on all subprograms consisting only the variables contained in a SCCs; Eliminate SCCs whose abstract interpretation results are contained in an input data dependent SCC abstract interpretation result, but add its decision predicates to the input data dependent abstract interpretation SCC decision set" in col. 9, lines 19-39).
Lowe and Ward are analogous art because they are related to identifying strongly connected components.
Therefore, it would have been obvious to one of ordinary skill in this art before the effective filing date of the claimed invention to use Ward with Lowe, because Ward shows "that state traversal guided by algorithm generated hints can substantially speed up reachability analysis. Orders-of-magnitude improvement have been obtained is several cases, and visible gains have been achieved in most experiments that have been run. The hints prescribe constraints for the input and state variables of the system. Deriving the hints requires some knowledge of the circuit organization and behavior, at the level a verification engineer needs to devise simulation stimuli or properties to be checked. Simple heuristics often allow one to find hints that are effective for both properties that fail and properties that pass" (see col. 11, lines 39-50).
As to claim 3, Ward discloses wherein marking a strongly connected subgraph as incomplete comprises: sorting the candidate SCCs from the set of candidate SCCs in order of decreasing size as a sorted list; and for each strongly connected subgraph in the order of the sorted list: identifying the vertices of the strongly connected subgraph as discovered (see "The final step of the procedure sorts the list of candidates using the information on data dependencies provided by the PDG. One hint is then produced from each candidate subgraph by extracting its path enabling predicate. The path enabling predicate of a path is the conjunction of the predicates of all choice nodes along the path" in col. 7, line 64 to col. 8, line 2; "The resulting CFG augmented with the data dependence information is referred to as Gdd=(V, E U Edd). Data dependence information is used to identify strongly connected components (SCCs) that may exist for a trace of the execution flow of a program. A Program Dependence Graph (PDG) derived from the program text is a lossless transformation of the original program. It is possible to go back and forth from one to the other. The PDG is used as an intermediate representation. The PDG, which represents significant information regarding the control and data dependencies of a program, can be defined in terms of the CFG; PDG=(V, E U EcdUEdd" in col. 5, lines 16-27); and Lowe discloses responsive to a strongly connected subgraph including a vertex identified as discovered, marking the strongly connected subgraph as incomplete (see "Some nodes have no successors. It is advantageous, when starting a search from such a node, to avoid creating a Search object with its associated stacks, but instead to just mark the node as complete and to create a singleton SCC containing it" in page 137, 4th paragraph).
As to claim 4, Lowe discloses wherein marking a strongly connected subgraph as incomplete comprises: for each strongly connected subgraph in the order of the sorted list: responsive to a strongly connected subgraph not including any vertex identified as discovered, keeping strongly connected subgraph as an SCC of the graph (see "Some nodes have no successors. It is advantageous, when starting a search from such a node, to avoid creating a Search object with its associated stacks, but instead to just mark the node as complete and to create a singleton SCC containing it" in page 137, 4th paragraph).
As to claim 5, Lowe discloses wherein marking the states of vertices as processed is performed using an atomic write operation (see "Other operations on nodes require atomicity. In particular, a single operation on a node, using a synchronized block, corresponds to most of the operations of lines 20–28 of Fig. 4, obtaining the node’s status, search and index, and also (a) if the node’s status is unseen, its search and status are updated" in page 137, 2nd paragraph).
As to claim 6, Lowe discloses wherein two or more threads process vertices of the same strongly connected components (see "the version for finding SCCs. The concurrent algorithm runs several searches concurrently… The algorithm suspends a search that encounters a node currently being explored by another search; when that node is completed, the search is unblocked; the corresponding worker thread can execute a different search in the meantime" in page 132, 3 Concurrent Tarjan’s Algorithm, 1st paragraph).
As to claim 7, Lowe discloses a non-transitory computer readable medium comprising stored instructions, which when executed by one or more computer processors (see "concurrent versions of algorithms based on depth-first search, all variants of Tarjan’s Algorithm [24]. We consider algorithms for three closely related problems: 1. To find the strongly connected components (SCCs) of a graph" in page 129, col. 1, last paragraph), cause the one or more computer processors (see "[o]ur implementation uses a number of worker threads (typically one per processor core), which execute searches" in page 135, next to last ¶ paragraph) to… determine a set of candidate SCCs (see "Rooted search. A search starts at the root of the graph, and explores out from there. Only the reachable part of the state space is explored. New searches can be started from any new node seen by another search, i.e. from any successor of an expanded node" in page 136, col. 1, 5th paragraph; "candidate" as "SCCs that are reachable from the root node", "The algorithm in rooted mode produces precisely the SCCs that are reachable from the root node" in page 136, col. 2, 6th paragraph) comprising, by each thread from a plurality of threads executing concurrently on the one or more computer processors (see "concurrent versions of algorithms based on depth-first search" in page 129, col. 1, last paragraph): select a first vertex from the set of vertices with a state of void (see "void" as "unseen", "if (node has an unexplored edge to child){ else if (child . status == unseen)" in page 132, Fig. 4, lines 19-20), wherein the states of the vertices are initially assigned as void (see "void" as "unseen", "var status : {unseen… each node has a status, one of: unseen when it has not yet been encountered" in page 130, last paragraph to page 131, 1st paragraph); perform a depth first search (see "Abstract… concurrent algorithms, based on depth-first search" in page 129, lines 1-2) starting from the first vertex; mark the states of vertices traversed by the depth first search as processed (see "Other operations on nodes require atomicity. In particular, a single operation on a node, using a synchronized block, corresponds to most of the operations of lines 20–28 of Fig. 4, obtaining the node’s status, search and index, and also (a) if the node’s status is unseen, its search and status are updated" in page 137, 2nd paragraph) once the depth first search started from the first vertex is completed, wherein the depth first search skips vertices with states previously marked as processed (see "otherwise, child is complete, nothing to do" in page 132, Fig. 4, line 30); and determine a candidate SCC within the set of candidate SCCs based on the vertices traversed by the depth first search (see "if (node. lowlink == node.index){ start new SCC… until (w == node)" in page 132, Fig. 4, lines 36-42)…
Lowe does not disclose, but Ward discloses receive (see “Parse input source and create CFG” in col. 9, line 19) a circuit design (see "sorting of the nodes of an individual SCC is based on identifying a starting node, and then enumerating the elementary circuits of the SCC. As enumerate elementary circuits are enumerated from the designated start node, nodes are added to the total order as they appear in some elementary circuit" in col. 8, lines 44-49) represented as a graph comprising a set of vertices and a set of edges (see "Preparation of a CFG… A control flow graph CFG of a program P with statements S is a directed graph G=(V, E), where: V=S U {exit,entry,junction} is a finite set of nodes, where {entry, exit, junction} are distinguished entry, exit, and junction nodes, respectively, and E C VxV is a control flow relation, whose elements are directed edges" in col. 4, lines 8-26)… and filter out one or more candidate SCCs from the set of candidate SCCs and storing remaining candidate SCCs as SCCs of the graph (see "Generate hints from remaining SCCs using the decision sets of each SCC following the partial ordering on the subprogram SCCs. During the determination of hints, a goal is to retrieve pertinent information (valid paths, over-approximate reachable states, etc.) from the original program text by utilizing the smallest subset of the original program text during the analysis while achieving the same results. Program slicing allows efficient and effective achievement of this goal… The statements selected constitute a subprogram with respect to the variable occurrence. For a statement Si in a PDG, the static program slice with respect to Si is the set of statements S1, S2, S3, . . . in the PDG that can reach Si via a path of flow or control dependence edges. The program slice for a set of statements S is simply the union of each statement Si program slice… Program slicing or parsing is employed during infeasible path analysis and valid computational paths to minimize the size of the original source used to verify these properties" in col. 9, lines 40-63), comprising: mark a strongly connected subgraph that is a subset of another strongly connected subgraph as an incomplete SCC; and remove the incomplete SCC from the set of candidate SCCs (see "Parse input source and create CFG; Perform control and data dependence analysis on CFG; Generate PDG; Eliminate infeasible data dependency paths from PDG using abstract interpretation (integer interval abstract domain) if model checking of subprogram reachability property timeouts; Extract data dependency SCCs from the PDG… Perform abstract interpretation (integer interval abstract domain) on all subprograms consisting only the variables contained in a SCCs; Eliminate SCCs whose abstract interpretation results are contained in an input data dependent SCC abstract interpretation result, but add its decision predicates to the input data dependent abstract interpretation SCC decision set" in col. 9, lines 19-39).
As to claim 14, Lowe discloses a system comprising: one or more computer processors (see "[o]ur implementation uses a number of worker threads (typically one per processor core), which execute searches" in page 135, next to last ¶ paragraph); and a non-transitory computer readable medium comprising stored instructions, which when executed by the one or more computer processors (see "concurrent versions of algorithms based on depth-first search, all variants of Tarjan’s Algorithm [24]. We consider algorithms for three closely related problems: 1. To find the strongly connected components (SCCs) of a graph" in page 129, col. 1, last paragraph), cause the one or more computer processors to… determine a set of candidate SCCs (see "Rooted search. A search starts at the root of the graph, and explores out from there. Only the reachable part of the state space is explored. New searches can be started from any new node seen by another search, i.e. from any successor of an expanded node" in page 136, col. 1, 5th paragraph; "candidate" as "SCCs that are reachable from the root node", "The algorithm in rooted mode produces precisely the SCCs that are reachable from the root node" in page 136, col. 2, 6th paragraph) comprising, by each thread from a plurality of threads executing concurrently on the one or more computer processors (see "concurrent versions of algorithms based on depth-first search" in page 129, col. 1, last paragraph): select a first vertex from the set of vertices with a state of void (see "void" as "unseen", "if (node has an unexplored edge to child){ else if (child . status == unseen)" in page 132, Fig. 4, lines 19-20), wherein the states of the vertices are initially assigned as void (see "void" as "unseen", "var status : {unseen… each node has a status, one of: unseen when it has not yet been encountered" in page 130, last paragraph to page 131, 1st paragraph); perform a depth first search (see "Abstract… concurrent algorithms, based on depth-first search" in page 129, lines 1-2) starting from the first vertex; mark the states of vertices traversed by the depth first search as processed starting from the first vertex, marking the states of vertices traversed by the depth first search as processed (see "Other operations on nodes require atomicity. In particular, a single operation on a node, using a synchronized block, corresponds to most of the operations of lines 20–28 of Fig. 4, obtaining the node’s status, search and index, and also (a) if the node’s status is unseen, its search and status are updated" in page 137, 2nd paragraph) once the depth first search started from the first vertex is completed, wherein the depth first search skips vertices with states previously marked as processed (see "otherwise, child is complete, nothing to do" in page 132, Fig. 4, line 30); and determine a candidate SCC within the set of candidate SCCs based on the vertices traversed by the depth first search (see "if (node. lowlink == node.index){ start new SCC… until (w == node)" in page 132, Fig. 4, lines 36-42)…
Lowe does not disclose, but Ward discloses receive (see “Parse input source and create CFG” in col. 9, line 19) a representation of a graph comprising a set of vertices and a set of edges (see "Preparation of a CFG… A control flow graph CFG of a program P with statements S is a directed graph G=(V, E), where: V=S U {exit,entry,junction} is a finite set of nodes, where {entry, exit, junction} are distinguished entry, exit, and junction nodes, respectively, and E C VxV is a control flow relation, whose elements are directed edges" in col. 4, lines 8-26)… and filter out one or more candidate SCCs from the set of candidate SCCs and storing remaining candidate SCCs as SCCs of the graph (see "Generate hints from remaining SCCs using the decision sets of each SCC following the partial ordering on the subprogram SCCs. During the determination of hints, a goal is to retrieve pertinent information (valid paths, over-approximate reachable states, etc.) from the original program text by utilizing the smallest subset of the original program text during the analysis while achieving the same results. Program slicing allows efficient and effective achievement of this goal… The statements selected constitute a subprogram with respect to the variable occurrence. For a statement Si in a PDG, the static program slice with respect to Si is the set of statements S1, S2, S3, . . . in the PDG that can reach Si via a path of flow or control dependence edges. The program slice for a set of statements S is simply the union of each statement Si program slice… Program slicing or parsing is employed during infeasible path analysis and valid computational paths to minimize the size of the original source used to verify these properties" in col. 9, lines 40-63), comprising: mark a strongly connected subgraph that is a subset of another strongly connected subgraph as an incomplete SCC; and remove the incomplete SCC from the set of candidate SCCs (see "Parse input source and create CFG; Perform control and data dependence analysis on CFG; Generate PDG; Eliminate infeasible data dependency paths from PDG using abstract interpretation (integer interval abstract domain) if model checking of subprogram reachability property timeouts; Extract data dependency SCCs from the PDG… Perform abstract interpretation (integer interval abstract domain) on all subprograms consisting only the variables contained in a SCCs; Eliminate SCCs whose abstract interpretation results are contained in an input data dependent SCC abstract interpretation result, but add its decision predicates to the input data dependent abstract interpretation SCC decision set" in col. 9, lines 19-39).
As to claims 10-13 and 17-20, these claims recite a computer readable medium and a system for performing the method of claims 3-6. Lowe discloses "[o]ur implementation uses a number of worker threads (typically one per processor core), which execute searches" (see page 135, next to last ¶ paragraph) for performing a method that teaches claims 3-6. Therefore, claims 10-13 and 17-20 are rejected for the same reasons given above.
Response to Arguments
Regarding the claim objections, the amendment corrected all deficiencies, and the objections are withdrawn.
Regarding the rejections under 112, the amendment corrected some deficiencies, and those objections are withdrawn. The amendment also created new deficiencies.
Regarding the rejections under 101, Applicant's arguments have been considered but they are not persuasive. Claim rejections remain. Applicant argues, (see page 9, 2nd-3rd paragraphs):
‘… claim 1 recites "by each thread from a plurality of threads executing concurrently on a processor: selecting a first vertex . . ., performing a depth first search..., marking the states of vertices . . ., and determining a candidate SCC . . ." Claim 1 expressly recites that multiple threads executing concurrently each perform the four substeps recited in claim 1. Humans cannot practically execute multiple threads concurrently.
More importantly, the executing threads perform depth first searches "wherein the depth first search skips vertices with states previously marked as processed." The actions of one thread (marking the state of a vertex as processed), influence the actions of another thread (to skip the marked vertex). These claim elements are specific to multi-threaded computer implementation. Humans also cannot do this step…’
The MPEP reads (underline emphasis added):
'2106.04(a)(2) Abstract Idea Groupings [R-07.2022]… III. MENTAL PROCESSES… A. A Claim With Limitation(s) That Cannot Practically be Performed in the Human Mind Does Not Recite a Mental Process Claims do not recite a mental process when they do not contain limitations that can practically be performed in the human mind, for instance when the human mind is not equipped to perform the claim limitations…
2106.05(f) [R-10.2019]… (2) Whether the claim invokes computers or other machinery merely as a tool to perform an existing process. Use of a computer or other machinery in its ordinary capacity for economic or other tasks (e.g., to receive, store, or transmit data) or simply adding a general purpose computer or computer components after the fact to an abstract idea (e.g., a fundamental economic practice or mathematical equation) does not provide significantly more'.
Examiner's response: Applicant's argument is not persuasive, because Applicant's analogy fails. A contradictory argument cannot be found persuasive. Applicant's analysis of the MPEP falls short (See MPEP 2106.04(a)(2)IIIA supra). Applicant's argument “Humans cannot practically execute multiple threads concurrently… Humans also cannot do this step” contradicts Examiner's rejection supra (bold emphasis added):
“… these limitations amount to implementation of mathematical concepts.
As to the limitations "for determining strongly connected components (SCCs) of a circuit design in parallel… determining a set of candidate SCCs comprising, by each thread from a plurality of threads executing concurrently on a processor… determining a candidate SCC within the set of candidate SCCs based on the vertices traversed by the depth first search", see for example in the Specification (underline emphasis added):
'[0019]… The system identifies and filters out the incomplete SCCs from the set of SCCs determined and returns the filtered set of SCCs. Accordingly, the system is able to determine strongly connected components faster than other techniques by using multiple processors. For example, the techniques disclosed were experimentally measured to reduce SCC computation that takes one hour or more on large netlists to a couple of minutes using a 20 cores machine…
[0035] The system adds 330 the vertices to a queue structure. The system starts 340 multiple threads for parallel execution of the steps for determining 350A, 350B, ..., 350N SCC components… Each thread performs the steps for determining 350 candidate SCCs. The process executed by each thread for identifying a candidate SCC is referred to as SCC discovery. The SCC discovery procedure computes non-trivial strongly connected subgraphs (SCS), i.e., SCSs with more than a single node".
As to the limitations "performing a depth first search starting from the first vertex", see for example in the Specification (underline emphasis added):
"[0038]… system performs a DFS from some unindexed vertex and iterates that process until all vertices have received a DFS index. As the system performs the DFS and indexing, the system maintains v.lowlink as the smallest DFS number (including v.dfsNum) observed when performing the DFS from v. The DFS performed from vertex v is included in TFI(v), but may not encounter the full TFI(v) as DFS indexes are assigned only once. Any vertex that has v.dfsNum is equal to v.lowlink defines a SCC. The system performs this computation using multiple threads"'.
As to these limitations, use of a computer or other machinery in its ordinary capacity does not integrate the exception into a practical application or provide significantly more. See MPEP 2106.05(f)(2) supra.
Applicant further argues, (see page 9, last paragraph to page 10, 2nd paragraph):
‘… As stated in the Application [0015] (emphasis added):
Typical techniques for identifying SCCs process the input circuit design sequentially by identifying the strongly connected components one at a time. This makes processing of large circuit designs that may include billions of gates very costly. Certain approaches to parallel SCC require instant access to both direction of the edges of a vertex to perform forward and backward traversal. This requires extra memory. One approach for computing SCCs called Trajan's algorithm does not require instant access to both direction of the edges of vertices, but is inherently sequential. In contrast, the disclosed techniques can be executed in parallel on multiple processes.
Thus, claim 1 is an improvement to this field of technology…’
The MPEP reads (underline emphasis added):
'2106.04(d)(1) Evaluating Improvements in the Functioning of a Computer, or an Improvement to Any Other Technology or Technical Field in Step 2A Prong Two [R-10.2019]... the "improvements" analysis in Step 2A determines whether the claim pertains to an improvement to the functioning of a computer or to another technology… invention may integrate the judicial exception into a practical application by demonstrating that it improves the relevant existing technology although it may not be an improvement over well-understood, routine, conventional activity… the word "improvements" in the context of this consideration is limited to improvements to the functioning of a computer or any other technology/technical field, whether in Step 2A Prong Two or in Step 2B...'.
Examiner's response: Applicant's argument is not persuasive, because the claims may provide improved math ('computing SCCs') but do not provide limitations such that an improvement to the functioning of a computer itself or to any other technology is realized. Improved math is a species of the genus math and is not an improvement to the functioning of a computer itself or to any other technology. An improved abstract idea is a species of the genus abstract idea. The claimed invention lacks “improvements to the functioning of a computer or any other technology/technical field". See supra, Specification paragraphs [0019], [0035] and MPEP 2106.04(d)(1): 'the word "improvements"… is limited to improvements to the functioning of a computer or any other technology/technical field'.
Therefore, the rejections are maintained.
Regarding the rejections under 103, Applicant's arguments have been considered. Applicant argues, (see page 10, 3rd paragraph to page 11, 3rd paragraph):
‘… Lowe's list is continuously growing as he adds newly identified SCCs. Lowe does not ever "filter out one or more candidate SCCs from the set of candidate SCCs," as recited in claim 1.
Lowe and claim 1 use opposite approaches. Lowe starts with an empty list of identified SCCs and adds to that list as actual SCCs are identified. In contrast, claim 1 first "determine[es] a set of candidate SCCs" and then "filter[s] out one or more candidate SCCs." The remaining candidate SCCs are then stored as SCCs of the graph…’
Examiner's response: Ward discloses the argued features. See rejection supra.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Examiner would like to point out that any reference to specific figures, columns and lines should not be considered limiting in any way, the entire reference is considered to provide disclosure relating to the claimed invention.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JUAN CARLOS OCHOA whose telephone number is (571)272-2625. The examiner can normally be reached Mondays, Tuesdays, Thursdays, and Fridays 9:30AM - 7:00 PM.
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, Renee Chavez can be reached on 571-270-1104. 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.
/JUAN C OCHOA/Primary Examiner, Art Unit 2186
1 Electric Power Group, LLC v. Alstom S.A., 119 USPQ2d 1739 Fed. Cir. 2016