Data processing: structural design – modeling – simulation – and em – Structural design
Reexamination Certificate
1998-07-13
2001-09-18
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Structural design
C703S020000, C703S023000, C708S160000, C713S001000, C714S742000, C717S152000
Reexamination Certificate
active
06292762
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to Field-Programmable Gate Arrays, and more particularly to dynamically changing values used by the gate arrays using a modified configuration bitstream.
BACKGROUND OF THE INVENTION
The invention provides a solution for the following general problem. At first blush, this problem may appear purely hypothetical, however, such a problem does exist in the real world, and the invention provides a solution to the problem.
A “writer” stores logical zeroes and ones in locations of a table stored in a memory. During the writing, some arbitrary procedure, chosen by the writer, selects the addresses and values to be stored in the memory locations. After the memory locations have been written, the writer is denied write access to the memory.
Subsequently, an “adversary” permutes (scrambles) the address lines to the memory in some unknown manner, that is, the adversary secretly switches the address lines around.
A “reader” who knows the procedure used by the writer, but not the permutation applied by the adversary, must use the permuted address lines to correctly read the values stored in the memory by the writer. The goal is to discover how the address lines were permuted by the adversary, of course, without the adversary's cooperation, and, in addition, to have the writer communicate a message to the reader that is as large as possible using the memory as the communication channel.
In the real world, one type of circuit component that is sometimes used by system designers is a Field-Programmable Gate Array (FPGA). FPGAs combine the flexibility of software, and the speed of hardware. FPGAs are frequently used in applications where specialized high-speed processing of digital signals (data) is required: processing that would be unsuitable for general purpose processors executing conventional software. Typical applications where FPGAs can be found include: real-time video signal processing, data reformatting, pattern recognition, and data encryption. FPGAs are especially attractive to a one-of-a-kind or low volume designs where the development of traditional hardware solutions would be too costly and time-consuming.
Generally, FPGAs comprise the following basic components: input and output pins connected to internal pads, logic resources, flip-flops, and routing resources. The logic resources often are multiple replications of the same logic building blocks. For example, an elementary block of logic can be a look-up table (LUT) with two, three, four, or five inputs (address) lines. The LUTs are like ROMs or some other interconnected arrangement of gates that provide an equivalent functionality. For some LUTs, it is possible to actually write the “truth table” of the LUT and thus use the LUT as a RAM.
For all the FPGAs, the programmable gates are configured by a configuration bitstream produced by an FPGA software tool from a “design” corresponding to the application to be implemented in the FPGA. For example, the logic elements of a “design” can be implemented using the equivalent of Read-only Memory (ROM) elements configured as a look-up table (LUT). In essence, the LUT operates as a logical function, input value on “address” lines are used to “index” the LUT and corresponding logical values (zeroes and ones) stored in the LUT at the indexed address are returned as output values, hence a transformation.
To set initial logical values in an FPGA LUT, for example, initializing a truth table when part of the FPGA is used as logic function, the input is specified as part of the FPGA “circuit” in source design form. The source design is processed by the FPGA design tools to obtain a new configuration for the FPGA. The FPGA tools perform operations such as mapping the logic parts of the design to the elementary logic elements of the FPGA, placing those mapped elements, and routing the wiring between the elements. After the mapping, placement and routing phases, the tools have the complete map of all the configuration that the FPGA needs to perform according to the original design. From this map, the tools generate a configuration bitstream ready to be downloaded to the FPGA. Once configured, the FPGA can be used according to the design.
These FPGA design tools, depending on the complexity of the source design, take anywhere from minutes to hours to complete their processing of the source design definitions. After the FPGA has been configured, data can be processed.
For some application, such as pattern matching and encryption, it is beneficial, in terms of silicon space and speed, to produce slightly different instances of the “design” for each different pattern or key processed, rather than using a single “design” accepting different patterns or keys, with all the machinery to load and store new patterns or keys. For example, if a user key is used to encrypt user data, then the key needs to be changed for every different user. In such applications, circuits used to load different keys would take extra space. For these applications, it would be useful to be able to change directly the small part of the “design” that is specific to a key or pattern directly in the configuration bitstream, rather than to do a full FPGA tool cycle each time. Also, if the changes have to be made outside of a development environment, for example, in an FPGA embedded in an end-user machine, then the FPGA design tools may not be readily available to change the run time values.
FIG. 1
shows the phases and general data flow of a traditional FPGA design cycle. The input to the flow is some source design
110
that includes logic elements
111
and
112
, where
112
is a particular element that fits into one of the elementary LUTs of the FPGA, a four-input LUT in FIG.
1
. The source design
110
transforms some input data to output data
114
. The source design
110
includes, for example, logical elements S
0
, S
1
, S
2
, and S
3
that are to process input data connected to inputs x
0
, x
1
, x
2
, x
3
of a LUT
112
of the FPGA by lines
115
. The elements
111
are arbitrary, what is of interest here is the input data on lines
115
. Most of the FPGAs are based on either 3 or 4 or 5 input table LUTs as elementary logic blocks.
In this case, the LUT
112
is “indexed” according to the data on the four inputs x
0
, x
1
, x
2
, x
3
115
. For each input value in the range of 0 to 15, the LUT
112
provides either a zero or a one as output on line
114
. In other words, the LUT
112
stores sixteen zero or one bits in a vector that form the truth table for the possible input data values, and the logic elements are to be combined to perform some function f(x
0
, x
1
, x
2
, x
3
) on the input data to produce output bits on line
114
. Note that logical element S
0
is connected to input x
0
, and so forth.
In phase
10
, the design tools take the source design
110
to generate a “mapped” design
120
for the actual target FPGA. Note, the mapped design
120
does not directly correspond to the original source design
110
. After the source design
110
has been mapped by the tools, a configuration bitstream
131
is produced.
A shaded portion
132
of the configuration bitstream
131
corresponds to the initial sixteen values (x . . . x) of the LUT
112
. Tables
133
and
134
respectively show a mapping of a function as determined in the source, and comparable function g as determined by the tools. The positions of the bits are shown as in hexadecimal (bold) and binary form. At this point, note that these are different, in other words, function g is a permutation of functions f. The values (x, . . . , x)
132
in the bitstream
131
contain no indication how they are ordered.
For applications like the ones presented above, where the “design” has to be slightly changed, usually values of LUTs,
FIG. 2
shows the major steps of the prior art design process
200
. A source design
210
and initial values
220
are presented to FPGA design tools
230
, as in phase
10
of FIG.
1
. The tools
230
produce a configuration bitstream
240
. In step
250
, the confi
Broder Andrei Z.
Mitzenmacher Michael David
Moll Laurent Rene
Shand Mark Alexander
Compaq Computer Corporation
Fenwick & West LLP
Phan Thai
Teska Kevin J.
LandOfFree
Method for determining a random permutation of variables by... 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 determining a random permutation of variables by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining a random permutation of variables by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2501571