Hetergeneous method for determining module placement in FPGAs

• US 6,457,164 B1
• Filed: 06/29/2000
• Issued: 09/24/2002
• Est. Priority Date: 03/27/1998
• Status: Expired due to Fees

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Dellinger, Eric F., Hwang, L. James, Wittig, Ralph D., Patterson, Cameron D., Mohan, Sundararajarao, Mitra, Sujoy
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/608,694
• Time in Patent Office: 817 Days
• Field of Search: 716/8, 716/10, 716/9, 716/16, 716/18
• US Class Current: 716/121
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

The invention provides parametric modules called Self Implementing Modules (SIMs) for use in programmable logic devices such as FPGAS. The invention further provides tools and methods for generating and using SIMs. SIMs implement themselves at the time the design is elaborated, targeting a specified FPGA according to specified parameters. In one embodiment, a SIM references or includes one or more floorplanners each of which may employ one or more placement algorithms. Such placement algorithms might include, for example: a linear ordering algorithm that places datapath logic bitwise in a regular linear pattern; a rectangular mesh algorithm that implements memory in a grid pattern in distributed RAM; a columnar algorithm for counters and other arithmetic logic; or a simulated annealing algorithm for random logic such as control logic. Therefore, a design including more than one SIM can utilize a plurality of placement algorithms at the same or different levels of hierarchy. The design as a whole can therefore utilize a non-uniform global placement strategy.

Claims

1. A data storage medium comprising a first module for an IC, the first module comprising:

means for specifying a logical function of the first module; and

means for specifying a first floorplanner that executes at the time the first module is executed, the first floorplanner determining a shape of the first module as implemented in the IC according to a first floorplanning algorithm, the first floorplanner further determining a logical implementation of the logical function,

wherein the first floorplanning algorithm implements the module as one of a row and a column of elements.

2. The data storage medium of claim 1, wherein the first floorplanner has the ability to exchange information with other floorplanners associated with other modules.

3. The data storage medium of claim 1, wherein the first floorplanner is written by a module user.

4. The data storage medium of claim 1, wherein the first floorplanning algorithm cycles through a set of precomputed implementations and selects one of the implementations based on a scoring mechanism.

5. The data storage medium of claim 1, wherein the first floorplanning algorithm is a datapath algorithm.

6. The data storage medium of claim 1, wherein the first floorplanning algorithm is a simulated annealing algorithm.

7. The data storage medium of claim 1, wherein the first floorplanning algorithm implements the module as a column of elements.

8. The data storage medium of claim 1, wherein the first floorplanning algorithm implements the module as a row of elements.

9. The data storage medium of claim 1, wherein the first module further comprises a second floorplanner using a second floorplanning algorithm.

10. The data storage medium of claim 9, wherein the IC is a programmable IC and wherein one of the first and second floorplanners is chosen to implement the first module, based on resource constraints in an area of the programmable IC to which the first module is assigned.

11. The data storage medium of claim 1, wherein the first module further comprises an instantiation of a child module, the child module having an associated child floorplanner.

12. The data storage medium of claim 11, wherein the first floorplanner has the ability to exchange information with the child floorplanner.

13. The data storage medium of claim 1, wherein the first module is written in an object-oriented language.

14. The data storage medium of claim 1, wherein the first module further comprises the first floorplanner.

15. A data storage medium comprising a first module for an IC, the first module comprising:

means for specifying a logical function of the first module; and

means for specifying a first floorplanner that executes at the time the first module is executed, the first floorplanner determining a shape of the first module as implemented in the IC according to a first floorplanning algorithm, the first floorplanner further determining a logical implementation of the logical function,

wherein the first module is written in an object-oriented language, and

wherein the object-oriented language is Java.

16. A data storage medium comprising a first module for an IC, the first module comprising:

means for specifying a logical function of the first module; and

means for specifying a first floorplanner that executes at the time the first module is executed, the first floorplanner determining a shape of the first module as implemented in the IC according to a first floorplanning algorithm, the first floorplanner further determining a logical implementation of the logical function,

wherein the first floorplanner is written in an object-oriented language.

17. The data storage medium of claim 16, wherein the object-oriented language is Java.