Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-07-25
2002-12-10
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C713S002000, C713S100000, C717S114000, C711S170000
Reexamination Certificate
active
06493862
ABSTRACT:
TECHNICAL FIELD
This invention relates to integrated circuits, particularly programmable logic devices or field programmable gate arrays (FPGAs). More particularly, this invention relates to compression methods for reducing the size of a bitstream used to program an FPGA.
BACKGROUND OF THE INVENTION
Field programmable gate arrays (FPGAs) are configured to perform particular functions by loading a stream of bits, or bitstream, into a memory that controls configuration of configurable logic blocks (CLBs). Each CLB includes configurable logic, horizontal and vertical line segments that connect across adjacent cells to form interconnect lines, and a routing or switching structure to selectively connect the logic to the line segments.
It is sometimes desirable to change the functionality of the FPGA by reconfiguring some or all of the logic blocks. In the past, reconfiguration involved reprogramming the entire FPGA by loading a complete new bitstream into the FPGA to reconfigure all of the CLBs.
As FPGAs have grown rapidly in size, partial reconfiguration techniques have evolved to enable reconfiguration of selected portions of the FPGA without affecting other portions of the same FPGA. Due to the architecture of FPGAs, however, partial reconfiguration has been traditionally limited to reconfiguring entire columns of memory for controlling CLBs.
FIG. 1
shows an FPGA
20
to illustrate the limitations of conventional partial reconfiguration. The FPGA
20
has an array of tiles, each tile comprising configurable logic and related interconnect, which are collectively referred to as a configurable logic block (CLB)
22
. For illustration purposes, only a few CLBs are shown in FIG.
1
and only a few of the interconnect lines have been drawn. Typically, an FPGA
20
is implemented with thousands of repeatable CLBs
22
, each having many horizontal and vertical line segments. Young, Chaudhary and Bauer in U.S. Pat. No. 5,914,616 describe such a structure in more detail, and this patent is incorporated herein by reference.
Each CLB
22
has configurable logic, horizontal and vertical line segments that connect across adjacent cells to form interconnect lines, and a routing or switching structure to selectively connect the logic to the line segments. configuration of the logic and connection between line segments is controlled by a configuration memory, into which a configuration is loaded for enabling the logic and interconnect lines to perform a desired function. In some FPGAs, data in the configuration memory is loaded by addressing sections of configuration memory on address lines and applying data to data lines. In some FPGAs, a frame of configuration data is fed serially into a shift register, then shifted in parallel to an addressed column of configuration memory cells. Vertical wires form address lines, as represented by address lines
24
, that generally span the height of the FPGA. Horizontal wires form data lines, as represented by data lines
26
, that usually span the width of the FPGA.
In the FPGA of
FIG. 1
, configuration data from the bitstream is placed onto the data lines
26
by a shift register
28
. The bitstream contains frames of data, where each frame fills the shift register
28
and is used to program one column of memory cells accessed by a corresponding address line. As an example, the shift register
28
might hold a frame consisting of several thousands bits. The bitstream also contains commands to load a corresponding data frame into the shift register and once loaded, commands to select the appropriate address line associated with the data frame.
After an entire frame is loaded into the shift register
28
, the data bits may be temporarily transferred to a shadow register
30
so that the shift register
28
is free to begin receiving the next frame of data. An address line is selected to transfer the data from the shadow register
30
via the data lines
26
into selected memory cells of the CLBs. This process is repeated for all address lines
24
to fully program the CLBs
22
on the FPGA
20
.
Using conventional methods, FPGA
20
can be partially reconfigured by shifting data bits into the shift register
28
and selecting only the address lines
24
of the CLBs
22
that are being reprogrammed. Unfortunately, since the address lines
24
span entire columns of CLBs
22
, all of the CLBs connected by the common address lines
24
are reconfigured, whether or not the programmer wants to change all blocks. This is represented pictorially in
FIG. 1
as a partial reconfiguration zone
32
.
As FPGAs continue to increase in size and complexity, it would be desirable and advantageous to partially reconfigure smaller sections of the FPGA that include less than all of the CLBs connected to a common address line. Accordingly, there is a need for an improved process or architecture that enables partial reconfiguration of selectable CLBs on the FPGA.
Another problem resulting from the FPGA's rapid growth in size concerns the enormously increasing length of the bitstream used to program the FPGA. Clock speeds used to shift the bitstreams into an FPGA have increased, but less dramatically, thus increasing the length of time required to load the bitstream into the FPGA.
In an effort to address this problem, some FPGA architectures dedicate multiple data pins to receive the bitstream, rather than a single pin as used in earlier design generations. This improvement, however, costs package pins, and there remains a desire to further reduce the time required to configure or reconfigure an FPGA.
One way to improve the speed of FPGA configuration is to reduce the size of the bitstream. Unfortunately, standard compression algorithms used in other signal processing environments are not effective for FPGA bitstreams because they require large amounts of memory. Conventional compression algorithms that do not require large amounts of memory, such as run length encoding (RLE), have not proven effective with typical bitstream data. Accordingly, there remains a need to compress the size of the bitstream in a way that reduces the length of time required to load the bitstream into the FPGA.
SUMMARY OF THE INVENTION
This invention relies on an FPGA architecture that can reconfigure a part of the FPGA at a resolution of one word. In one embodiment, the method enables partial reconfiguration of selectable configurable logic blocks (CLBs) connected to one or more address lines, without affecting other CLBs connected to the same address lines.
This invention concerns a system and method to reduce the size of the bitstream used in configuring or reconfiguring the FPGA. The compression method evaluates the configuration data and identifies, for a given frame, the most similar frame in the configuration data. The most similar frame may be an identical frame, in which all words or bits are the same, or a similar frame in which only a few bits or words differ between them. The compression method reorganizes the frames within the bitstream to group the similar frames so that the amount of data bits being changed from one frame to the next is minimized. Duplicated words/bits that do not change from one frame to the next are removed, leaving only their corresponding commands and addresses for selecting the address lines that are intended to program cells with this data.
To enable loading of individual words, as opposed to whole frames, the FPGA is implemented with an addressable data register instead of a conventional shift register. Individual words from a data frame of the bitstream can be loaded directly into the data register at an addressed location.
REFERENCES:
patent: 5426379 (1995-06-01), Trimberger
patent: 5457408 (1995-10-01), Leung
patent: 5635855 (1997-06-01), Tang
patent: 5781756 (1998-07-01), Hung
patent: 5870586 (1999-02-01), Baxter
patent: 5914616 (1999-06-01), Young et al.
patent: 5946478 (1999-08-01), Lawman
patent: 6105105 (2000-08-01), Trimberger
patent: 6272669 (2001-08-01), Anderson et al.
patent: 6304101 (2001-10-01), Nishihara
AT&T Field Programmable Gate Array
Lindholm Jeffrey V.
Young Steven P.
Brown Scott R.
Kik Phallaka
Lee Lewis C.
Smith Matthew
Xilinx , Inc.
LandOfFree
Method for compressing an FPGA bitsream does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for compressing an FPGA bitsream, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for compressing an FPGA bitsream will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2991257