# US 10,503,861 B1 · Placing and routing an interface portion and a main portion of a circuit design > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,861 B1 - Document ID: US10503861B1 - Status: Granted - Kind: B1 - Application number: 15/984,870 - Filed: 2018-05-21 - Granted: 2019-12-10 - Earliest claimed: 2018-05-21 - Assignees: Xilinx, Inc. - Applicants: Xilinx, Inc. - Inventors: Dinesh D. Gaitonde; Henri Fraisse; Sachin K. Bhutada; Aashish Tripathi; Ramakrishna K. Tanikella - Web page: https://patentgrep.com/patent/US10503861B1 ## CPC - G06F 30/394: Routing (G06F30/396 takes precedence) - G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist - G06F 30/34: for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] - G06F 30/343: Logical level - G06F 30/347: Physical level, e.g. placement or routing - G06F 30/392: Floor-planning or layout, e.g. partitioning or placement - G06F 2119/12: Timing analysis or timing optimisation - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A netlist of a circuit design includes an interface portion and a main portion. The interface portion is decomposed into multiple levels. Each level specifies connections between a respective first set of circuit elements and a respective second set of circuit elements. The second set of circuit elements in each level, except a last level, includes the first set of circuit elements in a next level. The first set of circuit elements identified in a first level of the multiple levels have fixed locations. The second set of circuit elements in the multiple levels is placed-and-routed. The placing-and-routing of the second set of circuit elements in one level is completed before commencing placing-and-routing of the second set of circuit elements in the next level. The main portion is placed-and-routed after placing-and-routing the second set of circuit elements in the multiple levels. ## Claims ### Claim 1 A method, comprising: inputting a netlist of a circuit design to a programmed computer, the netlist including an interface portion and a main portion; decomposing, by the computer, the interface portion into multiple levels, wherein: each level specifies connections between a respective first set of circuit elements and a respective second set of circuit elements, the respective second set of circuit elements in each level, except a last level, includes the respective first set of circuit elements in a next level, and the respective first set of circuit elements identified in a first level of the multiple levels have fixed locations; placing-and-routing, by the computer, the respective second set of circuit elements in the multiple levels, including completing the placing-and-routing of the respective second set of circuit elements in one level before commencing placing-and-routing of the respective second set of circuit elements in the next level; and placing-and-routing, by the computer, the main portion after placing-and-routing the respective second set of circuit elements in the multiple levels. ### Claim 2 (depends on 1) The method of claim 1, wherein the respective second set of circuit elements in each level includes circuit elements of the circuit design that are not directly connected to one another. ### Claim 3 (depends on 2) The method of claim 2, wherein the placing-and-routing the respective second set of circuit elements includes placing-and-routing a single circuit element. ### Claim 4 (depends on 1) The method of claim 1, wherein the placing-and-routing the respective second set of circuit elements includes placing-and-routing to only the respective second set of circuit elements. ### Claim 5 (depends on 1) The method of claim 1, wherein the placing-and-routing the respective second set of circuit elements includes: determining actual timing of the respective first set of circuit elements based on placement of and routing to the respective first set of circuit elements; and placing-and-routing the respective second set of circuit elements based on the actual timing of the respective first set of circuit elements. ### Claim 6 (depends on 5) The method of claim 5, wherein: the determining the actual timing includes: determining respective actual delays to the respective first set of circuit elements based on placement of and routing to the respective first set of circuit elements, and for each connection from each circuit element of the first set to a circuit element of the second set, determining a respective timing constraint based on the respective actual delay; and the placing-and-routing each circuit element of the respective second set is based on the respective timing constraint of each connection to the circuit element. ### Claim 7 (depends on 1) The method of claim 1, further comprising identifying, by the computer, the interface portion of the netlist by the computer based on circuit elements of the circuit design being associated with a communication protocol. ### Claim 8 (depends on 1) The method of claim 1, further comprising identifying, by the computer, the interface portion of the netlist by the computer based on a timing requirement of a first portion of the netlist being more strict than a timing requirement of a second portion of the netlist. ### Claim 9 (depends on 1) The method of claim 1, wherein decomposing the interface portion includes: generating a graphical representation of the netlist, the graphical representation including a plurality of vertices corresponding to the circuit elements of the interface portion and a plurality of edges that connect the plurality of vertices and correspond to pin-to-pin connections between the circuit elements of the interface portion; assigning first vertices corresponding to circuit elements having fixed locations and vertices corresponding to the circuit elements of the interface portion having edges connected to the first level; and segmenting the plurality of vertices and plurality of edges other than vertices and edges assigned to the first level into respective bipartite graphs. ### Claim 10 (depends on 1) The method of claim 1, wherein the placing-and-routing the respective second set of circuit elements includes executing a Boolean satisfiability (SAT) based algorithm or an integer linear programming (ILP) based algorithm. ### Claim 11 (depends on 1) The method of claim 1, further comprising: generating, by the computer, configuration data from placed-and-routed circuit elements of the interface portion and placed-and-routed circuit elements of the main portion; and configuring, by the computer, a programmable integrated circuit (IC) with the configuration data. ### Claim 12 A system, comprising: a computer system including: a processor; and a memory configured with instructions that when executed by the processor cause the processor to perform operations including: decomposing an interface portion of a circuit design into multiple levels, wherein: each level specifies connections between a respective first set of circuit elements and a respective second set of circuit elements, the respective second set of circuit elements in each level, except a last level, includes the respective first set of circuit elements in a next level, and the respective first set of circuit elements identified in a first level of the multiple levels have fixed locations; placing-and-routing the respective second set of circuit elements in the multiple levels by the computer, including completing the placing-and-routing of the respective second set of circuit elements in one level before commencing placing-and-routing of the respective second set of circuit elements in the next level; and placing-and-routing a main portion of the circuit design by the computer after placing-and-routing the respective second set of circuit elements in the multiple levels. ### Claim 13 (depends on 12) The system of claim 12, wherein the respective second set of circuit elements in each level includes circuit elements of the circuit design that are not directly connected to one another. ### Claim 14 (depends on 12) The system of claim 12, wherein the placing-and-routing the respective second set of circuit elements includes placing-and-routing a single circuit element. ### Claim 15 (depends on 12) The system of claim 12, wherein the placing-and-routing the respective second set of circuit elements includes placing-and-routing to only the respective second set of circuit elements. ### Claim 16 (depends on 12) The system of claim 12, wherein the placing-and-routing the respective second set of circuit elements includes: determining respective actual delays to the respective first set of circuit elements based on placement of and routing to the respective first set of circuit elements; for each connection from each circuit element of the first set to a circuit element of the second set, determining a respective timing constraint based on the respective actual delay; and placing-and-routing each circuit element of the respective second set of circuit elements based on the respective timing constraint of each connection to the circuit element. ### Claim 17 (depends on 12) The system of claim 12, wherein the memory is configured with instructions that when executed by the processor cause the processor to perform operations including: identifying the interface portion of the netlist by the computer based on circuit elements of the circuit design being associated with a communication protocol. ### Claim 18 (depends on 12) The system of claim 12, wherein the memory is configured with instructions that when executed by the processor cause the processor to perform operations including: identifying the interface portion of the netlist by the computer based on a timing requirement of a first portion of the netlist being more strict than a timing requirement of a second portion of the netlist. ### Claim 19 (depends on 12) The system of claim 12, wherein decomposing the interface portion includes: generating a graphical representation of the netlist, the graphical representation including a plurality of vertices corresponding to the circuit elements of the interface portion and a plurality of edges that connect the plurality of vertices and correspond to pin-to-pin connections between the circuit elements of the interface portion; assigning first vertices corresponding to circuit elements having fixed locations and vertices corresponding to the circuit elements of the interface portion having edges connected to the first level; and segmenting the plurality of vertices and plurality of edges other than vertices and edges assigned to the first level into respective bipartite graphs. ### Claim 20 (depends on 12) The system of claim 12, wherein the memory is configured with instructions that when executed by the processor cause the processor to perform operations including: generating configuration data from placed-and-routed circuit elements of the interface portion and placed-and-routed circuit elements of the main portion; and configuring a programmable integrated circuit (IC) with the configuration data.