Element placement method and apparatus

• US 20040139413A1
• Filed: 08/18/2003
• Published: 07/15/2004
• Est. Priority Date: 08/21/2002
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: DeHon, Andre, Wrighton, Michael
• Granted Patent: US 7,210,112 B2
• Time in Patent Office: Days
• US Class Current: 716/9
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method and a device for performing placement of a plurality of elements for circuit design. A potential location is assigned to each element and a placement engine is assigned to each potential location. Pairing operations are performed, in parallel, between placement engines to determine whether to perform exchange of the elements associated with the engines. Exchange determination is based both on a cost function and on randomness considerations. Also self-placement is allowed, where the placement engines are implemented on the same hardware system on which the elements are to be placed.

Claims

1. A method of performing placement of a plurality of elements for electronic circuit design, comprising:

a) providing a plurality of processing units, each processing unit of the plurality of processing units being able to communicate with one or more neighboring processing units of the plurality of processing units;

b) establishing an initial placement for the elements by forming an initial association between each element and a processing unit;

c) for each processing unit, in parallel, updating or not updating a list of processing units associated with the elements to be connected with the element associated with that processing unit;

d) repeating step c) for a number of times; and

e) for each processing unit, in parallel;

e1) selecting a pairing processing unit to be paired with the processing unit; and

e2) determining whether to exchange, between the processing unit and the pairing processing unit, the elements associated with the processing unit and the pairing processing unit.

2. The method of claim 1, wherein step e2) is a function of randomness and expected improvement of a cost function.

3. The method of claim 2, wherein step e2) is a combination of a comparison between a randomly generated number and a parameter and a comparison of a value of a cost function after the exchange with a value of the cost function before the exchange.

4. The method of claim 3, wherein step e2) is performed by means of a first comparing step where a randomly generated number is compared with a parameter and, in case the first comparing step is not satisfied, by means a second comparing step where a value of a cost function after the exchange is compared with a value of the cost function before the exchange.

5. The method of claim 4, wherein the parameter is a variable parameter that changes over time.

6. The method of claim 5, wherein the parameter decreases linearly over time.

7. The method of claim 1, wherein the processing units are disposed as a systolic array.

8. The method of claim 7, wherein, for each repetition of steps e1) and e2), a combination of steps e1) and e2) is performed up to four times, to pair each processing unit with all neighboring processing units able to communicate with that processing unit.

9. The method of claim 1, wherein the method is performed on a field programmable gate array (FPGA).

10. The method of claim 7, wherein the method is performed on a systolically connected array of FPGAs.

11. The method of claim 1, wherein the optimal element placement information is used to perform element placement on a field programmable gate array (FPGA).

12. The method of claim 1, wherein the initial placement is established in a random manner.

13. The method of claim 1, wherein, in step e1), the pairing processing unit is selected among the one or more neighboring processing units.

14. The method of claim 1, wherein step c) is repeated for a number of times equal to the number of processing units.

15. The method of claim 1, further comprising a step of outputting information indicating an optimal placement of said elements.

16. The method of claim 1, wherein step c) further comprises the steps:

c1) communicating location information and identification information of an element to one of the one or more neighboring processing units; and

c2) receiving location information and identification information of an element from a different one of the one or more neighboring processing units,

and wherein updating or not updating the list of processing units associated with the elements to be connected with the element associated with that processing unit is based on the information received in step c2).

17. The method of claim 1, further comprising a step of providing each processing unit with an initial list of elements to be connected with the element associated with that processing unit.

18. The method of claim 1, further comprising the steps:

f) repeating steps e1) and e2) for a number of times; and

g) repeating steps c) through f) for a number of times.

19. The method of claim 1, wherein step c) is performed by means of a position update chain.

20. The method of claim 1, wherein step c) is performed by means of a tree-based update.

21. The method of claim 20, wherein the tree is a binary tree, and wherein a sequentialization procedure is provided to manage contemporaneous transmission of two children nodes of the tree to their parent node.

22. The method of claim 20, wherein the tree is a binary tree, and wherein an elimination procedure is provided to select among contemporaneous transmission of two children nodes of the tree to their parent node.

23. The method of claim 20, wherein each node of the tree is provided with staleness information.

24. The method of claim 20, wherein subtrees are used to perform a partial update procedure.

25. The method of claim 1, wherein step c) comprises providing timing information.

26. The method of claim 25, wherein update information and timing information are simultaneously provided to the processing units.

27. The method of claim 2, wherein the cost function is a bounding box.

28. The method of claim 1, wherein the processing units are implemented on the same circuit on which the elements are to be placed.

29. The method of claim 1, wherein the method is executed on a reconfigurable substrate and the resultant placement is used to configure placement information for said reconfigurable substrate.

30. A method for coordinating exchanges among distributed parallel processing units, wherein:

each processing unit is locally connected with one or more neighboring processing units;

each processing unit is able to be associated with an element, to be ordered according to a predetermined criterion;

each processing unit is able to be paired with one of the one or more processing unit to reach a determination on whether to exchange associations with the respective elements between the paired processing units, the determination being in part based on randomness and in part based on a cost function.

31. A placement device for performing placement of a plurality of elements for electronic circuit design, comprising a plurality of processing units, wherein:

each processing unit of the plurality of processing units is able to communicate with one or more neighboring processing units of the plurality of processing units;

each processing unit of the plurality of processing units is able to be associated with one element of the plurality of elements to be placed;

each processing unit comprises an exchangeable element connection list of elements to be connected with the element associated with the processing unit and a corresponding updatable processing unit connection list of processing units associated with the elements of the element connection list.

32. The device of claim 31, wherein:

placement of elements of different types is performed; and

placement of elements of one type is performed through exchanges of elements associated with processing units of the same type.

33. The device of claim 31, wherein the processing units are implemented on the same circuit on which the elements are to be placed.

34. A processing unit for use in a placement device performing placement of a plurality of elements for electronic circuit design, the processing unit being associatable with an element of the plurality of elements and comprising a content addressable memory (CAM), the CAM comprising:

a first memory component storing a connection list of elements connected, in the placement, with the element associated with the processing unit; and

a plurality of second memory components connected with the first memory component, each second memory component able to store information about one element of the elements of the connection list,

wherein the CAM operates according to either;

a first mode, where the connection list stored in the first memory component is exchanged with a connection list of another processing unit;

or

a second mode, where the second memory components are set to store information in accordance with the connection list;

or

a third mode, where identification information of an element received by the CAM is compared with the information stored in the second memory components, to provide address information of a location storing position information of a processing unit associated with the element whose identification information is received.

35. The processing unit of claim 34, wherein the first memory component is a dual-port RAM.

36. The processing unit of claim 34, wherein each second memory component comprises a plurality of RAMs.

37. The processing unit of claim 34, wherein the CAM also operates according to a fourth mode, where the second memory components are reset, to allow information in accordance with a different connection list to be stored in the second memory components.

38. A method of performing placement of a plurality of elements for electronic circuit design, comprising:

a) providing a plurality of processing units, each unit being able to be associated with one or more of the elements to be placed;

b) for each processing unit;

b1) selecting a pairing processing unit to be paired with the processing unit; and

b2) determining whether to exchange, between the processing unit and the pairing processing unit, the elements associated with the processing unit and the pairing processing unit; and

c) for each processing unit, updating a list of processing units associated with the elements to be connected with the one or more elements associated with that processing unit.

39. The method of claim 38, wherein step b) is performed in parallel

40. The method of claim 38, wherein step c) is performed by means of a sorting network.

41. The method of claim 40, wherein each processing unit has a position and, in case of empty positions, the empty positions are provided with dummy destination addresses.

42. The method of claim 38, wherein IO pads are associated with the elements, and placement of the IO pads is also performed.

43. The method of claim 42, wherein placement of the elements is performed before placement of the IO pads.

44. The method of claim 43, wherein placement of the IO pads is performed by means of a greedy algorithm.

45. The method of claim 38, wherein the number of processing units provided is inferior to the number of elements to be placed, and wherein placement is performed by means of a windowing approach.

46. The method of claim 38, wherein the number of processing units provided is inferior to the number of elements to be placed, and wherein placement is performed by means of a folding approach, wherein each processing unit is able to be associated with more than one element.

47. A method of performing placement of a plurality of elements, comprising:

assigning a potential location to each element;

assigning a placement engine to each potential location, whereby each element is assigned to a placement engine; and

performing pairing operations between placement engines, wherein, at the end of each pairing operation, association of the elements to the paired placement engines is either exchanged or remains the same.

48. The method of claim 47, wherein performing pairing operations comprises performing a plurality of discrete pairing operations, each discrete pairing operation comprising a parallel pairing of a first half of the placement engines with a second half of the second engines.

49. The method of claim 47, wherein element association exchange is a function of a cost function and randomness.

50. The method of claim 49, wherein element association exchange mostly depends on randomness at the beginning of the method and mostly depends on the cost function towards the end of the method.

51. The method of claim 47, wherein the placement engines are implemented on the same hardware system on which the elements are to be placed.

52. A method of performing placement of a plurality of elements by means of processing units built out of a plurality of said elements, comprising:

grouping elements and configuring the elements to be processing units;

combining the elements to be placed in clusters of elements;

performing cluster placement on the clusters; and

performing element placement on the elements combined in the placed clusters,

wherein cluster placement is performed through;

assignment of a processing unit to each cluster;

pairing operations between processing units, wherein, at the end of each pairing operation, association of the clusters to the paired processing unit is either exchanged or remains the same.

53. The method of claim 52, wherein element placement is performed through:

assignment of a processing unit to each element;

pairing operations between processing units, wherein, at the end of each pairing operation, association of the elements to the paired processing unit is either exchanged or remains the same.

54. The method of claim 52, wherein cluster association exchange is a function of a cost function and randomness.

55. The method of claim 53, wherein element association exchange is a function of a cost function and randomness.

56. A method of performing placement of elements by means of processing units built out of a plurality of said elements, comprising:

performing a first design transformation such that transformed elements to be placed each contain sufficient resources to implement a processing unit;

configuring the device as a set of processing units; and

performing placement on the transformed elements using said set of processing units.

57. The method of claim 56, wherein placed transformed elements have placement information about the original elements before the transformation, so that no further placement is needed.

58. The method of claim 56, where the original elements are placed by performing a second design transformation from the transformed placed elements to the original elements;

and

performing placement on the original elements using said set of processing units.

59. The method of claim 58, wherein second design transformation and placement on the original elements are performed in series on the placed transformed elements.

60. The method of claim 58, wherein second design transformation and placement on the original elements are performed in parallel on the placed transformed elements.