Patent Document

BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to the field of circuit partitioning. More specifically, the present invention relates to the partitioning of a circuit design for the purpose of implementing or emulating the circuit design using a number of reconfigurable logic devices.  
           [0003]    2. Background Information  
           [0004]    [0004]FIG. 1 illustrates a typical prior art approach to partitioning a circuit design for the purpose of implementing or emulating the circuit design using a number of reconfigurable logic devices, such as field programmable gate arrays (FPGA). As illustrated, because of the complexity of modern day circuit designs, typically, a circuit design, such as integrated circuit (IC) design  102  having multiple functional blocks (FB), FB-a  104   a , FB-b  104   b , and so forth, would be provided to a partitioner, such as partitioner  104 , along functional block lines, and correspondingly partitioned. For example, a processor design having an instruction fetch and dispatch block, an arithmetic logic unit (ALU), a floating point processing unit (FPU), an on-chip cache memory block, a bus interface unit, and so forth, would be provided to partitioner  104  along these functional block lines, and correspondingly partitioned.  
           [0005]    As illustrated, the partitioning would results in x 1  partitions  106   a  for FB-a  104   a , x 2  partitions  106   b  for FB-b  104   b  and so forth. The partitions would be provided in turn to a “compiler”, such as compiler  108 , to be correspondingly compiled into a number of corresponding configuration files  110   a - 110   n  for configuring the reconfigurable logic resources of a number of corresponding logic devices to correspondingly implement or realize the constituting elements of the corresponding partitions  106   a - 106   n  of the function blocks  104   a - 104   n . In other words, for x 1 , x 2 , . . . xn partitions  106   a - 106   n  for FB-a  104   a  through FB-n  104   n , x 1 , x 2 , . . . xn configuration files for a total of x 1 +x 2 + . . . xn logic devices would result.  
           [0006]    This prior art partitioning approach may be inefficient in its usage of reconfigurable logic devices for various circuit designs, especially for IC designs where the partitioning of each function block results in one or more “small” partitions of consituting elements. Examples of IC designs where such phenomenon may occur include but are not limited to IC designs having multiple clock domains. In the multiple clock domain case, while the majority of the constituting elements of a functional block would operate in one clock domain, for various purposes, e.g. for interfacing with other function blocks that operate in other clock domains, each function block typically has small groups of consituting elements that operate in one or more of the other clock domains. Since each reconfigurable logic device typically supports only a single clock domain, accordingly the “small” partitions of constituting elements are resulted.  
           [0007]    As those skilled in the art would appreciate that corresponding implementation or realization of these “small” partitions of consituting elements in corresponding logic devices often result in leaving a substantial amount of the reconfigurable logic resources of the corresponding logic devices remain unused. The amount of left over or wastage increases over time, as successive generations of reconfigurable logic devices tend to be equipped with more and more reconfigurable logic resources.  
           [0008]    Accordingly, an improved approach to partitioning a circuit design for implementation or emulation on a number of reconfigurable logic devices is desired.  
         SUMMARY OF THE INVENTION  
         [0009]    A first and a second netlist of a first and a second function block of a circuit design are correspondingly partitioned into at least a first and a second partition, and a third and a fourth partition respectively. The first and third partitions include majorities of the constituting elements of the first and second netlists respectively. The second and fourth partitions include minorities of the constituting elements of the first and second netlists. Placements of the constituting elements of the first and third partitions are correspondingly determined. The second and fourth partitions are merged to form a composite partition, which in turn is partitioned for joint determination of placement of these minority constituting elements of the first and second netlists of the first and second function blocks on logic devices.  
           [0010]    In one embodiment, the second and fourth partitions operate in the same clock domain, while the first and third partitions operate in one or more other clock domains.  
       
    
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0011]    The present invention will be described by way of exemplary embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which:  
         [0012]    [0012]FIG. 1 illustrates a typical prior art approach to partitioning a circuit design with multiple function blocks;  
         [0013]    [0013]FIG. 2 illustrates the partitioning approach of the present invention, in accordance with one embodiment;  
         [0014]    [0014]FIG. 3 illustrates the operation flow of the relevant aspects of the merge function of FIG. 2, in accordance with one embodiment;  
         [0015]    [0015]FIG. 4 illustrates the incorporation of the elements of the present invention in an EDA software suite, in accordance with one embodiment;  
         [0016]    [0016]FIG. 5 illustrates the incorporation of the EDA software suite of FIG. 4 in a workstation, which may be a component of an emulation system, in accordance with one embodiment; and  
         [0017]    [0017]FIG. 6 illustrates the incorporation of the EDA software suite of FIG. 4 in a networked server, in accordance with one embodiment.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0018]    In the following description, for purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without the specific details. In other instances, well known features are omitted or simplified in order not to obscure the present invention.  
         [0019]    Parts of the description will be presented using terms such as accounts, IDs, objects, end-user interfaces, buttons, and so forth, commonly employed by those skilled in the art to convey the substance of their work to others skilled in the art. Parts of the description will be presented in terms of operations performed by a computer system, using terms such as creating, empowering, and so forth. As well understood by those skilled in the art, these quantities and operations take the form of electrical, magnetic, or optical signals capable of being stored, transferred, combined, and otherwise manipulated through mechanical and electrical components of a digital system; and the term digital system include general purpose as well as special purpose data processing machines, systems, and the like, that are standalone, adjunct or embedded.  
         [0020]    Various operations will be described as multiple discrete steps performed in turn in a manner that is most helpful in understanding the present invention, however, the order of description should not be construed as to imply that these operations are necessarily order dependent, in particular, the order the steps are presented. Furthermore, the phrase “in one embodiment” will be used repeatedly, however the phrase does not necessarily refer to the same embodiment, although it may.  
         [0021]    Referring now FIG. 2, wherein a block diagram illustrating an overview of the method of the present invention for partitioning and placing a circuit design onto a number of reconfigurable logic devices, is shown. As alluded to earlier, the partition and placement may be performed for the purpose of implementing or emulation the circuit on the reconfigurable logic devices, which may e.g. be general purpose or emulation specific FPGAs. Examples of general purpose FPGAs include but are not limited to those available from manufacturers such as Xlinx and Altera, both of San Jose, Calif.; and examples of emulation specific FPGA include but are not limited to the FPGA disclosed is U.S. Pat. No. 5,573,388.  
         [0022]    As illustrated, the partitioning and placement process of the present invention starts as the prior art process with the netlists of the function blocks of a circuit design, such as function blocks  104   a - 104   n of IC design  102 , being provided along function block lines to a partitioner, such as partitioner  104 , to be correspondingly partitioned along function block lines into partitions  106   a - 106   n . That is, the partitioning results in x 1  partitions  106   a  for FB-a  104   a , x 2  partitioned partitions  106   b  for FB-b  104   b , and so forth.  
         [0023]    However, from this point on, the process of the present invention advantageously diverges from the prior art. Instead of correspondingly compiling all partitions  106   a - 106   n  into configuration files to configure corresponding reconfigurable logic devices to implement or emulate the constituting elements of the partitions  106   a - 106   n , partitions  106   a - 106   n  are provided to merger  112  for processing.  
         [0024]    Merger  112  analyzes the partitions  106   a - 106   n , and accords them different treatment in accordance with the results of the analysis. More specifically, in accordance with one embodiment, merger  112  determines if each of the partitions  106   a - 106   n  is to be considered a “majority” partition or a “minority” partition. In one embodiment, a “majority” partition is a partition that contains a percentage of the constituting elements of the corresponding function block in excess of a predetermined threshold percentage (e.g. 5%), whereas a “minority” partition is a partition that contains a percentage of the constituting elements of the corresponding function block that is smaller than the predetermined threshold percentage.  
         [0025]    The “majority” partitions are passed onto compiler  108  for corresponding compilation into configuration files  110   a - 110   n  for configuring corresponding reconfigurable logic devices to implement or realize the partitions. Accordingly, y 1  configuration files for y 1  logic devices will result for partition  106   a , y 2  configuration files for y 2  logic devices will result for partition  106   b , and so forth, where y 1 , y 2 , . . . yn are less than or equal to x 1 , x 2 , . . . xn, respectively.  
         [0026]    The “minority” partitions, on the other hand are merged into one or more (z) composite partitions  114 . In one embodiment, the “minority” partitions are merged in accordance with the operating clock domains of the “minority” partitions. That is, “minority” partitions with the same operating clock domain are merged together across function blocks. The merged composite partitions in turn are provided to partitioner  104  to be partitioned again. As shown, the partitioning results in w 1  through wn cross function composite partitions  116 . These composite partitions  116  are then in turn provided to compiler  108  for compilation into w 1  through wn configuration files for correspondingly configuring a sum of w 1  through wn reconfigurable logic devices to implement or realize the constituting elements of these partitions. Experience has shown that a smaller number of reoconfigurable logic devices will be required to implement or realize the circuit elements of these “minority” partitions, as compared to the prior art approaches.  
         [0027]    For example, if a dozen minority partitions are merged into two composite partitions, the two composite partitions are re-partitioned, with the first composite partition partitioned into e.g. 2 composite partitions and the second composite partition partitioned into e.g. 3 partitions. The 5 composite partitions are then compiled into 5 configuration files for configuring 5 reconfigurable logic devices. Thus, 5 reconfigurable logic devices will be used to implement or realize the circuit elements of these “minority” partitions, as opposed to a dozen of reconfigurable logic devices under the prior art.  
         [0028]    Except for merger  112 , partitioner  104  and compiler  108  are intended to represent a broad range of such elements known in the art. Accordingly, except for merger  112 , which will be described in more below, partitioner  104  and compiler  108  will not be further described. From the description to follow, and as it is known for partitioner  104  and compiler  108 , each of these elements, merger  112 , partitioner  104  and compiler  108  may be implemented in any one or more of a number of programming languages known in the art.  
         [0029]    Referring now to FIG. 3, wherein a block diagram illustrating the operating flow of the relevant aspects of merger function  112  of FIG. 2, in accordance with one embodiment. As illustrated, the process starts with merger function  112  selecting a function block for analysis, block  302 ; more specifically, the partitions of the function block. As will be apparent from the totality of the description, the order through which the function blocks are selected for analysis is immaterial, as long as they all get selected and analyzed. At block  304 , merger function  112  selects a specific partition of the currently selected function block for analysis. Similarly, the order through which the partitions of a selected function block are selected for analysis is immaterial, as long as they all get selected and analyzed. At block  306 , merger function  112  determines if the selected partition is to be characterized as a “majority” or a “minority” partition, in accordance with e.g. a predetermined percentage threshold as described earlier.  
         [0030]    As described earlier, if a partition being analyzed is to be characterized as a “majority” partition, the partition is provided to compiler  108  for compilation into a configuration file to configure a corresponding reconfigurable logic device to implement or emulate the circuit elements of the partition, block  308 . On the other hand, if the partition being analyzed is to be characterized as a “minority” partition, the partition is merged into a composite partition instead. As described earlier, in one embodiment, the partitions are merged in accordance with their operating clock domain.  
         [0031]    As illustrated, for the embodiment, merger function  112  determines whether a composite partition exists into which the “minority” partition may be merged, block  314 . If such composite partition exists, the “minority” partition is merged into the composite partition accordingly, block  318 . Otherwise, a new composite partition is first created, block  316 , before merging the “minority” partition into the newly created composite partition.  
         [0032]    Upon dispatching a “majority” partition to compiler  108  or upon merging a “minority” partition into a composite partition, the process continues at block  310 , wherein merger function  112  determines if there are additional partitions of the selected function block to be analyzed. If so, the process returns to block  304  and continues from there as earlier described. If not, merger function  112  determines if there are additional function blocks to be analyzed. If so, the process returns to block  302  and continues from there as earlier described. If not, the process terminates.  
         [0033]    [0033]FIG. 4 illustrates the incorporation of the elements of present invention, i.e. partitioner  104 , merger function  112  and compiler  108  into an Electronic Design Automation (EDA) software suite  402 . Beside, partitioner  104 , merger function  112  and compiler  108 , EDA software suite  402  may further include one or more other EDA tools known in the art. Examples of these tools include but are not limited to synthesis tools, place and route tools, design verification check tools, simulation and/or emulation tools, and the like.  
         [0034]    [0034]FIG. 5 illustrates the incorporation of EDA software suite  402  in a workstation  502 . Workstation  502  includes storage medium  506  for storing the implementing programming instructions of EDA software suite  402 . Preferably, storage medium  506  include non-volatile as well as volatile storage for storing “permanent” as well as “temporal” (i.e. working) copies of the implementing programming instructions of EDA software suite  402 . Workstation  502  also includes processor  504  coupled to storage medium  506  to execute the implementing programming instructions of EDA software suite  402 .  
         [0035]    Except for EDA software suite  402  incorporated therein, workstation  502  is otherwise intended to represent a broad range of computer systems known in the art. Suitable systems include but are not limited to those available from Dell Computer of Austin Texas and Hewlett Packard of Palo Alto, Calif.  
         [0036]    For the illustrated embodiment, workstation  502  is a component of emulation system  500 . In addition to workstation  502 , emulation system  500  further includes emulator  512  having a number of reconfigurable logic devices (with reconfigurable logic resources) and reconfigurable interconnect resources for realizing circuit designs. Partitioner  104 , merger  112  and compiler  108  are employed to partition and place a circuit design onto selected ones of the reconfigurable logic resources  514  of emulator  512  in accordance with the more efficient cross function block manner of the present invention. As a result, for an emulator  512  having a given size of reconfigurable logic resources  514 , a large circuit design may be emulated. As those skilled in the art, this is a significant advantage in view of continuous increase in size and complexity of circuit design, and the cost of emulation systems.  
         [0037]    Except for the elements of the present invention incorporated therein, emulation system  500  is also otherwise intended to represent a broad range of emulation systems known in the art. Examples of such emulation systems include but are not limited to the SimExpress and Celaro emulation systems available from the Meta System Division, Les Ulis, France, of Mentor Graphics Corp. of Wilsonville, Oreg., USA.  
         [0038]    [0038]FIG. 6 on the other hand illustrates the incorporation of the EDA software suite  402  having partitioner  104 , merger  112  and compiler  108  of the present invention, onto server  606 . Similar to workstation  502 , server  606  includes storage medium  610  and one or more processor  608  for storing and executing EDA software suite  402 . Server  606  also includes a number of networking/communication resources (not shown) for making EDA software suite  402 , including partitioner  104 , merger  112  and compiler  108  of the present invention available for use by remote client devices  602  across networking fabric  604 .  
         [0039]    Server  606  may be any one of a number of “mid-range” to “high-end” servers known in the art, including but are not limited to those available from manufacturers such as IBM of Armonk, N.Y. and Sun Microsystems of Menlo Park, Calif. Client devices  602  may be any one of a number of networking/communication enabled computing devices known in the art, including but are not limited to those examples enumerated earlier for workstation  502 . Networking fabric  604  is intended to represent private LAN or WAN of “private” enterprises, as well as public networks, such as the Internet.  
         [0040]    Thus, a method and apparatus for partitioning and placement of a circuit design onto reconfigurable logic devices in a cross function block manner have been described. While the method and apparatus of the present invention have been described in terms of the above illustrated embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described. The present invention can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of restrictive on the present invention.

Technology Category: 3