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 § 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, 6-8, 10, 12, 18, 20, and 22 are rejected under 35 U.S.C. 103 as being unpatentable over US Pub. No. 2008/0155485 to Lin et al. (“Lin”) in view of US Patent No. 7,685,540 to Madden et al. (“Madden”) and in further view of US Pub. No. 2023/0071424 to Kibardin et al. (“Kibardin”).
As to independent claim 18 and similarly recited independent claims 1 and 22, a system (¶ 0003, 0033) for laying out an integrated circuit (¶ 0003), comprising: an input configured to receive a netlist of circuit elements comprising a plurality of macro blocks and standard cells of the integrated circuit requirement (¶ 0003, 0005, 0006, 0033-0035, 0038-0043. Lin teaches a computer-implemented floorplanner that receives and operates upon a hierarchical IC netlist comprising standard cell instances and large IP modules corresponding to the claimed standard cells and macro blocks, respectively, and uses the known dimensions and estimated floorspace requirements of those elements when allocating them to placement regions.); at least one automated processor, configured to (¶ 0003, 0033): obtain a hierarchical abstract relative positioning of the circuit elements and associated kernel graphs, within a hierarchy of regions, by at least one of repeatedly partition the netlist using bisection, (¶ 0034, 0038-0044, 0047-0051. Lin teaches obtaining a hierarchical abstract relative positioning of circuit elements within a hierarchy of regions by repeatedly performing the two way partitioning/bisection, assigning netlist/hypergraph modules to the resulting daughter regions, and recursively repeating the operation before exact module positions are established.); store the hierarchical abstract relative positioning (SHARP) of the circuit elements in a memory (Under BRI, SHARP is construed as stored information representing hierarchical relative placement relationships of circuit elements within a hierarchy of regions. ¶ 0033, 0034, 0052-0055, 0066-0069. Lin stores hierarchical relative placement information represented by recursively generated regional assignments and B*-tree relationships, retains the regional placement representation for subsequent refinement levels, and merges/reuses those tree representations as the hierarchical regions are combined.);
define a plurality of arrangements of the macro blocks and standard cells within a respective region utilizing the SHARP (¶ 0054, 0055, 0065, 0066. Lin defines multiple alternative regional arrangements by iteratively perturbing the retained B*-tree relative placement representation through node moves/swaps, rotations, and resizing, thereby producing alternative compacted floorplans within a respective region.); iteratively legalize the plurality of arrangements of the macro blocks and standard cells, (¶ 0035, 0038, 0040-0043, 0052-0055, 0065-0070. Lin iteratively transforms tentative regional circuit element arrangement into admissible/refined regional floorplans by packing, reshaping, repositioning, and repeatedly perturbing retained B*-tree placement representations. Lin accounts for the space requirements of the modules and reuses the retained tree/floorplan representation during successive refinement stages and when merged regions are further legalized.); and merge the legalized regions to generate (¶ 0041, 0055, 0066-0070. Lin iteratively merges neighboring legalized/refined regional floorplans, merges their corresponding B*-tree representations, and further refines the combined region until the overall IC floorplan is formed.);
Thus, Lin teaches the principal physical design framework of claims 1, 18, and 22, including the automated computer implementation, IC netlist containing standard cells and marco-like large IP modules having space requirements, hierarchical bisection into regions, hierarchical relative placement information, storage/reuse of that information through retained B*-tree structures, multiple alternative regional arrangements, iterative legalization/refinement, and merging of legalized regions.
Lin, however, does not expressly teach: associated kernel graphs received with the circuit-element information, hierarchically positioned, and carried through legalization; a plurality of legalization techniques for each respective arrangement; retaining the resulting as a set of potential placements; and an output port/interface configured to communicate that set.
These features are taught by Madden and Kibardin.
Madden is directed to methodology to handle the placement of design with huge number of blocks (2:55-58). Madden teaches legalization of mixed size placements containing standard cells and macro blocks using multiple legalization techniques, including a hybrid of dynamic programming and a greedy algorithm, wherein multiple candidate locations generate partial placement solutions, subsequent blocks are combined with prior partial solutions, and subsets for the resulting candidate solutions are retained or pruned according to placement objectives, and Madden’s solver returns a set of solutions (2:3-15, 4:20-31, 6:55-65, 7:1-35, claims 7-9).
Kibardin is directed to techniques in placement of compute and memory for accelerated deep learning (Abstract). Kibardin teaches receiving a kernel graph in which nodes represent kernels and arcs represent communication/buffering; physically laying out the graph by assigning each kernel a non-overlapping area constrained rectangular region; representing the kernels’ hierarchical relative positions using a binary space partition tree having horizontal and vertical partition relationships; iteratively updating the tree and placement; searching among multiple tree defined placements while maintaining a population of candidate solutions; and outputting placement annotations defining the physical placement of the graph nodes (¶ 1029, 1030, 1035, 1036, 1043-1058).
It would have been obvious to a PHOSITA to modify Lin’s hierarchical IC floorplanner by (1) using Madden’s hybrid dynamic programming/greedy legalization technique when legalizing Lin’s candidate regional arrangements and retaining Madden’s multiple candidate solutions, and (2) augmenting the placement information handled by the resulting Lin/Madden system with Kibardin’s kernel graphs associated with computational functions assigned to the corresponding physical circuit resources, such that the kernel graphs are hierarchically positioned and their placement information is carried through the placement process and communicated with the resulting candidate placements.
The PHOSITA would have had reason to use Madden’s legalization techniques within Lin’s regional floorplanning framework because Madden provides a known technique for improving the legality and quality of mixed size placements of the same type of circuit elements processed by Lin.
The PHOSITA would have had reason to augment the Lin/Madden floorplanning framework with Kibardin’s kernel graph information because Kibardin teaches using kernel connectivity, workload, and spatial resource requirements when determining placement of computational functions on physical resources, thereby allowing the placement process to account not only for the physical area and connectivity of Lin’s circuit elements but also for the computational and communication relationships of the kernels implement by those resources. Such a modification would predictably improve resource allocation and routing of kernel associated circuitry while retaining Lin’s hierarchical regional placement framework.
As to claim 2, the method according to claim 1, wherein the hierarchical abstract relative positioning of the circuit elements is obtained by repeatedly partitioning the netlist using bisection (Lin: ¶ 0034, 0038, 0039, 0042-0051. Lin teaches repeated two-way netlist/hypergraph partitioning.).
As to claim 6 and similarly recited claim 20, the method according to claim 1, wherein the hierarchical abstract relative positioning of the circuit elements comprises a tree, said obtaining the hierarchical abstract relative positioning of the circuit elements within the hierarchy of regions comprises inducing cut lines in the tree to produce a cut tree, the method further comprising pruning the cut tree using pareto optimization (Kibardin: ¶ 1047, 1053-1056. Madden: 7:3-35. Kibardin teaches a hierarchical placement represented by a binary space partition tree whose internal nodes encode horizontal or vertical cuts and further teaches maintaining and pruning candidate tree defined placements. Madden teaches pruning placement solutions using multidimensional Pareto optimization.).
As to claim 7 and similarly recited claim 20, the method according to claim 6, further comprising pruning the cut trees according to at least one of a feasibility criterion and a performance characteristic (Kibardin: ¶ 1053-1056.).
As to claim 8, the method according to claim 1, further comprising: comparing performance-related characteristics of the potential placements; and selecting a potential placement according to the compared performance-related characteristics (Lin: ¶ 0052, 0055, 0065, 0066. Lin teaches generating and evaluating alternative potential floorplans, comparing those floorplans according to performance related characteristics including area, wirelength, and aspect ratio conformity through a cost function, and selecting the floorplan having the lowest resulting cost for further use.).
As to claim 10, the method according to claim 1, further comprising: modifying a size of a respective circuit element; and defining a second plurality of arrangements of the modified size respective circuit element within a respective region re-utilizing at least one SHARP; said iteratively legalizing comprising legalizing the second plurality of arrangements of the macro blocks and standard cells within the respective region and associated kernel graphs to form second legalized regions, and the second legalized regions are merged to generate a second set of potential placements (Lin: ¶ 0055, 0066-0070, Madden: 6:55-61, 7:3-10, Kibardin as cited in the rejection of claim 1. Lin teaches modifying a circuit element by resizing a soft module, reusing the existing B8-tree hierarchical placement representation to iteratively generate additional compacted floorplans, retaining the placement representation for subsequent refinement, and thereafter merging and further refining the resulting regional floorplans using the merged B8-trees. Madden teaches generating and retaining a set of candidate placement solutions during legalization, including combining subsequent blocks with prior partial solutions. Accordingly, the primary combination teaches resizing a circuit element, generating a second plurality of arrangement while reusing the stored hierarchical placement representation, legalizing/refining those subsequent arrangements, merging the resulting regional placements, and producing a second set of potential placements, with Kibardin supplying the associated kernel graph processing as set forth for claim 1.).
As to claim 12, the method according to claim 1, wherein the plurality of arrangements of the macro blocks and standard cells within the respective region are legalized using dynamic programming (Madden: 4:26-31, claim 7.).
Claim Rejections - 35 USC § 103
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Lin, Madden, and Kibardin as applied to claim 1 above, and further in view of US Pub. No. 2015/0012901 to Chan et al. (“Chan”).
The combination of Lin, Madden, and Kibardin does not expressly teach the limitations of claim 3.
Chan teaches performing a global distribution of mixed size circuit module and states the analytical based approach or force directed approach can be applied to generate that place (¶ 0022). After the analytical placement, the initial floorplan is obtained, although overlap remains (¶ 0022). Chan then generates a slicing tree by applying the recursive partition-based approach to module positions obtained in the step one and repeatedly divides these modules in the region into two subregions (¶ 0023). Chan further explains the region is divided into subregions by recursively applying bipartition algorithm to the circuit module distribution and that a slicing tree is built based on the result (¶ 0022-0025, 0028).
Thus, Chan teaches generating an analytical/global placement and thereafter inducing successive spatial partition boundaries (i.e., cut lines) into that placement to form a hierarchical slicing tree representation of the relative positions of the circuit modules.
It would have been obvious to a PHOSITA to modify the Lin/Madden/Kibardin system to obtain its hierarchical abstract relative positioning using Chan’s known technique of analytically placing the circuit elements and then recursively bipartitioning the resulting placement to generate a slicing tree. Chan expressly teaches this approach preserves the global placement relationships while enabling subsequent legalization and produces stable legal placement with improved wire length (Chan: ¶ 0009-0011, 0028). A skilled artisan therefore would have had reason to use Chan’s analytic placement derived partition hierarchy as a known alternative way of generating the hierarchical relative placement used in the primary combination, with a reasonable expectation of success.
Claims 9 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Lin, Madden, and Kibardin as applied to claims 1 and 18 above, and further in view of US Patent No. 6,378,811 to Shenoy et al. (“Shenoy”).
The combination of Lin, Madden, and Kibardin does not teach limitations of claims 9 and 19.
Shenoy teaches using physical placement information to drive performance optimization of the circuit by modifying both the netlist and circuit elements, including resizing gates, adding/deleting cells or buffers, modifying nets, changing cell locations and generating an improved netlist based on the resulting placement information (3:20-25, 41-46, 4:8-17,34-40).
It would have been obvious to a PHOSTIA to modify the Lin/Madden/Kibardin system/methodology such that, after legalization of a regional placement, the resulting placement information is used in the manner taught by Shenoy to identify performance driven netlist and circuit element changes, and to update the stored SHARP to reflect those changes. Lin’s SHARP/B*-tree representation is already retained and reused during subsequent placement refinement, while Shenoy teaches feeding placement information back into synthesis to optimize circuit performance and generate an updated netlist and modified circuit elements. The PHOSITA would have had reason to incorporate Shenoy’s placement driven optimization feedback into the stored hierarchical placement representation so that subsequent legalization operates on the updated circuit design, thereby maintaining consistency between the physical placement hierarchy and the optimized netlist/circuit elements.
Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over Lin, Madden, and Kibardin as applied to claim 1 above, and further in view of US Patent No. 4,918,614 to Modarres et al. (“Modarres”).
The combination of Lin, Madden, and Kibardin does not teach the limitations of claim 11.
Modarres teaches circuit functions include blocks and may themselves contain lower level function; that each parent block may have its own binary slicing tree representing the relative placement of its internal children; that a node representing the parent block in a higher level slicing tree is linked to the separate slicing tree representing that block’s internal structure; and that the parent’s previously estimated area is subsequently updated based on the placement and shaping of those internal children. Accordingly, Modarres teaches hierarchically expanding a block level placement representation with an internal hierarchical placement representation and using the internal placement to determine the block’s resulting area, corresponding to replacing a macro block with a SHARP representing its internal structure and relieving the macro level area requirement.
It would have been obvious to a PHOSITA to modify the Lin/Madden/Kibardin methodology such that a macro block represented in Lin’s stored hierarchical placement representation is expanded or replaced by a linked internal placement hierarchy as taught by Modarres. Modarres expressly teaches doing so to maintain the design hierarchy while floorplanning at multiple hierarchical levels, and further teaches that placing the internal children permits the parent block’s area and shape to be determined more accurately (Modarres: 5:5-25, 46-65.). The PHOSITA therefore would have had reason to substitute Modarres’s internal slicing tree representation for a macro level node in Lin’s hierarchy so that the placement process could account for the macro’s internal structure rather than treating the macro solely as a monolithic area constrained block, while reserving Lin’s hierarchical placement framework.
Claims 13-17, and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Lin, Madden, and Kibardin as applied to claims 1 and 18 above, and further in view of “Kernal Mapping Techniques for Deep Learning Neural Network Accelerators” to Rao et al. (“Rao”).
The combination of Lin, Madden, and Kibardin does not teach the limitations of claim 13 and 21.
Rao is directed to mapping deep learning computational kernels onto available processor hardware (Abstract). Roa teaches kernel graph comprising computational kernels to be mapped onto processor resources and teaches a mapping approach that applies dynamic programming to perform kernel selection and mapping (Page 24, column 2, ¶ 3). The dynamic programming process determines non-dominated kernel implementations and combines selected kernel implementations into physical arrangements, including horizontal strips and stacked rows (Page 25.).
It would have been obvious to a PHOSITA to modify the kernel graph placement/legalization process/system of Lin, Madden, and Kibardin to employ Rao’s dynamic programming kernel selection and mapping technique. Kibardin already teaches mapping computational kernels of a kernel graph to physical compute resources, while Madden supplies dynamic programming as a legalization technique. Roa teaches a known dynamic programming technique directed specifically to the same problem of selecting and physical mapping kernel implementations onto available compute resources. The PHOSITA therefore would have had reason to sue Rao’s dynamic programming technique in the combined system to support more complex performance models, permit multi-row kernel mappings, and avoid computational explosion as the number of possible mapping increases.
As to claim 14, the method according to claim 13, wherein a respective kernel graph is traversed from inputs to outputs, in breadth-first order, and the order in which kernels are encountered by traversal is selected as the order in which to place kernels across the layout (Rao: Section: “4 MAPPING DEEP LEARNING KERNELS TO RECONFIGURABLE ARCHITECTURES”. Rao teaches traversing a kernel graph from inputs to outputs using breadth-first traversal and thereafter using the traversal order as the kernel-placement order across the processor.).
As to claim 15, the method according to claim 14, wherein a non-dominated subset of potential placements is determined using Bentley's divide and conquer algorithm (Under BRI, these alternative kernel implementations and combinations constitute potential placements, because they represent alternative physical implementations having respective dimensions and arrangements from which the subsequent processor layout is constructed. Rao: Section: “4 MAPPING DEEP LEARNING KERNELS TO RECONFIGURABLE ARCHITECTURES”. Rao teaches generating a plurality of candidate physical kernel implementations and candidate combinations thereof and filtering those candidate placements to retain a non-dominated subset using Bentley’s divide and conquer Pareto-dominance algorithm.).
As to claim 16, the method according to claim 13, wherein non-dominated horizontal sequential subsets of kernels are determined with the dynamic programming, and the non-dominated horizontal sequential subsets of kernels are arranged as strips, the method further comprising stacking the strips into horizontal rows using dynamic programming (Rao: Section: “4 MAPPING DEEP LEARNING KERNELS TO RECONFIGURABLE ARCHITECTURES”. Rao teaches using dynamic programming to determine non-dominated horizontal sequential subsets of kernels, arranging those subsets as optimal horizontal strips, and thereafter applying dynamic programming again to combine the strips into a multi-row stacked placement.).
As to claim 17, the method according to claim 16, wherein alternate strips are disposed in reverse order, to create a serpentine pattern (Rao: Page 26, ¶ 1).
Allowable Subject Matter
Claims 4 and 5 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 4 and 5 would be allowable if amended in the manner above because the prior art of record does not teach or suggest a method having all the combinations of steps or elements as recited in and required by claims 4 or 5.
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
