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
In claim 15, at line 4: replace “points” in phrase “second points” with “point” to correct a typographical error.
In claim 19, at line 3: delete the unmatched parenthesis.
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.
Claims 19 and 20 are 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.
In each of claims 19 and 20, at lines 1-2, the phrase “the distance” in phrase “the distance of the shortest path” lacks antecedent basis.
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 and 11 are rejected under 35 U.S.C. 103 as being unpatentable over US Patent No. 10,515,177 to Ruehl et al. (“Ruehl”) in view of US Patent No. 6,915,361 to Alpert et al. (“Alpert”).
As to independent claim 1 and similarly recited independent claim 11, a method of designing a layout of an integrated circuit (2:20-27, 3:31-37, 4:53-66. Ruehl teaches designing an IC layout by performing routing aware floorplanning and place in which blocks/cells/pins are placed or manipulated in a floorplan or placement layout.), the method comprising: generating floorplan data by performing a floorplan operation based on input data for the integrated circuit (4:53-66, 7:59-8:5, 13:45-65, 14:1-3. Ruehl teaches performing a floorplanning/placement operation using physical input data for the electronic design and generating/updating the floorplan/placement representation used for routing.); receiving physical data including physical information about the integrated circuit, for input data on the integrated circuit (Limitation is recited in claim 11. 13:45-65, 14:1-3. Ruehl receives physical design input describing blocks, pin locations, routing tracks, grids, layers, layout regions, and connectivity and uses that physical information in the floorplanning/placement process.); searching for a path between a first point and a second point, which are specified, based on the floorplan data (9:20-30, 14:7-39, 19:59-20:13. Ruehl identifies source and destination locations in the floorplan and invokes routing operations to determine a geometric interconnection between those locations using the physical floorplan and legal routing resources.); and positioning components of the layout based on a result of the searching (9:34-38, 49-65, 10:1-30. Ruehl uses generated routing results to guide placement and to constrain, modify, or relocate blocks and pins in the physical layout.), wherein the searching for the path comprises, distinguishing a first region, where routing is possible, from a second region, where the routing is not possible, the distinguishing based on the floorplan data (14:7-39, 17:5-25. Ruehl distinguishes routable space from blocked/non-routable space by deriving free design space from the physical floorplan after accounting for existing component boundaries and routing blockages, and uses the resulting free space tiles for route generation.), receiving position data on the first point and the second point (13:54-62, 19:59-66. Ruehl receives physical pin location information and identifies the source and destination pin locations that define the endpoints of the route.), and searching for a (14:34-39, 17:5-25, 20:45-53. Ruehl teaches searching/generating a path between the source and destination through available/legal routing resources of the free design space, as discussed above. Ruehl also teaches selecting routing resources near the source or destination where an objective is to reduce or minimize net length.).
Ruehl teaches the claimed physical layout generation, receipt of physical information, routable/non-routable region distinction, endpoint positions, route generation, and route driven component positioning, but Ruehl does not expressly teach searching for a shortest path between the first point and the second point.
Alpert is directed to automated IC routing (1:9-13). Alpert teaches representing physical IC routing space as a grid of physical positions, excluding/constraining obstacle positions, and using a shortest path algorithm to determine an optimum routing path between two endpoint vertices (1:50-65, 2:1-6, 3:1-18, 54-58).
It would have been obvious to a PHOSITA to employ Alpert’s known shortest path algorithm technique in Ruehl’s routing aware floorplanning system to determine the geometric route between Ruehl’s source and destination pins. Doing so would predictably provide an optimized legal route between Ruehl’s specified source and destination through the available routing space while avoiding blocked space, consistent with Ruehl’s stated routed and placement objectives (Ruehl: 9:20-38, 14:34-39, 17:5-25, 20:45-53).
Claims 2-4 are rejected under 35 U.S.C. 103 as being unpatentable over Ruehl in view of Alpert and in further view of US Pub. No. 20180107778 to Muuss (“Muuss”).
Ruehl in view of Alpert does not teach the limitations of claim 2.
Muuss is directed to global routing in IC design (¶ 0001). Muuss teaches representing an IC physical design using a routing grid that includes the physical locations of nets and pins, dividing that routing grid into tiles of substantially equal or similar area, and representing the tiles as vertices connected to adjacent tiles for global routing (¶ 0014-0017, 0022).
It would have been obvious to a PHOSITA to implement the routing space representation of Ruehl and Alper using Muuss’s tiled routing grid representation because Muuss teaches such tiles are used by the global router to represent physical routing space and generate routes between pins. Such an implementation amount to use of a known IC routing spatial representation for its known purpose of facilitating route generation through the physical design.
As to claim 3, the method of claim 2, wherein the unit area is set by an external control (Muuss: ¶ 0016-0018. Muuss teaches the size of the substantially equal or similar routing grid tiles may be selected by a user before running the global router thereby teaching the unit area is set by an external control.).
As to claim 4, the method of claim 2, wherein the distinguishing of the first region from the second region comprises, in the array, representing the components of the array corresponding to the first region and the components of the array corresponding to the second region with different characters (Alpert: 3:1-18. Alpert assigns respective values of 0 and 1, thereby teaching representation of the two routing regions with different characters.).
Claims 5-7, 9, and 14-16 are rejected under 35 U.S.C. 103 as being unpatentable over Ruehl in view of Alpert and in further view of US Patent No. 10,402,533 to Reece et al. (“Reece”).
Ruehl in view of Alpert does not expressly teach the limitations of claims 5 and 14, which depend from claims 1 and 11, respectively.
As to claims 5 and 14, Reece teaches imposing a maximum routed distance constraint on a connection between nodes and iteratively determing whether additional candidate points should be considered based on satisfaction of design/performance constraints (6:54-61, 8:62-65, 9:1-5, 10:-24-26). Thus, Reece teaches evaluating a routed path distance relative to a reference distance and using the result of that evaluation to determine whether further searching is necessary.
It would have been obvious to a PHOSITA to apply Reece’s maximum routed distance constraint and iterative search technique to the shortest path routing of Ruehl as modified by Alpert. Comparing that shortest path distance with Reece’s maximum routed distance would determine whether the existing route satisfies the desired routing distance constraint, and, if not, whether additional searching should be performed. The motivation would be to reduce routing resources and computational effort while obtaining an acceptable circuit layout.
As to claims 6 and 15, the method of claim 5, wherein the determining of whether to search again comprises, in response to the distance of the shortest path being greater than the reference distance, receiving position data on at least one new point replacing at least one of the first point and the second point and searching for a new shortest path between two points (Alpert: 1:50-65, 2:1-6, 3:1-18, 54-58. Reece: 7:34-59, 8:39-60. Applying Reece’s maximum routed distance constraint to Alpert’s shortest path distance would make the shortest path exceeding that maximum a failed constraint. Reece teaches selecting another candidate position when a candidate fails constraints, and applying Alpert again to the changed endpoint pair would determine the new shortest path.).
As to claim 7 and similarly recited claim 16, the method of claim 5, wherein the positioning of the components of the layout comprises, in response to the distance of the shortest path being less than or equal to the reference distance connecting cells along the shortest path by arranging the cells to correspond to the first point and the second point (Alpert: 1:50-65, 2:1-6, 3:1-18, 54-58. Reece: 5:8-16, 6:53-60, 7:45-59, 8:39-60. Applying Reece’s maximum routed distance constraint to the shortest path distance determined by Alpert such that, when the shortest path distance is less than or equal to the maximum routed distance, the corresponding endpoint positions are accepted as the cell placement positions and the cells are connected along the shortest path determined by Alpert.).
As to claim 9, the method of claim 5, wherein the reference distance is set by an external control (Reece: 6:53-60. Reece teaches the maximum routed distance constraint may be specified by a user.).
Claims 8 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over the combination of Ruehl, Alpert and Reece and in further view of US Patent No. 6,006,024 to Guruswamy et al. (“Guruswamy”).
The combination of Ruehl, Alpert, and Reece does not teach the limitation of claim 8 or the latter alternative recited in claim 16.
Gururswamy is directed to the design and manufacture of IC and producing optimized cell structure (2:5-8). Guruswamy teaches automatically setting the physical positions of the I/O ports included in standard cells by selecting or moving the ports to particular grid locations based on routing/wirelength considerations, thereby improving the interconnection between the cells (41:16-33, 42:16-23, 45:14-31.). Under BRI, Guruswamy’s I/O ports of standard cells correspond to the claimed “ports included in the cells”, and selection or movement of those ports to particular grid locations teaches setting positions of the ports. The claim does not require a particular type of port or a particular mechanism for assigning the port coordinates.
It would have been obvious to a PHOSITA to modify the routing aware layout method of Ruehl, as modified by Alpert and Reece, to set the positions of cell ports as taught by Guruswamy. Alpert determines the shortest path between the first and second endpoint positions, and Reece provides a maximum routed distance constraint for determining whether the resulting routing distance is acceptable. Once the shortest path distance is less than or equal to that maximum distance, one of ordinary skill would have had reason to implement the accepted connection by positioning the ports of the respective cell at locations corresponding to the route endpoints, using Guruswamy’s known technique of selecting cell port positions to minimize interconnection wire length and facilitate routability.
Claims 10 and 17 are rejected under 35 U.S.C. 103 as being unpatentable over the combination of Ruehl and Alpert in view of US Pub. No. 2022/0121803 to Seong et al. (“Seong”).
The combination of Ruehl and Alpert does not teach the limitations of claim 10 or 17.
Seong is directed to path routing technology (¶ 0001). Seong teaches routing between specified start and end locations of a semiconductor substrate using a connectivity graph and finding a path between nodes of the connectivity graph using an A* algorithm, with routing connections selected according to routing cost (¶ 0046, 0047, 0071, 0072, 0075-0079).
It would have been obvious to a PHOSITA to perform the shortest path search of Ruehl as modified by Alpert using Seong’s A* algorithm. Alpert already formulates IC routing as a shortest path problem using Dijstra’s algorithm to determine the shortest path. Substituting Seong’s A* search for Alpert’s Djkstra search would have amounted to using a known alternative graph search technique for the same purpose of determining an optimized routing path between specified endpoints, with predictable results.
Claim 12 are rejected under 35 U.S.C. 103 as being unpatentable over Ruehl in view of Alpert and in further view of US Patent No. 7,685,545 to Chapman et al. (“Chapman”).
The combination of Ruehl and Alpert does not teach the limitations of claim 12.
Chapman teaches receiving and using both DEF and LEF data as inputs to an IC place-and-route process, wherein DEF represents the IC floorplan and includes die-area, region, blockage, and routing information, and LEF describes physical cell layouts, routing rules, pins, and routing blockages (14:32-38, 45:60-67, 47:3-10, 48:23-35).
It would have been obvious to a PHOSITA to provide the physical IC information used by the routing aware physical design method of Ruehl as modified by Alpert in the DEF and LEF formats taught by Chapman. The motivation is merely use of known standardized IC physical design input formats for their established purpose of communicating floorplan, cell, pin, blockage, routing layer, and related physical information to a place-and-route tool, with predictable results.
Claim 13 is rejected under 35 U.S.C. 103 as being unpatentable over Ruehl in view of Alpert and in further view of US Patent No. 8,826,215 to Li et al. (“Li”).
The combination of Ruehl and Alpert teach representing the components of the array corresponding to the first and second region with different characters ((Alpert: 3:1-18. Alpert assigns respective values of 0 and 1, thereby teaching representation of the two routing regions with different characters.), however, does not expressly teach the other limitations recited in claim 13.
Li teaches partitioning an IC layout into discrete rectangular spatial units and representing the layout as an array of tiles, each tile constituting a spatial component of that array for global routing (clam 1, Abstract, Fig. 1).
It would have been obvious to a PHOSITA to implement the routing space representation of Ruehl and Alpert using the tiled array representation taught by Li. Using such an array of tiles representation would have been a known and predictable way to discretize the physical routing space so that routing availability and routing operations could be associated with respective spatial units.
Claim 18 is rejected under 35 U.S.C. 103 as being unpatentable over Alpert in view Chapman and in further view of Li.
As to independent claim 18, a system (Fig. 2) configured to design a semiconductor chip (5:1-5), the system (Fig. 2) comprising: a processor (Fig. 2: 202); and a memory (Fig. 2: 204) connected to the processor (Fig. 2: BUS, 202, 204, 208) and storing machine-readable commands that, when executed by the processor (5:1-18, 6:22-35,50-65), cause the system to perform a wiring path search operation for designing the semiconductor chip (5:1-18, 6:22-35,50-65), wherein, by using the commands, the processor is configured to, receive physical information (3:1-18. Alpert teaches using physical information concerning positions and physical obstacles of an IC when performing routing.), based on the physical information, distinguish a first region, where routing is possible, from a second region, where the routing is impossible in the semiconductor chip (3:11-18. Alpert teaches distinguishing physical IC routing locations based on routing availability by assigning one state to locations overlapping physical obstacles and another state to locations not overlapping physical obstacles.), generate a spatial representation of the IC (3:1-10. Alpert teaches generating/using a spatial representation of the physical IC as a Cartesian grid of physical IC positions, but does not expressly teach the spatial representation as an array having a size corresponding to the semiconductor chip.), represent a first group corresponding to the first region and a second group corresponding to the second region (3:11-18. Alpert teaches separately representing routable/non-obstacle and non-routable/obstacle physical IC positions using respective values of 1 and 0. ), receive position information about a first point and a second point, which are specified (Alpert: claim 1 and 19. Alpert receives specified source and sink locations defining the two endpoint positions used for determining the routing path.), and search for a shortest path between the first point and the second point in the first (1:50-67, 2:1-5, 3:1-18, claims 1 and 19. Alpert teaches searching for a shortest routing path between specified physical IC endpoints using a grid based shortest path algorithm while accounting for physical obstacles that constrain routing choices.).
Thus, Alpert teach the processor/memory system, physical IC routing information, differentiation of obstacle and non-obstacle routing locations, specified source and sink positions, and shortest path searching.
Alpert, however, does not expressly teach: receiving the physical information specifically as DEF data and LEF data, or generating an array having a size corresponding to the semiconductor chip and representing first and second component groups of that array corresponding respectively to the routable and non-routable regions.
Chapman teaches receiving and using DEF and LEF physical design data as inputs to an IC place-and-route process, wherein DEF supplies floorplan, die-area, region, blockage, and routing information and LEF supplies physical layout, pin, routing layer, and blockage information (14:32-38, 45:60-67, 47-3-10, 48-23-35.).
Li teaches dividing the physical layout area of an IC in to an array of spatial tiles, each tile representing a corresponding portion of the IC layout and collectively covering the IC design area for routing analysis (Abstract, claim 1).
It would have been obvious to a PHOSITA to modify Alpert’s shortest path routing system to receive its physical design information from the DEF and LEF data taught by Chapman because it is merely the use of known standardized IC physical design input formats for their established purpose of communicating floorplan, cell, pin, blockage, routing layer, and related physical information to a place-and-route tool, with predictable results.
Furthermore, it would have been obvious to a PHOSITA to represent Alpert’s physical routing space using the array of tiles representation taught by Li because using such an array of tiles representation would have been a known and predictable way to discretize the physical routing space so that routing availability and routing operations could be associated with respective spatial units.
Claim 19 rejected under 35 U.S.C. 103 as being unpatentable over the combination of Alpert, Chapman, and Li and in further view of Reece.
The combination of Alpert, Chapman, and Li does not teach all the limitations of claim 19.
Reece teaches applying a maximum routed distance constraint to circuit node placement, rejecting a candidate point that fails applicable design constraints, selecting another physical point as a replacement candidate, and performing rerouting based on the newly selected node position (6:54-60, 7:33-57, 8:35-60, claim 17.).
It would have been obvious to a PHOSITA to apply Reece’s maximum routed distance constraint and replacement point technique to the shortest path routing system of Alpert as modified by Chapman and Li. Alpert determines a shortest path between specified endpoints, while Reece teaches imposing a maximum routed distance constraint, rejecting a candidate position that fails the constraint, selecting another candidate point, and rerouting. Thus, when Alpert’s short path distance exceeds Reece’s maximum routed distance, one of ordinary skill would have been led to replace the corresponding endpoint with another candidate point and perform Alpert’s shortest path search again using the updated endpoints. This would predicably yield a new shortest path satisfying the desired routing distance requirement.
Claim 20 is rejected under 35 U.S.C. 103 as being unpatentable over the combination of Alpert, Chapman, and Li and in further view of Reece.
The combination of Alpert, Chapman, and Li does not teach the limitations of claim 20.
Reece teaches applying a maximum routed distance constraint to circuit routing, selecting physical positions for cells/nodes, updating the layout with the selected positions, and, after positioning the nodes, setting routing lines that connect the positioned nodes (3:17-27, 4:28-38, 6:55-60, 7:1-3, 45-59).
It would have been obvious to a PHOSITA to apply Reece’s maximum routed distance constraint and cell placement technique to the shortest path routing system of Alpert as modified by Chapman and Li. Alpert already determines a shortest path between specified first and second points. Reece teaches imposing a maximum routed distance constraint, selecting physical cell/node positions that satisfy applicable design constraints, and thereafter setting routing lines connecting the positioned nodes.
Accordingly, when the distance of Alpert’s shortest path is less than or equal to Reece’s maximum routed distance, the routed distance constraint is satisfied, and one of ordinary skill would have been led to use the corresponding endpoint positions as accepted cell/node placement positions and connect the positioned cells along Alpert’s shortest path. This would predictably provide a cell placement and connection satisfying the desired maximum routing distance constraint.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Examiner SURESH MEMULA whose telephone number is (571)272-8046, and any inquiry for a formal Applicant initiated interview must be requested via a PTOL-413A form and faxed to the Examiner's personal fax phone number: (571) 273-8046. Furthermore, Applicant is invited to contact the Examiner via email (suresh.memula@uspto.gov) on the condition the communication is pursuant to and in accordance with MPEP §502.03 and §713.01. The Examiner can normally be reached Monday-Thursday: 9am-6pm. If attempts to reach the Examiner by telephone are unsuccessful, the Examiner’s supervisor, Jack Chiang, can be reached on 571-272-7483. The fax phone number for the organization where this application or proceeding is assigned (i.e., central fax phone number) is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/SURESH MEMULA/Primary Examiner, Art Unit 2851
Prosecution Insights