IC layout buffer insertion method

An integrated circuit (IC) layout system designs nets for interconnecting cells forming modules of a hierarchical IC design. Each module is defined as having one or more ports through which the nets extend when linking cells forming different modules. The layout system automatically inserts buffers into selected segments of the nets to reduce signal path delays through the nets and assigns the inserted buffers to selected modules. However the layout system inserts buffers only into those net segments for which a buffer insertion would not alter the number of ports any module needs to accommodate the net.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates in general to computer-aided design (CAD) tools for producing layouts based on modular integrated circuit (IC) designs, and in particular to a method for determining whether a buffer inserted by a CAD tool into any signal path within an IC layout will alter the ports of any module of the IC.

2. Description of Related Art

FIG. 1is a data flow diagram illustrating an integrated circuit design process in which an IC designer initially generates a register transfer language (RTL) netlist1describing an IC as a set logic blocks linked though signal paths (“nets”). An RTL netlist1often describes the logic blocks somewhat abstractly, using mathematical statements to define the boolean logic they are to carry out. However after having created RTL netlist1, the designer may employ a synthesis tool2to convert the RTL level netlist into a “gate level” netlist4describing the logic blocks more concretely by referencing the particular circuit devices that are to implement the logic.

As illustrated inFIG. 2, the gate level netlist4ofFIG. 1typically organizes the IC design10into a hierarchy of interconnected leaf cells12and modules14. The leaf cells12, represented by small circles inFIG. 1, are standard circuit components described by entries in a cell library3(FIG. 1). Thus rather than directly describing each leaf cell12, gate level netlist4indirectly describes the cell by referencing its corresponding entry in cell library3. Leaf cells12may range from small standard circuit components such as individual transistors and logic gates, up to very large components such random access memories and microprocessors. Gate level netlist3organizes the cells12forming the IC into a hierarchy of modules14with each module14residing at any given level of the design hierarchy being formed by a set of interconnected leaf cells and/or modules residing at a next lower level of the hierarchy.

Although gate level netlist4identifies the cells forming the IC and names the nets that carry signals between their terminals, it does not describe how the components are to be arranged in a semiconductor substrate and does not indicate how the nets that interconnect them are to be implemented within the substrate. Therefore, after creating gate level netlist4, the designer uses a layout tool5(FIG. 1) to generate a layout6for the IC design described by gate level netlist4. Layout6describes how and where each cell is to be formed in a semiconductor substrate and indicates how the nets interconnecting them are to be formed and routed. Layout tool5consults cell library3to determine the size, shape and internal layout of each leaf cell. As it designs the nets interconnecting cell terminals, layout tool5tries to satisfy various constraints7the designer places on cell placement and path routing. Layout “tool”5may be implemented as a collection of separate tools for carrying out all the various procedures needed to convert a gate level netlist4into IC layout6in a manner that satisfies constraints7including, for example, tools for floor planning, placement and routing, clock tree synthesis, and timing analysis.

During the design process, the designer employs simulation and verification tools11to check the IC design specified by RTL and gate level netlists1and4to determine whether they describe an IC, or selected modules thereof will behave as expected. After layout tool5generates IC layout6, a netlist compiler8processes layout6to produce another “layout level” netlist9modeling the circuit as a set of library cells interconnected by the nets designed by layout tool5. The inclusion of behavioral models of the nets renders layout level netlist9a more accurate model of the behavior of the IC than RTL and gate level netlists1and4. The designer may again employ simulation and verification tools11to determine whether the IC the layout level netlist9describes will behave as expected.

RTL level and gate level netlists1and4IC usually describe an IC as a modular hierarchy because the designer usually finds a hierarchical IC design easier to comprehend and manipulate than a “flat” design consisting only of interconnected leaf cells that are not organized into modules. A designer often creates, simulates and verifies each module separately before assembling them into the full netlist description of the IC.

However a typical layout tool5ignores the modular, hierarchical nature of the IC design described by gate level netlist4and places each leaf cell without regard to its position in the modular design hierarchy. Thus leaf cells forming separate modules can be intermingled to some extent within layout6. The layout level netlist8derived from flat layout6therefore typically describes a flat IC design, rather than a hierarchical IC design. The loss of modularity of the layout level netlist version of the IC design makes it difficult for the designer to separately simulate or verify the behavior of each module of the design because the modules no longer exist as identifiable entities at the layout level of the design. Thus the designer is unable to easily compare synthesized behavior of any particular module of the RTL or gate level netlist design with the collective behavior of cells of the layout level netlist design that would otherwise have formed that module.

U.S. patent application Ser. No. 10/117,761, entitled “IC Layout System Employing a Hierarchical Database”, filed Apr. 3, 2002 and incorporated by reference herein, describes a layout tool that compiles gate level netlist4into a hierarchical database13(as depicted inFIG. 1herein) that keeps track not only of the position of each cell within layout6but also of the position of each cell of the design within the modular hierarchy defined by4gate level netlist4. With such information available in database13, the designer may direct layout tool5to place cells forming selected modules within separate and distinct areas of the semiconductor substrate. Although such restrictions on cell placement can make it more difficult for layout tool5to place and route the IC design, restricting selected modules to distinct areas of the substrate provides some advantages. For example, when the design of a module placed in a distinct area of a substrate is changed, layout tool5may be able to subsequently modify the layout of that module only without having to modify the layout of any other portion of the IC, provided that the dimensions of the space needed to contain the revised module and the number, nature and position of the module's input and output (I/O) terminals (ports) remain unchanged.

A hierarchical database13that remembers how cells are organized in the modular design hierarchy also enables netlist compiler8to produce a layout level netlist9in which cells are organized into a modular hierarchy that is analogous to that of and gate level netlist4. This would make it easier for the designer to compare simulation and verification results of the gate and layout level netlists4and9for all modules, even modules that are not placed in distinct areas of the substrate. Unfortunately, in the course of generating layout6, layout tool5can alter the definition of a module in a way that makes it more difficult to compare simulator results for that module before and after placement.

As discussed above, gate level netlist4defines each module residing at any given level of the hierarchy as being a collection of interconnected leaf cells and/or other modules residing at a lower level of the hierarchy. A module's “ports” are the input/output terminals of the module that are connected to the nets linking the module's cells with cells of other modules. Those module ports form a part of a module's definition in RTL and gate level netlists1and4. When a simulator11simulates the behavior of a particular module described by the RTL or gate level netlist1or4, it generates data describing the behavior of signals passing in an out of the module ports via those nets. To make it easy to compare results of simulating a corresponding module described by layout level netlist9, that layout level module should include the same set of ports as the corresponding module described by RTL and gate level netlists1and4.

However, in the course of designing the nets that interconnect the cells forming the modules, layout tool5can alter the number and nature of ports a module may need to accommodate one or more of the nets by inserting buffers into the nets to decrease signal path delays. Even though compiler8may be able to compile layout6into a hierarchical layout level netlist9, simulation and verification results of some of the modules described by layout level netlist9may not be directly comparable with simulation and verification results of corresponding modules described by the RTL and layout level netlists1and4because corresponding modules may not have the same set of ports.

FIG. 3illustrates a hierarchy of modules A–E as might be depicted by gate level netlist4ofFIG. 1. Module A includes a pair of gate cells18and19, and modules B and C include gate cells20and21, respectively. Within the design hierarchy defined by gate level netlist4ofFIG. 1, modules B and C are submodules (“descendants”) of a common “ancestor” module D, and modules A and D are in turn descendants of their common ancestor module E. The output of cell18drives inputs of cells19–21via a common net22entering the modules though various ports P1–P4. While gate level netlist4describes modules A–D as having ports P1–P4, respectively, interconnected by net22, it does not place any restriction on the manner in which layout tool5might route signal paths forming net22between modules ports and to the gate terminals within the modules.

A designer will often want delays through selected paths between cells within the IC to remain below specified maximum path delays and will therefore impose constraints7(FIG. 1) on the layout directing layout tool5to keep those signal path delays within the specified maximums. Therefore after layout tool5generates layout6, it employs a timing analysis tool to calculate the delays within the routing paths of interest based on the physical characteristics of the paths. Where path delays are excessive, layout tool5inserts buffers in various segments of the signal paths as necessary to reduce path delays. The capacitance of a signal path contributes to signal path delay by increasing the rise and fall time of signal edges, and when layout tool5places a buffer in a path segment, the buffer supplies additional charging current that reduces signal rise and fall times, thereby reducing path delay.

When layout tool5inserts a buffer in a signal path, it updates hierarchical database13to indicate that the buffer has been incorporated into the IC and assigns the buffer to a particular module of the hierarchical design. Compiler8thereafter adds the buffer to the indicated module when generating layout level netlist9. Simulation and verification tools11may then account for the affects of the inserted buffer when simulating or verifying module behavior.

Since adding a buffer to a module of layout level netlist9does not alter the logic of a module, the buffer does not necessarily alter the module's definition in a way that renders simulation and verification results for that module any less comparable with simulation and verification results for a corresponding module of gate level netlist4. However depending on how a signal path is routed within and between modules, depending on which segment of the signal path receives the buffer insertion, and depending on the module to which the inserted buffer is assigned, insertion of the buffer can force compiler8to alter the number of ports of one or more modules of layout level netlist9needed to accommodate the net. When simulating and verifying behavior of a module, the designer is usually interested in the behavior of the signal appearing at the module's ports. Thus when the layout tool5alters the number of ports of a module, it becomes more difficult for the designer to compare gate level and layout level simulation and verification results. Changing the number of ports of a module during the layout process also makes it impossible to alter the layout of that module only without having to also alter the layout of other modules that communicate with it through those ports.

FIG. 5illustrates how layout tool5might generate a modular netlist from the layout ofFIG. 4after the layout tool has inserted a buffer24in the net to decrease the path delay from cell18to cells20and21. In this example layout tool5has assigned buffer24to a portion of module E that is external to its descendant modules A and D. Here the insertion of buffer24into the net in module E outside of modules A or D does not affect the number of ports of any module. As illustrated inFIGS. 6 and 7, layout tool5could also have assigned buffer24to a portion of module D outside modules B and C or to module A without having affected the nature or number or ports of any module.

FIG. 8illustrates an alternative in which layout tool5assigns buffer24to module B. This alternative forces compiler8to increase the number of ports of module B from one to two in layout level netlist9because it has to “split” port P2into two separate ports. In such case, simulation and verification results for module B of layout level netlist9ofFIG. 1would not be port-by-port comparable with simulation and verification results for the corresponding module B of the RTL and gate level netlist1and4as depicted inFIG. 3.

FIGS. 4–8demonstrate that the insertion of buffer24into the net linking cell18to cells20and21may or may not require compiler8to alter the number of ports for module B, depending in part on the module to which the inserted buffer24is assigned. With buffer24assigned to module A as inFIG. 7, no change is required in the number of module ports. However with the buffer assigned to module B as inFIG. 8, there is no way for compiler8to create a module B in layout level netlist9having only a single port associated with the net linking cell18to cells19–21.

FIG. 9illustrates another net layout tool5might create to link cell18to cells19–21.FIGS. 10–13illustrate alternative approaches layout tool5might take for reducing path delay from cell18to cells19and21without affecting the path delay to cell20. InFIG. 10a buffer26inserted into segment27is assigned to module A. This buffer insertion plan requires compiler8to unacceptably split port P1of module A and port P4of module D, thereby adversely affecting the module definition of both ports.FIG. 11shows that assigning buffer26to module E at the same hierarchical level as modules A and D splits ports P1and P4. Assigning buffer26to module A would also split ports P1and P4.

FIG. 12illustrates a buffer insertion plan in which layout tool5inserts separate buffers28and30into segments29and31of the network ofFIG. 9. This approach reduces signal path delays from cell18to cell19and21but does not split any module ports. Although port P1appears to be split inFIG. 12, compiler8would not treat the two occurrences of port P1as separate ports because segment27ties them together so the two P1ports convey the same signal. The same is true with respect to port P4.

FIGS. 9–11demonstrate that in some cases inserting a buffer into one segment of a net will change the number of ports of one or more modules regardless of the module to which the buffer is assigned.FIGS. 9–12also show that it is possible to insert buffer into some, but not all, segments of a net without splitting module ports.

A buffer insertion can also cause a reduction in the number of module ports. For example assume that, as illustrated inFIG. 13, gate level netlist4ofFIG. 1defines module A as having two ports P1A and P1B as illustrated inFIG. 13, and that ports P1A and P1B are tied together in module E, outside of module A. When layout tool5inserts a buffer32as illustrated inFIG. 14to decrease the path delay between cells18and19, with buffer32being assigned to module E, then there is no change to the number of module A ports. However if layout tool assigns buffer32to module A as illustrated inFIG. 15, then compiler8ofFIG. 1would have show port P1B as being disconnected from the net. Simulation and verification results for module A of the layout level netlist9(FIG. 1) would therefore no longer be directly comparable to the results of a corresponding module A of RTL and gate level netlists1and4on a port-by-port basis.

The foregoing examples demonstrate that for compiler8ofFIG. 1to produce a hierarchical layout level netlist9in which each module has the same set of ports as a corresponding module of gate level netlist4, it is necessary for layout tool5to avoid inserting buffers in a way that spits module ports or disconnects them from the net. What is needed is a system for enabling a layout tool to determine when a proposed buffer insertion will split or disconnect a module port so that the layout tool will know to choose an alternative buffer insertion approach when adjusting path delays in any net.

BRIEF SUMMARY OF THE INVENTION

An integrated circuit (IC) layout system determines positions within a semiconductor substrate of each cell forming modules of a hierarchical IC design. The layout system also designs nets for interconnecting the cells. Each module is defined as having one or more ports through which the nets extend when linking cells forming different modules. The layout system automatically inserts buffers into selected segments of the nets to reduce signal path delays through the nets and assigns the inserted buffers to selected modules.

However in accordance with the invention, the layout system inserts buffers only into those net segments for which a buffer insertion would not alter the number of ports any module needs to accommodate the net.

To determine whether insertion of a buffer into a net segment would cause a change in the number of ports of any module, the layout system first determines the lowest level modules containing ports interconnected to the net downstream of the buffer and then assigns the buffer to a lowest common ancestor module of those lowest level modules. The layout system then inserts the buffer into the segment only when the buffer insertion does not split a module port. A split module port is detected when the port is found to be connected to the net both upstream and downstream of the buffer.

The claims appended to this specification particularly point out and distinctly claim the subject matter of the invention. However those skilled in the art will best understand both the organization and method of operation of what the applicant(s) consider to be the best mode(s) of practicing the invention, together with further advantages and objects of the invention, by reading the remaining portions of the specification in view of the accompanying drawing(s) wherein like reference characters refer to like elements.

DETAILED DESCRIPTION OF THE INVENTION

This specification describes one or more exemplary embodiments and/or applications of the invention considered by the applicant(s) to be the best modes of practicing the invention. It is not intended, however, that the invention be limited to the exemplary embodiment(s) described below or to the particular manner in which the exemplary embodiments operate.

FIG. 16is a data flow diagram depicting an integrated circuit design process in accordance with the invention that can be viewed as an improvement to the prior art design process ofFIG. 1. Similar elements are therefor identified by similar reference characters. Referring toFIG. 16, an IC designer initially generates a register transfer language (RTL) netlist1describing an IC as a set of circuit nodes (“nets”) coupled through abstractly described blocks of logic. Thereafter, using synthesis tool2, the designer converts RTL level netlist1into a gate level netlist4describing the logic blocks in terms of the circuitry needed to implement the logic.

As exemplified inFIG. 2, gate level netlist4organizes the IC design10into a hierarchy of interconnected leaf cells12and modules14. After creating gate level netlist4, the designer uses a layout tool40to generate a layout6for the IC design described by gate level netlist4. U.S. patent application Ser. No. 10/117,761, filed Apr. 3, 2002 (incorporated herein by reference) describes a layout system implementing many of the features of layout tool40. Consulting cell library3to determine the size, shape and internal layout of each leaf cell12layout tool40finds a suitable position for each leaf cell within a semiconductor substrate and determine how to route signal paths interconnecting cell terminals in the manner described by the netlist. In developing layout7, layout tool40tries to satisfy various constraints7the designer places on cell placement and path routing.

Layout tool40maintains a hierarchical database13referencing each cell of layout6and indicating its position within the design hierarchy. When told to do so by constraints7, layout tool40may place some of the modules of the design in separately identifiable areas of the substrate. However cells forming all other modules of the design may be placed irrespective of their position in the modular hierarchical and may be intermingled in the substrate. Consulting database13to determine the module to which each cell of layout6is assigned. A netlist compiler8converts layout6into a hierarchical layout level netlist9, consulting database13to determine the module to which each cell is assigned. During the design process, the designer may employ simulation and verification tools11to check IC design specified by RTL, gate and layout level netlists1,4and9to determine whether the modules they describe will behave as expected. For example the designer may employ a circuit simulator to produce waveform data inditing how signal produces at the input/output terminals (ports) of modules change with time when the IC is stimulated with a defined set of input signals.

As it generates layout6, layout tool40may insert buffers into various segments of nets it creates for routing signals between terminals of the cells forming the ICs. The buffers reduce signal path delays to keep them within maximum limits specified by constraints7. The buffers may be either inverting or non-inverting buffers, but when inverting buffers are employed, they are inserted in multiples of two within any signal path between transmitting and receiving cells to avoid altering signal states at the receiving cell. When layout tool40inserts a buffer into a segment of any net within layout6, it assigns the buffer to one of the modules and then updates database13to include a reference to the buffer. Thereafter netlist compiler8includes the inserted buffer in that module of the layout level netlist9.

Synthesis tool2, netlist compiler8and simulation and verification tools11, layout tool40and netlist compiler8are suitably implemented by storing software programs on computer-readable media which are then supplied as program inputs to one or more conventional, general purpose computers, thereby causing the computer(s) to carry out the functions of these tools. Well-known computer-readable media suitable for storing the software include but are not limited to, compact disks, floppy disks, hard disks, and random access or read only memory. Cell library3is suitably implemented as a database included in the computer-readable media accessed by the computer(s). RTL level netlist1and constraints7may be supplied to the computer(s) implementing Synthesis tool2, simulation and verification tools11and layout tool40in the form of data contained on the computer-readable media or through any appropriate user interface. The computer(s) implementing synthesis tool2, layout tool40and netlist compiler8create and maintain data files in computer-readable media, the data files implementing gate level netlist4, hierarchical database13, layout8, layout level netlist9.

The invention relates in particular to a “buffer insertion verification” (BIV) tool42that layout tool40consults before inserting a buffer into any signal path. BIV tool42is suitably implemented in the form of software stored on computer-readable media which causes a computer (preferably the computer that also implements layout tool40) to carry out the function of BIV tool42. BIV tool42may be incorporated into software implementing layout tool5as a subroutine or procedure thereof.

As discussed above, when a layout tool inserts a buffer into a signal path, it is possible that netlist compiler8may have to alter the number an nature of ports of one or more modules when generating layout level netlist9. In such case a lack of correspondence between number and nature of module ports would render results of simulation and verification of a module of the layout level netlist9less directly comparable with results of simulation and verification of a corresponding module of gate level net list4. Therefore when layout tool40wants to insert a buffer into some segment of a net within layout6, it requests BIV tool42to approve the proposed buffer insertion.

BIV tool42first selects a module to which the buffer can be assigned so as to render the buffer insertion least likely to alter the number of module ports connected to the network. BIV tool42then determines whether insertion of the buffer assigned to the selected module in the net segment selected by layout tool5will cause a change in the number of ports of any module. If the buffer insertion has no effect on the number of ports of any module of the IC, BIV tool42replies to the buffer insertion request by telling layout tool40that the proposed buffer insertion is acceptable and indicating the module to which the buffer is to be assigned. Layout tool40then updates database13to indicate that the buffer has been inserted into the desired net segment and that the buffer has been assigned to the module chosen by BIV tool42. Otherwise when BIV tool42determines that the buffer insertion will change the number of ports, its reports back to layout tool40that the proposed buffer insertion is unacceptable, so that layout tool40develop another buffer insertion plan.

FIG. 17is a flow chart illustrating how BIV tool42responds to a buffer insertion request from layout tool40. BIV tool42initially (step50) determines the lowest level modules containing ports that are downstream of the “target” segment of the net that is to receive the buffer. In the example ofFIGS. 4–8, when reviewing the proposed insertion of buffer24into the target segment, BIV tool42finds that only ports P2and P3are downstream of the buffer and that those ports reside in modules B and C.

BIV tool42then (step51) assigns the buffer to the lowest level common ancestor module (D) of the modules (B and C) containing the downstream ports, as illustrated inFIG. 6. BIV tool42next determines whether insertion of the buffer will cause an increase in the number of ports of any module by splitting a port. To do so, BIV tool42(step52) determines whether the same port appears both upstream and downstream of buffer, as this indicates that the buffer insertion has split a module port. If the same port does not appear both upstream and downstream of the buffer, BIV tool42responds to the request by accepting the buffer insertion (step52). Layout tool40then appropriately updates database13to incorporate the buffer into the IC design.

For example, having assigned buffer24to module D as illustrated inFIG. 6(step52), BIV tool42finds only port P1upstream of buffer24and finds only ports P2, P3and P4downstream of the buffer. Since the same port does not appear both upstream and downstream of buffer24(step54), BIV tool42reports back to layout tool40that the proposed insertion of buffer24is acceptable (step53). Note that by assigning buffer24to the lowest level common ancestor module D of the modules B and C containing downstream ports, BIV tool42avoids the possibility of splitting a port by assigning buffer24too low in the modular hierarchy as illustrated, for example, inFIG. 8.

In the example ofFIGS. 9–11, when layout tool40proposes inserting a buffer26into net segment27, BIV tool42first checks database13to determine the lowest level modules containing the ports downstream of buffer26(step50) and finds downstream ports P1and P3reside in modules A and C, respectively. BIV tool42next (step51) determines from database13that module E is the lowest level common ancestor module of the modules A and C containing downstream ports P1and P3and therefore assigns buffer26to module E as illustrated inFIG. 11. However, at step52, looking downstream of buffer26, BIV tool42finds ports P1, P4and P3, and looking upstream of buffer26, BIV tool42finds ports P1, P2and P4. Since it finds ports P1and P4both upstream and downstream of buffer26, BIV tool42determines that assigning buffer26to module E has split those ports and therefore does not accept the assignment of buffer26to module E. It instead tries to reassign the buffer to another level module.

To do so, BIV tool42first determines the lowest level modules containing ports upstream of the buffer to be inserted (step54). In this case BIV tool42sees modules A, B and D contain ports P1, P2and P4upstream of buffer26. It therefore re-assigns buffer26to the lowest level common ancestor (module E) of all modules containing upstream ports (step55). It then determines whether the same port appears both upstream and downstream of the re-assigned buffer (step56). If not, BIV tool42accepts the buffer insertion (step57). However in the example case, with buffer26assigned (again) to module E, ports P1and P4appear both upstream and downstream of buffer26. BIV tool42therefore responds to the buffer insertion request by indicating that the proposed buffer insertion is unacceptable (step58). Layout tool40may then try inserting one or more buffers into other segments of the net, or may try re-designing the net.

In the example ofFIGS. 13–15, when layout tool40proposes inserting buffer32into the net between ports P1A and P1B, BIV tool42finds only port P1B residing downstream of buffer32(step50) and therefore, as illustrated inFIG. 14, assigns buffer32to module E, the lowest level common ancestor of the lowest level module A containing port P1B (step52). Finding no single port appearing both upstream and downstream of buffer32(step54), BIV tool42notifies layout tool40that the proposed buffer insertion is acceptable (step58). Note that by assigning buffer26to the lowest level ancestor module E of module A rather than to module A itself, as illustrated inFIG. 15, BIV tool42avoids the possibility of the buffer insertion disconnecting port P1B from the net, thereby preserving the number of active module A ports.

FIG. 18illustrates a method for carrying out step52or56ofFIG. 17, in which BIV tool42determines whether any port appears both upstream and downstream of the buffer.FIG. 18depicts the net ofFIG. 4in which layout tool40has proposed inserting a buffer in a net segment S7extending between ports P1and P4. In order to determine whether any port appears both upstream and downstream of buffer24, BIV tool42first builds the following Table I representing the net as a tree having an entry for each segment of the net, with the “segments” of the net being separated by ports and branch nodes:

Similarly port count entry for segment S5contains a single data pair [P3,1] indicating one occurrence of port P3because port P3is the only port downstream of segment S5. BIV tool42builds the entry for segment S5incrementing the entry for segment S2to include the count for the port P3traversed when moving down the tree from segment S2to segment S5.

BIV tool42next builds the entry for segment S6, by combining the entries for segments S4and S5. BIV tool42then builds the entry for segment S7by adding an occurrence of traversed port P4to the entry for segment S6and thereafter builds the entry for segment S8by adding an occurrence of traverse port P1to the entry for segment S7. Finally, the entry for root segment S9is generated by summing the entries for segments S3and S8.

At this point the table entry for segment S7indicates the number of occurrences of each port downstream of buffer24.
Downstream ports=[P2,1]+[P3,1]+[P4,1]
To determine the number of occurrences of each port upstream of buffer24, BIV tool42subtracts the entry for segment S7from the entry for root segment S9as follows:

Upstream⁢⁢ports=⁢[P1,1]+[P2,1]+[P3,1]+[P4,1]-⁢[P2,1]-[P3,1]-[P4,1]=⁢[P1,1]
Since ports P2, P3and P4appear downstream of the buffer, only port P1appears upstream of the buffer, BIV42can easily determine that the same port does not appear both upstream and downstream of the buffer. BIV tool42thus reports the proposed buffer insertion to be acceptable.

FIG. 19illustrates the tree BIV42traverses for the net illustrated inFIG. 9where layout tool40has proposed inserting a buffer26in segment27(segment S9ofFIG. 19). BIV tool42, having assigned buffer26to module E as illustrated inFIG. 10, builds the following Table II for that buffer insertion proposal:

Upstream⁢⁢ports=⁢[P1,2]+[P2,1]+[P3,1]+[P4,2]-⁢[P1,1]-[P3,1]-[P4,1])=⁢[P1,1]+[P2,1]+[P4,1]
Comparing the downstream and upstream ports, BIV tool42finds that ports P1and P2appear both downstream and upstream of buffer27, and therefore rejects the proposed buffer insertion.

While those of skill in the art will appreciate that in other embodiments of the invention BIV tool42may employ other approaches to determining whether a proposed buffer insertion will alter a number of module ports, the table-building approach described above is preferred as being computationally efficient.

The foregoing specification and the drawings depict exemplary embodiments of the best mode(s) of practicing the invention, and elements or steps of the depicted best mode(s) exemplify the elements or steps of the invention as recited in the appended claims. However the appended claims are intended to apply to any mode of practicing the invention comprising the combination of elements or steps as described in any one of the claims, including elements or steps that are functional equivalents of the example elements or steps of the exemplary embodiment(s) of the invention depicted in the specification and drawings.