METHOD AND APPARATUS FOR IDENTIFYING CONNECTIONS BETWEEN CONFIGURABLE NODES IN A CONFIGURABLE INTEGRATED CIRCUIT

• US 20070245287A1
• Filed: 06/30/2004
• Published: 10/18/2007
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Teig, Steven, Rohe, Andre
• Granted Patent: US 7,284,222 B1
• Time in Patent Office: Days
• US Class Current: 716/134
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G06F 30/3947 global
• CPC Class Codes: H03K 19/17708 using an AND matrix followed by an OR matrix, i.e. programmable logic arrays

Abstract

Some embodiments provide a method that defines a set of connections that connect the nodes in a configurable node array. The method identifies different sets of connections for connecting a set of the nodes. For each identified set of connections, the method computes a metric score that quantifies a quality of the identified set of connections. The method then selects one of the identified sets of connections to connect the configurable nodes in the array.

Claims

1. A method of designing a configurable node array comprising a plurality of configurable nodes, the method comprising:

a) identifying different sets of direct connections between configurable nodes;

b) computing a cost for each of a plurality of the identified direct connections; and

c) selecting a set of direct connections based on the computed costs, wherein none of the direct connections in the identified sets of direct connections comprise an intervening interconnect circuit.

9. The method of claim 1, wherein the identifying and the computing are part of an optimization process that tries to identify an optimal set of direct connections for connecting the configurable nodes in the configurable node array.

10. The method of claim 9, wherein the optimal set of direct connections defines a dispersed connection graph for connecting the configurable nodes.

11. The method of claim 10, wherein the dispersed connection graph is a topological graph.

12. The method of claim 1, wherein the configurable node array comprises at least fifty configurable nodes arranged along a plurality of rows and a plurality of columns.

13. The method of claim 1, wherein the identified set of direct connections defines a set of direct connections for each configurable node in the configurable node array.

14. The method of claim 1, wherein the identified set of direct connections comprises different sub-sets of direct connections, wherein each sub-set specifies a plurality of direct connections for each of a plurality of configurable nodes.

15. The method of claim 14, wherein the configurable nodes that comprise the same sub-set of direct connections comprise a similar structure.

21. The method of claim 1 further comprising defining at least one direct connection by using a set of wire segments.

22. The method of claim 21, wherein said defining at least one direct connection also uses at least one via.

23. The method of claim 1 further comprising defining at least one direct connection by using at least one via.

24. The method of claim 1, wherein no direct connection comprises any intervening circuit.

25. The method of claim 1, wherein each of at least two direct connections comprises a buffer circuit.

26. The method of claim 1, wherein no direct connection comprises any intervening circuits other than intervening buffer circuits.

2. For a configurable node array comprising a plurality of configurable nodes, a method of defining connections for connecting the plurality of configurable nodes in the configurable node array, the method comprising:

a) identifying different sets of connections between configurable nodes;

b) computing a cost for each of a plurality of the identified sets of connections; and

c) selecting a set of connections between the configurable nodes based at least partly on the computed costs, wherein the cost of each identified set of connections is based at least partly on how many configurable nodes would be reachable under a specified set of conditions from a set of configurable nodes.

4. The method of claim 2, wherein the set of configurable nodes comprises all the configurable nodes of the configurable node array.

5. The method of claim 2, wherein the set of configurable nodes does not comprise all the configurable nodes of the configurable node array.

6. The method of claim 5, wherein the set of configurable nodes comprises a configurable node at a center of the configurable node array.

27. The method of claim 2, wherein the specified set of conditions comprises a maximum number of connections.

28. The method of claim 2, wherein the specified set of conditions comprises a maximum connection length.

29. The method of claim 2, wherein the specified set of conditions comprises a maximum connection length and a maximum number of connections.

3. (canceled)

7. (canceled)

8. (canceled)

16. A method of defining a set of connections for connecting a plurality of configurable circuits of an integrated circuit (IC) , the method comprising:

a) iteratively

identifying at least one direct connection for connecting at least two configurable circuits;

computing a metric score that quantifies a quality of the identified direct connection; and

b) based on the computed metric scores, selecting a plurality of direct connections for connecting the configurable circuits in the IC, wherein a plurality of the selected direct connections do not comprise an intervening interconnect circuit.

17. The method of claim 16, wherein the metric scores quantify a reachability criterion.

18. The method of claim 16, wherein the plurality of configurable circuits comprises at least three hundred configurable circuits arranged along a plurality of rows and a plurality of columns.

19. The method of claim 16, wherein the configurable circuits comprise the same structure.

20. The method of claim 19, wherein the configurable circuits comprise the same circuit elements and the same wiring between a set of elements.

30. A method of designing an integrated circuit (IC) comprising an arrangement of configurable circuits, the method comprising:

a) performing an optimization process to examine a plurality of direct connections for connecting the configurable circuits; and

b) defining at least two direct connections for connecting the configurable circuits based at least partly on the examination during the optimization process;

wherein said defining does not entail configuring said configurable circuits of said IC.

33. The method of claim 30, wherein at least two direct connections do not comprise intervening configurable circuits.

34. The method of claim 30, wherein at least two direct connections do not comprise intervening interconnect circuits.

35. The method of claim 30, wherein at least two direct connections do not comprise intervening interconnect circuits but do comprise intervening buffer circuits.

36. The method of claim 30, wherein at least two direct connections do not comprise intervening circuits.

38. The method of claim 30, wherein said optimization process comprises:

a) generating a plurality of direct connection schemes; and

b) evaluating each of said plurality of direct connection schemes to determine its quality.

39. The method of claim 38, wherein evaluating a direct connection scheme comprises determining how many circuits can be reached from a given circuit through a given number of direct connections of the direct connection scheme.

40. The method of claim 30, wherein said performing an optimization process identifies a wiring architecture for the IC that increases the interconnectivity between said configurable circuits in the arrangement.

31. The method of 30, wherein said performing an optimization process comprises computing metric costs to evaluate different sets of direct connections for connecting the configurable circuits of said IC.

32. The method of claim 31, wherein computing a metric cost comprises determining how many configurable circuits can be reached within a given number of hops, wherein a hop comprises passing through one direct connection.

37. The method of 30, wherein said defining the direct connections comprises defining a layout of wire segments to implement the direct connections.

41. A method of designing an integrated circuit (IC) comprising an arrangement of configurable circuits, the method comprising:

a) performing an optimization process to examine a plurality of direct connections for connecting the configurable circuits; and

b) specifying at least two direct connections for connecting the configurable circuits based at least partly on the examination performed during the optimization process;

wherein a plurality of the specified direct connections do not comprise an intervening interconnect circuit.

42. The method of 41, wherein none of the specified direct connections comprise an intervening interconnect circuit.

43. The method of 41, wherein a plurality of the specified direct connections do not comprise any intervening circuit.

44. The method of 41, wherein a plurality of the specified direct connections comprise an intervening buffer circuit.