Element placement method and apparatus

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.

1 - 30 . (canceled)  
   
   
       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 - 46 . (canceled)  
   
   
       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.