# US 8,789,001 B1 · System and method for using fabric-graph flow to determine resource costs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,789,001 B1 - Document ID: US8789001B1 - Status: Granted - Kind: B1 - Application number: 13/831,144 - Filed: 2013-03-14 - Granted: 2014-07-22 - Earliest claimed: 2013-02-20 - Assignees: Tabula, Inc. - Applicants: Eric A. Sather; Steven Teig - Inventors: Eric A. Sather; Steven Teig - Web page: https://patentgrep.com/patent/US8789001B1 ## CPC - G06F 30/347: Physical level, e.g. placement or routing - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G06F 30/34: for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] - G06F 30/392: Floor-planning or layout, e.g. partitioning or placement - G06F 30/394: Routing (G06F30/396 takes precedence) - G06F 30/398: Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36) - G06F 9/00: Arrangements for program control, e.g. control units (program control for peripheral devices G06F13/10) - G06F 15/177: Initialisation or configuration control {(processor initialisation G06F9/4405)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system and method of determining paths of components when placing and routing configurable circuits. The method identifies a probabilistic data flow through multiple components using a simplified connection matrix. The simplified connection matrix is used to determine a probabilistic data flow through the components without data flowing from any component to itself. The probabilistic data flow is used to determine a probabilistic data flow through the components with some of the components having data flowing from themselves back to themselves. The probabilistic data flow through each component and the number of inputs of the components are used to determine a cost for each component. The cost of a path through the circuit is determined from the costs of the individual components in the path. The costs of the components are used to determine which path of components to use. ## Claims ### Claim 1 A method of defining a configuration for an integrated circuit (IC) with configurable circuits, the method comprising: determining a probabilistic flow of data through each of a plurality of components of the IC; identifying a first path of components and a second path of components in the IC; based on the probabilistic flow of data through the each component of the first path, identifying a cost of the first path; based on the probabilistic flow of data through each component of the second path, identifying a cost of the second path; and based on the identified costs of each of the paths, selecting, using a computer, one of the paths for the configuration. ### Claim 2 (depends on 1) The method of claim 1, wherein determining the probabilistic flow of data through a component of the IC comprises calculating a probabilistic flow of data through a particular input of the component, wherein the calculated probabilistic flow of data through the particular input of the component is an average flow of data through each of a set of inputs of the component. ### Claim 3 (depends on 2) The method of claim 2, wherein the average flow of data through each input of the set of inputs of the component is calculated based on a total number of physical inputs of the component and an additional temporal input of the component. ### Claim 4 (depends on 1) The method of claim 1 further comprising computing a first probabilistic flow value through a component based on physical inputs of the component and computing a second probabilistic flow value through the component based on at least one physical input of the component and at least one temporal input of the component. ### Claim 5 (depends on 4) The method of claim 4, wherein a component has a temporal input when the component is capable of storing data for a variable number of clock cycles. ### Claim 6 (depends on 1) The method of claim 1, wherein the paths use different components in different clock cycles of a plurality of clock cycles. ### Claim 7 (depends on 6) The method of claim 6, wherein the plurality of clock cycles are a plurality of sub-cycles of a longer user design clock cycle. ### Claim 8 (depends on 1) The method of claim 1, wherein the probabilistic flow of data through each of the plurality of components of the IC is calculated backward in run time and a probabilistic flow of data between components of a path is calculated from an input of one component in the path to an output of a previous component in the path. ### Claim 9 (depends on 1) The method of claim 1, wherein a component with only one input has zero cost. ### Claim 10 (depends on 9) The method of claim 9, wherein a component with only one physical input and a temporal input has a non-zero cost. ### Claim 11 A non-transitory machine readable medium storing a program for defining a configuration for an integrated circuit (IC) with configurable circuits, the program comprising sets of instructions for: determining a probabilistic flow of data through each of a plurality of components of the IC; determining a cost for each of the plurality of components based on the probabilistic flow of data through the plurality of components; identifying, based on said costs, a cost of a first path of the components; identifying, based on said costs, a cost of a second path of the components; and selecting, based on the identified costs of each of the paths, one of the first path and the second path for the configuration. ### Claim 12 (depends on 11) The non-transitory machine readable medium of claim 11, determining the probabilistic flow of data through a component of the IC comprises calculating a probabilistic flow of data through a particular input of the component, wherein the calculated probabilistic flow of data through the particular input of the component is an average flow of data through a set of inputs of the component. ### Claim 13 (depends on 12) The non-transitory machine readable medium of claim 12, wherein the average flow of data through the set of inputs of the component is calculated based on a total number of physical inputs of the component and a total number of temporal inputs of the component. ### Claim 14 (depends on 11) The non-transitory machine readable medium of claim 11, wherein the program further comprises sets of instructions for computing a first probabilistic flow value through at least one component based on a total number of physical inputs of the component and computing a second flow through the component based on the total number of physical inputs of the component and a total number of temporal inputs of the component. ### Claim 15 (depends on 14) The non-transitory machine readable medium of claim 14, wherein a component has a temporal input when the component is capable of storing data for a variable number of clock cycles. ### Claim 16 (depends on 11) The non-transitory machine readable medium of claim 11, wherein the probabilistic flow of data through each of a plurality of components of the IC is calculated backward in run time and a probabilistic flow of data between components of a path is calculated from an input of one component in the path to an output of a previous component in the path. ### Claim 17 (depends on 11) The non-transitory machine readable medium of claim 11, wherein a component with only one input has zero cost. ### Claim 18 (depends on 17) The non-transitory machine readable medium of claim 17, wherein a component with only one physical input and a temporal input has a non-zero cost. ### Claim 19 A method of designing a configuration for an integrated circuit (IC) with configurable circuits, the method comprising: determining a set of relationships between a plurality of components of the IC; identifying a steady state probabilistic flow of data through each of the plurality of components based on the determined set of relationships; identifying a cost for each component based on the identified steady state probabilistic flow of data through each component; and defining, a set of configurations for the IC based on the identified costs. ### Claim 20 (depends on 19) The method of claim 19, wherein the set of relationships between the plurality of components comprises a connection matrix for the plurality of components. ### Claim 21 (depends on 20) The method of claim 20 further comprising simplifying the connection matrix. ### Claim 22 (depends on 20) The method of claim 20 further comprising adjusting the connection matrix to simulate connections to re-circulate probabilistic flow that would leave the plurality of components without said adjustment.