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 Objections
Claim(s) 10 and 20 objected to because of the following informalities: "analyzing the implementation results of the hardware" was not properly disclosed in the claim or the claim it depends on but rather the "HDL description". Appropriate correction is required.
Claim(s) 5 and 15 objected to because of the following informalities: "at least one maximal complexity among the operations at the levels" was not properly disclosed in the claim or the claim it depends on. Appropriate correction is required.
Specification
The disclosure is objected to because of the following informalities: paragraph 25 discloses "design flow for a hardware (HW) accelerator 300 of FIG. 1" but a "hardware (HW) accelerator 300 of FIG. 1" does not exist in the drawing and should be "hardware (HW) accelerator 100 of FIG. 1". Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claim(s) 4 and 14 recites “a first coefficient for indicating an importance of the graph structure optimization” where there is insufficient antecedent basis for "the graph structure optimization" and is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
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.
Claim(s) 1-3, 6, 8-12, 16, 18-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Sharma et al. (U.S. Doc. No. 11321606) in view of Van Eijndhoven et al. (U.S. Doc. No. 9081928).
Regarding claim 1, Sharma discloses a method for evaluating a hardware accelerator, the method comprising (col 1, “For one embodiment of the present invention, a hardware accelerator with a heterogenous architecture for training quantized neural networks is described.”; also, col 24, “this specification describes a novel method for analytically calculating the optimal breakdown of the platform resources 3140 for the exemplary architecture presented in 2000”: generating a data processing graph for describing at least one algorithmic operation (col 12, “the DNN workflow begins with a programmer defining a Dataflow Graph (DFG) of the DNN using a high-level API”; also, col 23, “the workflow 3100 begins with the programmer defining the DataFlow Graph (DFG) of the neural network in step 3110”); evaluating a complexity and performance of the data processing graph using complexity and performance metrics (col 13, “the dataflow analyzer component iterating over the nodes of the dataflow graph of the DNN and generates a list of pairs (e.g., operation type, precision, operation count) for the forward and backward passes of training”; also, col 25, “the scheduler generates the cycle counts for Q-array 2010 and MP-array 2020.”); data processing graph based on set constraints, and the evaluated complexity and performance to generate multiple data processing graphs; evaluating the multiple data processing graphs using the complexity and performance metrics; and selecting at least one optimal graph from among the multiple data processing graphs for design of the hardware accelerator.
However, in a similar field of endeavor, Van Eijndhoven discloses modifying the data processing graph based on set constraints, and the evaluated complexity and performance to generate multiple data processing graphs (col 17, “Transformation step 2200 identifies a bottleneck in a seed design 2298 that is selected from the seed pool 2499. The selection is based on the user-specified design constraints 2001 and the area and delay estimates of the seed design.”; also, col 17, “the design transformation process 2000 transforms the initial design 1999 as produced by the analysis step 1000 into multiple design alternatives 2999, each with different area and delay trade-offs”); evaluating the multiple data processing graphs using the complexity and performance metrics (col 22, “an estimator 2100 updates the delay and area estimates of the transformed design 2329. If the resulting design 2339 is a pareto point with respect to the design alternatives 2399, it is added to the design alternatives 2399, otherwise it is discarded.”); and selecting at least one optimal graph from among the multiple data processing graphs for design of the hardware accelerator (col 29, “a pareto point 3004 is a design point which is not strictly dominated by another design point. This means that each pareto point represents a design that is the best choice in the design space close to that point.”; also, col 18, “It then iteratively optimizes this design by selecting the design alternative with the lowest delay and adding this design alternative to the seed pool 2499 for the next optimization. Each intermediate pareto point is added to the design alternatives 2999.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Sharma's invention of generating a hardware accelerator from a dataflow graph that is evaluated for its operation-count resource requirements and its cycle-count performance with the features of van Eijndhoven's invention of transforming a design derived from a data flow graph, subject to user-specified design constraints, into multiple design alternatives and selecting the Pareto-optimal alternative that is the best choice across the area, delay, and power design space. One of ordinary skill in the art would have been motivated to make this combination for the following reasons. First, Sharma optimizes a single template architecture iteratively, feeding profiled results back so that "the output 3150 is fed back to the dfg analysis step 3111 for the next plurality of iterations of Neural Network training and inference," and van Eijndhoven supplies an explicit population of candidates by transforming the design "into multiple design alternatives 2999, each with different area and delay trade-offs," giving Sharma's workflow several candidate graphs to choose among rather than a single iteratively tuned design. Second, Sharma already computes complexity by "iterating over the nodes of the dataflow graph" and performance from "the cycle counts," and van Eijndhoven's selection of the alternative that is "the best choice in the design space" provides an objective criterion that uses exactly those area, delay, and power quantities to pick the optimal candidate. Third, van Eijndhoven teaches that exploring the alternatives along the trade-off curve yields "an implementation requiring less hardware," so applying its Pareto selection to Sharma's accelerator-generation flow predictably produces a hardware accelerator design that satisfies the user's constraints.
Regarding claim 2, Sharma as modified by Van Eijndhoven discloses the method of claim 1, wherein the evaluating the multiple data processing graphs comprises evaluating for the set constraints at least one or more of performance characteristics, hardware overhead and power consumption. Sharma does not disclose the evaluating the multiple data processing graphs comprises evaluating for the set constraints at least one or more of performance characteristics, hardware overhead and power consumption.
However, in a similar field of endeavor, Van Eijndhoven discloses the evaluating the multiple data processing graphs comprises evaluating for the set constraints at least one or more of performance characteristics, hardware overhead and power consumption (col 22, “an estimator 2100 updates the delay and area estimates of the transformed design 2329. If the resulting design 2339 is a pareto point with respect to the design alternatives 2399, it is added to the design alternatives 2399, otherwise it is discarded.”; also, col 29, “The location of these points is given by the value of characterizing quantities of the design they correspond to. Examples of these quantities are area, delay, power consumption and monetary cost.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Sharma's invention of generating a hardware accelerator from an evaluated dataflow graph with the features of van Eijndhoven's invention of evaluating the design alternatives by their delay, area, and power consumption. One of ordinary skill in the art would have been motivated to make this combination because van Eijndhoven evaluates each candidate by "the value of characterizing quantities" that are "area, delay, power consumption and monetary cost," which correspond to the claimed performance characteristics, hardware overhead, and power consumption, thereby supplying Sharma's accelerator-generation flow with a constraint-aware evaluation of the multiple candidate graphs.
Regarding claim 3, Sharma as modified by Van Eijndhoven discloses the method of claim 1, wherein the evaluating a complexity and performance of the data processing graph comprises determining the complexity metric based on one or more of a number of edges, a number of nodes, a number of connectivity components, an operation index, a number of available operations, a number of times an operation is used in the data processing graph, a complexity level of the operation, and weight coefficients (Sharma: col 13, “the dataflow analyzer component iterating over the nodes of the dataflow graph of the DNN and generates a list of pairs (e.g., operation type, precision, operation count) for the forward and backward passes of training”; also, col 13, “the operation count field describes the number of scalar operations”).
Regarding claim 6, Sharma as modified by Van Eijndhoven discloses the method of claim 1, wherein . Sharma does not disclose the modifying the data processing graph to generate multiple data processing graphs provide graphs that satisfy the set constraints, reduce the evaluated complexity and increase the evaluated performance.
However, in a similar field of endeavor, Van Eijndhoven discloses the modifying the data processing graph to generate multiple data processing graphs provide graphs that satisfy the set constraints, reduce the evaluated complexity and increase the evaluated performance (col 17, “the design transformation process 2000 transforms the initial design 1999 as produced by the analysis step 1000 into multiple design alternatives 2999, each with different area and delay trade-offs”; also, col 17, “Optimizations include design transformations to increase concurrency and to map elements in the design alternative's program variation to computation and communication hardware in the embedded system.”; also, col 37-38, “This sharing of hardware resources can lead to an implementation requiring less hardware, at the cost of a longer execution time”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Sharma's invention of generating a hardware accelerator from an evaluated dataflow graph with the features of van Eijndhoven's invention of transforming the design into multiple alternatives that increase concurrency and require less hardware. One of ordinary skill in the art would have been motivated to make this combination because van Eijndhoven generates "multiple design alternatives 2999, each with different area and delay trade-offs" and applies transformations that "increase concurrency" while permitting "an implementation requiring less hardware," which corresponds to producing graphs that reduce the evaluated complexity and increase the evaluated performance while satisfying the design constraints that Sharma imposes on the accelerator.
Regarding claim 8, Sharma as modified by Van Eijndhoven discloses the method of claim 1, further comprising: generating hardware description language (HDL) descriptions of the multiple data processing graphs (Sharma: col 26, “the builder 3114 generates a synthesizable accelerator in case of FPGA implementation, along with the optimized values of circuit parameters using both the optimized set of architectural parameter and execution schedule.”; also, col 13, “a builder operation to generate a synthesizable accelerator using the optimal resource breakdown from operation 1030.”).
Regarding claim 9, Sharma as modified by Van Eijndhoven discloses the method of claim 8, further comprising: implementing a hardware based on the HDL descriptions (Sharma: col 4, “the present design targets FPGAs for their flexibility and develops a heterogenous architecture, which is an accelerator for training quantized DNNs.”; also, col 14, “the simulator component divides the FPGA's LUT and DSP resources into 16×16 systolic arrays for the forward and backward passes using the p obtained from the resource partitioner.”).
Regarding claim 10, Sharma as modified by Van Eijndhoven discloses the method of claim 9, further comprising: analyzing the implementation results of the hardware (Sharma: col 26, “the dfg analysis step 3111 then repeats the process of observing and sampling runtime characteristics of the Neural Network during the execution of training iterations.”; also, col 26, “the output 3150 is fed back to the dfg analysis step 3111 for the next plurality of iterations of Neural Network training and inference”).
Regarding claim 11, Sharma discloses a system comprising (col 1, “In one example, a data processing system to perform a workflow for generating a hardware accelerator, comprises memory; and a processor coupled to the memory.”): a host configured for hardware accelerator development (col 18, “Data processing system 1202, as disclosed above, includes a general purpose instruction-based processor 1227 and an accelerator 1226”); a storage device (col 19, “The exemplary computer system 1200 includes a data processing system 1202, a main memory 1204 (e.g., read-only memory (ROM), flash memory, dynamic random access memory (DRAM) such as synchronous DRAM (SDRAM) or DRAM (RDRAM), etc.), a static memory 1206 (e.g., flash memory, static random access memory (SRAM), etc.), and a data storage device 1216 (e.g., a secondary memory unit in the form of a drive unit, which may include fixed or removable computer-readable storage medium), which communicate with each other via a bus 1208.”); and a hardware accelerator designable by the host and coupled between the host and the storage device (col 18, “Data processing system 1202, as disclosed above, includes a general purpose instruction-based processor 1227 and an accelerator 1226”; also, col 26, “the builder 3114 generates a synthesizable accelerator in case of FPGA implementation, along with the optimized values of circuit parameters using both the optimized set of architectural parameter and execution schedule”), wherein the storage device is configured to store data associated with a calculated performance of the hardware accelerator (col 25, “the scheduler generates the cycle counts for Q-array 2010 and MP-array 2020.”), wherein the host is configured to: generate a data processing graph for describing at least one algorithmic operation (col 12, “the DNN workflow begins with a programmer defining a Dataflow Graph (DFG) of the DNN using a high-level API.”; also, col 23, “the workflow 3100 begins with the programmer defining the DataFlow Graph (DFG) of the neural network in step 3110”); evaluate a complexity and performance of the data processing graph using complexity and performance metrics (col 13, “the dataflow analyzer component iterating over the nodes of the dataflow graph of the DNN and generates a list of pairs (e.g., operation type, precision, operation count) for the forward and backward passes of training”; also, col 25, “the scheduler generates the cycle counts for Q-array 2010 and MP-array 2020”); data processing graph based on set constraints, and the evaluated complexity and performance to generate multiple data processing graphs; and evaluate the multiple data processing graphs using the complexity and performance metrics to select at least one optimal graph from among the multiple data processing graphs for design of the hardware accelerator.
However, in a similar field of endeavor, Van Eijndhoven discloses modify the data processing graph based on set constraints, and the evaluated complexity and performance to generate multiple data processing graphs (col 17, “Transformation step 2200 identifies a bottleneck in a seed design 2298 that is selected from the seed pool 2499. The selection is based on the user-specified design constraints 2001 and the area and delay estimates of the seed design.”; also, col 17, “the design transformation process 2000 transforms the initial design 1999 as produced by the analysis step 1000 into multiple design alternatives 2999, each with different area and delay trade-offs”); and evaluate the multiple data processing graphs using the complexity and performance metrics to select at least one optimal graph from among the multiple data processing graphs for design of the hardware accelerator (col 29, “a pareto point 3004 is a design point which is not strictly dominated by another design point. This means that each pareto point represents a design that is the best choice in the design space close to that point.”; also, col 18, “It then iteratively optimizes this design by selecting the design alternative with the lowest delay and adding this design alternative to the seed pool 2499 for the next optimization. Each intermediate pareto point is added to the design alternatives 2999.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Sharma's invention of generating a hardware accelerator from a dataflow graph that is evaluated for its operation-count resource requirements and its cycle-count performance with the features of van Eijndhoven's invention of transforming a design derived from a data flow graph, subject to user-specified design constraints, into multiple design alternatives and selecting the Pareto-optimal alternative that is the best choice across the area, delay, and power design space. One of ordinary skill in the art would have been motivated to make this combination for the following reasons. First, Sharma optimizes a single template architecture iteratively, and van Eijndhoven supplies an explicit population of candidates by transforming the design "into multiple design alternatives 2999, each with different area and delay trade-offs," giving Sharma's workflow several candidate graphs to choose among rather than a single iteratively tuned design. Second, Sharma already computes complexity by "iterating over the nodes of the dataflow graph" and performance from "the cycle counts," and van Eijndhoven's selection of the alternative that is "the best choice in the design space" provides an objective criterion that uses those area, delay, and power quantities to pick the optimal candidate. Third, van Eijndhoven teaches that exploring the alternatives along the trade-off curve yields "an implementation requiring less hardware," so applying its Pareto selection to Sharma's accelerator-generation flow predictably produces a hardware accelerator design that satisfies the user's constraints.
Regarding claim 12, Sharma as modified by Van Eijndhoven discloses the system of claim 11, wherein set constraints include performance characteristics, hardware overhead and power consumption.
However, in a similar field of endeavor, Van Eijndhoven discloses the set constraints include performance characteristics, hardware overhead and power consumption (col 17, “Transformation step 2200 identifies a bottleneck in a seed design 2298 that is selected from the seed pool 2499. The selection is based on the user-specified design constraints 2001 and the area and delay estimates of the seed design.”; also, col 29, “The location of these points is given by the value of characterizing quantities of the design they correspond to. Examples of these quantities are area, delay, power consumption and monetary cost.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Sharma's invention of generating a hardware accelerator from an evaluated dataflow graph with the features of van Eijndhoven's invention of constraining the design by its area, delay, and power consumption. One of ordinary skill in the art would have been motivated to make this combination because van Eijndhoven applies "user-specified design constraints 2001" and characterizes the design space by "area, delay, power consumption," which correspond to the claimed hardware overhead, performance characteristics, and power consumption, thereby giving Sharma's accelerator-generation flow the constraint set that bounds the search for the optimal candidate.
Regarding claim 16, Sharma as modified by Van Eijndhoven discloses the system of claim 11, wherein multiple data processing graphs include graphs that satisfy the set constraints, reduce the evaluated complexity and increase the evaluated performance.
However, in a similar field of endeavor, Van Eijndhoven discloses the multiple data processing graphs include graphs that satisfy the set constraints, reduce the evaluated complexity and increase the evaluated performance (col 17, “the design transformation process 2000 transforms the initial design 1999 as produced by the analysis step 1000 into multiple design alternatives 2999, each with different area and delay trade-offs.”; also, col 17, “Optimizations include design transformations to increase concurrency and to map elements in the design alternative's program variation to computation and communication hardware in the embedded system.”; also, col 37-38, “This sharing of hardware resources can lead to an implementation requiring less hardware, at the cost of a longer execution time.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Sharma's invention of generating a hardware accelerator from an evaluated dataflow graph with the features of van Eijndhoven's invention of transforming the design into multiple alternatives that increase concurrency and require less hardware. One of ordinary skill in the art would have been motivated to make this combination because van Eijndhoven generates "multiple design alternatives 2999, each with different area and delay trade-offs" and applies transformations that "increase concurrency" while permitting "an implementation requiring less hardware," which corresponds to producing graphs that reduce the evaluated complexity and increase the evaluated performance while satisfying the design constraints that Sharma imposes on the accelerator.
Regarding claim 18, Sharma as modified by Van Eijndhoven discloses the system of claim 11, wherein the host is further configured to generate hardware description language (HDL) descriptions of the multiple data processing graphs (Sharma: col 26: the builder 3114 generates a synthesizable accelerator in case of FPGA implementation, along with the optimized values of circuit parameters using both the optimized set of architectural parameter and execution schedule.”; also, col 13, “a builder operation to generate a synthesizable accelerator using the optimal resource breakdown from operation 1030”).
Regarding claim 19, Sharma as modified by Van Eijndhoven discloses the system of claim 18, wherein the hardware accelerator comprises hardware based on the HDL descriptions (Sharma: Col 4, “the present design targets FPGAs for their flexibility and develops a heterogenous architecture, which is an accelerator for training quantized DNNs.”; also, col 14, “the simulator component divides the FPGA's LUT and DSP resources into 16×16 systolic arrays for the forward and backward passes using the p obtained from the resource partitioner.”).
Regarding claim 20, Sharma as modified by Van Eijndhoven discloses the system of claim 19, wherein the host is further configured to analyze implementation results of the hardware (Sharma: col 26, “the dfg analysis step 3111 then repeats the process of observing and sampling runtime characteristics of the Neural Network during the execution of training iterations.”; also, col 26, “the output 3150 is fed back to the dfg analysis step 3111 for the next plurality of iterations of Neural Network training and inference.”).
Allowable Subject Matter
Claim(s) 7 and 17 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. Each recites that "the optimal graph selected comprises a graph with the highest performance and the lowest power consumption from among the multiple data processing graphs." The prior art of record selects an optimal design along a multi-objective trade-off rather than a single graph that is simultaneously best in both performance and power. van Eijndhoven selects the non-dominated "design alternative with the lowest delay" from a design space whose characterizing quantities merely include "area, delay, power consumption and monetary cost," and Sharma selects an optimal resource breakdown for a single template architecture; neither reference, alone or in combination, teaches or suggests selecting a single graph exhibiting both the highest performance and the lowest power consumption from among the multiple graphs.
Claim(s) 5 and 15 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, and if the antecedent-basis objections above are addressed. The prior art of record does not teach or suggest determining the performance metric "based on a number of levels in the data processing graph and at least one maximal complexity among the operations at the levels." Sharma evaluates performance from cycle counts produced by cycle-accurate scheduling and van Eijndhoven evaluates a design by its delay and area estimates, but neither reference determines a performance metric from the number of levels in the graph together with a maximal per-level operation complexity.
Claim(s) 4 and 14 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. The prior art does not teach weight coefficients that include "a first coefficient for indicating an importance of the graph structure optimization" and "a second coefficient for the importance of the number and complexity of the operations within the data processing graph."
Claim(s) 13 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. Unlike parallel method claim 3, which recites the complexity metric as determined "based on one or more of" the listed quantities and is therefore satisfied by teaching any single listed quantity, claim 13 recites the complexity metric as determined "based on a number of edges, a number of nodes, a number of connectivity components, an operation index, a number of available operations, a number of times the operation is used in the data processing graph, a complexity level of the operation, and weight coefficients" in the conjunctive, thereby requiring all of the enumerated quantities. The prior art of record does not teach or suggest determining a single complexity metric from the conjunctive combination of all of these quantities, including "a number of connectivity components," "an operation index," "a complexity level of the operation," and "weight coefficients."
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Jai Li whose telephone number is (571)272-1170. The examiner can normally be reached Mon-Thu between 06:00-16:00 EST.
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, Xiao Wu can be reached at (571)272-7761. 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.
/JAI W LI/Junior Examiner, Art Unit 2613
/XIAO M WU/Supervisory Patent Examiner, Art Unit 2613
Prosecution Insights