Method and apparatus for function decomposition

• US 7,610,566 B1
• Filed: 05/25/2007
• Issued: 10/27/2009
• Est. Priority Date: 03/22/2007
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Caldwell, Andrew, Teig, Steven
• Primary Examiner(s): Chiang, Jack
• Assistant Examiner(s): Memula, Suresh
• Application Number:
  US11/754,264
• Time in Patent Office: 886 Days
• Field of Search: 716/2, 716/6, 716/3
• US Class Current: 716/132
• CPC Class Codes: G06F 30/3323 using formal methods, e.g. equivalence checking or property checking
• CPC Class Codes: H03K 19/1733 Controllable logic circuits H03K19/177 takes precedence

Abstract

Some embodiments provide a method of performing circuit synthesis that receives a design that has a function with several inputs. The method identifies a set of early arriving inputs of the function and performs a function decomposition on the function based on one of the early arriving inputs. In some embodiments, the method estimates the number of circuits a signal has to travel through to reach each input of the function and selects a set of inputs with signals that travel through fewer numbers of circuits compared to signals of inputs that are not selected. In some embodiments in which the design has more than a particular number of inputs, the method recursively identifies early arriving signals and performs function decomposition until function decomposition results in a set of functions all of which with fewer than the particular number of inputs. In some embodiments, the function decomposition is Shannon decomposition.

Claims

1. A computer implemented method for defining configuration data sets that direct an integrated circuit (IC) to perform a function based on a plurality of inputs, the method comprising:

a) receiving, via a computer system, a design comprising said function;

b) identifying a set of early arriving inputs of said function;

c) performing a function decomposition on said function that (i) selects one of said early arriving inputs and (ii) defines at least a first sub-function and a second sub-function, each sub-function for producing a partial result of said function based on a set of the plurality of inputs that excludes said selected early arriving input;

d) for a particular logic circuit of the IC, defining (i) a first configuration data set for configuring said particular logic circuit to perform said first sub-function and (ii) a second configuration data set for configuring said particular logic circuit to perform said second sub-function, wherein said particular logic circuit comprises at least one less input than the plurality of inputs; and

e) defining said selected early arriving input as a signal of the IC for determining which of said first and second configuration data sets to supply to the particular circuit.

2. The method of claim 1, wherein the function decomposition is Shannon decomposition.

3. The method of claim 1, wherein performing the function decomposition to select one of said early arriving inputs comprises:

a) estimating a number of circuits a signal has to travel through to reach each input of the function; and

b) selecting a set of inputs with signals that travel through fewer numbers of circuits compared to signals of inputs that are not selected as the set of early arriving inputs.

4. The method of claim 3, wherein said circuits that a signal has to travel through are logic circuits.

5. The method of claim 1, wherein said design has more than a particular number of inputs, the method further comprising recursively performing operations a) to e) until the function decomposition results in a set of functions all of which having fewer than said particular number of inputs.

6. The method of claim 5, wherein the particular number of inputs is less than or equal to number of inputs of said particular logic circuit used to implement the circuit design.

7. The method of claim 5, wherein the particular number of inputs is at least three.

8. The method of claim 1, wherein the function decomposition is performed on said function based on an input that is an earliest arriving input.

9. The method of claim 1, wherein the function decomposition is performed on an input in the set of early arriving inputs that minimizes a cost function.

10. The method of claim 9, wherein the input that minimizes the cost function is determined by trial and error.

11. A computer readable storage medium storing a computer program for defining configuration data sets that direct an integrated circuit (IC) to perform a function based on a plurality of inputs, the computer program is executable by at least one processor, the computer program comprising:

a) a set of instructions for receiving a design comprising said function;

b) a set of instructions for identifying a set of early arriving inputs of said function;

c) a set of instructions for performing a function decomposition on said function that (i) selects one of said early arriving inputs and (ii) defines at least a first sub-function and a second sub-function, each sub-function for producing a partial result of said function based on a set of the plurality of inputs that excludes said selected early arriving input;

d) a set of instructions for defining (i) a first configuration data set for configuring a particular logic circuit of the IC to perform said first sub-function and (ii) a second configuration data set for configuring said particular logic circuit to perform said second sub-function, wherein said particular logic circuit comprises at least one less input than the plurality of inputs; and

e) a set of instructions for defining said selected early arriving input as a signal of the IC for determining which of said first and second configuration data sets to supply to the particular circuit.

12. The computer readable storage medium of claim 11, wherein the function decomposition is Shannon decomposition.

13. An integrated circuit (IC) comprising:

a) a plurality of configurable logic circuits for configurably performing a set of logic functions based on a plurality of configuration data sets, said plurality of configurable logic circuits comprising a particular configurable logic circuit with a particular number of inputs, wherein the particular configurable logic circuit produces a result of a particular function that requires more inputs than the particular number of inputs by performing a first sub-function and a second sub-function of the particular function, each sub-function producing a partial result of the particular function; and

b) a selector circuit for supplying configuration data sets to the particular configurable circuit, said configuration data sets for configuring the particular configurable circuit to perform the first sub-function and the second sub-function based on an early arriving input of said particular function that is not used as an input to neither of the first and second sub-functions.

14. The IC of claim 13, wherein the particular configurable circuit performs the first sub-function at a first context and performs the second sub-function at a second context.

15. The IC of claim 14, wherein the first and second contexts comprise different subcycles of a user clock cycle at which the IC operates.

16. The IC of claim 13, wherein the early arriving input of said function is a user signal that is generated within the IC during runtime operation of the IC.

17. A computer implemented method for defining configuration data sets that direct an integrated circuit (IC) to perform a function based on a plurality of inputs, the method comprising:

a) receiving, via a computer system, a design comprising said function;

b) identifying a particular early arriving input from said plurality of inputs of said function, wherein the particular early arriving input arrives before a specified time threshold;

c) performing a function decomposition on said function that defines at least a first sub-function and a second sub-function, each sub-function for producing a partial result of said function based on a set of the plurality of inputs that excludes said particular early arriving input; and

d) defining configuration data sets that are supplied to at least one particular logic circuit of the IC based on a value of said extracted early arriving input, said configuration data sets for configuring the particular logic circuit to perform at least one of said first and second sub-functions, wherein the particular logic circuit comprises at least one less input than said plurality of inputs.

18. The method of claim 17, wherein defining the configuration data sets to configure the particular logic circuit comprises configuring the particular logic circuit to perform said first and second sub-functions at different cycles of the IC.

19. The method of claim 18, wherein said cycles are different sub-cycles of a user defined clock cycle.

20. The method of claim 17, wherein defining the configuration data sets to configure the particular logic circuit comprises configuring a first logic circuit to perform the first sub-function and a second logic circuit to perform the second sub-function.