Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
In 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.
Specification
The disclosure is objected to because of the following informalities:
Paragraph [0048] incorrectly states the properties of pulldown and pullup networks. The paragraph should be fixed to avoid confusion:
One stage transistor-level networks are composed of two main blocks called pulldown and pull up networks. Pullup networks, connected between VDD and the output, [[is]] are composed of PMOS transistors, and [[is]] are responsible for bringing an high ('1') state to the output. Conversely, pulldown networks, connected between the output and [[VDD]] VSS/GND, [[is]] are composed of NMOS transistors, and [[is]] are responsible for bringing a low ('0') state to the output.
Appropriate correction is required.
Claim Interpretation
The term “factored form literals” is used in claim 1 line 7, and claim 1 lines 8-9. The term is also included in corresponding independent claim 14. The term is therefore at least incorporated by reference in all of the claims. The specification gives the following definitions:
...literals (variables complemented or not complemented). Thus, factored forms can be directly represented by an AIG by translating ANDs to ANDs, and ORs to ANDs using De Morgan's law.
(Specification [0039] lines 3-5).
In claim 1 line 7, the limitation “to globally optimize for factored form literals” is not specifically defined in the specification. However, the claim language must be given the broadest reasonable interpretation in light of the specification, which gives the following guidance:
Factored form is a powerful multi-level representation of a Boolean function that readily translates into an implementation of the function in CMOS technology. In particular, the number of literals of a factored form correlates well with the number of transistors in the CMOS implementation. Aspects of the technology involve developing novel methods for minimizing the total number of factored form literals needed to represent combinational logic given as an and inverter graph (AIG). The methods lead to reduced literal counts, compared to the traditional methods focusing on minimizing the number of AIG nodes.
(Specification [0035] lines 1-7).
After reviewing the art, the following excerpt from “MIS: A Multiple-Level Logic Optimization System” (1987-Brayton) seems relevant:
To justify the use of the total number of literals in the factored form as an area complexity measure, consider the implementation of f1 as a CMOS complex gate. It can be implemented as shown in Fig. 3 using nine pairs of n-type and p-type MOS transistors (assuming all signals and their complements are available). Thus, the number of literals in the factored form corresponds to the number of transistors needed to implement the function as a complex gate.
(1987-Brayton [page 1067 col 2 paragraph 7]).
In claim 3, the terms “algebraic or Boolean factoring” are used. No definition is provided in the specification. After reviewing the art, the following excerpt from “MIS: A Multiple-Level Logic Optimization System” (1987-Brayton) seems relevant:
When f and g have disjoint support, fg is an algebraic product (no Boolean operations are needed to obtain the product); otherwise jg is a Boolean product. For example, ( a + b )( c + d ) = ac + ad + be + bd is an algebraic product, and both (a + b)(a + c) = aa + ab + ac + bc = a + bc and ( a + b) ( !b + c) = a!b + ac + b!b + bc = a!b + bc are Boolean products.
(1987-Brayton [page 1067 col 1 paragraph 8]).
As a last note regarding claim interpretation, Applicant incorporates by reference the entirety of the provisional application U.S. 63/426,935 (see Specification [0001]). The provisional application includes an Appendix 1 with a paper titled “Improving Standard-Cell Design Flow Using Factored Form Optimization”. The following paragraph from that paper is relevant:
We implemented a global re-mapping method for AIGs targeting the minimization of FF literals. The method is similar to cost-based mappers applied to graphs [8]. It consists of cost driven mapping, followed by Boolean decomposition of each cut in the cover into an AIG, which can be seen as re-mapping. The algorithm works by computing cuts for each node using the fast cut enumeration procedure [16] and assigning to each cut a cost based on the FF representation. The FF is computed using the irredundant SOP (ISOP) extracted from the Boolean function of the cut. The SOP is then factored using algebraic or Boolean factoring [17]. Next, the technology mapper selects a cover to minimize the number of FF literals in the Boolean functions of the cuts used to cover the AIG.
(see “Improving Standard-Cell Design Flow Using Factored Form Optimization”, [page 5 col 2 paragraph 3 lines 8-13]).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-6 and 14-17 is/are rejected under 35 U.S.C. 103 as being unpatentable over “Efficient Transistor-Level Design of CMOS Gates” (2013-Possani) in view of “Automatic Generation and Evaluation of Transistor Networks in Different Logic Styles” (2008-daRosa)
With respect to claim 1, Possani teaches A computer-implemented method to perform transistor-level synthesis for an integrated circuit element, the method comprising (“the method is divided in four well defined steps. The first three steps aim to build the kernels. The fourth one tries to
merge the kernels found in order to deliver an optimized switch network”, [page 192 col 2 paragraph 2 lines 4-7]; and computer-implemented: “Intel Core i5 at 2.8GHz with 4Gb of RAM”, [page 196 col 1 paragraph 1 lines 2-3]) generating, by one or more processors of a computer system (Intel Core i5, [page 192 paragraph 1 lines 2-3]), single-stage transistor networks from Boolean functions (The proposed method starts from an ISOP, and tries to combine the cubes of a function to build NSP and SP kernels, [page 192 col 2 paragraph 2 lines 1-2]; definition of ISOP is irredundant sum of products, which refers to a Boolean expression, [page 192 col 2 paragraph 1]; and applied to 53 functions, [page 195 col 1 paragraph 1 line 6]; in this stage, the kernels are mapped to switch networks as shown in FIGS. 4 and FIG. 6, which teaches generating single stage transistor networks, [page 193]: “The NSP kernels are mapped to switch networks applying a reordering in the label of the edges”, [page 193 col 1 paragraph 1]; “Similarly to the step (A), the algorithm of the step (B) must apply some transformations over the graph to map each found SP kernel to a switch network”, [page 193 col 1 paragraph 4 lines 1-3]), wherein each single-stage transistor network is composed of a pulldown network and a pullup network (the algorithm is applied to CMOS gates, (see [Title] and [Abstract]; It is important to notice that CMOS gates are made of two logically complementary networks, one PMOS network for pull up and one NMOS network for pull-down, as illustrated in Fig. 1; The remainder of this paper aims the generation of individual networks that can be used for either pull-up or pull down planes, [page 191 col 1 paragraph 2]-[page 191 col 2 paragraph 1]); scaling, by the one or more processors (Intel Core i5, [page 192 paragraph 1 lines 2-3]), the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals (The fourth one tries to merge the kernels found in order to deliver an optimized switch network, [page 192 col 2 paragraph 2 lines 5-7]; the intent of which is provide a literal count better than factorization, see [page 191 col 2 paragraph 2]; and “when considering only the literal count metric”, [page 191 col 2 paragraph 4 lines 4-5]) and performing, by the one or more processors (Intel Core i5, [page 192 paragraph 1 lines 2-3]), ... based on the factored form literals to generate a circuit design (It is worth to notice that existing techniques apply usually greedy
strategies and deliver satisfactory results. However, to the best of our knowledge, no one of these methods can achieve the best results even for a set of simple functions when considering only
the literal count metric [13], [page 191 col 2 paragraph 4 lines 1-5]; where “techniques” refer to factorization and graph based methods, [page 191 col 2 paragraphs 2-3]; and the purpose of reducing literal count is: “The transistor arrangement optimization is an effective possibility to improve VLSI design, especially when generating CMOS logic gates to be inserted in standard cell libraries”, [Abstract] lines 1-3; where the standard cell library is part of a larger process referred to as technology mapping; see also: “Transistor netlists are of special interest when designing standard cell libraries [4] or custom gates for IC design improvement”, [page 191 col 1 paragraph 1 lines 4-6]).
Possani does not specifically teach how technology mapping leads to VLSI/circuit design, but makes reference to “designing standard cell libraries”, which a person having skill in the art would recognize as part of the technology mapping process, but daRosa makes this explicit.
DaRosa teaches and performing, by the one or more processors, technology mapping based on the factored form literals to generate a circuit design (The proposal of standard-cell design is to reduce the implementation effort by reusing a library of cells,. The advantage of this approach is that the cells only need to be designed and verified once for a given technology, and they can be reused many times, thus amortizing the design cost, [page 16 paragraph 3]-[page 17 paragraph 1 line 2]; then “Technology mapping is the procedure of expressing a given Boolean network in terms of logic cells or gates. Typically, the objective function aims the optimal use of all gates in the library to implement a circuit with critical-path delay less than a target value and minimum area”, [page 17 paragraph 3 lines 1-4]; where the algorithms are performed on a CPU, [page 20 paragraph 2 line 7]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani with daRosa because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. In the first paragraph, Possani provides a specific teaching, suggestion, motivation for the purpose of the method, [page 191 col 1 paragraph 1 lines 1-6]. DaRosa goes into further detail explaining the bigger picture. The standard cell library is part of Technology mapping. Technology mapping is part of a larger process known as logic synthesis, which in turn is part of the process of circuit design:
PNG
media_image1.png
426
570
media_image1.png
Greyscale
(daRosa [page 18]).
A person having skill in the art would have a reasonable expectation of building an optimized Cell Library using the method and system of Possani, which in turn can be used in the larger process that includes technology mapping as described by daRosa. Therefore, it would have been obvious to combine Possani with daRosa to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 2, Possani in view of daRosa teaches all of the limitations of claim 1, as noted above. Possani further teaches wherein generating the single-stage transistor networks includes: representing a function to be performed by the integrated circuit element as a sum-of-products (SOP) (The proposed method starts from an ISOP, and tries to combine the cubes of a function to build NSP and SP kernels, [page 192 col 2 paragraph 1 lines 1-2]); and finding a factorization that minimizes a number of the factored form literals (see [page 191 col 2 paragraph 2]; factorization could be applied to the (B) SP kernel finder step, [page 192 col 2 paragraph 2 bullet (B)]; note, section 3.2 and FIG. 6 shows a graph based method to find the kernel, [page 193]; Possani teaches that graph-based or factorization can be used, but chooses to use graph because graph methods can also find NSP arrangements, see [page 191 col 2 paragraph 3 lines 5-8]; for SP kernel finding, graph-based and factorization can be substituted for one another).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani with Possani because this simple substitution of one known element for another to obtain predictable results. The graph based method of Possani is the base reference that teaches all limitations except for using factoring to get the SP kernels. As described by Possani, the substituted component of factoring for finding SP kernels is well-known in the art and the purpose of using factoring methods to optimize transistor networks is well known in the art, (Possani [page 191 col 2 paragraph 2]). One of ordinary skill in the art could have substituted the factoring method for the method at least in SP kernel finding, and the results of the substitution would have been predictable. Therefore, it would have been obvious to combine the main method of Possani that uses graph based method to find the SP kernel with the factoring disclosed in Possani to find the SP kernel to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 3, Possani in view of Marques teaches all of the limitations of claim 2, as noted above. Possani further teaches wherein finding the factorization includes performing one of algebraic or Boolean factoring (The most traditional solutions are based on algebraic and Boolean factorization, [page 191 col 2 paragraph 2 lines 2-3]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani with Possani because this simple substitution of one known element for another to obtain predictable results. The graph based method of Possani is the base reference that teaches all limitations except for using factoring to get the SP kernels. As described by Possani, the substituted component of factoring for finding SP kernels is well-known in the art and the purpose of using factoring methods to optimize transistor networks is well known in the art, (Possani [page 191 col 2 paragraph 2]). One of ordinary skill in the art could have substituted the factoring method for the method at least in SP kernel finding, and the results of the substitution would have been predictable. Therefore, it would have been obvious to combine the main method of Possani that uses graph based method to find the SP kernel with the factoring disclosed in Possani to find the SP kernel to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 4, Possani in view of daRosa teaches all of the limitations of claim 3, as noted above. Possani does not teach wherein the Boolean factoring generates a solution represented as an AND-OR graph, in which factored forms are generated for both the function to be performed and a complement of the function to be performed.
However, daRosa teaches wherein the Boolean factoring generates a solution represented as an AND-OR graph, in which factored forms are generated for both the function to be performed and a complement of the function to be performed (see specifically FIG. 2.19, [page 44], but more generally, [page 43 paragraph 2]-[page 45 paragraph 2]; FIG. 2.19 gives the factorized form of an equation using and-or graphs; with reference to eq’s. (2.13) and (2.14), the onset equation (2.13) represents the pullup network, and the offset equation represents the pulldown network, [page 44], The equation (2.14) can be factorized into equation (2.15). Equation (2.15) can be used to implement a topologically complementary switch network that respects the minimum number of elements in series, [page 45 paragraph 1]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani with daRosa because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani teaches both factorization and graph-based methods, [page 191 col 2 paragraphs 2-3], but focuses mostly on graph-based methods because they find NSP arranges that factorization methods cannot, [page 191 col 2 paragraph 3 lines 5-8]. DaRosa, who is also an author on the Possani paper, provides further details on factorization procedures, and how and why most programs start from SOP form (sum-of-products), which is a two-level AND-OR graph, but then factorize the Boolean function, which results in a multi-level AND-OR graph;
PNG
media_image2.png
318
502
media_image2.png
Greyscale
According to Mintz (2005), factorization is the procedure of deriving a factorized form from a SOP form of a function. For example, if f = a *e+a *d+b *c then one possible factorization off is a*(e+d)+b*c. In most logic synthesis systems Boolean functions are internally stored in the SOP form (SENTOVICH, 1992; KARMA, 2008). However, the number of elements in a switch network is more accurately represented by the number of literals in the factorized form of the network. This means that an efficient factorization method is required in order to minimize a switch network.
(daRosa [page 44 paragraph 1 lines 1-7]).
A person having skill in the art would have a reasonable expectation of optimizing as switch network using the method and system of Possani, using the factorization method of daRosa, at least for the SP kernel finding step. Therefore, it would have been obvious to combine Possani with daRosa to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 5, Possani in view of daRosa teaches all of the limitations of claim 3, as noted above. Possani does not teach wherein finding the factorization includes creating an AND-OR graph for each transistor topology corresponding to the factored form literals.
However, daRosa teaches wherein finding the factorization includes creating an AND-OR graph for each transistor topology corresponding to the factored form literals (see specifically FIG. 2.19, [page 44], but more generally, [page 43 paragraph 2]-[page 45 paragraph 2]; FIG. 2.19 gives the factorized form of an equation using and-or graphs; with reference to eq’s. (2.13) and (2.14), the onset equation (2.13) represents the pullup network, and the offset equation represents the pulldown network, [page 44], The equation (2.14) can be factorized into equation (2.15). Equation (2.15) can be used to implement a topologically complementary switch network that respects the minimum number of elements in series, [page 45 paragraph 1]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani with daRosa because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani teaches both factorization and graph-based methods, [page 191 col 2 paragraphs 2-3], but focuses mostly on graph-based methods because they find NSP arranges that factorization methods cannot, [page 191 col 2 paragraph 3 lines 5-8]. DaRosa, who is also an author on the Possani paper, provides further details on factorization procedures, and how and why most programs start from SOP form (sum-of-products), which is a two-level AND-OR graph, but then factorize the Boolean function, which results in a multi-level AND-OR graph;
PNG
media_image2.png
318
502
media_image2.png
Greyscale
According to Mintz (2005), factorization is the procedure of deriving a factorized form from a SOP form of a function. For example, if f = a *e+a *d+b *c then one possible factorization off is a*(e+d)+b*c. In most logic synthesis systems Boolean functions are internally stored in the SOP form (SENTOVICH, 1992; KARMA, 2008). However, the number of elements in a switch network is more accurately represented by the number of literals in the factorized form of the network. This means that an efficient factorization method is required in order to minimize a switch network.
(daRosa [page 44 paragraph 1 lines 1-7]).
A person having skill in the art would have a reasonable expectation of optimizing as switch network using the method and system of Possani, using the factorization method of daRosa, at least for the SP kernel finding step. Therefore, it would have been obvious to combine Possani with daRosa to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 6, Possani in view of daRosa teaches all of the limitations of claim 3, as noted above. Possani teaches wherein generating the single-stage transistor networks comprises generating an irredundant sum-of-products (ISOP) ... (The proposed method starts from an ISOP, and tries to combine the cubes of a function to build NSP and SP kernels, [page 192 col 2 paragraph 2 lines 1-2]; definition of ISOP is irredundant sum of products, which refers to a Boolean expression, [page 192 col 2 paragraph 1]).
Possani does not specifically teach that the ISOP is ...from a truth table.
However, daRosa teaches ...from a truth table (both network generation and network optimization start from on-set and off-set equations, see for example eq’s. (2.9) and (2.10), [page 38], eq’s. (2.11) and (2.12), [page 43], and eq’s. (2.13) and (2.14), [page 44]; the equations are ISOP based on the definition, “A prime irredundant SOP with minimum cube literal cost for function f is a prime irredundant SOP where the maximum number of literals in a single cube is minimum for function”, [page 28 paragraph 2 lines 2-4]; previous sections describe how to generate on-set and off-set equations and why they are generated from truth tables: “For a given Boolean function, the set of input vectors that produces an output value is called on-set. '1' In the same way, the set of input vectors that produces an output value '0' is called off-set”, [page 24 paragraph 2]; and “Basically, logic network can be constructed with their logic planes in a shared structure or not”, [page 37 paragraph 2 lines 1-2], but for a full understand read all of [page 37 paragraph 2]-[page 39 paragraph 1], which gives a detailed explanation of how to generate pullup and pulldown networks from on-set and off-set equations.
It would have been obvious to one skilled in the art before the effective filing date to combine Possani with daRosa because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani teaches both factorization and graph-based methods, [page 191 col 2 paragraphs 2-3], but focuses mostly on graph-based methods because they find NSP arranges that factorization methods cannot, [page 191 col 2 paragraph 3 lines 5-8]. DaRosa, who is also an author on the Possani paper, provides further details on everything from factorization procedures to basics like how to generate on-set and off-set equations from truth tables in order to apply factorization procedures. A person having skill in the art would have a reasonable expectation of optimizing as switch network using the method and system of Possani, using the factorization method of daRosa, at least for the SP kernel finding step. Therefore, it would have been obvious to combine Possani with daRosa to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 14, Possani teaches A computing system, comprising: memory configured to store integrated circuit information; and one or more processors operatively coupled to the memory, the one or more processors being configured to (computer running method described in Abstract running in an Intel Core i5 at 2.8GHz with 4Gb of RAM, [page 196 col 1 paragraph 1 lines 1-4]):
Regarding the rest of claim 14, incorporating the rejection of claim 1, claim 14 is rejected for a substantially similar rationale.
With respect to claim 15, Possani in view of daRosa teaches all of the limitations of claim 14, as noted above. Possani further teaches wherein the one or more processors are further configured ... in the memory (computer running method described in Abstract running in an Intel Core i5 at 2.8GHz with 4Gb of RAM, [page 196 col 1 paragraph 1 lines 1-4]).
Possani does not teach ... to store the circuit design...
However, daRosa teaches wherein the one or more processors are further configured to store the circuit design in the memory (see circuit design methodology in Fig. 1.2, [page 18], where the caption “Digital circuit design methodology using predefined cell library” uses the word “digital” to indicate method is implemented on a computer; author describes three tools, where tools in this context refers to software running on a computer, “In this context, an academic environment composed of 3 parts was idealized by our group. The first one is a logic synthesis tool, which only performs logic manipulations over Boolean functions. This tool is called KARMA 3. The second one is an electrical synthesis tool, developed to provide transistor networks generation, manipulation and evaluation at cell level. This tool is named ELECTRO. The last one is a physical synthesis tool, proposed to implement, optimize and evaluate the layout of logic cells, [page 131 paragraph 2 lines 1-7]; because the tools are implemented in software, the circuit design including the “Spice netlist description”, [page 140 paragraph 3 line 3], would be stored in memory while being generated into an image such as figure E11, [page 141]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani with daRosa because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. In the first paragraph, Possani provides a specific teaching, suggestion, motivation for the purpose of the method, [page 191 col 1 paragraph 1 lines 1-6]. DaRosa goes into further detail explaining the bigger picture. The standard cell library is part of Technology mapping. Technology mapping is part of a larger process known as logic synthesis, which in turn is part of the process of circuit design:
PNG
media_image1.png
426
570
media_image1.png
Greyscale
(daRosa [page 18]).
A person having skill in the art would have a reasonable expectation of building an optimized Cell Library using the method and system of Possani, which in turn can be used in the larger process that includes technology mapping as described by daRosa. Therefore, it would have been obvious to combine Possani with daRosa to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 16, incorporating the rejections of claim 2 and claim 14, claim 16 is rejected for substantially similar rationale.
With respect to claim 17, incorporating the rejections of claim 6 and claim 14, claim 17 is rejected for substantially similar rationale.
Claim(s) 7-13 and 18-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over “Efficient Transistor-Level Design of CMOS Gates” (2013-Possani) in view of “Automatic Generation and Evaluation of Transistor Networks in Different Logic Styles” (2008-daRosa) in further view of Boolean Decomposition for AIG Optimization (2017-Machado)
With respect to claim 7, Possani in view of daRosa teaches all of the limitations of claim 1, as noted above. Possani and daRosa do not teach wherein scaling the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals includes And-inverter graph (AIG) rewriting for the factored form literals.
However, Machado teaches wherein scaling the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals includes And-inverter graph (AIG) rewriting for the factored form literals (see section labeled AIG optimization, where “In this work, multi-output decomposition is used by iteratively selecting the Boolean divisor that minimizes the literals of the functions factored forms, [page 144 col 2 paragraph 4 lines 3-5]; Algorithm provided in detail in FIG. 5 and FIG. 6, where FIG. 5 shows the AIG input in line 1 and the BoolDecompose algorithm is invoked at line 8, [page 146]; and the BoolDecompose function is shown in FIG. 6, with the numLiterals defined at line 10 and checked at line 34, [page 146]; see also “The cost function to be minimized is defined as the sum of literals of all functions in factored form (numLiterals, line 10), [page 146 col 2 paragraph 4 lines 3-5]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani in view of daRosa with Machado because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani in view of daRosa discloses a system and method that teaches how to perform a first pass at network optimization. Machado introduces concepts of rewriting and refactoring, which additionally applies local optimizations:
Restructuring techniques for And-Inverter Graphs (AIG), such as rewriting and refactoring, are powerful, scalable and fast, achieving highly optimized AIGs after few iterations. However, these techniques are biased by the original AIG structure and limited by single output optimizations. This paper investigates AIG optimization for area, exploring how far Boolean methods can reduce AIG nodes through local optimization.
A person having skill in the art would have a reasonable expectation of successfully further optimizing the networks produced in the system and method of Possani in view of daRosa by modifying Possani in view of daRosa with the local optimizations of Machado. Therefore, it would have been obvious to combine Possani in view of daRosa with Machado to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 8, Possani in view daRosa and Machado teach all of the limitations of claim 7, as noted above. Possani and daRosa do not teach wherein the AIG rewriting includes replacing a part of a circuit component using one or more precomputed smaller structures that are smaller than the circuit component.
However, Machado teaches wherein the AIG rewriting includes replacing a part of a circuit component using one or more precomputed smaller structures that are smaller than the circuit component (see FIG. 5 lines 10-11: new klcut = AIG network of divisors; and replace klcut by new klcut in AIG, [page 146]; all the divisors are computed previously using algorithm shown in FIG. 6, [page 146], at FIG. 5 line 8, [page 146]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani in view of daRosa with Machado because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani in view of daRosa discloses a system and method that teaches how to perform a first pass at network optimization. Machado introduces concepts of rewriting and refactoring, which additionally applies local optimizations:
Restructuring techniques for And-Inverter Graphs (AIG), such as rewriting and refactoring, are powerful, scalable and fast, achieving highly optimized AIGs after few iterations. However, these techniques are biased by the original AIG structure and limited by single output optimizations. This paper investigates AIG optimization for area, exploring how far Boolean methods can reduce AIG nodes through local optimization.
A person having skill in the art would have a reasonable expectation of successfully further optimizing the networks produced in the system and method of Possani in view of daRosa by modifying Possani in view of daRosa with the local optimizations of Machado. Therefore, it would have been obvious to combine Possani in view of daRosa with Machado to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 9, Possani in view of daRosa teaches all of the limitations of claim 1, as noted above. Possani and daRosa do not teach wherein the AIG uses size as a cost function to limit a number of AIG nodes.
However, Machado teaches wherein the AIG uses size as a cost function to limit a number of AIG nodes (This paper studies technology-independent transformations that reduce the AIG size by exploring the use of Boolean decomposition, [page 143 col 2 paragraph 2 lines 1-3]; where the specific line in the algorithm is FIG. 5 line 9: “if size of divisors < size of klcut then”, [page 146];).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani in view of daRosa with Machado because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani in view of daRosa discloses a system and method that teaches how to perform a first pass at network optimization. Machado introduces concepts of rewriting and refactoring, which additionally applies local optimizations:
Restructuring techniques for And-Inverter Graphs (AIG), such as rewriting and refactoring, are powerful, scalable and fast, achieving highly optimized AIGs after few iterations. However, these techniques are biased by the original AIG structure and limited by single output optimizations. This paper investigates AIG optimization for area, exploring how far Boolean methods can reduce AIG nodes through local optimization.
A person having skill in the art would have a reasonable expectation of successfully further optimizing the networks produced in the system and method of Possani in view of daRosa by modifying Possani in view of daRosa with the local optimizations of Machado. Therefore, it would have been obvious to combine Possani in view of daRosa with Machado to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 10, Possani in view of daRosa teaches all of the limitations of claim 1, as noted above. Possani and daRosa do not teach , wherein scaling the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals includes And-inverter graph (AIG) resubstitution for the factored form literals.
However, Machado teaches wherein scaling the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals includes And-inverter graph (AIG) resubstitution for the factored form literals (see section labeled AIG optimization, where “In this work, multi-output decomposition is used by iteratively selecting the Boolean divisor that minimizes the literals of the functions factored forms, [page 144 col 2 paragraph 4 lines 3-5]; see also “The cost function to be minimized is defined as the sum of literals of all functions in factored form (numLiterals, line 10), [page 146 col 2 paragraph 4 lines 3-5]; the last step in the process is AIG rewriting if improved, which is a form of resubstitution as shown in FIG. 2, [page 144]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani in view of daRosa with Machado because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani in view of daRosa discloses a system and method that teaches how to perform a first pass at network optimization. Machado introduces concepts of rewriting and refactoring, which additionally applies local optimizations:
Restructuring techniques for And-Inverter Graphs (AIG), such as rewriting and refactoring, are powerful, scalable and fast, achieving highly optimized AIGs after few iterations. However, these techniques are biased by the original AIG structure and limited by single output optimizations. This paper investigates AIG optimization for area, exploring how far Boolean methods can reduce AIG nodes through local optimization.
A person having skill in the art would have a reasonable expectation of successfully further optimizing the networks produced in the system and method of Possani in view of daRosa by modifying Possani in view of daRosa with the local optimizations of Machado. Therefore, it would have been obvious to combine Possani in view of daRosa with Machado to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 11, Possani in view of daRosa teaches all of the limitations of claim 1, as noted above. Possani and daRosa do not teach wherein scaling the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals includes performing refactoring.
However, Machado teaches wherein scaling the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals includes performing refactoring (see section labeled AIG optimization, where “In this work, multi-output decomposition is used by iteratively selecting the Boolean divisor that minimizes the literals of the functions factored forms, [page 144 col 2 paragraph 4 lines 3-5]; see also “The cost function to be minimized is defined as the sum of literals of all functions in factored form (numLiterals, line 10), [page 146 col 2 paragraph 4 lines 3-5]; the last step in the process is AIG rewriting if improved as shown in FIG. 2, [page 144]; rewriting and refactoring are related, see [Abstract], where the selected result is “refactorization” because considered in factored form: In this work, multi-output decomposition is used by iteratively selecting the Boolean divisor that minimizes the literals of the functions factored forms, [2], [page 144 col 2 paragraph 4 lines 3-5]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani in view of daRosa with Machado because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani in view of daRosa discloses a system and method that teaches how to perform a first pass at network optimization. Machado introduces concepts of rewriting and refactoring, which additionally applies local optimizations:
Restructuring techniques for And-Inverter Graphs (AIG), such as rewriting and refactoring, are powerful, scalable and fast, achieving highly optimized AIGs after few iterations. However, these techniques are biased by the original AIG structure and limited by single output optimizations. This paper investigates AIG optimization for area, exploring how far Boolean methods can reduce AIG nodes through local optimization.
A person having skill in the art would have a reasonable expectation of successfully further optimizing the networks produced in the system and method of Possani in view of daRosa by modifying Possani in view of daRosa with the local optimizations of Machado. Therefore, it would have been obvious to combine Possani in view of daRosa with Machado to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 12, Possani in view of daRosa teaches all of the limitations of claim 11, as noted above. Possani and daRosa do not teach wherein refactoring includes rewriting maximum fanout-free cones (MFFCs) with a new factored implementation when a number of gates decreases.
However, Machado teaches wherein refactoring includes rewriting maximum fanout-free cones (MFFCs) with a new factored implementation when a number of gates decreases (the last step in the process is AIG rewriting if improved as shown in FIG. 2, [page 144]; rewriting and refactoring are related, see [Abstract], where the selected result is “refactorization” because considered in factored form: In this work, multi-output decomposition is used by iteratively selecting the Boolean divisor that minimizes the literals of the functions factored forms, [2], [page 144 col 2 paragraph 4 lines 3-5]; AIG rewriting and refactoring perform local transformations, extracting the local context with K-cuts [16], windows or maximum fanout-free cones (MFFCs), [page 143 col 1 paragraph 3 lines 1-3]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani in view of daRosa and Machado with this teaching of Machado because this simple substitution of one known element for another to obtain predictable results. Possani in view of daRosa discloses a system and method that teaches how to perform a first pass at network optimization. Machado introduces concepts of rewriting and refactoring, which additionally applies local optimizations, (see Machado [Abstract]). To perform local transformations local portions of the AIG need to be defined, and Machado provides a description of three methods to extract local contexts in order to perform local optimizations:
AIG rewriting and refactoring perform local transformations, extracting the local context with K-cuts [16], windows or maximum fanout-free cones (MFFCs).
(Machado [page 143 col 1 paragraph 2 lines 1-3]).
In the main embodiment, Machado teaches extracting KL-cuts as shown in Fig. 2, (Machado [page 144]), but the reference clearly contemplates that the other methods of local context extraction are possible. The MFFC method is well known in the art, as is noted by citing reference [11], (Machado [page 143 col 2 paragraph 6]). One of ordinary skill in the art could have substituted the MFFC method for the KL-cut method for extracting local contexts, and the results of the substitution would have been predictable. Therefore, it would have been obvious to combine Possani in view of daRosa and Machado with the MFFC method disclosed in Machado to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 13, Possani in view of daRosa teaches all of the limitations of claim 11, as noted above. Possani and daRosa do not teach wherein scaling the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals includes performing technology mapping driven by the factored form literals.
However, Machado teaches wherein scaling the single-stage transistor networks to multi-stage transistor networks to globally optimize for factored form literals includes performing technology mapping driven by the factored form literals (In this work, multi-output decomposition is used by iteratively selecting the Boolean divisor that minimizes the literals of the functions factored forms, [page 144 col 2 paragraph 4 lines 3-5]; Table 4 shows technology mapping performed for FPGAs and standard cells using the AIGs from Table 3. Area reduction was observed simply by changing the input with smaller AIGs, [page 148 col 1 paragraph 2 lines 1-4]; see also Table 4, [page 148]).
It would have been obvious to one skilled in the art before the effective filing date to combine Possani in view of daRosa with Machado because a teaching, suggestion, or motivation in the prior art would have led one skilled in the art to combine prior art teaching to arrive at the claimed invention. Possani in view of daRosa discloses a system and method that teaches how to perform a first pass at network optimization. DaRosa teaches technology mapping, but not in the scaling step as described in the claim. Machado introduces concepts of rewriting and refactoring, which additionally applies local optimizations. These optimizations are shown to improve the AIG in table 3, but the values in table 3 cannot show things like improving area, which requires the last step of technology mapping, which is why table 4 shows the results of technology mapping. A person having skill in the art would have a reasonable expectation of successfully further optimizing the networks produced in the system and method of Possani in view of daRosa by modifying Possani in view of daRosa with the local optimizations of Machado. Therefore, it would have been obvious to combine Possani in view of daRosa with Machado to a person having ordinary skill in the art, and this claim is rejected under 35 U.S.C. 103.
With respect to claim 18, incorporating the rejections of claim 7 and claim 14, claim 18 is rejected for substantially similar rationale.
With respect to claim 19, incorporating the rejections of claim 10 and claim 14, claim 19 is rejected for substantially similar rationale.
With respect to claim 20, incorporating the rejections of claim 11 and claim 14, claim 20 is rejected for substantially similar rationale.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
“MIS: A Multiple-Level Logic Optimization System” (1987-Brayton) - For multilevel design, two basic methodologies have evolved: 1) "global" optimization, where the logic functions are "factored" into an optimal multilevel form with little consideration of the form of the original description (e.g., the Yorktown Silicon Compiler, part of Angel [17], SOCRATES, and FDS [13]); 2) "peephole" optimization, where local transformations are applied to the user specified ( or globally-optimized) logic function (e.g., a part of Angel, LSS, MAMBO [16], and SOCRATES), [page 1062 col 2 paragraph 4]-[page 1063 col 1 paragraph 1].
“DAG-Aware AIG Rewriting A Fresh Look at Combinational Logic Synthesis” (2006-Mishchenko) - All non-redundant AIG subgraphs of the representative functions of the useful equivalence classes are pre-computed in advance as a shared DAG containing approximately one thousand nodes and hashed by the truth table. This DAG is compiled into the program as an integer array, which noticeably reduces the setup time of the rewriting package, [page 533 col 1 paragraph 7]; most relevant to claim 8 because of the word “pre-computed”.
“Technology Mapping for Virtual Libraries Based on Cells with Minimal Transistor Stacks” (2008-Marques) – FIG. 3.1, [page 28], is the original of the figure 1.2 used in da Rosa, [page 18]. Both references provide an excellent overview of the art, and da Rosa or Marques could have been used as a secondary reference. Marques provides detailed steps within technology matching, [pages 33-37], but these steps do not appear to be claimed. DaRosa focuses a little more on factoring methods, so da Rosa was ultimately chosen as the better secondary reference.
“Graph-Based Transistor Network Generation Method for Supergate Design” (2016-Possani) - The proposed method comprises two main modules: 1) the kernel identification and 2) the switch network composition. The former receives an ISOP F and identifies individual NSP and SP switch networks, representing subfunctions of f. The latter composes those networks into a single network by performing logic sharing. The provided output is an optimized switch network representing the target function f, [page 593 col 1 paragraph 3]; Either 2016-Possani or 2013-Possani could have been the primary reference, but 2013-Possani provides a little more explanation regarding CMOS gates having pullup and pulldown planes.
“An Integrated Technology Mapping Environment” (2005-Mishchenko) - The cost function computes the total of the switching activities of the gates in the MFFC of each match. The match that satisfies the required times and minimizes the switching activity is selected at each node. The area of the MFFC is used as a tie-breaker in prioritizing matches, [page 4 col 2 paragraph 2 lines 1-5].
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DANIEL MILLER whose telephone number is (408) 918-7548. The examiner can normally be reached on Monday-Friday from 11am to 5pm (PT). If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jack Chiang, can be reached at telephone number 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 an application may be obtained from Patent Center and the Private Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from Patent Center or Private PAIR. Status information for unpublished applications is available through Patent Center and Private PAIR to authorized users only. Should you have questions about access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free).
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) Form at https://www.uspto.gov/patents/uspto-automated- interview-request-air-form.
/D.M./Examiner, Art Unit 2851
/JACK CHIANG/Supervisory Patent Examiner, Art Unit 2851
Prosecution Insights