Analytical placement methods with minimum preplaced components

• US 6,957,406 B1
• Filed: 10/16/2002
• Issued: 10/18/2005
• Est. Priority Date: 11/28/2001
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Stenz, Guenter
• Primary Examiner(s): Thompson, A. M.
• Assistant Examiner(s): LIN, SUN J
• Application Number:
  US10/273,074
• Time in Patent Office: 1,098 Days
• Field of Search: 716/9, 716/8, 716/10, 364/491, 437/250
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

The invention relates to a method for placing design components of an integrated circuit. A first site is selected. Other sites that are at maximum distances from already used sites may be selected. Components that have minimum connectivity to already placed components are selected. These components are used for preplacement. Preferably, the number of preplaced components is small. The rest of the design components are placed. An overlap ratio is computed. If the overlap ratio is above a predetermined value, the result is unplaced and additional components are preplaced. Another placement is performed. Overlap ratio is again computed. The steps of unplacing, adding preplaced components and computing overlap ratio are repeated until the overlap ratio falls below the predetermined value.

Claims

1. A method for placing a set of components, comprising:

identifying a set of candidate sites;

identifying a set of candidate components;

selecting a first free site from said set of candidate sites;

selecting a first unplaced component from said set of candidate components for placing into said first free site;

locating a second free site from said set of candidate sites that has. a maximum distance from said first free site; and

selecting a second unplaced component from said set of candidate components for placing into said second free site, said second unplaced component having a minimum connectivity with said first unplaced component.

2. The method of claim 1 wherein said set of candidate components contains input-output blocks.

3. The method of claim 1 wherein said candidate sites are located at a perimeter of an integrated circuit.

4. The method of claim 1 wherein said candidate components are represented by nodes in an undirected graph, and said connectivity is associated with logical length between said nodes.

5. The method of claim 1 further comprising:

generating an objective function;

minimizing said objective function to obtain an equation; and

solving said equation.

6. The method of claim 5 further including adding a force function into the equation.

7. The method of claim 1 further comprising:

location another free site from said set of candidate sites that has a maximum distance from already located sites; and

selecting another unplaced component from said set of candidate components for placing into said another free site, said another unplaced component having minimum connectivity with already selected components.