| Element placement method and apparatus -> Monitor Keywords |
|
|
  Element placement method and apparatusUSPTO Application #: 20070214445Title: 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. (end of abstract) Agent: Alessandro Steinfl C/o Ladas & Parry - Los Angeles, CA, US Inventors: Andre DeHon, Michael Wrighton USPTO Applicaton #: 20070214445 - Class: 716010000 (USPTO) Related Patent Categories: Data Processing: Design And Analysis Of Circuit Or Semiconductor Mask, Circuit Design, Floorplanning, Constraint-based Placement (e.g., Critical Block Assignment, Delay Limits, Wiring Capacitance) The Patent Description & Claims data below is from USPTO Patent Application 20070214445. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS REFERENCE TO RELATED APPLICATIONS [0001] This application is a divisional of U.S. application Ser. No. 10/643,772 filed on Aug. 18, 2003, which claims the benefit of U.S. provisional Patent Application Ser. No. 60/405,112 filed on Aug. 21, 2002 for a "Method and Apparatus for Hardware Acceleration of the Placement Problem" by Andre' DeHon and Michael Wrighton, U.S. provisional Patent Application Ser. No. 60/416,080 filed on Oct. 4, 2002 filed by Michael Wrighton and Andre' DeHon for "Hardware-assisted simulated annealing with application for fast FPGA Placement" and U.S. provisional Patent Application Ser. No. 60/473,722 filed on May 28, 2003 by Michael Wrighton for "Spatial Approach To FPGA Cell Placement By Simulated Annealing," the disclosure of all of which is incorporated herein by reference. BACKGROUND OF THE INVENTION [0003] 1. Field of the Invention [0004] The present invention relates to the field of electronic circuit design. More specifically, a method and apparatus for element placement in the context of placement problems for standard or custom cells, field programmable gate arrays (FPGAs), programmable systems on chip (PSoC) or multiprocessors are disclosed. [0005] 2. Description of the Prior Art [0006] The most time-consuming operation in the design automation flow from a hardware description language representation of a digital circuit to an FPGA programming bitstream is the placement step. Large designs can have placement runtimes of hours or even days for modem multimillion user-gate devices. Software algorithms and workstation capabilities are not improving fast enough to keep up with the exponentially increasing number of resources available on FPGAs. [0007] Placement is a NP-complete problem. A widely used approach is simulated annealing, as disclosed, for example in S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220(4598), pp. 671-680, 1983. Another well known approach is the force-directed algorithm disclosed in S. Goto, "An efficient Algorithm for the Two-Dimensional Placement Problem in Electrical Circuit Design," IEEE Transactions on Circuits and Systems, vol. CAS-28, pp. 12-18, 1981. Force-directed algorithms can give acceptable results, but often terminate trapped in local minima. [0008] Most placers are designed to execute on sequential uniprocessors. Within the domain of fast placers, there are three different approaches to the problem. Most commonly, traditional, sequential software is optimized for substantial speed increased. Less commonly, placement software is parallelized over some small number (less than a dozen) of microprocessors. Rarely, approaches to the placement problem are seen that involve a very large number of processing elements. [0009] Parallel approaches are disclosed, for example, in U.S. Pat. No. 5,144,563 to Date et al. and U.S. Pat. No. 5,796,625 to Scepanovic et al. [0010] Prior art schemes attempting to use a very large number of processing elements are the schemes developed by Banerjee, Horrvath, Shankar, Pandya, and Chyan, Breuer. [0011] To accelerate force-directed placement, a scheme to assign one processor element to each cell of an ASIC design is described in P. Banerjee, "Parallel Algorithms for VLSI Computer-Aided Design," Chapter 3, Englewood Cliffs, N.J.: PTR Prentice Hall, 1994, and E. I. Horvath, R. Shankar, and A. S. Pandya, "A Parallel Force Directed Standard Cell Placement Algorithm," Technical Report Dept. Computer Science, Florida Atlantic University, Boca Raton, Fla., 1992. Unfortunately, this design mostly depends on a large-scale supercomputer. D.-J. Chyan and M. A. Breuer, in "A Placement Algorithm for Array Processors," presented at the ACM/IEEE Design Automation Conference, Miami Beach, Fla., 1983 envision a force-directed, systolically interconnected placement engine with one processing element per module. However, also the Chyan-Breuer algorithm is trapped in local minima. [0012] Prior art schemes are not able to achieve both high quality and large speedups. The attempts for large speedups with large number of processors fall short in quality and are highly sequentialized by the schemes used to communicate updates among processors. Attempts to achieve high quality with simulated annealing either have limited quality or limited speedup. None of the prior art schemes teaches how to employ large numbers of processors profitably to achieve large speedups, high quality, and avoid performance bottlenecks in communications. SUMMARY [0013] The present disclosure provides a spatial approach to the simulated annealing solution of the placement problem. According to the present disclosure, hardware can be constructed to mimic the structure of the problem, resulting in a solution to the placement problem that scales with the ability to build larger and larger devices. [0014] According to a first aspect of the present invention, a method of performing placement of a plurality of elements for electronic circuit design is provided, 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. [0015] According to a second aspect of the present invention, a method for coordinating exchanges among distributed parallel processing units is provided, 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. [0016] According to a third aspect of the present invention, a placement device for performing placement of a plurality of elements for electronic circuit design is provided, 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. [0017] According to a fourth aspect of the present invention, a processing unit for use in a placement device performing placement of a plurality of elements for electronic circuit design is provided, 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. [0018] According to a fifth aspect of the present invention, a method of performing placement of a plurality of elements for electronic circuit design is provided, 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. [0019] According to a sixth aspect of the present invention, a method of performing placement of a plurality of elements is provided, 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. [0020] According to a seventh aspect of the present invention, a method of performing placement of a plurality of elements by means of processing units built out of a plurality of said elements is provided, comprising: grouping elements and configuring the elements to be processing units; combining the elements to be placed in clusters of elements; performing duster placement on the clusters; and performing element placement on the elements combined in the placed clusters, [0021] 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. [0022] According to an eighth aspect of the present invention, a method of performing placement of elements by means of processing units built out of a plurality of said elements is provided, 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. Continue reading... Full patent description for Element placement method and apparatus Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Element placement method and apparatus patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Element placement method and apparatus or other areas of interest. ### Previous Patent Application: Method for indicating differential signal lines in a layout Next Patent Application: Design stage mitigation of interconnect variability Industry Class: Data processing: design and analysis of circuit or semiconductor mask ### FreshPatents.com Support Thank you for viewing the Element placement method and apparatus patent info. IP-related news and info Results in 3.2995 seconds Other interesting Feshpatents.com categories: Qualcomm , Schering-Plough , Schlumberger , Seagate , Siemens , Texas Instruments , |
||
