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 .
Specification
The disclosure is objected to because of the following informalities:
(Text within parentheses is either a missing or a corrected information to character(s) in bold.)
[0006] The first redundant node may be determined based (on) one or more of a truth table or a binary decision diagram of the logic network.
[0041] … For example, the system 100 my (may) start at the root node 110 and add nodes 104 that provide an input to the root node 110.
Appropriate correction is required.
Claim Objections
(Text within parentheses is either a missing or a corrected information to character(s) in bold.)
Claim 3 objected to because of the following informalities:
The method of Claim 1, wherein the first redundant node is determined based (on) one or more of a truth table or a binary decision diagram of the logic network.
Appropriate correction is required.
Claim Rejections - 35 USC § 102
Claims 1-20 are rejected under 35 U.S.C. 102(a)(1) and (a)(2) as being anticipated by Luca Gaetano Amaru (US 10740517 B1).
Regarding claim 1
Luca Gaetano Amaru (US 10740517 B1), hereinafter Amaru, discloses
A method for adjusting a logic network, the method comprising:
(Amaru, col. 1, lines 39-41 “Some embodiments described herein provide techniques and systems for circuit optimization using Boolean resynthesis.”)
(Amaru, col. 1, lines 60-62 “During operation, some embodiments optimize a logic network in an IC design by sorting nodes of the logic network in topological order to obtain a sorted list of nodes.”)
adding, to the logic network, a first redundant node
(Amaru, col. 2, lines 7-11 “In some embodiments, expanding the reconvergent cut to obtain the window of the logic network comprises adding every external node to the reconvergent cut that is not contained in the reconvergent cut, but has fanins inside the reconvergent cut.”)
(Amaru, col. 6, lines 31-33 “Consider now 1-resubstitution, where the library of primitive operations for resub consists only of AND-2 connectives.”)
determining a first adjustment to a first node of the logic network within a transitive fanin of the first redundant node
(Amaru, col. 1, lines 63-67 “Next, for each node in the sorted list of nodes that is a root of a maximum fanout-free cone, the embodiments perform the following steps: (a) determine a reconvergent cut based on the node; (b) expand the reconvergent cut to obtain a window of the logic network”)
(Amaru, col. 2, lines 7-11 “In some embodiments, expanding the reconvergent cut to obtain the window of the logic network comprises adding every external node to the reconvergent cut that is not contained in the reconvergent cut, but has fanins inside the reconvergent cut.”)
and making the first adjustment to the first node based on determining that a first gain based on the first adjustment satisfies a threshold.
(Amaru, col. 1, line 66 – col. 2 line 2 “(c) determine a metric that indicates how beneficial resubstitution is expected to be on the window; (d) compare the metric with a threshold”)
Regarding claim 2
Amaru teaches all aspects of claim 1, and further discloses
The method of Claim 1, further comprising:
adding, to the logic network, a second redundant node
(Amaru, col. 5, lines 13-16 “This approach generalizes to k-resubstitution, which adds exactly k new nodes and reduces the size if the node's Maximum Fanout-Free Cone (MFFC) has at least k+1 nodes.”)
determining a second adjustment to a second node of the logic network within a transitive fanin of the second redundant node
(Amaru, col. 11, line 65 – col. 12, line 2 “If the window is not expected to benefit from resubstitution (“No” branch), then the process can select the next node in the sorted list of nodes that is a root of a maximum fanout free cone (step 662).”)
and removing the second redundant node from the logic network based on determining that the threshold exceeds a second gain based on the second adjustment.
(Amaru, col. 12, lines 13-17 “In step 660, the process can determine a metric that indicates how beneficial resubstitution is expected to be on the window, and then compare the metric with a threshold to determine whether or not resubstitution should be performed.”)
Regarding claim 3
Amaru teaches all aspects of claim 1, and further discloses
The method of Claim 1, wherein the first redundant node is determined based one or more of a truth table or a binary decision diagram of the logic network.
(Amaru, col. 6, lines 26-27 “For such windows, truth tables (up to 15 inputs), or BDDs (up to 20 inputs), for each node are computed quickly.”)
(Amaru, col. 8, lines 19-21 “We refer to this second truth table as FFF(C, n), where C is the logic network, or window, and n is the node considered.)
Regarding claim 4
Amaru teaches all aspects of claim 1, and further discloses
The method of Claim 1, wherein the first adjustment comprises removal of the first node.
(Amaru, col. 11, lines 7-10 “At this point, each node of the window is tried for various resubstitutions, in a waterfall model, i.e., the first resubstitution succeeding is the one kept.”)
(Amaru, col. 11, lines 30-32 “Inside each of the resub type, the filtering rules described above are used to evaluate only candidates leading to valid resubstitutions.”)
Regarding claim 5
Amaru teaches all aspects of claim 1, and further discloses
The method of Claim 1, wherein the first adjustment comprises substituting the first node with another node in the logic network.
(Amaru, col. 11, lines 7-10 “At this point, each node of the window is tried for various resubstitutions, in a waterfall model, i.e., the first resubstitution succeeding is the one kept.”)
(Amaru, col. 10, lines 55-58 “Specifically, the top procedure (line 1 in FIG. 6A) spans through the entire logic network, considering each node in topological order, but resubstitution is only applied to small/medium windows created around a node.”)
Regarding claim 6
Amaru teaches all aspects of claim 1, and further discloses
The method of Claim 1, wherein adding the first redundant node to the logic network maintains functionality of an output of the logic network.
(Amaru, col. 6, lines 24-29 “Resub is usually applied to small/medium windows of logic, say up to 15-20 inputs, rather than to the global logic network. For such windows, truth tables (up to 15 inputs), or BDDs (up to 20 inputs), for each node are computed quickly. These data structures efficiently support functional equivalence checks for individual resub moves.”)
Regarding claim 7
Amaru teaches all aspects of claim 1, and further discloses
The method of Claim 1, further comprising: selecting a second node of the logic network; and forming, from the second node, a window encompassing the second node and a third node of the logic network, wherein the second node and the third node are in the transitive fanin of the first redundant node, and wherein the first redundant node is added based on the window
(Amaru, col. 2, lines 7-11 “In some embodiments, expanding the reconvergent cut to obtain the window of the logic network comprises adding every external node to the reconvergent cut that is not contained in the reconvergent cut, but has fanins inside the reconvergent cut.”)
(Amaru, col. 10, lines 58-63 “The window computation proceeds as follows. First a reconvergent cut is found for the current node (line 5 in FIG. 6A). Then, the cut is expanded w.r.t. its boundaries (line 6 in FIG. 6A), i.e., every external node which is not contained by the cut, but has fanins inside the cut, is added.”)
Regarding claim 8
Amaru teaches all aspects of claim 7, and further discloses
The method of Claim 7, wherein the third node is outside a transitive fanout of the second node.
(Amaru, col. 11, lines 50-56 “The process can begin by sorting nodes of a logic network in topological order to obtain a sorted list of nodes (step 652). Next, the process can select a node in the sorted list of nodes that is a root of a maximum fanout free cone (step 654). The process can then determine a reconvergent cut based on the selected node (step 656).”)
(Amaru, col. 11, line 63 – col. 12, line 2 “The process can then determine whether or not the window is expected to benefit from resubstitution (step 660). If the window is not expected to benefit from resubstitution (“No” branch), then the process can select the next node in the sorted list of nodes that is a root of a maximum fanout free cone (step 662).”)
Regarding claim 9
Amaru teaches all aspects of claim 1, and further discloses
The method of Claim 1, wherein the first redundant node comprises one or more of an AND gate or an OR gate.
(Amaru, col. 11, lines 35-39 “The types of supported resub, in increasing computational complexity order, are: and (and-2 node/gate), xor (xor-2 node/-gate), ao (and-or nodes/gates), xa (xor-and nodes/gates), ax (and-xor nodes/gates), mux (mux node/gate) and mx (mux-xor nodes/gates).”)
(Amaru, col. 6, lines 31-33 “Consider now 1-resubstitution, where the library of primitive operations for resub consists only of AND-2 connectives.”)
Regarding claim 10
Amaru teaches all aspects of claim 1, and further discloses
The method of Claim 1, wherein the first gain comprises one or more of an area of the logic network, a power consumption of the logic network, or a number of gates in the logic network.
(Amaru, col. 5, lines 44-46 “The change is accepted if there is an improvement in the selected cost metric (usually number of gates in the network).”)
(Amaru, col. 12, lines 17-22 “Specifically, the metric can be computed by dividing a volume of the window by an input size of the window. In some embodiments, the volume of the window proportional to the number of nodes in the window, and the input size of the window is equal to the number of inputs of the window.”)
Regarding claim 11
Amaru discloses
A system for adjusting a logic network, the system comprising:
(Amaru, col. 1, lines 39-41 “Some embodiments described herein provide techniques and systems for circuit optimization using Boolean resynthesis.”)
(Amaru, col. 1, lines 60-62 “During operation, some embodiments optimize a logic network in an IC design by sorting nodes of the logic network in topological order to obtain a sorted list of nodes.”)
a memory and a processor communicatively coupled to the memory, the processor configured to
(Amaru, col. 15, lines 2-7 “The term “IC design system” generally refers to a hardware-based system that facilitates the design and manufacture of ICs. FIG. 8 illustrates an IC design system in accordance with some embodiments described herein. IC design system 802 can include processor 804, memory 806, and storage device 808.”)
add, to the logic network, a first redundant node;
(Amaru, col. 2, lines 7-11 “In some embodiments, expanding the reconvergent cut to obtain the window of the logic network comprises adding every external node to the reconvergent cut that is not contained in the reconvergent cut, but has fanins inside the reconvergent cut.”)
(Amaru, col. 6, lines 31-33 “Consider now 1-resubstitution, where the library of primitive operations for resub consists only of AND-2 connectives.”)
determine a first adjustment to a first node of the logic network within a transitive fanin of the first redundant node;
(Amaru, col. 1, lines 63-67 “Next, for each node in the sorted list of nodes that is a root of a maximum fanout-free cone, the embodiments perform the following steps: (a) determine a reconvergent cut based on the node; (b) expand the reconvergent cut to obtain a window of the logic network”)
(Amaru, col. 2, lines 7-11 “In some embodiments, expanding the reconvergent cut to obtain the window of the logic network comprises adding every external node to the reconvergent cut that is not contained in the reconvergent cut, but has fanins inside the reconvergent cut.”)
and make the first adjustment to the first node based on determining that a first gain based on the first adjustment satisfies a threshold.
(Amaru, col. 1, line 66 – col. 2 line 2 “(c) determine a metric that indicates how beneficial resubstitution is expected to be on the window; (d) compare the metric with a threshold”)
Regarding claim 12
Amaru teaches all aspects of claim 11, and further discloses
The system of Claim 11, wherein the processor is further configured to:
add, to the logic network, a second redundant node
(Amaru, col. 5, lines 13-16 “This approach generalizes to k-resubstitution, which adds exactly k new nodes and reduces the size if the node's Maximum Fanout-Free Cone (MFFC) has at least k+1 nodes.”)
determine a second adjustment to a second node of the logic network within a transitive fanin of the second redundant node
(Amaru, col. 11, line 65 – col. 12, line 2 “If the window is not expected to benefit from resubstitution (“No” branch), then the process can select the next node in the sorted list of nodes that is a root of a maximum fanout free cone (step 662).”)
and remove the second redundant node from the logic network based on determining that the threshold exceeds a second gain based on the second adjustment.
(Amaru, col. 12, lines 13-17 “In step 660, the process can determine a metric that indicates how beneficial resubstitution is expected to be on the window, and then compare the metric with a threshold to determine whether or not resubstitution should be performed.”)
Regarding claim 13
Amaru teaches all aspects of claim 11, and further discloses
The system of Claim 11, wherein the first redundant node is determined based on a truth table of the logic network.
(Amaru, col. 6, lines 26-27 “For such windows, truth tables (up to 15 inputs), or BDDs (up to 20 inputs), for each node are computed quickly.”)
(Amaru, col. 8, lines 19-21 “We refer to this second truth table as FFF(C, n), where C is the logic network, or window, and n is the node considered.)
Regarding claim 14
Amaru teaches all aspects of claim 11, and further discloses
The system of Claim 11, wherein the first adjustment comprises removal of the first node.
(Amaru, col. 11, lines 7-10 “At this point, each node of the window is tried for various resubstitutions, in a waterfall model, i.e., the first resubstitution succeeding is the one kept.”)
(Amaru, col. 11, lines 30-32 “Inside each of the resub type, the filtering rules described above are used to evaluate only candidates leading to valid resubstitutions.”)
Regarding claim 15
Amaru teaches all aspects of claim 11, and further discloses
The system of Claim 11, wherein the first adjustment comprises substituting the first node with another node in the logic network.
(Amaru, col. 11, lines 7-10 “At this point, each node of the window is tried for various resubstitutions, in a waterfall model, i.e., the first resubstitution succeeding is the one kept.”)
(Amaru, col. 10, lines 55-58 “Specifically, the top procedure (line 1 in FIG. 6A) spans through the entire logic network, considering each node in topological order, but resubstitution is only applied to small/medium windows created around a node.”)
Regarding claim 16
Amaru teaches all aspects of claim 11, and further discloses
The system of Claim 11, wherein adding the first redundant node to the logic network maintains functionality of an output of the logic network.
(Amaru, col. 6, lines 24-29 “Resub is usually applied to small/medium windows of logic, say up to 15-20 inputs, rather than to the global logic network. For such windows, truth tables (up to 15 inputs), or BDDs (up to 20 inputs), for each node are computed quickly. These data structures efficiently support functional equivalence checks for individual resub moves.”)
Regarding claim 17
Amaru teaches all aspects of claim 11, and further discloses
The system of Claim 11, wherein the processor is further configured to: select a second node of the logic network; and form, from the second node, a window encompassing the second node and a third node of the logic network, wherein the second node and the third node are in the transitive fanin of the first redundant node, and wherein the first redundant node is added based on the window.
(Amaru, col. 2, lines 7-11 “In some embodiments, expanding the reconvergent cut to obtain the window of the logic network comprises adding every external node to the reconvergent cut that is not contained in the reconvergent cut, but has fanins inside the reconvergent cut.”)
(Amaru, col. 10, lines 58-63 “The window computation proceeds as follows. First a reconvergent cut is found for the current node (line 5 in FIG. 6A). Then, the cut is expanded w.r.t. its boundaries (line 6 in FIG. 6A), i.e., every external node which is not contained by the cut, but has fanins inside the cut, is added.”)
Regarding claim 18
Amaru teaches all aspects of claim 11, and further discloses
The system of Claim 11, wherein the first redundant node comprises one or more of an AND gate or an OR gate.
(Amaru, col. 11, lines 35-39 “The types of supported resub, in increasing computational complexity order, are: and (and-2 node/gate), xor (xor-2 node/-gate), ao (and-or nodes/gates), xa (xor-and nodes/gates), ax (and-xor nodes/gates), mux (mux node/gate) and mx (mux-xor nodes/gates).”)
Regarding claim 19
Amaru discloses
A non-transitory computer readable medium storing instructions that, when executed by a processor, cause the processor to
(Amaru, col. 16, lines 8-11 “ A non-transitory computer-readable storage medium storing instructions that, when executed by a computer, cause the computer to perform operations for optimizing a logic network.”)
form, from a first node of a logic network, a window encompassing the first node and a second node of the logic network, wherein the second node is in a transitive fanin of the first node;
(Amaru, col. 2, lines 7-11 “In some embodiments, expanding the reconvergent cut to obtain the window of the logic network comprises adding every external node to the reconvergent cut that is not contained in the reconvergent cut, but has fanins inside the reconvergent cut.”)
(Amaru, col. 10, lines 58-63 “The window computation proceeds as follows. First a reconvergent cut is found for the current node (line 5 in FIG. 6A). Then, the cut is expanded w.r.t. its boundaries (line 6 in FIG. 6A), i.e., every external node which is not contained by the cut, but has fanins inside the cut, is added.”)
add at least one of an AND gate or an OR gate to the logic network such that an output of the first node and an output of the second node are input to the AND gate or OR gate;
(Amaru, col. 11, lines 35-39 “The types of supported resub, in increasing computational complexity order, are: and (and-2 node/gate), xor (xor-2 node/-gate), ao (and-or nodes/gates), xa (xor-and nodes/gates), ax (and-xor nodes/gates), mux (mux node/gate) and mx (mux-xor nodes/gates).”)
(Amaru, col. 6, lines 31-33 “Consider now 1-resubstitution, where the library of primitive operations for resub consists only of AND-2 connectives.”)
(Amaru, col. 6, lines 61-63 “We support resub moves with up to 3 inputs, as they cover the most common gates in today's libraries.”)
based on a truth table of the logic network remaining unchanged after adding the AND gate or OR gate, determine an adjustment to a third node of the logic network within the transitive fanin of the first node;
(Amaru, col. 6, lines 26-33 “For such windows, truth tables (up to 15 inputs), or BDDs (up to 20 inputs), for each node are computed quickly. These data structures efficiently support functional equivalence checks for individual resub moves. For our runtime analysis purposes, equivalence checks are the primitive operations in the resub algorithm. Consider now 1-resubstitution, where the library of primitive operations for resub consists only of AND-2 connectives.”)
(Amaru, col. 10, lines 55-65 “Specifically, the top procedure (line 1 in FIG. 6A) spans through the entire logic network, considering each node in topological order, but resubstitution is only applied to small/medium windows created around a node. The window computation proceeds as follows. First a reconvergent cut is found for the current node (line 5 in FIG. 6A). Then, the cut is expanded w.r.t. its boundaries (line 6 in FIG. 6A), i.e., every external node which is not contained by the cut, but has fanins inside the cut, is added. This process is continued until (i) no more nodes can be added or (ii) a volume limit is hit.”)
and make the adjustment to the third node based on determining that a gain based on the adjustment satisfies a threshold.
(Amaru, col. 12, lines 13-17 “In step 660, the process can determine a metric that indicates how beneficial resubstitution is expected to be on the window, and then compare the metric with a threshold to determine whether or not resubstitution should be performed.”)
Regarding claim 20
Amaru discloses all aspects of claim 19 and further discloses
The medium of Claim 19, wherein the adjustment comprises at least one of (i) removing the third node from the logic network or (ii) substituting the third node with another node in the logic network.
(Amaru, col. 11, lines 4-10 “Only windows passing the filtering tests move to truth table computation. Truth tables, functional support, and related properties, are calculated for every node in the window, using the framework described above. At this point, each node of the window is tried for various resubstitutions, in a waterfall model, i.e., the first resubstitution succeeding is the one kept.”)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RAYAPPU SOUNDRANAYAGAM whose telephone number is (571)272-0629. The examiner can normally be reached Mon-Fri: 8:00AM-5:00PM.
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, Jack Chiang can be reached at (571) 272-7483. 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.
/R.S./Examiner, Art Unit 2851
/JACK CHIANG/Supervisory Patent Examiner, Art Unit 2851