Placement processing for programmable logic devices

[0002] The present invention relates to programmable logic devices (PLDs), such as field-programmable gate arrays (FPGAs), and, more specifically, to computer-aided design (CAD) tools for such devices.

[0003] An FPGA is a programmable logic device having an array of configurable logic blocks (CLBs) connected together via a programmable routing structure. A typical FPGA may have tens of thousands of CLBs, each CLB having a plurality of primitive logic cells (or gates). Primitive cells of a CLB may be interconnected in a variety of ways to implement a desired logic function corresponding to that CLB.

[0004] FIGS. 1A-C illustrate a representative FPGA 100 comprising a plurality of CLBs 102 surrounded by input-output (I/O) blocks 104 and interconnected through a routing structure 106. CLBs 102 are typically connected to form a plurality of nets, one of which, net 108, is depicted in FIG. 1B. Illustratively, net 108 has ten CLBs 102 interconnected via routing structure 106 (not shown in FIG. 1B) as indicated by the solid lines. The physical dimensions of net 108 are characterized by a bounding box 110 shown by the dashed line in FIG. 1B. A different net may include a different number of CLBs 102 and/or I/O blocks 104. Each CLB 102 and/or I/O block 104 may belong to more than one net.

[0005] FIG. 1C shows schematically a representative structure of a configurable logic block. CLB 102 of FIG. 1C includes clusters 112-128. Each cluster has one or more primitive cells and is configured to implement a particular logic function/operation. For example, a cluster may be a look-up table (LUT), D-type flip-flop (DFF), multiplexer (MUX), carry chain, counter, multiplier, etc. Clusters within each CLB 102 may be interconnected in different ways to form one or more groups of clusters. A group may be defined as a set of one or more interconnected clusters in a CLB that are not connected to any other clusters in that CLB. Illustratively, clusters 112-116 are interconnected to form a first group 130 of clusters. Similarly, clusters 118-126 are interconnected to form a second group 132 of clusters. Cluster 128 is not connected to other clusters within CLB 102 and is referred to as an unrelated cluster (i.e., a single-cluster group). However, like all clusters, cluster 128 may be connected to one or more cells/clusters located in one or more different CLBs.

[0006] When an FPGA, such as FPGA 100 of FIG. 1, comprises thousands of CLBs in a large number of nets, the task of establishing the required multitude of interconnections between the CLBs in a net and between the different nets becomes so onerous that it requires CAD implementation. Accordingly, manufacturers of FPGAs including the assignee hereof, Lattice Semiconductor, Inc., develop place-and-route CAD tools to be used, e.g., by their customers (FPGA programmers) to implement their respective circuit designs. Typically, place-and-route software implements an iterative process aimed at producing a circuit configuration that meets certain customer specifications, such as insertion delays between specified pins and/or operation (clock) frequency. However, human intervention is often required to refine/finalize the CAD-optimized circuit configuration. Such intervention is relatively time-consuming and may result in longer time to market and higher product development costs.

[0007] The problems in the prior art are addressed in accordance with the principles of the present invention by a method for placing configurable logic blocks (CLBs) in a programmable logic device (PLD), such as a field-programmable gate array. In certain embodiments, after packing gates/clusters into blocks and then assigning those blocks to CLBs (e.g., using simulated annealing) to generate an initial placement for the PLD, the method changes the packing and/or placement of one or more CLBs prior to performing CLB routing. According to one embodiment, the K most critical paths in the initial placement are identified. For each node (e.g., a primitive cell or a cluster) of the most critical of the K paths (e.g., the path with the longest delay), moving the node to a different CLB located within a certain area adjacent to the current CLB is considered in order to reduce the criticality of that path. A move is applied if certain acceptability conditions are met. After the most critical path is improved, the rest of the identified paths are updated and the procedure is repeated for the new most critical of those K paths. In a preferred implementation, the present invention involves a combination of a net-based placement procedure, such as simulated annealing, with path-based node relocation. The method, which can be automated to reduce human intervention in the design process, improves circuit performance, e.g., by enabling higher circuit operation frequencies.

[0008] According to one embodiment, the present invention is a method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD). According to the method, a mapping of the circuit elements to the CLBs in the PLD is generated, a critical path is selected in the PLD corresponding to the mapping, and, for at least one node of the critical path, node assignment is changed from a current location to a different location based on change of circuit performance corresponding to the change in node assignment.

[0009] According to another embodiment, the present invention is a circuit mapping generated by implementing the previously described method. According to yet another embodiment, the present invention is a machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements the previously described method.

[0010] Other aspects, features, and benefits of the present invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which:

[0011] FIGS. 1A-C show block diagrams of a representative FPGA;

[0012] FIG. 2 is a flowchart of a place-and-route method that may be used for implementing a particular logic circuit using the FPGA of FIG. 1;

[0013] FIG. 3 is a flowchart of a place-and-route method according to one embodiment of the present invention;

[0014] FIG. 4 is a flowchart of a node relocation act in the method of FIG. 3 according to one embodiment of the present invention; and

[0015] FIGS. 5A-B show schematically a node relocation technique that may be used in the method of FIG. 3 according to one embodiment of the present invention.

[0016] Reference herein to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment can be included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments.

[0017] Placement is part of the design process, during which CLB nets (such as net 108 in FIG. 1B) are mapped onto physical locations in a PLD, such as an FPGA. Timing-driven placement (TDP) is a placement method based on optimizing (e.g., minimizing) circuit delays. TDP methods have been classified as either net-based or path-based. Net-based TDP methods seek to control delays, e.g., by imposing on each net a delay upper bound that is related to the size of the net bounding box, such as box 110 for net 108 of FIG. 1B. Path-based TDP methods seek to explicitly take into account delays corresponding to each signal propagation path. Optimization of relatively large FPGAs is typically net-based since explicit enumeration of all paths becomes a difficult task.

[0018] FIG. 2 is a flowchart of a place-and-route method 200 that may be used for implementing a particular logic circuit using a PLD such as FPGA 100 of FIG. 1. In process block 202 of method 200, a logic circuit design is loaded into a CAD tool. In block 204, a packing algorithm is run to assign (pack) logic cells/clusters corresponding to the design to different blocks that will eventually be mapped to CLBs in the FPGA. Typically, the packing algorithm optimizes local connectivity between cells and/or clusters and, for example, attempts to place a group of related clusters (e.g., group 110 in FIG. 1C) into a single block rather than distributing that group over different blocks. Block 204 is followed by block 206, which is typically a net-based placement process block. In block 206, the packed blocks are mapped (placed) onto CLBs 102 in FPGA 100. Block 206 may, for example, be a TDP block implemented using a simulated annealing (SA) algorithm. After block 206, each CLB may have one or more of the following: (i) one or more groups of clusters (such as groups 110 and 120 in FIG. 1C); (ii) one or more unrelated clusters (such as cluster 140 in FIG. 1C); and (iii) unassigned (i.e., unutilized) gates/cells/clusters (not shown in FIG. 1C). Then, in block 208, routing structure 106 is configured to route the interconnections between different CLBs corresponding to the placement generated in block 206.

[0019] One problem with method 200 is associated with unrelated clusters, such as cluster 140 (FIG. 1C). For example, if unrelated clusters are not packed into CLBs, the utilization of hardware resources in FPGA 100 may become disadvantageously low. On the other hand, packing unrelated clusters into CLBs may significantly impair circuit performance due to the substantial circuit delays associated with signal propagation between unrelated clusters and clusters in other CLBs. One way to deal with the above-indicated problem is by human intervention. In particular, prior to process block 208 of method 200, the current placement may be evaluated by an engineer using, e.g., a graphical user interface. The engineer may choose to move some cells/clusters from their current CLBs to different CLBs to improve circuit performance. However, as indicated earlier, such human intervention is relatively time-consuming and may not be feasible for large circuits.

[0020] FIG. 3 is a flowchart of a place-and-route method 300 according to one embodiment of the present invention. Method 300 is similar to method 200 of FIG. 2. However, in addition to process blocks 202-208, method 300 includes block 302, which is preferably performed between blocks 206 and 208. As will be discussed in more detail below, during block 302, a CAD tool attempts to revise some of the packing decisions of block 204 and/or the placement decisions of block 206 to improve circuit performance. In one implementation, block 302 is path-based and is performed without human intervention. Alternatively, as described below, certain parts of block 302 may be performed manually to enable a user of the CAD tool to provide input on node relocation. The CAD tool could provide hints of critical paths, their delay values, and possible improvement suggestions to a user. Then, the user would be able to make changes either through a description file or through a GUI (Graphical User Interface) such as a floor-planner.

[0021] FIG. 4 is a flowchart of block 302 according to one embodiment of the present invention. In block 402, the K most critical paths (i.e., those paths having the longest signal propagation delays) corresponding to the placement of CLBs generated in block 206 (FIG. 3) are determined and sorted based on their criticality (e.g., from longest to shortest delay). Different algorithms for determining critical paths are known in the art. For example, one such algorithm is disclosed by S. H. C. Yen, D. H. C. Du, and S. Ghanta in an article entitled “Efficient Algorithms for Extracting the K Most Critical Paths in Timing Analysis” (paper 39.1 in the Proceedings of the 26-th ACM/IEEE Design Automation Conference, 1989, pages 649-654), the teachings of which are incorporated herein by reference. K is typically selected to be between 100 and 1000.

[0022] In process block 404, following block 402, one or more nodes of the most critical of the K paths are moved to one or more different CLBs in order to reduce the delay of that path. This move may be done automatically by a CAD tool or manually by a user who selects the one or more nodes and/or one or more CLBs based on the hints provided by the CAD tool. Each different node may be a set of two or more interconnected clusters in the same CLB (e.g., group 132 in FIG. 1C or clusters 118, 120, and 122 in FIG. 1C), an unrelated cluster (e.g., cluster 128 in FIG. 1C), a primitive cell, or a single gate. In block 406, the signal propagation delays of the K paths are updated based on the modification made in block 404, and the K paths are re-sorted. If the path modified in block 404 remains the most critical of the K updated paths, then the processing of block 302 is terminated. However, if a different path of the K updated paths becomes the most critical path, then the processing returns to block 404, where node relocation for the new most critical path is performed. In one implementation, blocks 404 and 406 are repeated until (1) the current most critical path remains the most critical of the K paths after node relocation and (2) the delay corresponding to that path cannot be reduced any further, after which the processing is terminated. In a different implementation, the processing may be terminated when the delay corresponding to the current most critical path becomes less than a specified threshold value. The final placement from block 302 is used for configuring routing structure 106 in block 208 of method 300.

[0023] In the embodiment described above, block 406 is implemented by updating only the K paths originally identified in block 402. In a different embodiment, block 406 may be implemented by determining a new set of K most critical paths after the modification of block 404, similar to the original determination performed in block 402.

[0024] FIGS. 5A-B illustrate a node relocation technique that may be used in block 404 according to one embodiment of the present invention. In particular, FIGS. 5A-B show schematically two parts of a critical path (labeled 502), where different arrows indicate signal routes between different nodes of that path. Nodes (A-F), shown in FIG. 5A, are the first six nodes of path 502, while nodes (V-Z), shown in FIG. 5B, are the last five nodes of path 502. Since a node may correspond to either an entire group or just a portion of a group within a CLB, each consecutive pair of nodes in path 502 may fall within either two different CLBs or the same CLB.

[0025] FIG. 5B illustrates node relocation for a terminal node (e.g., sink node Z) of path 502. More specifically, an attempt is made to move node Z to a different location within a circle (labeled 504 in FIG. 5B) centered at the connecting node (i.e., node Y) and having a radius corresponding to a specified distance measure between nodes Y and Z. In one implementation, the distance measure is the Manhattan distance (i.e., the sum of vertical and horizontal distances) between nodes Y and Z. Source node A of FIG. 5A (i.e., another terminal node) may be similarly relocated.

[0026] FIG. 5A illustrates node relocation for an intermediate node (e.g., node D) of path 502. More specifically, an attempt is made to move node D to a different location within an ellipse (labeled 506 in FIG. 5A). Ellipse 506 is defined such that (I) the two connecting nodes (i.e., nodes C and E) are the foci of the ellipse, and (II) the size of the major axis of ellipse 506 corresponds to a specified distance measure. In one implementation, the specified distance measure is the sum of the Manhattan distances between (1) nodes C and D and (2) nodes D and E. Different intermediate cells may be similarly relocated.

[0027] Note that, although Manhattan distances are preferred, the areas depicted in FIGS. 5A-B are based on Cartesian distances, another possible distance measure.

[0028] In one embodiment, relocation of each node is attempted by identifying a possible move. Different types of possible moves include: (i) swapping two similar nodes between two different CLBs; (ii) moving a node into an unassigned area of a different CLB; and (iii) swapping two dissimilar nodes between two different CLBs. Similar nodes are nodes involving equivalent sets of circuitry. As such, similar nodes may be swapped without involving any other circuitry. For example, when two nodes each consist of a LUT and a DFF, such similar nodes may be swapped without involving any other circuitry. Dissimilar nodes, on the other hand, are nodes involving unequal sets of circuitry. As such, swapping dissimilar nodes will involve other circuitry. For example, in order for a node consisting of a LUT and a DFF in a first CLB to be swapped with another node consisting of a LUT in a second CLB, the second CLB must also have an unassigned DFF to implement the node moved from the first CLB. In such a case, the first CLB would end up with an unassigned DFF in addition to a node consisting of a LUT.

[0029] If a move is available, then the move is evaluated using one or more specified conditions. Possible conditions include: (a) whether the move reduces the delay of the current path, (b) whether the move increases the delay of any of the rest of the K paths, (c) whether the move increases the delay of any other path in the FPGA; (d) whether the move increases the size of the bounding box (e.g., the sum of the vertical and horizontal dimensions of box 110 in FIG. 1B) for any net by more than a predefined threshold amount (e.g., 0.1%). If the specified conditions are satisfied, then the move is acceptable. If more than one move for the current node is acceptable, then additional criteria may be used to select a “best” move from the different acceptable moves. Such additional criteria may be, for example, the move that results in the greatest decrease (or least increase) in the relative sizes of the bounding boxes for the affected nets.

[0030] In one embodiment, node relocation (e.g., as illustrated in FIG. 5) is attempted for all nodes of path 502 until the delay corresponding to that path can no longer be improved or no acceptable moves are available. In one implementation, node relocation for path 502 is performed successively, e.g., starting at one terminal node (e.g., source node A) and proceeding toward the opposing terminal node (e.g., sink node Z) in the connecting order in path 502 (e.g., B, C, D, . . . , X, Y, Z). After node Z has been processed, the processing returns to node A and again proceeds toward node Z. The processing continues until no more nodes can be relocated. In another implementation, the processing is performed in an order determined based on the individual delay values corresponding to each particular node in path 502. For example, the processing order may be determined by (a) ascertaining, for each terminal node, the delay between that terminal node and the corresponding connecting node and, for each intermediate node, the sum of delays between that node and the two connecting nodes; and (b) selecting the order of processing in the order of decreasing individual delay values. After the node corresponding to the smallest individual delay has been processed, the individual delay values are updated and the processing returns to the node having the current largest individual delay. The processing continues until no more nodes can be relocated.

[0031] Table I compares the results of circuit optimization obtained by applying methods 200 and 300 to several representative benchmark circuits. In particular, Table I indicates a maximum clock frequency obtained for one of the global clocks in each circuit using the two methods.

[0032] The first and second columns of the table show circuit number and circuit characteristics, respectively. The third and fourth columns show the maximum clock frequency obtained using method 200 and method 300, respectively. The fifth column shows the relative improvement of the maximum clock frequency obtained with method 300 over that of method 200. As indicated in the table, the outcome of method 300 is generally better than that of method 200, with an average improvement of 7.3% for the six exemplary circuits.

[0033] While this invention has been described with reference to illustrative embodiments, this description is not intended to be construed in a limiting sense. Although the present invention was described in reference to simulated annealing, it may also be used in conjunction with other optimization algorithms/methods, such as, for example, a partition-placement algorithm or a mincement cut placement algorithm. In addition, the present invention may be applied to different PLD architectures (e.g., block-structured or channel-structured) and implementation technologies (e.g., SRAM or anti-fuse) as well as PLDs other than FPGAs, such as Field-Programmable Logic Arrays (PLAs), Simple Programmable Logic Devices (SPLDs), and Complex Programmable Logic Devices (CPLDs).

[0034] Although certain embodiments of the present invention have been described in the context of swapping pairs of nodes, the invention is not so limited. In general, the present invention can be implemented using any suitable placement modification, including those involving more than two nodes at a time.

[0035] Although the present invention has been described in the context of time constraints (circuit delays), alternative or additional constraints, such as those related to power, routing congestion, or routing overlaps, may be applied. Various modifications of the described embodiments, as well as other embodiments of the invention, which are apparent to persons skilled in the art to which the invention pertains are deemed to lie within the principle and scope of the invention as expressed in the following claims.

[0036] The present invention may be implemented as circuit-based processes, including possible implementation on a single integrated circuit. As would be apparent to one skilled in the art, various functions of circuit elements may also be implemented as part of a software program. Such software may be employed in, for example, a digital signal processor, micro-controller, or general-purpose computer.

[0037] The present invention can be embodied in the form of methods and apparatuses for practicing those methods. The present invention can also be embodied in the form of program code embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus, for practicing the invention. The present invention can also be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium or carrier, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a unique device that operates analogously to specific logic circuits.

[0038] Although the acts in the following method claims, if any, are recited in a particular sequence with corresponding labeling, unless the claim recitations otherwise imply a particular sequence for implementing some or all of those acts, those acts are not necessarily intended to be limited to being implemented in that particular sequence.