Placement processing for programmable logic devices

Details Placement processing for programmable logic devices Placement processing for programmable logic devices

2002-11-05

2004-11-02

Whitmore, Stacy A. (Department: 2812)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06813754

ABSTRACT:

TECHNICAL FIELD
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.
BACKGROUND
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.
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.
1
B. 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.
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.
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.
SUMMARY
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.
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.
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.


REFERENCES:
patent: RE34363 (1993-08-01), Freedman
patent: 5448493 (1995-09-01), Topolewski et al.
patent: 5659484 (1997-08-01), Bennett et al.
patent: 5740069 (1998-04-01), Agrawal et al.
patent: 5825662 (1998-10-01), Trimberger
patent: 6086629 (2000-07-01), McGettigan et al.
patent: 6086631 (2000-07-01), Chaudhary et al.
patent: 6127843 (2000-10-01), Agrawal et al.
patent: 6130551 (2000-10-01), Agrawal et al.
patent: 6208163 (2001-03-01), Wittig et al.
“Efficient Algorithms for Extracting the K. Most Critical Paths in Timing Analysis,” by Steve H.C. Yen, David H.C. Du, S. Ghanta, Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, 26th ACM/IEE Design Automation Conference, pp. 649-654, 1989.

Affiliated with

Also associated with

Rating

Placement processing for programmable logic devices does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Placement processing for programmable logic devices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Placement processing for programmable logic devices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3282918