Reconfigurable logic for table lookup
AssigneeChameleon Systems, Inc.
InventorsChristopher E. Phillips, Dale Wong, Laurence H. Cooke
Life of this patent
Estimating the term…
Abstract
An integrated circuit which contains a processor, and configurable logic with configuration memory such that the configurable logic can emulate a large memory array when the contents of the array are very sparse. This structure allows for fast access and a continuous updating capability while remaining internal to the chip. A methodology for recompressing the contents of the configurable logic while updating the configurable logic is also described.
Claims26
An apparatus comprising:
- a processor;
- and
- coupled to the processor, configurable logic and associated configuration latches for defining a fast sparse table lookup function.
A table lookup method using configurable logic, comprising the steps of:
- compressing a large sparse table to minimize resources required by the configurable logic;
- and
- using the configurable logic to execute the table lookup function.
A method of updating a configurable sparse table lookup function comprising the steps of:
- providing updates to the configurable logic;
- maintaining a separate complete and current lookup table;
- compressing the lookup table;
- and
- providing a new configuration to the configurable logic.
A method for incrementally updating an existing hardware lookup table, comprising the steps of:
- receiving an incremental update;
- and
- processing the incremental update in less time than the time required to build an entire table;
- wherein the updates may be in the form of a single entry or a table.
A method for implementing a look up table for performing lookup of data by keys in accordance with key/data associations, comprising the steps of:
- converting key-and-data-associations into a programmable logic implementation of a boolean function whose inputs are the bits of the keys and whose outputs are the bits of the data;
- and
- evaluating the boolean function.
A method for implementing a look up table for performing lookup of data by keys in accordance with key/data associations, comprising the steps of:
- converting key-and-data-associations into a programmable logic implementation of a boolean function whose inputs are the bits of the keys and whose outputs are the bits of the data;
- evaluating the boolean function;
- grouping entries of a table according to one or more designated data field;
- for each group of entries:
- listing all the values of the keys of all the entries in the group;
- treating each bit of the key field as a boolean input, creating a single boolean function which evaluates to TRUE and asserts a match line for the group when its inputs match any of the list of key values in the group, and which evaluates to FALSE and deasserts the match line otherwise;
- and
- creating a decoding function whose inputs are the match lines of the groups and whose output is the value of the one or more designated data fields of the group whose match line is TRUE;
- wherein the boolean function and the decoding function realize a hardware lookup table.
A method for implementing a lookup table in reconfigurable logic wherein each bit of the key field is treated as a Boolean input, by creating a single Boolean function which evaluates to TRUE when its inputs match any of the list of key values in the group, and which evaluates to FALSE otherwise.
A machine-implemented method comprising the steps of:
- incrementally updating an existing reconfigurable logic implementation of a lookup table;
- and
- simultaneously compressing the existing reconfigurable logic implementation of a lookup table.
A method for compressing a reconfigurable logic implementation of a lookup table, comprising:
- adding one or more negative entries which do not exist in the original lookup table and which complete a contiguous block of existing entries such that the contiguous block can be represented by a single entry with an increased number of don't care bits relative to the existing entries alone;
- and
- the configurable logic implementation negating the compressed block with the one or more negative entries.
A method for incrementally updating and simultaneously compressing an existing reconfigurable logic implementation of a lookup table, comprising:
- iteratively selecting a single bit position;
- matching all other bit positions of the update entry with all other existing entries in the lookup table;
- and
- re-encoding all matches with don't-care bits in the selected bit position.
Dependencies are inferred from the claim text.