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

• US 20080059937A1
• Filed: 09/09/2007
• Published: 03/06/2008
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Andre Rohe, Steve Teig
• Inventors: Teig, Steven, Rohe, Andre
• Granted Patent: US 7,849,434 B2
• Time in Patent Office: Days
• US Class Current: 716/16
• 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-20. -20. (canceled)

21. A method of designing an integrated circuit (IC) comprising a plurality of configurable nodes, the method comprising:

a) identifying a plurality of different direct connection schemes for connections between configurable nodes;

b) computing a cost for each of said plurality of different direct connection schemes; and

c) selecting a first direct connection scheme for a first set of configurable nodes based on the computed costs.

22. The method of claim 21 further comprising selecting a second direct connection scheme for a second set of configurable nodes based on the computed costs.

23. The method of claim 22, wherein a computed cost for the IC is lower when both the first and second direct connection schemes are selected than when either is selected without the other.

24. The method of claim 21 further comprising selecting a plurality of direct connection schemes for a plurality of sets of configurable nodes based on the computed costs.

25. The method of claim 24, wherein a computed cost for the IC is lower when all of said selected plurality of direct connection schemes are selected than when any subset is selected without the others.

44. The method of claim 21, wherein a node comprises configurable logic circuits and configurable interconnect circuits.

26. A method of designing an integrated circuit (IC) comprising a plurality of configurable nodes, the method comprising:

a) generating a first direct connection scheme comprising a set of direct connections from a particular configurable node to a first set of configurable nodes to which said particular configurable node is directly connected in said first direct connection scheme;

b) computing a score for said first direct connection scheme based on applying said first direct connection scheme to each of at least two configurable nodes of said plurality of configurable nodes;

c) generating a second direct connection scheme comprising a set of direct connections from said particular configurable node to a second set of configurable nodes to which said particular configurable node is directly connected in said second direct connection scheme;

d) computing a score for said second direct connection scheme based on applying said second direct connection scheme to each of at least two configurable nodes of said plurality of configurable nodes; and

e) selecting a direct connection scheme for implementing on said IC based on a score of said direct connection scheme.

27. The method of claim 26 further comprising:

a) generating a plurality of direct connection schemes, each direct connection scheme of said plurality of direct connection schemes comprising a set of direct connections from said particular configurable node to a particular set of configurable nodes to which said particular configurable node is directly connected in said direct connection scheme; and

b) computing a score for each direct connection scheme of said plurality of direct connection schemes, wherein said score is based on applying said direct connection scheme to each of at least two configurable nodes of said plurality of configurable nodes.

28. The method of claim 26, wherein computing a score for a direct connection scheme comprises determining an expectation value of a length of a connection from said particular configurable node to a random configurable node of said IC.

29. The method of claim 26, wherein said first and second sets are generated before either of said scores are computed.

30. The method of claim 26, wherein said score for said first direct connection scheme is computed before said second direct connection scheme is generated.

31. The method of claim 26, wherein computing a score for a direct connection scheme comprises determining a number of configurable nodes reachable from a given configurable node when said direct connection scheme is applied to said plurality of configurable nodes.

32. The method of claim 26, wherein generating said first direct connection scheme comprises selecting a random set of direct connections.

33. The method of claim 32, wherein generating said first direct connection scheme further comprises adding a set of unit length direct connections to said random set of direct connections.

34. The method of claim 32, wherein generating said first direct connection scheme further comprises adding a set of direct connections that are symmetrical to said random set of direct connections.

35. The method of claim 34, wherein said set of direct connections that are symmetrical to said random set of direct connections comprises a set of direct connections in which:

a) each direct connection corresponds to a direct connection of said random set of direct connections, and

b) each direct connection is rotated by a same angle relative to the corresponding direct connection of said random set of direct connections.

36. The method of claim 34, wherein said set of direct connections that are symmetrical to said random set of direct connections comprises a set of direct connections in which:

a) each direct connection corresponds to a direct connection of said random set of direct connections, and

b) each direct connection is reflected about an axis relative to the corresponding direct connection of said random set of direct connections.

37. A method of designing an integrated circuit (IC) comprising multiple pluralities of configurable nodes, the method comprising:

a) generating a first set of direct connection schemes, each direct connection scheme comprising a set of direct connections from a particular configurable node to a set of configurable nodes to which said particular configurable node is directly connected in said direct connection scheme;

b) generating a second set of direct connection schemes, each direct connection scheme comprising a set of direct connections from a particular configurable node to a set of configurable nodes to which said particular configurable node is directly connected in said direct connection scheme;

c) computing a score for said first set of direct connection schemes based on applying each direct connection scheme of said first set of direct connection schemes to at least one set of configurable nodes of said plurality of sets of configurable nodes;

d) computing a score for said second set of direct connection schemes based on applying each direct connection scheme of said second set of direct connection schemes to at least one set of configurable nodes of said plurality of sets of configurable nodes; and

e) selecting a set of direct connection schemes for implementing on said IC based on a score of said set of direct connection schemes.

38. The method of claim 37, wherein each of a plurality of direct connection schemes of said first set of direct connection schemes has a symmetrical relationship with the other direct connection schemes of said plurality of direct connection schemes.

39. The method of claim 38, wherein two direct connection schemes have a symmetrical relationship when one of them can be generated by rotating the other through an angle.

40. The method of claim 38, wherein two direct connection schemes have a symmetrical relationship when one of them can be generated by reflecting the other about an axis.

41. The method of claim 38, wherein two direct connection schemes have a symmetrical relationship when one of them can be generated by rotating the other through an angle then reflecting the other about an axis.

42. The method of claim 37, wherein generating said a first direct connection scheme of said first set of direct connection schemes comprises selecting a random set of direct connections.

43. The method of claim 42, wherein generating said first direct connection scheme of said first set of direct connection schemes further comprises adding a set of direct connections that are symmetrical to said random set of direct connections.

45. A method of generating a plurality of direct connection schemes for connecting a plurality of configurable nodes in an integrated circuit (IC), said method comprising:

a) generating a first direct connection scheme comprising a set of direct connections from a given configurable node to a set of at least two other configurable nodes; and

b) generating a second direct connection scheme that is different from said first direct connection scheme but is symmetrically related to said first direct connection scheme.

46. The method of claim 45, wherein said second direct connection scheme comprises a rotation of said first direct connection scheme through a particular angle.

47. The method of claim 46, wherein said second direct connection scheme further comprises a reflection of said first direct connection scheme about a particular axis.

48. The method of claim 45, wherein said second direct connection scheme comprises a reflection of said first direct connection scheme about a particular axis.

49. The method of claim 45, wherein said first direct connection scheme is asymmetrical and comprises at least two direct connections.

50. The method of claim 49, wherein said first direct connection scheme comprises at least four direct connections.

51. The method of claim 49, wherein said first direct connection scheme comprises at least six direct connections.

52. A method of designing hardwired connections of an integrated circuit (IC) comprising a plurality of configurable nodes, said method comprising:

a) specifying an arrangement of configurable nodes; and

b) performing a constrained optimization process to define an optimal set of direct connections between configurable nodes of said plurality of configurable nodes in view of a set of objectives.

53. The method of claim 52, wherein said optimization process comprises:

a) generating a plurality of direct connection schemes for connecting said plurality of configurable nodes;

b) rejecting direct connection schemes of said plurality of direct connection schemes that do not fit a set of constraints;

c) for each of at least two direct connection schemes of said plurality of direct connection schemes, determining a quality of an IC using that direct connection scheme; and

d) selecting a direct connection scheme that optimizes said quality and has not been rejected.

54. The method of claim 52, wherein said constrained optimization process comprises simulated annealing.

55. The method of claim 52, wherein said constrained optimization process comprises local optimization.

56. The method of claim 52, wherein said quality comprises a length of connections.

57. The method of claim 52, wherein said quality comprises a number of nodes that are reachable using no more than a particular number of direct connections in an IC using a given direct connection scheme.

58. The method of claim 52, wherein said quality comprises a number of nodes that are reachable under multiple conditions in an IC using a given direct connection scheme.