System and Method for Using Fabric-Graph Flow to Determine Resource Costs

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.

What is claimed is: 
     
         1 . A method of designing a configuration for an 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 and second path of components in the IC;   based on the probabilistic flow through the 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 cost of the paths, selecting one of the paths for the configuration.   
     
     
         2 . The method of  claim 1 , wherein the calculated probabilistic flow of data through an input of a component is an average flow of data through each of a set of inputs of the component. 
     
     
         3 . The method of  claim 2 , wherein the average flow of data through each input of at least one component is calculated based on a total number of physical inputs of the component and an additional temporal input of the component. 
     
     
         4 . 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. 
     
     
         5 . 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. 
     
     
         6 . The method of  claim 1 , wherein the paths use different components in a plurality of clock cycles. 
     
     
         7 . The method of  claim 6 , wherein the plurality of clock cycles are a plurality of sub-cycles of a longer user design clock cycle. 
     
     
         8 . The method of  claim 1 , wherein the probabilistic flow is calculated backward in run time and the probabilistic flow of data between components of a path is calculated from an input of one component to an output of the previous component in the path. 
     
     
         9 . The method of  claim 1 , wherein a component with only one input has zero cost. 
     
     
         10 . The method of  claim 9 , wherein a component with one physical input and a temporal input has a non-zero cost. 
     
     
         11 . A non-transitory machine readable medium storing a program for designing a configuration for an 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 components;   identifying, based on said costs, a cost of a first path of components;   identifying, based on said costs, a cost of a second path of components; and   selecting, based on the cost of the paths, the first path for the configuration.   
     
     
         12 . The non-transitory machine readable medium of  claim 11 , wherein the determined probabilistic flow of data through an input of a component is an average flow of data through a set of inputs of the component. 
     
     
         13 . The non-transitory machine readable medium of  claim 12 , wherein the average flow of data through each input of at least one component is calculated based on a total number of physical inputs of the component and a total number of temporal inputs of the component. 
     
     
         14 . The non-transitory machine readable medium of  claim 11 , wherein the program further comprises sets of instructions for computing a first flow 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. 
     
     
         15 . 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. 
     
     
         16 . The non-transitory machine readable medium of  claim 11 , wherein the flow is calculated backward in run time and the flow of data between components of a path is calculated from an input of one component to an output of the previous component in the path. 
     
     
         17 . The non-transitory machine readable medium of  claim 11 , wherein a component with only one input has zero cost. 
     
     
         18 . The non-transitory machine readable medium of  claim 17 , wherein a component with one physical input and a temporal input has a non-zero cost. 
     
     
         19 . A method of designing a configuration for an 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 set of relationships;   identifying a cost for each component based on the steady state probabilistic flow of data through each component; and   defining a set of configurations for the IC based on the identified costs.   
     
     
         20 . The method of  claim 19 , wherein the set of relationships between inputs of the plurality of components comprises a connection matrix for the plurality of components. 
     
     
         21 . The method of  claim 20  further comprising simplifying the connection matrix. 
     
     
         22 . 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.