Data structures for representing the logical and physical information of an integrated circuit Number:7,146,595 from the United States Patent and Trademark Office (PTO) owispatent A floor planner tool for integrated circuit design which provides tools and displays for a designer to create a floor plan to define desired placement of circuits defined in a logical netlist by creating a physical hierarchy comprised of nested pblocks. Each pblock is a data structure which contains data which defines which circuits from the logical netlist are assigned to it. Each pblock stands alone and can be input to a place and route tool without the rest of the physical hierarchy. Each pblock data structure contains pointers to the circuits on the netlist assigned to that plbock, identifies other pblocks nested within it and contains at least a list of boundary pins for that pblock. Net data structures in the physical hierarchy define which nets are connected to which pins. PCellview data structures define the internal structure of each pblock.<H representing, information, Data, structures, 7146595.html, Patent, pto, 7146595

Title: Data structures for representing the logical and physical information of an integrated circuit

Abstract: A floor planner tool for integrated circuit design which provides tools and displays for a designer to create a floor plan to define desired placement of circuits defined in a logical netlist by creating a physical hierarchy comprised of nested pblocks. Each pblock is a data structure which contains data which defines which circuits from the logical netlist are assigned to it. Each pblock stands alone and can be input to a place and route tool without the rest of the physical hierarchy. Each pblock data structure contains pointers to the circuits on the netlist assigned to that plbock, identifies other pblocks nested within it and contains at least a list of boundary pins for that pblock. Net data structures in the physical hierarchy define which nets are connected to which pins. PCellview data structures define the internal structure of each pblock.

Patent Number: 7,146,595 Issued on 12/05/2006 to Knol, et al.

Inventors: Knol; David A. (San Jose, CA), Raje; Salil Ravindra (San Jose, CA)
Assignee: Xilinx, Inc. (San Jose, CA)

Appl. No.: 10/800,042

Filed: March 12, 2004

Current U.S. Class: 716/11 ; 716/10; 716/8; 716/9

Current International Class: G06F 17/50 (20060101)

Field of Search: 716/8-11

References Cited [Referenced By]

U.S. Patent Documents


5140526	August 1992	McDermoth et al.
5499191	March 1996	Young
5513119	April 1996	Moore et al.
5617327	April 1997	Duncan
5648913	July 1997	Bennett et al.
5659484	August 1997	Bennett et al.
5991523	November 1999	Williams et al.
6170080	January 2001	Ginetti et al.
6223329	April 2001	Ling et al.
6408422	June 2002	Hwang
6631508	October 2003	Williams
2004/0078767	April 2004	Burks et al.

Other References

US. Appl. No. 10/792,164, filed Mar. 3, 2004 Knol et al. cited by other .
Wang, Maogang, et al., "Multi-Million Gate FPGA Physical Design Challenges," ICCAD '03, Nov. 11-13, 2003, pp. 891-898, Available from ICCAD, San Jose, California, USA. cited by other.

Primary Examiner: Siek; Vuthe
Assistant Examiner: Levin; Naum B.
Attorney, Agent or Firm: Fish; Ronald C. Maunu; LeRoy D.

Claims

What is claimed is:

1. A computer readable medium having stored thereon a data structure defining a physical block (pblock) in a hierarchy of pblocks (both parent and child) which defines the same integrated circuit structure by reference to data in a netlist which defines a logical hierarchy, the data defining said pblock comprising: A) a set of pointers to data defining boundary pins of said pblock, said boundary pins for connecting to nets external to the pblock and for connecting to nets internal to the pblock; B) a field containing a pointer to a first parent physical block cellview (pcellview) which contains said pblock; C) a field containing a pointer to a second pcellview data structure owned by said pblock, said second pcellview containing pointers to data which define lists of pins internal to the pblock, nets that connect to the internal pins and boundary pins of the pblock, child pblocks and child instances which have been assigned to said pblock and which define the functionality of said pblock; and D) a field containing coordinates on a floorplan representing a surface of an integrated circuit on which circuits assigned to said pblocks are to be formed, said coordinates to define a geometric shape representing said pblock and the size thereof, said geometric shape being displayed on a computer display of a computer executing a floor planning process.

2. The computer readable medium of claim 1 wherein the data structure further includes data pointers to data which define internal pins of instances contained within said pblock.

3. The computer readable medium of claim 1 wherein said data structure includes a pcellview data structure comprising: E) a list containing data which defines a list of pblocks which are included or nested within said pblock defined by data elements A through D; F) a list containing data or pointers to data on said netlist which define instances which have been assigned to said pblock; G) a list containing data or pointers to data which define boundary pins of said pblock which connect to internal nets of said pcellview; H) wherein the list containing pointers to data which define internal physical nets which connect from boundary pins of said pblock to internal pins completes the original connectivity between instances defined in said netlist; and I) a field which contains a pointer to a data object representing a parent pblock that envelopes the pcellview data object defined by data elements E through I.

4. A computer readable medium having stored thereon a data structure defining a physical block cellview (pcellview) owned by a particular pblock in a hiearchy of pblocks which defines the internals of said pblock which owns said pcellview, the data defining said pcellview comprising: A) a list containing data which defines a list of pblocks which are included or nested within said pblock defined by data elements A through D; B) a list containing data or pointers to data on a netlist which define instances which have been assigned to said pblock; C) a list containing pointers to data which define boundary pins of said pblock which connect to internal nets of said pcellview and to external nets of said pblock; D) a list containing pointers to data which define internal physical nets which connect from boundary pins of said pblock to internal pins of said pblock so as to complete the original connectivity between instances defined in said netlist; and E) a field which contains a pointer to a data object representing a parent pblock that envelopes the pcellview data object defined by data elements A through E.

5. A processor-based method for representing a netlist that defines a logical hierarchy, comprising: creating in a memory respective representations of a plurality of physical blocks (pblocks), wherein each pblock specifies, a set of boundary pins of the pblock, the boundary pins for connecting to nets external to the pblock and for connecting to nets internal to the pblock; a reference to a first parent physical block cellview (pcellview) that contains said pblock; a reference to a second pcellview owned by the pblock, the second pcellview specifying lists of pins internal to the pblock, nets that connect to the internal pins and boundary pins of the pblock, child pblocks and child instances assigned to said pblock and that define the functionality of the pblock; and a set of coordinates representing a surface of an integrated circuit on which each circuit assigned to the pblock is to be formed.

6. The method of claim 5, further comprising: displaying instances of the netlist in a first pane on a display and the pblocks in a second pane on the display; and highlighting display of instances of the netlist that are assigned to pblocks.

Description

FIELD OF USE AND BACKGROUND OF THE INVENTION

This patent application is related to the technology disclosed in a prior U.S. patent application entitled SYSTEM FOR REPRESENTING THE LOGICAL AND PHYSICAL INFORMATION OF AN INTEGRATED CIRCUIT filed on Mar. 3, 2004, Ser. No. 10/792,164.

Field programmable gate arrays (FPGAs) and application specific integrated circuits are increasingly popular types of integrated circuits. However, increasingly complex integrated circuits in general are increasing in popularity because integration of large systems on a chip substantially reduces manufacturing costs over other classic forms of construction of circuits.

When designing integrated circuits, the final design is reduced to a file called a netlist. A netlist is a description of the devices that are to be fabricated on an integrated circuit and the connections between each terminal of each device to form the circuit.

Layouts of integrated circuits are typically done on workstations which have a fixed amount of random access memory (RAM). In complex integrated circuits, the netlist can be so large that it cannot all be stored in the RAM available on the workstation. This results in part of the netlist being stored on the hard disk of the workstation and being paged in and out of RAM. This slows down the workstation and can be frustrating for the designer.

In laying out integrated circuits, it is important to keep devices that have to communicate data or signals with each other close to each other in the layout. Long lines of conductive material running across the chip between terminals of devices that need to communicate signals cause excessive amounts of parasitic capacitance. Parasitic capacitance slows down the operation of integrated circuits and limits the upper frequency of the clock speed that controls all switching on the chip. Keeping devices that need to communicate signals to each other close together optimizes a design for speed.

Designs of integrated circuits are implemented in terms of logical blocks, each of which performs a specific type function. Designers also want to group logical blocks that are connected together by many wires close to each other to minimize routing congestion. If two logical blocks that are highly interconnected are far apart on the chip, the expanse of chip area between the two logical blocks will have many wires running across it. This makes this space less useable because it is more difficult to integrate other circuitry in this space and get connections to it without interference with the other lines running across the space.

Netlists are expressed in pure logical terms of a hierarchy of logical blocks and how they are interconnected. The hierarchy is comprised of higher level logical blocks which are comprised of lower level logic blocks each of which is itself comprised of lower level logical blocks, and so on to the leaf nodes of the hierarchical tree. Logical blocks are such things as adders, an Arithmetic Logic Unit (ALU), system memory cache, system bus, display driver circuitry, etc. An example of a hierarchy might be a top level logical block which is a microprocessor and which has four ALUs. Each of these ALUs is comprised of four adders for this example. Each of these adders has two NAND gates and an OR gate for this example. These logical blocks represent a three level hierarchy, and the connections between these circuits define a logical netlist with a three level hierarchy.

The netlist is purely logical and relates what the different logical blocks are, how they are interconnected, and the hierarchy between the various logical blocks. There is no information in a logical netlist which indicates where on an integrated circuit any particular device such as a transistor, adder, etc. which is part of a logical block should be placed.

To actually physically lay out the circuit, the netlist is input to another tool running on a workstation called a floor planner. The floor planner lets the designer layout the general floor plan of the chip by allowing the designer to specify the locations on the chip for the high level logical blocks in the hierarchy. For example, "the arithmetic logic unit goes here", and the "RAM cache goes there" and "the system bus circuitry goes there", etc. The floor planner then outputs the netlist and a set of directives which are usually a separate file. The directives and netlist are then input to another tool called a placement and router tool which functions to specifically identify the location on the chip where every transistor and every other device goes and how the connections between devices will be routed.

Prior art floor planner tools did allow the designer to lay out the floor plan of the chip but only using logical blocks defined in the netlist. This was not optimal because it might result in placement of circuits that need to communicate with each other which are in different logical blocks far from each other on the chip.

Therefore, a need has arisen for a new floor planner tool which allows a chip floorplan to be generated which is laid out with performance issues in mind. To do its work, a floor planner tool according to the invention would have to be able to store the logical netlist in memory and then must generate another representation of the logical netlist that defines physical blocks in the floor plan layout and which logical blocks are in each physical block. Specifically, the floor planner tool needed would have to be able to generate a physical block hierarchy to define the physical layout of the chip without regard to the logical block boundaries defined by the logical netlist. The physical block hierarchy is all about performance as it allows the designer to place circuits that need to communicate with each other close together on the chip. The needed floor planner tool would then be able to provide the physical constraints and directives to the place and route tool based upon the physical block hierarchy.

The physical block hierarchy will contain a great deal of data, though usually not as much as the logical netlist. Still, any data at all for the physical hierarchy in addition to the large logical netlist aggravates the memory shortage problem for the place and route tool on complex designs. Large netlists and large physical directives files complicates and slows down the operations of all both the floor planner tool and the place and route tool if the size of the netlist and physical directive file exceeds the available RAM capacity. Frequently, place and route tools cannot handle all the gates in a large netlist even if they have 4 gigabytes of RAM. If the place and route tool or the floor planner tool cannot have all of the netlist in RAM, it will not operate unless virtual memory is turned on and part of the netlist on the workstation hard disk. Putting part of the netlist on hard disk and paging it in and out of RAM has not proved to be a desirable solution as it is very slow.

Therefore, a need has arisen for a floor planner tool which can generate a physical block hierarchy with a compact data structure. This physical block hierarchy must be generated from a netlist and maintain the functionality and connectivity defined in the netlist. Such a floor planner tool would allow a user to place physical restraints on the placement of certain logical blocks and provide as an output both a logical netlist as well as a physical block list which is compact in data structure. In particular, a need has arisen for a floor planner tool which generates a compact data representation of the physical blocks in the floor plan layout without repeating the entire content of the logical netlist by referencing the logical netlist. This enables the data required to do floor planning and generate output physical directives to all reside in RAM of the floor planner tool thereby speeding its operation.

Big logical netlists and compact representations of a physical layout still create problems for place and route tools though because this data can still exceed the capacity of the RAM of the workstation upon which the place and route tool is executing. Exceeding the RAM capacity frequency happens because the place and route tool uses the RAM as scratchpad memory to record trial placements while it is going through its placement and routing algorithms. This data can expand the data consumed by the netlist by a factor of three until a final place and route solution is reached by the tool whereupon the amount of data that needs to be stored shrinks back down. In other words, while the place and route tool is thinking, it generates large amounts of trial and error placement and routing data on proposed placements that must be stored. Once a solution is reached, the data on the proposed placements that were not adopted can be discarded. However, if the place and route tool runs out of RAM during this process, complications will arise.

Accordingly, a need has also arisen for a floor planner tool which can break the logical netlist and physical directives list up into stand alone segments each of which defines some portion of the overall chip design and which is much smaller than the overall netlist. In effect, the output of this tool would define a subchip within an overall chip layout. The subchip would usually have terminals which need to be connected to other terminals of other logical blocks and it would usually have timing constraints which must be met so that the overall chip will be able to meet its timing constraints. Such a floor planning tool would therefore provide pinout positions on the subchip as well as positions for all logical blocks within the one or more physical blocks of the subchip and it would provide timing constraints or a timing budget the subchip must meet. Each of these netlist segments would define a subchip which could be input to the place and route tool independently of the other segments. Each netlist segment would be small enough to entirely fit in RAM of the place and route tool. Because of the smaller size of the subchip netlist, the growth in data volume during the place and route algorithm would be unlikely to exceed the RAM capacity of the place and route workstation.

This divide and conquer approach has been known in the ASIC world, but no such floor planner tool exists yet the FPGA world.

It is possible to not use a floor planner in the above described process and just input the netlist to the place and route tool. Place and route tools are not very deterministic though. Thus, the results in terms of clock speed can vary wildly from one run of a place and route tool to the next with exactly the same netlist as the input. Thus, one run of the place and route tool can result in the final design have a clock speed of 130 Mhz, and the next run with exactly the same netlist having been input can result in a clock speed of 80 Mhz.

The inclusion of a floor planner in the process greatly improves the stability of the performance of the final design because it allows the designer with knowledge of the operation of the circuit to specify which logical blocks or groups of logical blocks need to be placed close to each other. This information then is reduced to directives which restrict the placement of individual transistors and other components by the place and route tool so that the final performance of the chip will be more predictable.

The place and route tool output can then be used as the input to a bitstream tool which sets the various switches in a field programmable gate array into appropriate on and off conditions to implement the functionality defined by the netlist. In the case of an application specific integrated circuit, the output of the place and route tool can be used to generate an appropriate mask set to define the functionality of the ASIC in accordance with the netlist.

Prior art floor planner tools were restricted to working with the logical blocks defined in the logical netlist. However, the floor planning process works better if the designer is allowed to create physical blocks which define a physical block hierarchy and then layout the floor plan with these physical blocks. Each of these physical blocks incorporates the circuitry of one or more logical blocks. If one floor plans with only the logical blocks defined by the netlist, it is often not possible to get the best performance. This is because some circuits in one logical block may be highly interconnected with a need to communicate with circuitry in another logical block. Performance issues would require that these two different circuits be placed close to each other on the chip. But if the floor planner is restricted to placement of logical blocks, it is possible that the two circuits in different logical blocks that need to communicate will not be placed close enough together on the chip to achieve optimum performance.

Further, chip designers like to evaluate a plurality of scenarios for a chip floor plan. In prior art floor planners, each different floor plan scenario required reading the entire logical netlist into RAM, and only one floor plan could be generated from each copy of the netlist. To do two floorplans would require two copies of the netlist. This aggravates the memory shortage problem

Therefore, a need has arisen for a floor planning tool which can invade the logical block boundaries to create physical blocks arranged in a hierarchy and each of which can span logical block boundaries while maintaining the connectivity expressed in the logical blocks of the netlist. A need has also arisen for a floor planning tool which can have multiple floor plan scenarios simultaneously while storing only one copy of the logical netlist in memory and simultaneously expressing the physical block hierarchy by reference to the logical netlist thereby keeping the data representation of the physical block hierarchy compact.

SUMMARY OF THE INVENTION

The teachings of the invention contemplate data structures, computer processes, programmed computers and computer readable media which contain instructions to control a computer to provide a new floor planning tool. These inventions implement a floor planning tool which allows users to creates new physical hierarchies to place circuits (instances) from a logical netlist (which contains no physical placement information) onto a floorplan of any integrated circuit and allows any instance from the logical netlist to be put into any physical block of a floorplan. This allows the user to give guidance to a place and route tool on where specific circuits are to be placed in the final chip layout so as to enhance performance and ensure that timing and power consumptions constraints can be met. This floor planning tool is useful in laying out conventional integrated circuits, FPGAs, ASICs, structured ASICs and any other type of integrated circuit.

The physical blocks define a physical hierarchy, and the computer processes allow invasion of the logical blocks of the netlist to get information needed to define the instances that have been assigned to various pblocks. Extensive use of pointers in the data structures of the physical hierarchy are used to save storage space needed to store the data structures of the physical hierarchy. These pointers point to data in data structures of the logical hierarchy so that this data does not have to be repeated in the data structures of the physical hierarchy.

The teachings of the invention include a data structure stored on a computer readable medium for physical blocks (hereafter pblock) which can be nested to define a pblock hierarchy. The teachings of the invention also contemplate data structures for physical nets, and a data structure for each physical cellview owned by a particular pblock.

The computer readable medium can be anything which can be read by a computer including CD-ROM, floppy disk, hard disk, DVD-R media, random access memory, flash memory, magnetic tape, punch cards, etc.

Each pblock has its own data object which defines the location of the pblock on the floor plan of the integrated circuit (chip) being designed. The floorplan provides the proposed placement of the circuits to be integrated on said chip. Each pblock data object also includes a list of child pblocks, said child pblocks being pblocks which are contained within the parent pblock. Each pblock data object includes a list of instances or circuits that are assigned to the pblock. Each instance entry on the list is implemented through use of a pointer to the data object which defines the instance in the original logical netlist thereby reducing the amount of data that needs to be stored for the physical hierarchy.

There is also a data structure which defines the floorplan being designed in terms of a single array which links every instance which has been assigned to a pblock to that pblock. The floorplan data structure includes a field which identifies a root pblock which is a pblock which will contain all other pblocks in the hierarchy (it is at the top of the hierarchical tree) and therefore will contain all instances assigned to the pblocks in the hierarchy.

Use of pblocks and a physical hierarchy to define the positions of circuits on chip floorplans greatly improves the performance of the chip because the logical netlist includes no position information. This leaves it up to the place and route tool to put circuits on the chip surface wherever it determines they need to be. This can result in some circuits being placed too far away from each other to meet timing constraints or power consumption constraints. By allowing the designer to place pblocks on a chip floorplan and then populate them with circuits from the logical netlist, a designer can place circuits that have hard to meet timing and power constraints close to each other in the final design. This decreases the amount of parasitic capacitance (parasitic capacitance is proportional to length) in the conductive lines between the chips and reduces the propagation delays and power consumption on these shorter lines.

The teachings of the invention also include a process a computer executes to create the physical hierarchy and a computer programmed to carry out this process and a computer readable medium of expression which stores instructions to control a computer to carry out the process. The overall process carried out by a computer to create a physical hierarchy is generally comprised of the following steps: A) storing the data structures of a logical netlist; B) displaying on one portion of a computer display a representation of the instances defined by said logical netlist; C) providing one or more tools a user can invoke to create and locate on a floorplan of an integrated circuit being designed and comprising one or more pblocks and responding to the use of said tools to create one or more said pblock(s) by creating data objects representing said pblocks, said floorplan being displayed on the same computer display as said representation of said instances defined by said logical netlist, and wherein pblocks can contain other pblocks so as to establish a physical hierarchy; D) providing one or more tools a user can invoke to assign instances from said displayed representation of instances defined by said logical netlist into pblocks in said displayed hierarchy of pblocks; E) responding to such assignment operations by changing the data in said data objects representing said pblocks to reflect which instances are assigned to each pblock; and F) further responding to such assignment operations by determining the original connectivity between instances defined in said logical netlist and automatically changing data in predetermined data objects of said physical hierarchy so as to recreate said original connectivity by creating new nets and new pins as necessary which recreate said original connectivity. Step E is the process carried out by the PTree Update process described in the Detailed Description portion of the invention. This process is responsible for updating the data objects that define the physical hierarchy when an instance (referred to in the following steps as instToAppend) is moved from one pblock to another. It is comprises generally of the following steps: marking instToAppend entries designating instances from said logical netlist which have been moved to a pblock with a pointer to the pblock to each instance has been moved, said pointer being in an array m_instanceAssignments (hereafter referred to as the array) which defines which instances are assigned to each pblock; marking all child instances in said logical hierarchy of each said instToAppend in said array to point to the same pblock to which said instToAppend was assigned; recursing up the logical hierarchy from instToAppend until a rooted parent is found which has been assigned to a pblock (hereafter called rootedPBlock) and mark the rooted parent as zero in said array, where a rooted parent is an instance which is defined by a data object in said physical hierarchy which has a flag set which indicated said rooted parent has been assigned to a pblock and where marking an instance to zero in said array causes said instance to disappear from the physical hierarchy, where disappear from the physical hierarchy means the instance is not assigned to a particular pblock; unwinding the recursion from said rooted parent along a line of said physical hierarchy toward said instToAppend and mark as zero in said array all ancestor instances in said physical hierarchy between said rooted parent and said instToAppend, where an ancestor instance is any instance in said physical hierarchy on a line of descendants between said rooted parent and said instToAppend not including either said rooted parent nor said instToAppend; marking all siblings of any ancestor instance in said array as assigned to said rooted pblock if not already so marked by setting a flag in a data structure representing said instance in said physical hierarchy to a "rooted" state and making sure a pointer to said sibling is present in a data structure representing said rooted pblock in said physical hierarchy; determining if all sibling instances of said instToAppend in said physical hierarchy are marked as belonging to the same pblock as said instToAppend, and, if so, performing a collapse operation to resurrect a parent instance of said siblings in said physical hierarchy by removing or setting to zero entries in said array for all said sibling instances which are components of said parent instance and adding an entry to said array for said parent instance and data indicating said parent instance is assigned to the same pblock as said sibling instances which were component instances of said parent instance.

Generally, what this process comprises is: changing the pointers in the m_instanceAssignments array to reflect the new pblock to which an instance has been assigned; marking all children instances of the instance which was moved as belonging to the same pblock as the parent instance which was moved; searching the physical hierarchy for a rooted parent and marking it in the array as zero so that it disappears and finding all the ancestors of the instance that moved along the line of descendants from the rooted parent to the instance that was moved and marking them as zero; marking all siblings of any ancestor found as belonging to the same pblock the rooted parent was assigned to and determining if all children of a parent are in the same pblock, and, if so, marking them as zero and resurrecting their parent as an entry in the array and marked as assigned to the same pblock as all the children of that parent.

When an instance is moved to a new pblock, all its connections that exist between its pins and other pins have to be disconnected and recreated using boundary pins on the boundaries of pblocks and new nets. This is done by the PNetwork Update process which is the process carried out by step F above. This is done by the following steps: determining which instances have been moved from one pblock to another; for each instance that has been removed from a pblock, and for each pin on the removed instance, disconnect the pin from any net to which it is connected and removing any nets not needed in a pblock, said disconnection of pins and removing of nets accomplished by altering data defining said physical hierarchy; for each instance that has been added to a pblock, and for each pin on the added instance, create one or more new physical nets and pblock boundary pins as needed to connect said pins of all instances which have been moved to a different pblock to the same other pins said pins of said instances which have been moved were originally connected to prior to said move, said creation of new boundary pins and nets accomplished by altering data defining said physical hierarchy.

After the floor planning tool according to the invention completes the new physical hierarchy, it outputs a new netlist based upon the physical hierarchy with directives on placement to the place and route tool.

In general, the genus of the invention is defined by the following characteristics which all species will share: any data structure and any process which creates said data structure which allows a designer to physically locate wherever the designer desires individual instances or circuits defined by a logical netlist on a floor plan of a chip being designed by assigning individual instances to pblocks in the floorplan; where the pblocks can contain any instance from the logical hierarchy without regard to the hierarchical structure of the logical netlist; and where the process automatically adjusts the data in the data structure so as to make sure that all instances from the logical netlist have been assigned to a pblock and so as to maintain the original connectivity defined by the logical netlist when instances are moved to pblocks for the first time or are later moved from one pblock to another. Various Subspecies within this Genus:

1) Use pointers to instances in the logical netlist as the data in the physical hierarchy data structure which defines which instances are in each pblock so as to save memory space needed to store the data of said physical hierarchy. The original logical netlist is kept intact and the physical hierarchy data structure is kept very compact through the liberal use of pointers to data structures in the logical netlist that do not have to be repeated in the physical hierarchy.

2) Another subspecies is to repeat the data from the logical hierarchy in the physical hierarchy.

3) Allow multiple different floor plans to be developed simultaneously by using different sets of pointers to the same logical netlist.

4) Allow instances to be assigned to pblocks by dragging and dropping instances from the logical netlist to the pblocks or dragging an instance from one pblock to another.

5) Another subspecies is to allow assignment of instances to pblocks by giving text commands in a command line interface.

6) Another subspecies is to make each pblock stand alone in the sense that all nets into or out of the pblock terminate on a pblock boundary pin, and each pblock has its own timing and power constraints for its nets. In this way, large netlists do not have to be stored in their entirety in the RAM of the place and route workstation. Instead, individual pblocks can be output from the floor planning tool to the place and route tool as if each individual pblock was its own stand alone chip. This allows place and route tools to work with large netlists using the directives output by the floor planner tool without exceeding the RAM capacity of the machine.

The ability to define pblocks to put instances together that are in different logical units in the netlist saves having to rewrite the netlist when a designer decides that two circuits in different logical units on the netlist need to be placed together by the place and route tool for performance reasons. Rewriting the netlist is a major problem because timing constraints may have been defined in terms of the original netlist and changing the logical hierarchy would invalidate all the existing constraints.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a symbolic diagram of a typical logical hierarchy that defines a chip.

FIG. 2 is a flowchart of a top level method to create a physical block hierarchy from the logical blocks defined on a netlist.

FIG. 3 is a flowchart of a more detailed embodiment of a method to create a floor plan using an improved floor planner tool according to the invention.

FIG. 4, comprised of FIGS. 4A and 4B, is a flowchart of the PTree update process.

FIG. 5 is symbolic of the types of information in a display on the floor planning tool showing an example logical hierarchy on the left and some sample pblocks on the right for purposes of illustrating operation of the tool. FIG. 5 also illustrates the drag and drop operation to create a physical hierarchy and the operation of the PTree routine to guarantee no circuit is left behind.

FIG. 6 is a flowchart of the PNetwork Update process.

FIG. 7 is a flowchart of the connect process of PNetwork Update.

FIG. 8 is a flowchart of the disconnect process of PNetwork Update.

FIG. 9 is a diagram of an example to illustrate the disconnect process and the re-connect and new net synthesis process.

FIG. 10 is a flowchart of an alternative embodiment of the PNetwork disconnect process which does not try to save any portion of nets connected to instances which have been moved.

FIG. 11 is an example physical hierarchy to illustrate the operation of certain steps of the PTree Update process.

FIG. 12 is a diagram illustrating how a physical hierarchy (floorplan) saves memory space by referencing the circuits or instances which are in each pblock by using pointers to the circuits in the original logical hierarchy defined by the netlist.

FIG. 13 illustrates how the pointer data in the physical hierarchy is changed by the PTree update process when F is dragged from pb1 (where it was assigned when its parent B was dragged to pb1) to pb2.

FIG. 14 illustrates how two different alternative floorplans can be developed for a chip using pointers to the same logical hierarchy instances.

FIG. 15 is a flowchart that shows the processing to disconnect and reconnect a pblock which has been dragged out of one parent pblock and into another parent pblock.

FIG. 16 is a sample physical hierarchy which will be used to explain this process of disconnecting and reconnecting a pblock which is dragged to a new parent.

DETAILED DESCRIPTION OF THE PREFERRED AND ALTERNATIVE EMBODIMENTS

Definitions

The teachings of the invention contemplate a general purpose computer coupled to a display, a keyboard and a pointing device and programmed with an operating system which executes as an application the floor planning software to be described below. The computer typically has a hard disk, and one or more ports for inputting and outputting data and may have a CD-ROM drive, floppy disk drive, DVD-RAM drive etc. to read in data stored on portable media.

To best understand the descriptions herein, consider the following terminology definitions.

Instance--a piece or block of logic. It can be `flat` (aka primitive), e.g., something simple and indivisible like an `AND` or `NOT`. It can also be hierarchical--e.g., something that is defined by and includes at a lower level in a hierarchy, individual instance of simpler circuits such as a set of flat instances to form a more complex block of logic, such as an ALU or large RAM.

Pin--represents an input or output node for piece of logic, I.e., an instance, either primitive or hierarchical. Every instance has a list of pins that represent all inputs and outputs for that block of logic.

Net--represents a connection between a set of pins on various instances. Nets define how instances interact with each other--one instance's output pin may serve as input to a pin on several other instances (a fanout).

Cellview--the "guts" or internals that define an instance or block of logic. Primitive instances have a "black box" cellview, I.e., no contents, since by definition they are not hierarchical.

Hierarchy is a convenience that allows users to work at higher levels of abstraction. What really defines how a circuit behaves is the connectivity of all the primitive instances in a design. This means that two circuits with the exact same primitive instances and flat connectivity will have the exact same behavior, regardless of how their hierarchy was built up. A logical hierarchy usually reflects the thought processes of the logic designer, but a different physical hierarchy might better reflect the realities of actual physical implementation on the chip, such as by putting logic blocks or circuits which must communicate frequently close together on the integrated circuit (hereafter chip). Another aspect of physical implementations of chips is that there are timing and power constraints which must be met. These can frequently be met only by keeping circuits that need to send signals between themselves close together on the chip. This is because the amount of parasitic capacitive loading on the nets coupling the circuits will slow down the signal propagation too much (and consume unnecessary power) to meet timing constraints if the nets are physically too long. Parasitic capacitance of a net is proportional to its length. Conductive paths on a chips are sometimes herein also referred to as wires although each wire is not really not so much a wire as a deposit of conductive material along a layer of a chip.

The goal of the physical hierarchy created using the teachings of the invention is therefore to allow the user to read in a design with its original logical hierarchy and see it the tool according to the teachings of the invention with the physical hierarchy so that floor planning to keep certain nets short, etc. Can be performed to improve the performance of the chip and meet its timing and power constraints. However, as the floor planning process progresses, the tool according to the invention also provides means for the development of a completely new physical hierarchy. A tool according to the invention does not alter the original logical hierarchy. A tool according to the teachings of the invention can read in constraints and other supplementary data files that have been written for the original logical hierarchy. A tool according to the invention also preserves in the physical hierarchy the flat connectivity of all the primitive instances defined in the logical hierarchy.

pblock (Physical Block) forms the backbone of the physical hierarchy. It behaves very much like a hierarchical logical instance in that it can and typically does contain other instances--both logical and other pblocks. Here is a simple definition for the class of pblock data objects:

TABLE-US-00001 class PBlock { List<Pins> m_pins // list of pblock boundary pins Rectangle m_optionalRectangle; //size and location on the floorplan of the pblock PCellview* m_parentCellview; // a pointer to the parent cellview PCellview m_internals; // Pcellview owned by pblock defining functionality of pblock via lists of pins, nets, child pblocks and child instances within the pblock, each list comprised of pointers to data structures defining said pins, nets, child plbock and child instances, some of said data structures being part of the original logical netlist };

Class PBlock has a pointer to the parent cellview which is the cellview of the parent pblock (which encloses the pblock). It also has a list of pins (List<Pins> m_pins) which represent the pblock boundary pins for the pblock created by the PNetwork Update process. These boundary pins are created for the purpose of maintaining a complete and legal physical hierarchy which maintains the same functionality and connectivity defined in the original logical netlist or logical hierarchy. How the same connectivity and functionality is maintained is described below.

There are two distinct types of pins. Both behave much the same way in that a pin can connect to a single net which is why they can be represented as a single class. However, one type of pin lives on the outside boundary of the instance and hence connects to a net external to the instance. This is sometimes referred to as InsTerm in the industry. The other type of pin lives on the inside boundary of the cellview and hence connects to a net internal to that cellview. This is sometimes referred to as a Terminal in the industry. For the sake of the data structures here, the pins are illustrated as one class that will either have a pointer to its instance (in the case of an InstTerm) or a pointer to its cellview (in the case of a Terminal).

The pins of the instances which have been dragged into the pblock are listed in the data objects for each instance in the preferred embodiment. In alternative embodiments, the list of pins in the pblock data object includes both the boundary pins and the internal pins. References in the description below that refer to pins listed in the pblock data object are to be understood as referring to either type embodiment.

The notation PCellview* m_parentCellview represents a pointer to the parent cellview which contains the pblock represented by the data object. This pointer is used to allow the software to regress up the physical hierarchy tree where necessary to do recursive functions defined below. Similar pointers in the pin, net and instances data objects allow the software to recurse up the logical hierarchy for recursive functions defined below. This is the preferred embodiment, but other embodiments may delete this pointer and regress using any other means available. A PBlock data object owns a pcellview (PCellview m_internals). That pcellview owns lists of pins, nets, child pblocks and child instances. Therefore, when the software needs to access any of that information, it goes to the cellview owned by the pblock as listed in the pblock data object and reads the required data.

The notation Rectangle m_optionalRectangle defines the coordinates of two opposite corners of a rectangle representing the pblock and displayed on the floorplan. It therefore defines both the size and the position of the pblock.

The notation PCellview m_internals is the physical hierarchy cellview that represents the internals of the pblock, including any logical instances or other pblocks that have been assigned to it. A pcellview is defined as follows:

TABLE-US-00002 class PCellview { PBlock *m_parentPBlock; List<Pin> m_pins; // connect to internal nets List<Net> m_nets; // internal nets that connect to boundary pins of pblock and/or internal pins List<PBlock> m_childPBlocks; // internal (child) pblocks List<Instance*> m_childInstances; // internal (child) instances };

In the PCellview data object definition, the notation List<PBlock> m_childPBlocks; within any data object representing a particular pblock defines a list of pblocks named m_childPBlocks which are pblocks which are included (nested) within the pblock defined by the data object. Likewise, the notation List<Instance*> m_childInstances within any data object representing a particular pblock defines a list named m_childInstances which contains pointers to the instances on the original logical netlist of the instances (circuits) which have been assigned to the pblock represented by the data object. The List<Pin> m_pins notation and the notation List<Net> m_nets represent the boundary pins and physical nets, respectively, created by the PNetwork Update process. Specifically, this is a list of internal nets that connect to boundary pins and/or internal pins All external nets that couple to pblock boundary pins can be found in the parent cellview. If a pblock is encompassed by the root pblock, all external nets coupled to the boundary pins of the pblock will be listed in the nets list of the cellview of the rootpblock. But if the pblock is nested within another pblock other than the root pblock, the external nets would be in the nets list of the parent cellview. The notation PBlock *m_parentPBlock represents a pointer to the parent pblock that envelopes the PCellview data object.

After a pblock has been located on the floor plan and filled with instances, it can be dragged to another location on the floorplan. When a pblock is simply dragged to another location in whatever parent pblock it is in, there is no need to disconnect the nets connecting the pblock to other pblocks and recreate these nets. However, when a pblock which has instances assigned to it is dragged into another parent pblock, the nets connecting the pblock to other parts of the design must be disconnected and recreated. FIG. 15 is a flowchart that shows the processing to disconnect and reconnect a pblock which has been dragged out of one parent pblock and into another parent pblock. FIG. 15 is discussed further below.

Other data structures in the physical hierarchy of interest are as follows. In the following data structure definitions, * denotes "a pointer to a" meaning it is referenced by a given class but owned by another class (such as a class in the logical hierarchy, and // denotes an inline comment which is not part of the class definition.

TABLE-US-00003 class Cellview { a. Instance *m_parentinstance; b. List <Pin> m_pins; // connect to internal nets c. List<Net> m_nets; // internal nets d. List<instance> m_instances; // internal (child) instances };

The class cellview defines the functionality of an instance and points to the data structure of the parent instance of the cellview in the logical netlist where the data regarding the functionality of the instance is found. The Cellview data structure also defines which pins and nets to which the circuit pointed to by the cellview is connected and list the child instances of the parent instance.

TABLE-US-00004 class Net { Cellview *m_parentCellview; List <pin*> m_pins; // may contain both cellview pins and child //instance pins };

The data structure for class net points to the parentCellview in the logical netlist and lists all the pins to which a net is coupled.

TABLE-US-00005 class PNet { Cellview *m_parentPCellview; List <pin*>m_Ppins;// list of Ppins which are boundary pins of pblocks List <pin*> m_pins; // may contain both cellview pins and child //instance pins

A data structure object in class PNet defines for a particular pnet in the physical hierarchy the boundary pins of particular pblocks to which the pnet is coupled, and the notation Cellview *m_parentPCellview is a pointer to the parent pcellview to which the net belongs. The notation List <pin*> m_pins identifies a list of pins in the logical hierarchy, if any, to which the pnet is coupled. Where a net crosses between two pblocks, it will couple to both logical pins and physical boundary pins on the boundaries of pblocks. An example is shown in FIG. 9. There, the net that couples logical pin 106 in pblock 1 to logical pin 94 in pblock 2 is broken into three pnets. Each pnet will have its own data object in class PNet. The two pin lists in the data object for segment 102 will list logical pin 106 in the list List <pin*> m_pins and will list boundary pin 100 in the Ppin list List <pin*> m_Ppins. The segment 118 will list just boundary Ppins 100 and 114 in the Ppin list and will not list any logical pins. The segment 104 will list Ppin 114 in its Ppin list and will list logical pin 94 in its logical pin list. In some embodiments, the lists of pins will contain pointers to the pin objects for the pins on the list. In other embodiments, the pin lists will contain the data that defines the pins themselves.

TABLE-US-00006 class Instance { Cellview *m_parentCellview; List<Pin> m_pins; // connect to external nets Cellview m_internals; // functionality of the instance };

Class instance points to the parentCellview in the logical netlist and lists the pins to which the instance and cellview m_internals defines the functionality of the circuit.

Referring to FIG. 1, there is shown a symbolic diagram of a logical hierarchy for a field programmable gate array or an ASIC. The hierarchy is a three level hierarchy. For the sake of example, assume node 10 represents a system bus, node 12 represents an arithmetic logic unit (ALU) and node 14 represents the control block. To understand how the logical netlist is used to generate a new physical netlist, refer to FIG. 2.

FIG. 2 is a flowchart of the generic process carried out by a floor planner tool according to the teachings of the invention to convert a logical netlist into a physical netlist defining physical blocks which define the same circuit as is defined in the logical netlist.

Step 18 represents the process of reading the original logical netlist prepared by the designer into the floor planner tool according to the invention. In step 20, the floor planner tool makes an initial physical block hierarchy from the top level of the netlist hierarchy. This results in the creation of a root node 24 in FIG. 1 which represents the logical blocks 10, 12 and 14 in FIG. 1. This is done to mimic the operation of prior art floor planner tools, but it can be eliminated in some embodiments and step 18 then transitions directly to step 22.

Significantly, the physical netlist does not replicate in memory all the data that defines the logical blocks 10, 12 and 14 as that would be redundant and use more memory space than is necessary. Instead, each node in the physical netlist is a data structure with a pointer or pointers to the appropriate data in the appropriate logical blocks of the logical hierarchy that define the circuitry that is to be located within that Pblock. In the example of FIG. 1, node 24 of the physical netlist has three pointers, represented by line 16 to the logical blocks 10, 12 and 14. Each of the other instances in the physical hierarchy which is the same circuit as an instance in the logical hierarchy has a pointer in the appropriate data structure of the physical hierarchy to point to the corresponding instance in the logical hierarchy. This allows the overall data structure of the physical hierarchy to be much less voluminous since the data in the data structure of the logical hierarchy which defines instances (circuits) in the physical hierarchy does not have to be repeated in the data objects of the physical hierarchy.

Step 22 is a key step. There, new Pblocks for the physical hierarchy are defined from the initial Pblock hierarchy by laying out the floorplan of the circuit in the way that makes the most physical sense. That is, circuits that need to be close to each other to keep their nets short are put in the same Pblock regardless of whether those circuits are in different logical blocks of the logical netlist hierarchy. This is a major difference and improvement over prior art floor planner tools. Specifically, a floorplanner tool according to the teachings of the invention allows invasion of logical block boundaries to gather up primitives or pieces of logic from different logical blocks that need to be placed close together or clustered on the chip into the same Pblock so that the place and route tool will place these circuits close together in the final layout of the chip. In other words, physical hierarchy supplies the place and route tool with much more definitive guidance regarding placement and clustering of circuits in the final design so as to improve the performance of the final chip layout provided by the place and route tool.

FIG. 3 is a flowchart of a process a user follows to create a floorplan with a floor planner tool according to the invention. The steps are: 1. Import a logical netlist and initialize a new floorplan repeat { 2. Define a new pblock, usually by drawing a rectangle to designate what area on the chip is devoted to circuitry to be included within this pblock. 3. Drag and drop any number of instances from the logical hierarchy browser into the pblock until satisfied with the floorplan 4. Export floorplan directives to guide the place & route tool

In step 1, represented by block 26, the user reads a logical netlist defining a chip to be laid out into a workstation upon which the floor planner tool according to the invention is resident. A new floorplan is initialized and this causes the workstation to display a blank area representing the chip surface upon which the circuitry is to be integrated. More than one floorplan can be initialized so that the designer can experiment with multiple chip floorplans. This is discussed further in connection with FIG. 14.

In the preferred embodiment, the logical netlist and the floorplan are displayed in side-by-side relationship on the workstation display to facility the operation of step 3. In the preferred embodiment, the displayed logical netlist has check boxes displayed next to each instance which are checked when the user either assigns the instance to a pblock or when the instance is automatically assigned to a pblock by the operation of the PTree Update process described below. The check boxes give visual feedback to the designer regarding which instances have been assigned to a pblock and which have not.

In some embodiments, the logical netlist is represented by a entry in a logical tree such as is displayed in the left pane of Windows explorer with the detailed instances on the logical netlist displayed in the right window when the logical netlist entry in the left pane is selected. In this embodiment, the operation of dragging and dropping of step 3 is altered so as to use copy and paste commands. A user would select an item from the logical netlist, give the copy command, move to the floor plan display, place the insertion point in the desired block, and give the paste command. In other embodiments, the user can give text commands to create, size and locate pblocks and then to assign particular instances to particular pblocks.

The step of initializing the floorplan is carried out according to the following process and using the following data structure:

TABLE-US-00007 Initializing the Floorplan class Floorplan { // data members Array<pblock*> m_instanceAssignments; // instance to pblock pointer lookups pblock m_rootpblock; };

Each floorplan includes an array (m_instanceAssignments) that contains a reference to a pblock for all logical instances (both hierarchical and primitive) in the design. In other words, the array m_instanceAssignments is an array of pointers which define which logical instances are in each pblock. the array is a cone column table with multiple rows. Each row corresponds to one instance and the row number is referred to as the index. The content of the array at that row number is a pointer to the pblock to which that instance has been assigned. This array can be used to quickly determine which pblock contains any given instance (circuit) on the logical netlist. The floorplan also is initialized by creating a single `root` pblock for itself--the top of the physical hierarchy--that will contain all other pblocks and logical instances in the physical hierarchy. The array m_instanceAssignments is then initialized to indicate that all logical instances in the design are contained by the root pblock. This is the "starting point" for all new floorplans. The notation pblock m_rootpblock is an identifier of the root pblock which the floorplan object owns. Because all other pblocks in the physical hierarchy are encompassed within the root pblock, the class floorplan object owns all the pblocks in the physical hierarchy.

Step 2, represented by block 28 in FIG. 3, represents the process of creating a pblock on the floorplan. This is done by drawing a blank rectangle on the floorplan in the area where the circuitry to be included within this pblock is to be located on the chip. This can be done as many times as desired. Each pblock can be included within the root pblock or within another pblock previously created.

Step 3 involves moving instances of circuitry from the logical netlist to