Method for determining a random permutation of variables by applying a test function

Abstract

A method determines a random permutation of input lines that produced a permuted set of bits in a bitstream. In a source design, the method replaces a logic element whose input lines are permutable with a test function. The source design is processed by a design tool to generate the bitstream including the permuted set of bits. The test function is probed with test values, and the probe results are compared with the permuted set of bits to discover the permutation of the set of bits. The test values can include a message.

Claims

We claim:

1. A method for determining a random permutation of input lines of a logic element of a source design that produces a permuted set of bits in a bitstream representing the source design, comprising the steps of:

replacing the logic element having permutable input lines with a test function to generate the bitstream including the permuted set of bits;

probing the test function with test values to obtain test results; and

comparing the test results with the permuted set of bits to discover the random permutation of the input lines.

2. The method of claim 1 including correctly reading the permuted set of bits using the random permutation.

3. The method of claim 2 including patching the bitstream using the random permutation to produce a patched bitstream.

4. The method of claim 3 including:

processing the patched bitstream by an FPGA to configure the FPGA for use.

5. The method of claim 1 wherein the values include a message.

6. The method of claim 1 including:

probing the test function using an exhaustive classification of all possible test functions.

7. The method of claim 6 wherein all possible test functions are assigned to equivalence classes, and a particular test function in a particular equivalence class is a permutation of any other test function in the same equivalence class, and the particular test function has no relation with test function in other equivalence classes.

8. The method of claim 7 where an equivalence class of cardinality n factorial is a useful class for discovering the permutation.

9. The method of claim 1 including probing the test function bit by bit, each probe discovering one additional bit of the permuted set of bits.

10. The method of claim 9 where n.log.sub.2 (n) probes are required.

11. The method of claim 5 wherein four input lines produce sixteen bits in the permuted set, a subset of the sixteen values being the message.

12. The method of claim 5 wherein a plurality of test functions are combined to maximize the size of the message.

13. The method of claim 3 including patching the patched bitstream.

14. The method of claim 1 wherein the replaced logic element is processed by design a design tool that permute the input lines of the replaced logic element.

15. The method of claim 14 wherein the logic element is a look-up table.

Description

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.sub.0, S.sub.1, S.sub.2, and S.sub.3 that are to process input data connected to inputs x.sub.0, x.sub.1, x.sub.2, x.sub.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.sub.0, x.sub.1, x.sub.2, x.sub.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.sub.0, x.sub.1, x.sub.2, x.sub.3) on the input data to produce output bits on line 114. Note that logical element S.sub.0 is connected to input x.sub.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 configuration bitstream is loaded into the FPGA, and the mapped design is used during a "run." In step 260, a decision is made to process data with different initial values, and steps 230 and 240 are repeated. For a complex design, each cycle may take hours with static assignment of new initial values at the start of each cycle.

During the mapping phase 10 of FIG. 1 or step 230 of FIG. 2, some tools allow the designer to explicitly specify the correspondence between the logical source address lines and the physical placement of the lines to an FPGA internal structure. In this case, there is less difficulty. However, many tools do not provide for this correspondence, and may scramble the input lines to the LUT in some unknown permuted manner. Therein lies the problem. Going back to FIG. 1, the relationship between the functions f and g with respect to like bits in part 132 are completely unknown.

For a conventional application, where the initial values are statically determined and do not need to change for each run, the unknown permutation on internal inputs is not a problem. This is true because the tools make sure that the overall outcome is logically correct with respect to the source design, no matter what the implementation of the mapped design. In addition, the time required to map the source to the physical wiring of the FPGA is not a concern. However, explicit input placement may limit the ability of the tools to optimally place and route the circuits, and in some cases, explicit placement makes it impossible for the tools to map the source to a working arrangement.

For some applications, it may be desired to allow the initial values to be modified dynamically during the operation of the FPGA without having to resort to a lengthy run of the FPGA tools. For example, periodically, new initial values would be patched directly into the configuration bitstream, and the FPGA is "reconfigured" on-the-fly. This could only be done if the ordering of the input on the LUT, and other like FPGA structures is known. If the ordering is known, then truth table bits can be put in the configuration bitstream in the correct order without having to suffer a full design cycle.

The purpose of the invention is to discover the permutation that FPGA design tools introduce between the order of inputs of internal components, such as LUTs, as specified in a source design and the order in an actual physical mapping of the design. If the ordering can be determined, then dynamic modification of LUT values becomes possible.

SUMMARY OF THE INVENTION

The invention provides a method for discovering a permutation of input lines of a logic element introduced by FPGA tools in the processing of a "design". Knowing the permutation, it is possible to modify the truth table of the logic element directly without fully reprocessing the source design.

More particularly, the method according to the invention provides a method that determines a random permutation of input lines that produce a permuted set of bits in a bitstream. In a source design, a logic element, whose input lines are permutable, is replaced by a test function. The source design is processed by a design tool to generate the bitstream including the permuted set of bits. The bitstream is used to configure the FPGA. The processing of the design can permute the input lines of the logic element. This purmutation can be seen in the bitstream as a set of permuted bits.

The test function is probed with test values, and the probe results are comparing with the permuted set of bits in the bitstream to discover the permutation. Test values can include a message.

In a practical application, the source design is for an FPGA, and the logic element that is replaced by the test function is a look-up table. It is the input address lines of the look-up table that may be permuted by the tools. The present invention discovers how the tools permute the address lines.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a flow diagram of the phases of a design cycle for a Field Programmable Gate Array;

FIG. 2 is a flow diagram of the steps of a prior art repeated design process;

FIG. 3 is a flow diagram of the steps for discovering a permutation of address lines;

FIG. 4 is a flow diagram of the steps for using the discovered permutation to dynamically modify a configuration bitstream for the FPGA;

FIG. 5 is a flow diagram of steps for generating a usable bitstream from a previously patched bitstream that can still be used for discovering a permutation;

FIG. 6 is a flow diagram for transmitting a maximum-sized message and discovering the permutation using an exhaustive search of the test functions space;

FIG. 7 is a flow diagram for discovering the permutation for a specific simple solution of a four input lookup table;

FIGS. 8A-8D are a flow diagram for discovering the permutation using combinations of solutions; and

FIG. 9 is a flow diagram for sending a scaled message to a receiver.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

Introduction

The main idea of the invention is to discover unknown permutations of input lines to logic elements introduced by Field-Programmable Gate Array (FPGA) design tools using a carefully chosen test function specified in a source design. The test function replaces the logic element which will be permuted by the tools. The source design, including the test function, is processed once by the tools. Then, using the test function, the permutation applied by the mapping of the tools can be determined. With this knowledge, new values can dynamically be provided to the FPGA as part of a configuration bitstream without having to use the design tools to generate the configuration bitstream, thus saving time.

Processing a configuration bitstream takes only microseconds, as compared with possibly hours of prior art design cycles, and therefore can be done with a minimal interruption of the application. On some recent FPGAs, it is even possible to reconfigure only the part of the design that has changed, further reducing the interruption time.

Permutation Discovery and Patching

FIGS. 3 and 4 show the steps of a method according to the invention for discovering the permutation of the FPGA design tool, and making modifications to the FPGA in real-time. In FIG. 3, an FPGA source design 310 including a special test function 320 are provided as input to the FPGA design tools 330 for mapping. The special test function 320 replaces a logic element that is to be change at run-time, and whose address lines are susceptible of being permutted by the design tool.

As an advantage, and as described in detail below, this input needs to be mapped only once. In step 330, a configuration bitstream 340 is generated. The configuration bitstream 340 is used by a software component 350 along with the test function 320 to discover the permutation. Specific solutions that can be implemented by the software 350 to discover the permutation are described below.

Continuing with FIG. 4, after the permutation 360 is discovered, the configuration bitstream 340 can be "patched" according to the permutation 360 with "real" values 370 in step 410 to generate a "patched" configuration bitstream 420. Actual production data are processed in step 450. When a new run has to be done, the application is temporarily stopped in step 460 and new initial values 370 are fed to the software patching component 410. As an advantage, "patching" of FPGAs can be done in milli- or microseconds.

The hard part of a practical implementation of the invention is the choice of the test function 320, and the discovery of the permutation in step 350. Disclosed herein are solutions for test functions and discovery procedures that work for a permutation of any number of input lines.

Quality Metrics

In addition to determining the permutation, defined is the concept of spatial and temporal quality metrics of the test function.

Spatial Metrics to Maximize Message Size

If the permutation discovery procedure needs fewer bits in the truth table of the test function than are available, i.e., bit values in a look-up table (LUT), then it is possible to use some of the other bits for other purposes. For example, if a LUT stores sixteen values, but only seven are used by the test function, the other nine available "entries" in the LUT can be used to store a message. The message can be used in a number of different ways. For example, the message can provide actual data with the test function, or the other bits in the unused space of the truth table can be used to store "fingerprints" of different instances of the function, that is, the message can uniquely identify an instance of a test function. The message can also contain actual data values.

Using this fingerprinting mechanism, the different function applications can be recognized during operation of the FPGA, no matter at what arbitrary location the FPGA design tools has placed them. The spatial quality metric of the test function considers the total number of bits in an associated truth table that are not used by the discovery algorithm. The larger the amount of unused space, the better the test function.

Temporal Metrics Including Complexity

The temporal quality metric of the test function measures the amount of time required to discover the permutation. The time is proportional to the complexity of the discovery method and the number of "probes" that need to be made to discover the permutation. The number of probes is less important than the complexity. Described are test functions and associated discovery procedures ("solutions" below) that simultaneously produce good spatial and temporal quality metrics. In particular, the metrics are within a low order additive term of provable lower bounds for the problem. The probes can be made by the software 350.

The two quality metrics, the size of the maximum message and the number of probes necessary to discover the permutation are exclusive. If one wants to put as big a message as possible, it will be necessary on the receiving side to probe the test function with all the initial values to decode the message. However, in a real application, the number of probes does not matter as much as the size of the message. From a temporal perspective, the complexity of the discovery procedure is more important.

This metric cannot be measured as precisely as the metrics above, but it is important that choosing a test function, encoding a message, discovering the permutation, and decoding the message are possible in a reasonable amount of time. The complexity metric, as described below, allows one to identify practical procedures.

Optimal Procedures and Bounds

Maximum Message Size

If n is the number of inputs, there are factorial n (n!) different permutations. A simple counting argument where each input (bit) used partitions the permutation search space into two parts, sets a hard limit to the minimum number of bits that must be "consumed" to do the permutation discovery to log.sub.2 (n!). The maximum number of bits the message can have is then 2.sup.n -log.sub.2 (n!). This bound can not be reached. An optimal method for the message size metrics can be determined by making an exhaustive classification of all the test functions as described below.

Number of Probes

For the "number of probes" metric, there exist a lower bound that is log.sub.2 (n!). However, this lower bound cannot be reached for the same counting reason as stated above. A one-time exhaustive search can find the optimal procedure for any n.ltoreq.5.

Trade-offs and Complexity of Algorithms

Given the two metrics mentioned above, it is difficult to define any single optimum solution for a given value of n, although the optimum for the first two metrics is known, and anything else will be somewhere between those two. This makes the complexity metric interesting as it allows one to accurately identify practical procedures.

The following solutions are described below:

I) an optimal solution using exhaustive classification which is practical for n.ltoreq.5;

II) a simple solution for the case where n=4;

III) a series of practical solutions for n=4, which is the case of interest, since it is common to use a look-up table with four inputs, and logically equivalent larger tables can be built from combinations of four input tables; and

IV) a combination of solutions which yields the optimal solution.

Solutions Used for FPGA Elements Other Than Look-up Tables

Some FPGAs do not use LUTs to implement the logic resources. They use much less regular sets of gates with programmable connections. The result is still a function of n binary inputs and 1 binary output. However, the function is more constrained than a full LUT. In this case, depending on the kind of element used, it may still be possible to apply the invention to discover permutations for other FPGA logic resources.

Direct Use of the Configuration Bit-stream

In the method of FIGS. 3 and 4, the original configuration bitstream 340 and the patched version 420 containing useful data. For some applications however, it may not be practical to keep both an original configuration bitstream and patched bitstreams.

For instance, if the invention is used to patch some type of static information in a configuration bitstream and the patching mechanism is not used very often, then it is much more practical to always store a single bitstream which can also be used to discover the permutation. This makes it possible to patch the bitstream, and to have the bitstream contain meaningful data, as shown in FIG. 5.

Each time the bitstream 420 is patched, the patch utility 410 makes sure that the replacement data (test function 320) still permit the discovery of the permutation. This is a slight modification of FIG. 4, as the "original configuration bitstream" 340 is forgotten. In FIG. 5, the original configuration bitstream 340 is replaced by the new "patchable" configuration bitstream 420' which has the same property of enabling the permutation discovery using some selected test function 320, but with different initial values for the "free bits" (message bits). In this case, a "repatched" bitstream 420' is produced.

In this case, the number of information bits that can go through the process is crucial. This number is the same as the "message size". It is clear, however, that the arrangement of the message bits in the test function is not very practical for an internal use of the LUT in the circuit. For the "Solution 4-2 with overlapping" described below, the message bits are at address positions 1100, 0100, 0001, 0111, 1011, 1101, 1110, 0000, 1111. These addresses are not consecutive.

Knowing the test function 320 that is going to be used, it is possible in this case to voluntarily introduce an intermediate encoding stage in front of the input lines of the LUT, so that the message bit values, nine in this case, appear contiguous. The encoder can be an n-input/n-output objective function. In the example, take a function e() so that e(000)=1100, e(0001)=0100, e(0010)=0001, e(0011)=0111, e(0100)=1011, e(0101)=1101, e(0110)=1110, e(0111)=0000 and e(1000)=1111.

This would give the user the choice of the first nine values of the LUT (the "message") while the discovery of the permutation is still possible. This encoding stage doesn't modify the discovery process. It just allows the message bits to appear in order instead of at random positions. Of course, the patching utility 410 must know about this intermediate coding so that the data it embeds in the bitstream look correct from the other side of the encoder.

If it is important only for the "original configuration bitstream" 420 to contain meaningful bits, then more message bits than the normal "message size" can be encoded. In the case of n=4 and the "Solution 4-2 with overlapping", besides the message bits, there is still a number of 1s and 0s taken by the solution. By using the above address encoding, it can be ensured that the first 12 bits of the 16 that can be addressed can look like any desired data. The standard "message" bits is used for part of it, and the mandatory 0s and 1s of the test function are used for the rest. The address encoding function is used to place the remaining 0s and 1s in the good order, so that the first 12 bits, for instance, look like a message that can be processed.

SOLUTIONS

As described below, the following general classes of solutions are given. An optimal solution using an exhaustive classification. A simple solution for a particular sized LUT (four inputs). A series of practical solutions for the four input LUT, and combinations thereof which provide an optimal solution.

I--Optimal Solution using Exhaustive Classification

FIG. 6 shows the steps for discovering the permutation using an exhaustive classification. During classifications 610, all possible test functions are put in equivalence classes, where each function is a permutation of any other test function in the same equivalence class, and the test function has no relation with function in other equivalence classes. This leads to two kinds of classes:

I. Classes of cardinality n! are the useful classes (Class I) 601. If a test function is taken from one of these useful classes, the n! permutation will produce n! different result functions. Thus, if a permutation is applied to any of these functions, then the comparison between the original function and the resulting functions always permits one to identify the applied permutation.

II. Classes of cardinality<n! are useless classes (Class II) 602 that cannot be used for permutation discovery because any test functions in any of these classes do not produce n! different result functions through the n! permutation, but only the cardinality of the class.

Therefore, the only classes of interest are the first type of Class I 601, with a cardinality equal to n!.

In step 620, choose in each useful class 601 a canonical member, e.g., the function with the smallest truth table for some total order. Label each of the canonical members, and thus all the classes, with consecutive integer numbers starting at zero in step 630. For instance, one could sort all the canonical members, and label the members with their sequence number in the sorted array. Message can be viewed as or converted to an integer number in the range of the possible labels in step 630.

For each choice of a test function, transmit a message, and discover the permutation in step 640. The sender encodes the message by using as test function the canonical member labeled with the message. The message is some positive number strictly smaller than the number of classes divided by the number of canonical members.

In step 650, the permutation is discovered by the receiver of the message. The receiver takes the permuted function, applies all the n! permutations to its inputs, and sorts the n! resulting functions. In the example used above, the smallest of all these functions is the canonical member of the class which contains the permuted function.

A simple lookup in the canonical member tables gives its label, which corresponds to the message itself. The permutation used to go from the permuted function and the canonical member is the inverse of the random permutation that is to be discovered. It is obvious that the message is between 0 and the number of classes. The maximum number of bits of the message is then the log.sub.2 of the number of classes.

Experimental data on the number of useful classes for different values of n are given in Table A below.

    TABLE A
            Nb classes/   Message size (log.sub.2  Theoretical bound:
      n     max message      of previous)      log.sub.2 (n!)
      2          4                2                  2
      3         16                4                  5.42
      4        1792              10.81              11.42
      5      34339072            25.03              25.09

• Inventors
  Moll, Laurent Rene; Mitzenmacher, Michael David; Broder, Andrei Z.; Shand, Mark Alexander;
• Assignee
  Compaq Computer Corporation (Houston, TX)
• Published
  Sep-18-2001
• Current US Classes:
  703/1
  703/20
  703/23
  708/160
  713/1
  714/742
  717/124
• Application #
  114753
• International Classes
  G06F 017/50
• Field of Search
  703/20 703/23 703/26 703/27 703/1 708/160 714/742 717/8 713/1
• Examiner
  Teska; Kevin J.
• Agent
  Fenwick & West LLP
• US Patent References:
  5003539
  5159690
  5164943
  5623548
  5684908
  5784636
  5856986
  5943248
  5983022
  6028939