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 .
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(d):
(d) REFERENCE IN DEPENDENT FORMS.—Subject to subsection (e), a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
The following is a quotation of pre-AIA 35 U.S.C. 112, fourth paragraph:
Subject to the following paragraph [i.e., the fifth paragraph of pre-AIA 35 U.S.C. 112], a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
Claim 20 rejected under 35 U.S.C. 112(d) or pre-AIA 35 U.S.C. 112, 4th paragraph, as being of improper dependent form for failing to further limit the subject matter of the claim upon which it depends, or for failing to include all the limitations of the claim upon which it depends.
For fee calculating purposes, Applicant's claim 20 was initially determined to be a dependent claim because of its reference to claim 19 (MPEP §608.01(n) II.). However, claim 20’s reference to claim 19 simply functions as a cross reference. The reference to claim 19 is not phrased so as the CRM of claim 20 further limits the method of claim 19. Instead, claim 20 is phrased as: claim 20 is drawn to a CRM that incorporates the limitations recited in claim 19.
While a dependent claim is required to make an express reference to a prior claim from which it depends (35 U.S.C. §112 (d)/4th paragraph), it does not follow that reference to another/prior claim indicates the claim is intended to be a dependent claim. Therefore, Applicant is required to cancel the claim, or amend the claim to place the claim in proper dependent form, or rewrite, in unequivocal terms, the claim in independent form.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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 for establishing a background for determining obviousness under 35 U.S.C. 103 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.
Claims 1, 2, 5-9, 11, 13, 19, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over US Patent No. 10,534,885 to Datta et al. in view of US Pub. No. 2012/0084743 to Ispir et al. (“Ispir”).
As to independent claim 1 and similarly recited independent claim 19, an apparatus (Fig. 12) for generating a register transfer level (RTL) representation of a circuit (Mere intended use is not given patentable weight. MPEP § 2111.02.), the apparatus comprising interface circuitry (Fig. 12: 615), machine-readable instructions (Fig. 12: 620) and processing circuitry to execute the machine-readable instructions (Fig. 12: 605) to: generate a graph representation of the circuit, the graph representation comprising a first set of vertices representing operators and a second set of vertices representing operands of the graph representation of the circuit (1:9-17, 3:7-13, 5:37-65, 6:1-3, Fig. 3. Datta generates a DFG representing the circuit in which operation nodes represent operators and separate variable/value input vertices represent the operands supplied to those operators.); identify one or more conditional operators, with each conditional operator defining at least two possible outcomes depending on the condition, and with each possible outcome being represented by a branch of the graph representation of the circuit (4:34-49, 5:47-65, 6:1-3. Datta identifies conditional operators as multiplexer nodes implementing RTL conditional statements, where the true and false outcomes correspond to respective fan-in cones/conditional branches of the DFG.); determine, for the possible outcomes of the one or more conditional operators, a condition imposed by the respective outcome (4:48-65, 5:1-5, 6:47-62. Datta determines a branch specific condition constraint set from the condition controlling the multiplexer, including a false-branch condition of var<25 and true-branch condition of var >= 25.); annotate at least a subset of the vertices of the respective branches representing the possible outcomes with the condition imposed by the corresponding outcome (4:48-65, 5:1-5, 6:47-62, 15:1-13. Datta associates each conditional branch with a condition constraint set derived from that branch’s outcome and propagates the constraint information through nodes of the branch, thereby providing the branch nodes with the claimed outcome dependent condition information.);
The difference between Datta and the claim 1/19 is narrow. Datta teaches the claimed DFG generation, conditional operator identification, branch specific condition determination, and propagation/annotation of those branch conditions, but Datta does not teach generating an RLT representation from the resulting graph representation.
The missing DFG-to-RTL step is taught by Ispir.
Ispir is directed to circuit synthesis using DFG (Abstract). Ispir teaches converting a circuit data flow graph into an RTL specification, including an express transformation algorithm for generating RTL specifications from a given DFG (¶ 0004, 0030, 0031, 0037-0041).
It would have been obvious to a PHOSITA to modify Datta’s EDA process to generate an RTL representation from Datta’s optimized DFG using the DFG-to-RTL transformation taught by Ispir. A PHOSITA would have had reason to apply Ispir’s DFG-to-RTl transformation to Datta’s optimized DFG so that the circuit represented by Datta’s optimized graph could be expressed in RTL form for use in a RTL based circuit design/synthesis flow. The combination merely applies Ispir’s known DFG-to-RTL conversion to Datta’s already generated and optimized DFG and would have predictably yielded the result of an RTL representation embodying Datta’s optimized graph.
As to claim 2, the apparatus according to claim 1, wherein the processing circuitry is to execute the machine-readable instructions to insert, for the identified conditional operators, the branches representing the possible outcomes of the one or more conditional operators (Datta: 3:7-11, 4:34-46, 5:14-20, 37-39, 49-65, 6:1-3. Datta teaches generating a DFG from TRL code in which an identified conditional statement is represented by a multiplexer node and the respective true and false possible outcomes are represented by separate fan-in cones/conditional blocks associated with the respective data inputs of the multiplexer. Accordingly, in generating the DFG, Datta inserts into the graph the respective conditional branches representing the possible outcomes of the identified conditional operator.).
As to claim 5, the apparatus according to claim 1, wherein the processing circuitry is to execute the machine-readable instructions to propagate the conditions imposed by the respective outcomes through the graph (Datta: 4:48-67, 5:1-2, 15:1-13. Datta teaches determining a condition constraint set corresponding to the true or false outcome of a conditional operator and propagating that outcome dependent condition constraint through).
As to claim 6, the apparatus according to claim 1, wherein the processing circuitry is to execute the machine-readable instructions to apply at least one optimization algorithm on the respective branches representing the possible outcomes, with the optimization algorithm being based on the condition imposed by the corresponding outcome (Datta: 4:34-65, 5:1-28, 6:47-65, 7:1-31. Datta teaches representing the true and false outcomes of a conditional statement by respective conditional blocks, deriving and propagating a condition constraint set associated with each outcome, using the resulting range information to optimize the DFG, and in Example 1 applying the condition constraint set for conditional block 237 to establish branch specific values ranges and remove multiplexer, selector, and unselected input circuitry rendered unnecessary by those ranges. ).
As to claim 7, the apparatus according to claim 6, wherein a condition-dependent branch-specific optimization is applied on the respective branches (Datta: 4:34-65, 5:1-28, 6:47-65, 7:1-31. Datta teaches separate conditional blocks corresponding to the true and false branches of a conditional statement, associates an outcome specific condition constraint set with those branches, and applies the constraint for a particular conditional block to determine branch specific ranges that establish certain alternative paths cannot be selected and permit their associated circuity to be removed.).
As to claim 8, the apparatus according to claim 1, wherein the processing circuitry is to execute the machine-readable instructions to detect at least one dead branch within the graph-based representation based on the condition or conditions the vertices of the branch are annotated with (Under BRI, a “dead branch” encompasses a branch/path that cannot be selected or reached under the conditions applicable to that branch. Datta: 4:34-65, 6:47-65, 7:1-31, 8:20-52. Datta teaches associating and propagating outcome specific condition constraints through conditional branches, using those constraints to determine a multiplexer can select only one alternative, and consequently identifying the other alternative as incapable of selection and removing the nodes belonging solely to that unselectable alternative.).
As to claim 9, the apparatus according to claim 1, wherein the respective branches representing the possible outcomes are data paths (Datta: 4:34-49, 5:9-23, 6:47-65, 7:1-25. Datta teaches each true or false possible outcome of a conditional statement is represented by a respective conditional block comprising the fan-in/logic cone of a multiplexer data input, through which data propagates over interconnected DFG nodes toward that data input.).
As to claim 11, the apparatus according to claim 1, wherein the graph representation is a data-flow graph representing the circuit (Datta: 3:8-14, 30-48, Ispir: ¶ 0030, 0031).
As to claim 13, the apparatus according to claim 1, wherein the processing circuitry is to execute the machine-readable instructions to generate the graph representation from a further RTL representation of the circuit (Datta: 3:8-14, 7:49-65, 8:1-23. Datta teaches generating a DFG directly from RTL code describing the circuit, with the DFG nodes corresponding to circuit elements, functions, and statement of the RTL code, and expressly exemplifies generating the Fig. 5 DFG from the RTL code of Example 2.).
As to claim 20, a non-transitory, computer-readable medium comprising a program code that, when the program code is executed on a processor, a computer, or a programmable hardware component, causes the processor, computer, or programmable hardware component to perform the method of claim 19 (Ispir: ¶ 0126-0128).
Claims 3 and 4 are rejected under 35 U.S.C. 103 as being unpatentable over Datta in view Ispir and in further view of US Pub. No. 2023/0004479 to Chimdyalwar et al. (“Chimdyalwar”).
The combination of Datta and Ispir teach determining, for each branch representing a respective conditional outcome, a combined or aggregate condition resulting from the condition constraint applicable to that branch and the propagation of that constraint through the vertices/nodes of the branch (Datta: 4:34-65, 5:1-3, 6:46-65, 7:1-11).
The combination, however, does not expressly teach determining, at the vertex representing the conditional operator where the respective branches converge, a union of the aggregate conditions determined for the respective branches.
Chimdyalwar concerns path sensitive interval analysis and teaches maintaining respective intervals along different paths and combining path information when the path meet at a join point (Abstract, Fig. 2, ¶ 0002). Chimdyalwar explains that multiple paths containing respective variable intervals meet at join point and are selected and merged at that join point (¶ 0043-0045). In particular, Chimdyalwar teaches that each path contains a variable interval having upper and lower bounds and expressly provides that paths may be merged when a union of the variable interval from the two or more paths forms a continual interval (¶ 0045). Chimdyalwar further identifies the operation as union over intervals (¶ 0046). The claimed vertex representing the conditional operator corresponds to the point at which the alternative conditional branches represented by Datta’s respective fan-in cones converge at the multiplexer. Chimdyalwar’s join point similarly constitutes a point at which alternative paths reconverge. Applying Chimdyalwar’s known interval join technique to Datta would result in determining, at the multiplexer/conditional operator vertex, the union of the aggregate range conditions determined for the respective incoming branches.
It would have been obvious to a PHOSITA to modify Datta’s condition sensitive range propagation technique according to Chimdyalwar by taking a union of the branch specific range conditions when the alternative conditional paths reconverge at multiplexor node. The PHOSITA would be motivated to employ Chimdyalwar’s union operation in Datta so that downstream analysis after the conditional accurately and conservatively represents the range of values that may arrive through either conditional branch, thereby permitting continued range propagation and optimization beyond the reconvergence point. This would have amounted to the predictable use of a known interval analysis join operation for its known purpose.
As to claim to claim 4, the apparatus according to claim 3, wherein the condition imposed by the respective conditional operator is related to interval arithmetic, wherein the processing circuitry is to execute the machine-readable instructions to evaluate, for the branches representing the possible outcomes, one or more constrained value intervals for one or more of the operands based on one or more conditions the vertices of the respective branches are annotated with, and to determine, for at least the vertices representing conditional operators, a union of the constrained value intervals evaluated for the branches representing the possible outcomes connected to the vertex representing the respective conditional operator (Datta: 4:20-65, 6:46-65, 7:1-11. Chimdyalwar: ¶ 0044-0046, 0048-0052. Datta teaches interval based conditional analysis by representing variable ranges with min and max values, deriving branch specific constrained intervals from conditional outcome, and propagating those constrained intervals through arithmetic operators, i.e., restricting the true branch of multiplier 236 to var=25-40 and propagating that interval through modification, addition, subtraction, and division to obtain successive constrained ranges. Chimdyalwar teaches respective conditional paths carry variable intervals having lower and upper bounds and that, when those paths meet at a join point, the interval information is combined using a union over the intervals. Accordingly, Datta in view of Chimdyalwar teaches evaluating constrained value intervals for operands based on the respective branch conditions and determing, at the conditional operator/join vertex, a union of the constrained value intervals from the respective possible outcome branches.).
Claims 10 are rejected under 35 U.S.C. 103 as being unpatentable over Datta in view of Ispir and in further view of US Pub. No. 2004/0226006 to Russell (“Russell”).
Datta in view of Ispir teaches representing the true and false outcome of a conditional statement as respective conditional blocks, deriving a condition constraint set corresponding to each outcome, identifying the nodes belonging to the respective conditional block, and propagating the applicable condition constraint set through those nodes. Therefore, Data teaches annotating, in substance, vertices of the respective possible outcome branches with the condition imposed by the corresponding outcome (Datta: 4:34-67, 6:1-3).
The combination, however, does not teach performing that annotation by inserting separate condition representing vertices into the graph and inserting edges between those condition vertices and the branch vertices being annotated.
Russell teaches generating graph representations from hardware specifications, including VHDL and Verilog, representing Boolean condition as a distinct control/predicate node, representing a conditionally executed branch operation as a separate graph node, and constructing a dependence graph by adding a control dependence edge between the predicate node and the branch operation node, with the edge identifying the corresponding outcome of the predicate (¶ 0041-0043, 0051-0054, 0066-0069). Thus, Russell teaches representing a condition by a graph vertex and associating that condition with a vertex governed by the condition through an inserted graph edge, as required by the structural annotation portion of claim 10.
It would have been obvious to a PHOSITA to modify the graph representation of Datta according to Russell by representing Datta’ branch specific conditions as respective condition/predicate vertices and inserting control dependence edges connecting those condition vertices to the branch vertices governed by the corresponding conditions. The PHOSITA would have been motivated to make such modification to facilitate graph-based dependency analysis, traversal, transformation, and optimization.
Claim 12 is rejected under 35 U.S.C. 103 as being unpatentable over Datta in view of Ispir and in further view of Impress: Large Integer Multiplication Expression Rewriting for FPGA HLS to Ustun et al. (“Ustun”).
The combination of Datta and Ispir does not teach graph representation is based on an equivalence graph.
Ustun teaches constructing an e-graph for hardware optimization, wherein the e-graph comprises e-classes containing equivalent expressions and compactly represents a large set of functionally equivalent hardware implementations (Abstract, page 1: column 2, ¶ 3.). Ustun then extracts an optimized hardware expression from the e-graph for high-level synthesis and FPGA implementation (page 1, column 2, ¶ 3-4). Accordingly, Ustun teaches a graph representation based on an equivalence graph as recited in claim 12.
It would have been obvious to a PHOSITA to employ Ustun’s e-graph representation in the Datta/Ispir optimization framework to retain and evaluate multiple equivalent circuit implementations before selecting an optimized implementation.
Allowable Subject Matter
Claims 14-18 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Claims 14-18 are allowed because the prior art of record does not teach or suggest an apparatus having all the combinations of elements as recited in and required by claim 14. Claims 15-18 depend from claim 14.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Examiner SURESH MEMULA whose telephone number is (571)272-8046, and any inquiry for a formal Applicant initiated interview must be requested via a PTOL-413A form and faxed to the Examiner's personal fax phone number: (571) 273-8046. Furthermore, Applicant is invited to contact the Examiner via email (suresh.memula@uspto.gov) on the condition the communication is pursuant to and in accordance with MPEP §502.03 and §713.01. The Examiner can normally be reached Monday-Thursday: 9am-6pm. If attempts to reach the Examiner by telephone are unsuccessful, the Examiner’s supervisor, Jack Chiang, can be reached on 571-272-7483. The fax phone number for the organization where this application or proceeding is assigned (i.e., central fax phone number) is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/SURESH MEMULA/Primary Examiner, Art Unit 2851
Prosecution Insights