Method and system for generating a programming bitstream including identification bits

[0002] The present invention generally relates to field programmable gate arrays, and more particularly to methods and systems for generating programming bitstreams for field programmable gate arrays.

[0003] Field programmable gate arrays (FPGAs), first introduced by XILINX in 1985, are becoming increasingly popular devices for use in electronics systems. For example, communications systems employ FPGAs in large measure because of the re-programmability of FPGAs. In general, the use of FPGAs continues to grow at a rapid rate because they permit relatively short design cycles, reduce costs through logic consolidation, and offer flexibility in their re-programmability.

[0004] The re-programmability of FPGAs, while a chief advantage of FPGAs over other solutions, has also created challenges to users of FPGAs, as well as to field engineers and other support personnel. Specifically, to trace the content of a particular FPGA programming bitstream, a user may need to reference identifying characteristics of certain design modules that are not readily available. The reason for the need to ascertain these characteristics arises from the fact that the design modules that are embodied in the programming bitstream have associated therewith characteristics such as logic core identifiers, revision levels, timestamps and assorted other information, and the identification of these characteristics may be necessary in order to troubleshoot problems that may arise from use of a particular design module with a particular FPGA. However, quickly identifying the characteristics may be cumbersome and time consuming depending upon how such information is managed.

[0005] In addition to the content of an FPGA programming bitstream, the software tools used to generate the bitstream may also impact operability. For example, when support personnel are presented with a programming bitstream which does not program a FPGA to function as expected, one consideration is the compatibility of the software tool with the particular FPGA. In addition, there may be compatibility issues between different versions of the software tool and revision levels of FPGAs. As with identification of the contents of the programming bitstream, identifying the software tools may be cumbersome or impossible depending upon how such information is managed.

[0006] Therefore, a method and system that addresses the aforementioned problems, as well as other related problems, are desirable.

[0007] A method and apparatus for generating a programming bitstream for a programmable gate array are provided in various embodiments of the invention. Certain segments of a programming bitstream generated from an input design specification are unused for storing programming bits. Selected items of information are encoded and stored in the unused segments of the programming bitstream.

[0008] In a first embodiment, a method is provided for generating a programming bitstream for the programmable gate array in response to an input design specification. The programming bitstream includes one or more unused segments, wherein an unused segment includes bits that are not used for programming the programmable gate array. One or more selected items of information are encoded to form binary representations of the items. The binary representations are inserted into one or more of the unused segments of the programming bitstream.

[0009] In another embodiment, a method is provided for generating a programming bitstream for a programmable gate array and ascertaining identification information from the programming bitstream. One or more selected items of information are encoded to form binary representations of the items. The binary representations are inserted into one or more of the unused segments of the programming bitstream. Binary representations of the items of information are read from the unused segments and the binary representation are decoded into the selected items of information.

[0010] A method for ascertaining identification information from a programming bitstream for a programmable gate array is provided in yet another embodiment. One or more of the unused segments have encoded therein binary representations of one or more selected items of information. The method comprises reading from at least one of the unused segments of the programming bitstream binary representations of one or more selected items of information. The binary representations are decoded into the selected items of information.

[0011] In another embodiment, an apparatus for generating a programming bitstream for a programmable gate array comprises: means for generating a programming bitstream for the programmable gate array including one or more unused segments in response to an input design specification; means for encoding one or more selected items of information to form binary representations of the items; and means for inserting the binary representations into one or more of the unused segments of the programming bitstream.

[0012] A system for generating a programming bitstream for a programmable gate array is yet another embodiment of the invention. The system comprises a bitstream generator configured to generate a programming bitstream responsive to an input design specification. The programming bitstream has one or more unused segments that are not used for programming the programmable gate array. An information encoder is coupled to the bitstream generator and configured to encode one or more selected items of information into respective binary representations and insert the binary representations into one or more of the unused segments of the programming bitstream.

[0013] In yet another embodiment, identification bits are appended to the bitstream rather than inserted into unused bits. In this embodiment, the bitstream is lengthened in order to accommodate the identification bits. The process for generating the bitstream of this embodiment is simpler than that of inserting identification bits into an existing bitstream, since the improved bitstream can simply be formed by adding the identification bits to the end of an existing bitstream. The improved bitstream is usually compatible with an older bitstream even though the bitstream must be made longer to accommodate the added bits. Typically, a header at the beginning of the bitstream specifies the length of the bitstream. This header is revised to specify the added length. In the FPGA, the added identification bits are simply passed through the device and not used.

[0014] In a combination embodiment, some identification bits are embedded in the bitstream and additional bits are appended to the bitstream.

[0015] The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.

[0016] Other aspects and advantages of the invention will become apparent upon seeing the following detailed description and upon reference to the drawings in which:

[0017] FIG. 1A shows a block diagram of a portion of an example field programmable gate array (FPGA) 10 with which the present invention may be used;

[0018] FIG. 1B is a block diagram of a portion of an example FPGA in which interconnections between tiles of the FPGA are illustrated;

[0019] FIG. 2 is a block diagram of example memory cells for an FPGA;

[0020] FIG. 3 is a design flow diagram that illustrates an example system and method in which the present invention may be used;

[0021] FIG. 4 is a data diagram that illustrates the information provided in a programming bitstream in accordance with an example embodiment of the invention;

[0022] FIG. 5 illustrates a data flow according to a first example embodiment of the present invention; and

[0023] FIG. 6 illustrates a data flow according to a second example embodiment of the present invention.

[0024] FIGS. 7A, 7B, and 7C show the information provided in bitstreams generated for one, one, and two FPGAs, according to another embodiment of the invention.

[0025] While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the detailed description is not intended to limit the invention to the particular forms disclosed. On the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

[0026] The present invention is believed to be applicable to a variety of systems for generating a programming bitstream for programmable logic devices. The present invention has been found to be particularly applicable and beneficial in generating programming bitstreams for field programmable gate arrays (FPGAs). While the present invention is not so limited, an appreciation of the present invention is presented by way of a particular example application, in this instance, in the context of and example system for generating a programming bitstream for an FPGA.

[0027] In various arrangements for programming FPGAs, a programming bitstream is generated that includes more bits than there are memory cells available to program. That is, some of the bits in the programming bitstream are unused for programming. This may occur, for example, for an FPGA that is not fully populated with SRAM. The extra unused bits are included in the bitstream, interspersed with the programming bits, instead of not including unused bits. The unused bits are included (1) for convenience in generating a bitstream if the SRAM is expanded and (2) simplifying the FPGA logic used to write the bits to SRAM. The present invention makes use of the unused bits by encoding in them information to identify, for example, logic cores used in generating the programming bitstream, software tools, software version numbers, timestamps, design change identifiers, authenticity codes, design names, design revision levels, design authors and various other types of information.

[0028] Before discussing the method and system of the present invention, a brief overview of an example field programmable gate array (FPGA) architecture is set forth in the following paragraphs which describe FIGS. 1A-B and 2.

[0029] FIG. 1A shows a block diagram of a portion of an example field programmable gate array (FPGA) 10 with which the present invention may be used. The FPGA 10 comprises a plurality of tiles 12. The tiles 12 are arranged in an array as shown in FIG. 1A. As shown in FIG. 1B, each of tiles 12a-dincludes a programmable routing matrix, for example, 201a-d,and a configurable logic block matrix, for example, 202a-d.Each tile 12 has a group of configuration memory cells (not shown) associated with it. Some of the associated memory cells are coupled to a configurable logic block matrix, for example 202aand some are coupled to the programmable routing matrix, for example 201a.Depending on the data stored in the associated group of memory cells, each logic block matrix may be configured to perform one of a variety of logic functions. The inputs and outputs of each logic block matrix 202a-d,for example, may also be coupled, through the programmable routing matrices 201a-d,to the inputs and outputs of other logic blocks or the inputs and outputs of the FPGA 10 in any one of a number of configurations. The coupling of the inputs and outputs is also specified by data stored in the associated group of memory cells.

[0030] Referring now to FIG. 2, a block diagram of example configuration memory cells 14 for the FPGA 10 is shown. The memory cells 14 are arranged on the FPGA 10 as an array 15 in rows 16 and columns 18 of cells 14. The array 15 of memory cells 14 illustrates only a portion of all memory cell in an FPGA 10. Additional rows and columns of similarly coupled memory cells 14 are represented in FIG. 2 by ellipses. The memory cells 14 are spaced apart across the FPGA 10 so that the cells 14 are positioned proximate the tile 12 with which they are associated. This arrangement advantageously reduces the area on the FPGA 10 that must be provided for interconnect structures that couple the memory cells 14 to their associated programmable routing matrix 201 and configurable logic block matrix 202.

[0031] In addition to having an output (not shown) that is coupled to one or several transistors of the appropriate tile 12, each of the memory cells 14 has an address input and a data input. In response to a signal on the address input, the signal applied to the data input is loaded into the memory cell 14. The memory cells 14 are static random access memory (SRAM) cells, for example. However, those skilled in the art will realize that the memory cells 14 may be implemented with other circuits such as an array of D-flip-flops or EPROM cells. A plurality of row buses 24 and column buses 26 are provided for coupling the data inputs and the address inputs, respectively, of the memory cells 14. Each time the address signal is asserted on a column bus 26, all the memory cells 14 in that column are loaded or written. Therefore, one column of data bits can be simultaneously written to the array 15 when the address is strobed.

[0032] A data register 20 stores a column of data before it is loaded into a column 18 of memory cells 14. The data register 20 is a shift register having a data input, a CLK input and a plurality of data outputs, for example. The data register 20 stores a plurality of bits equal in number to the number of rows 16 of the array 15. Each data output of the data register 20 is coupled by a respective row bus 24 to the memory cells 14 in a respective row 16 of the array 15. The data input of the data register 20 is coupled to receive a bit stream of data to be loaded into the memory cells 14, and the CLK input is coupled to receive a CLK signal indicating the time when the data register should be clocked or shifted.

[0033] An address register 22 is provided for specifying the column 18 of the array 15 that is to be loaded with data from the data register 20. The address register 22 is a shift register having a serial input, an address increment input (ADDR INC input), an address strobe input (ADDR STROBE input) and a plurality of address outputs 26. The address register 22 has a number of stages equal to the number of columns 18 in the array 15. Each stage stores a bit that specifies whether a particular column is to be addressed. Each stage also provides one of the plurality of address outputs. Each of the plurality of address outputs is part of a respective column bus 26 coupled to the address input of memory cells 14 in a respective column 18 of the array 15. The address increment input provides a way of shifting a token select bit through the address register 22.

[0034] FIG. 3 is a design flow diagram that illustrates an example system and method in which the present invention may be used. The example design flow 100 may be used with the Xilinx Alliance Series™ device-independent modular tool set for FPGA design on conventional computer platforms. (Xilinx Alliance Series is a trademarks of Xilinx, Inc., assignee of the present application.) The FPGA architecture description block 102 and Xilinx technology modeling system block 104 produce the physical device description of block 106. From the physical device description block 106, the design flow 100 proceeds to a technology mapper 108, an editor for programmable IC's 110, place and route 112, and a device independent logic partitioning system.

[0035] The design flow 100 begins with the design capture block 116, which comprises a number of possible behavioral or hardware description languages such as Abel or VHDL, as well as state machine, Boolean equation or schematic representations or a combination of these representations. Many FPGA designs are captured using schematics. Electronic Design Interchange Format (EDIF) 118, and Xilinx Net list File (XNF) 120 both produce a net list 122 comprising a logic description of the design. The constraint file 124, which interacts with the design capture block 116, includes design preferences and, with the net list 122, provides input to a Xilinx Generic Database (XGD) 125 for subsequent input to the technology mapper 108 to generate an annotated net list 126 to the design capture block 116. The technology mapper 108 in conjunction with the editor 110, place and route 112, and logic-partitioning system 114 develops a Xilinx Circuit Description (XCD) 128. By use of the logic-partitioning system 114, a number of XCDs 130 may be developed partitioning the design across multiple FPGAs. The XCDs 128, 130 are supplied as input to the timing module 132, which supplies inputs to the back annotation block 134 of the XGD 125. The XCDs 128, 130 furnish the necessary binary output to programming block 136 to be applied to the target FPGA to program the device to function in accordance with the circuit design.

[0036] FIG. 4 is a data diagram that illustrates the information provided in a programming bitstream in accordance with an example embodiment of the invention. The programming bitstream 202 corresponds, in one embodiment, to the output of the programming bitstream generator 136 of FIG. 3. This embodiment is further illustrated in FIG. 5. In another embodiment, the programming bitstream output from generator 136 is post-processed by a tool that then provides as its output programming bitstream 202. This other embodiment is shown in FIG. 6. The functional design modules 203 from which the programming bitstream 202 is generated correspond to the design information of the design capture block 116 of FIG. 3, for example.

[0037] Continuing now with FIG. 4, blocks 204 illustrate selected items of information to be encoded for inclusion in a programming bitstream. An example algorithm for implementing the encoding/decoding can be used in both embodiments, i.e., where the bitstream is post-processed and where the bitstream generator 136 (FIG. 3) generates the programming bitstream with the encoded information. The encoding process includes two phases: 1) encoding the information into bit vectors, and 2) inserting the bit vectors for all information into the bitstream's unused bits.

[0038] In encoding the selected information, binary representations of the various possible data types may be used. Block 206 illustrates the collection of bit vectors encoded from the selected items of information 204. A bit vector of the binary representations is created as described by the pseudo-code set forth below:

[0039] Create an empty bit vector, B.

[0040] If the information is a text string, then:

[0041] For each character in the text:

[0042] Convert the uni-code binary representation of the character to a binary string; and

[0043] Append the binary string to bit vector B.

[0044] End loop.

[0045] Else if the information is a Boolean value, then

[0046] Append a 0 or 1 to the bit vector B.

[0047] Else if the information is a number then

[0048] Convert the 32-bit binary representation of the number to a binary string; and

[0049] Append the binary string to the bit vector B.

[0050] Return bit vector B.

[0051] A set of semantic information types is used so that a binary representation may be interpreted in a selected context. For example, a timestamp may be construed not only as a text string, but as a string with a particular format that is recognized by both encoding and decoding functions. In the pseudo-code set forth below, a bit vector is created, as illustrated by bit vector 208, that includes the encoded items along with the semantic types. In the example, it is assumed that there are no more than 256 such semantic types and that the number of bits in a given bit vector does not exceed 65,535.

[0052] Create an empty bit vector, V.

[0053] Append number of items to V (16 bits).

[0054] For each information item, I:

[0055] Encode I into bits;

[0056] Append length in bits of I to V (16 bits);

[0057] Append semantic type of I in bits to V (8 bits); and

[0058] Append I bits to V.

[0059] Set bitmap address to first bit in bitstream.

[0060] For each bit in V:

[0061] Increment address until unused bit is found; and

[0062] Set that bit to the current V bit.

[0063] End loop.

[0064] After the bit vector 208 is created, it is merged with the programming bitstream 202. Specifically, the bits from the vector 208 are written to the unused bit segments 210a,210b,. . . , 210xof the programming bitstream. It will be appreciated that the bits from the bit vector 208 can be written into the bitstream 202 in an order other than an order in which the binary representations 206 of the items were generated. That is, the data can be scrambled so that it is not easily decoded without knowing the scrambling technique.

[0065] The decoding of the information in the unused bits involves reading into memory the whole bitstream and identifying unused bits as the bitstream is traversed. Each information item is parsed as an 8-bit semantic type and a bit-encoded Boolean, integer, or character string. An example method for decoding the information in the unused bits is set forth in the pseudo-code below. The example assumes that the items of information in the bitstream are not scrambled. Those skilled in the art will appreciate that the processing below can be modified to decode the scrambled information.

[0066] Get first 16 unused bits from bitstream.

[0067] Convert those bits to an integer, NUMITEMS.

[0068] Set ITEMCOUNT to 1.

[0069] Loop

[0070] Get next 8 unused bits from bitstream.

[0071] Convert those bits to an integer SEMANTICTYPE.

[0072] If SEMANTICTYPE is Boolean data, then:

[0073] Get the next unused bit in the bitstream; and

[0074] Set the information value to that bit value.

[0075] Else if SEMANTICTYPE is integer data, then:

[0076] Get the next 32 unused bits; and

[0077] Convert those bits to an integer value.

[0078] Else if SEMANTICTYPE is string data, then:

[0079] Get the next 16 unused bits from the bitstream;

[0080] Convert those bits to an integer LENGTH;

[0081] Set LENGTHCOUNT to 1;

[0082] Create an empty string S; and

[0083] Loop

[0084] Get the next 16 unused bits;

[0085] Convert to a uni-code character;

[0086] Append the character to the string S; and

[0087] Increment LENGTHCOUNT

[0088] Until LENGTHCOUNT>LENGTH.

[0089] Process the information.

[0090] Increment ITEMCOUNT

[0091] Until ITEMCOUNT>NUMITEMS.

[0092] FIG. 5 illustrates a data flow 300 according to a first example embodiment of the present invention. The embodiment of FIG. 5 includes an information encoder 302 that post-processes a programming bitstream 304 to include selected items of information 306 in unused bit segments, for example 210a-xof bitstream 202 of FIG. 2.

[0093] The bitstream generator 308 can be implemented in a manner consistent with the bitstream generator 136 of FIG. 3. Two data items are output by the bitstream generator 308. The first item is programming bitstream 304, and the second item is bitstream map 310. The programming bitstream 304 includes some segments having bits that are used to program the target device and some segments of bits that are not used for programming the device, as illustrated by bitstream 202 of FIG. 4. The bitstream map 310 indicates positions and sizes of the unused bit segments in the programming bitstream 304. For example, relative to programming bitstream 202 of FIG. 4, the bitstream map may include the respective positions of unused bit segments 210a-xrelative to the first position in the programming bitstream 202. In addition, if the unused bit segments 210a-xhave different sizes, bit-lengths of the unused bit segments are also associated with the unused bit segments.

[0094] The information encoder 302, implemented in accordance with the description set forth above, takes as input the programming bitstream 304, bitstream map 310, and the selected items of information 306 and generates an enhanced programming bitstream 312. The selected items of information include, for example, logic core identifiers, software tool identifiers, software version numbers, timestamps, design change identifiers, authenticity codes, design names, design revision levels, design authors and various other types of information. The encoding of the items of information 306 and placement of the encoded information within the bitstream can be accomplished as described in the discussion that accompanies FIG. 4.

[0095] FIG. 6 illustrates a data flow 400 according to a second example embodiment of the present invention. The data flow 400 generally corresponds to design flow 100 of FIG. 3 having various modifications made to support generation of an enhanced programming bitstream 402. The enhanced bitstream 402 is essentially the same as enhanced bitstream 312, although it is produced by different example methods.

[0096] Net list 403 is input to a database build module 404 and a net list database 406 is produced. The net list database 406 is a Xilinx generic database 125 (FIG. 3), for example. An example item of information to be included in the unused bit segments of a programming bitstream is identification information for logic cores included in the net list. Therefore, the database build module 404 identifies the logic cores, for example by detecting a core generator macro, in the net list and includes attributes such as names and version or revision levels in the net list database 406. From the net list database 406, the mapper module 408 generates a circuit database 410 that also includes the core attributes. The circuit database 410 corresponds to Xilinx circuit description 128 of FIG. 3, for example.

[0097] The bitstream generator 412 takes an input circuit database 410, along with the included core attributes, and other selected items of information 414 and generates an enhanced programming bitstream 402. The selected items of information 414 are those described in FIG. 5. In contrast to the example embodiment of FIG. 5, the bitstream generator 412 of FIG. 6 includes the information encoding processing of the information encoder 302 of FIG. 5.

[0098] A discussion will now be made of the embodiment in which identifying information is appended to the end of a bitstream. FIGS. 7A, 7B, and 7C show the information provided in a programming bitstream in accordance with such an embodiment. In FIGS. 7A and 7B, a single FPGA is to be configured from a single bitstream. Each separate bitstream includes three regions, a header 701 or 702, configuration data 711 or 712 for the FPGA, and identifying information 721 or 722 related to the bitstream or FPGA. (In the example of FIGS. 7A and 7B, the first FPGA is a larger FPGA than the second, although any combination of sizes may be used and a number of FPGAs greater than two may be used.) Header bits 701 and 702 appear at the beginning of the bitstreams BITSTREAM1 and BITSTREAM2 respectively, and identify the bitstream total length with a length count, and include other information such as redundancy encoding that may be used in the bitstream. (See Erickson, U.S. Pat. No. 5,321,704, for example, incorporated herein by reference.) Following the header 701 or 702 is the configuration data 711 or 712 for configuring the FPGA to implement the desired function. At the end of the bitstream is identifier information 721 or 722, which is either passed through the device and not used, or not passed through the device at all depending upon whether the identifier information has been counted in determining the length count of the header.

[0099] If the two FPGAs are working together on the same board, the two FPGAs may be configured from the same bitstream, as shown in FIG. 7C.

[0100] As two designs or two parts of one design are partitioned, placed and routed to be implemented by the two FPGAs, the two separate bitstreams BITSTREAM1 and BITSTREAM2 are first generated for the two FPGAs. Once the two separate bitstreams have been generated, a combined bitstream is formed. This combined bitstream includes a header 703 having a length count within it that is the sum of the length counts of headers 701 and 702. The combined bitstream next includes configuration data 711 from BITSTREAM1, configuration data 712 from BITSTREAM2, and finally identifying information 721 from BITSTREAM1 and identifying information 722 from BITSTREAM2. When the two FPGAs are placed into a system board having various integrated circuit devices, they are connected together into a daisy chain as discussed at pages 4-315 through 4-318 of the Xilinx 1998 Programmable Logic Data Book available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, incorporated herein by reference. The bitstream will be loaded into the two FPGAs and the identifying information at the end of the bitstream will be ignored, either by not loading the information into the FPGAs or by passing the information through the FPGAs and out (into nothingness). The identifiers in FIG. 7C are preferably modified to indicate which identifying information corresponds to the first FPGA and which to the second.

[0101] The invention applies to bitstreams having other formats as well as those described above. For example, some logic architectures do not use a header but instead use address information as well as data in the bitstream. Unused bits in such a bitstream can be used in the same manner. And for bitstreams not having a specified length, the bitstream can simply be lengthened to include identifying information.

[0102] As with other embodiments, the identifying information does not affect the FPGA configuration or function. However, this information can be examined to determine which software was used to generate the bitstream. In particular, the identifying information can be examined to determine whether licensed modules were used to generate part of a design implemented in the FPGA, or whether software having a guarantee of function or performance was used to configure the FPGA.

[0103] Accordingly, the present invention provides, among other aspects, a method and system for generating a programming bitstream for a programmable gate array. Other aspects and embodiments of the present invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and illustrated embodiments be considered as examples only, with a true scope and spirit of the invention being indicated by the following claims.