SYSTEM FOR IMPLEMENTATION OF A HASH TABLE

Abstract

The system contains at least one basic block formed by a first multiplexer having an output is connected to a flag register memory, implemented as a LUT table. An output of a circuit for write permit to the memory is connected to the input of the write signal to the memory, which is further equipped with the clock signal input and the data input. The data output from the memory of each basic block is connected to a masking block relevant for the given basic block. The outputs of these masking blocks are connected to the inputs of the second multiplexer, while its output is the output of the system of flags. The input of the control signal for writing to the memory of each basic block is connected to the output of the demultiplexer and to the second input of the masking block for the given basic block.

Claims

1. A system for the implementation of a hash table comprising: at least one basic block, where each basic block is formed by a first multiplexer, which is equipped with first and second address inputs and its output is connected to an address input of a flag register memory implemented as a LUT table, and of a circuit for write permit to the flag register memory, which is equipped with an input of a control signal of writing to the flag register memory, while its output is connected to an input of the write signal to the flag register memory, which is further equipped with a clock signal input and a data input, to which is, via an inverter, connected an input of the control signal for initialization of the flag register memory, which is also interconnected with the control input of a first multiplexer and with the control input of the circuit for write permit to the flag register memory, and a data output from the flag register memory of each basic block is connected to one input of a masking block relevant for the given basic block, where the outputs of these masking blocks are connected to inputs of a second multiplexer, while its output is the output of a system of flags, and where the input of the control signal for writing to the flag register memory of each basic block is connected to the output of a demultiplexer and simultaneously to a second input of the masking block relevant for the given basic block, and this demultiplexer is equipped with an input of the write permit signal, and with an address input, which is interconnected with the output of an address splitter equipped with an input of the address for the whole system of flags for normal operating mode with the width of K bits, where K is a positive integer number, and with an output of the address signal for addressing the flag register memory during normal operating mode, which is interconnected with the first address inputs of the first multiplexers of all basic blocks, while the second address inputs of the first multiplexers of all basic blocks are interconnected with the output of the address signal for addressing the flag register memory for a counter initialization mode, while one input of the counter is interconnected with the inputs of the control signal for the initialization of the flag register memory of the basic blocks and the second input is the input of the clock signal.

Description

EXPLANATION OF DRAWINGS

[0011] A system for implementation of a hash table according to the presented invention will be further explained by means of the attached drawings.

[0012] FIG. 1 shows the diagram of the basic block and

[0013] FIG. 2 shows an example of the connection of the complete system.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0014] The description of the technical solution of a hash table with fast initialization and low demands for system resources is, for better clarity, divided into the description of the basic block 1 in FIG. 1, and the system consisting of the basic block 1 and its supporting functions in FIG. 2.

[0015] The system contains at least one basic block 1. Basic block 1 consists of the first multiplexer 2, a circuit for write permit 3 to the flag register memory 4 and the flag register memory 4 itself implemented as a LUT table.

[0016] The first multiplexer 2 is equipped with the first and second address inputs and its output is connected to the address input 7 of the flag register memory 4. The circuit for write permit 3 to the flag register memory 4 is equipped with the input 8 of the control signal of writing to the flag register memory 4. The output of the circuit for write permit 3 to the flag register memory 4 is connected to the input 10 of the write signal to the flag register memory 4. The flag register memory 4 is further equipped with the clock signal input and data input, to which is, via the inverter 12 connected to the input 9 of the control signal for initialization of the flag register memory 4, which is also interconnected with the control input of the first multiplexer 2 and with the control input of the circuit for write permit 3 to the flag register memory 4. The data output 13 from the flag register memory 4 of each basic block 1 is connected to one input of the masking block 20 relevant for the given basic block 1, see FIG. 2. The outputs 21 of these masking blocks 20 are connected to the inputs of the second multiplexer 22. The output 23 of the second multiplexer 22 is the output of the system of flags. The input 8 of the control signal for writing to the flag register memory 4 of each basic block 1 is connected to the output of the demultiplexer 18 and simultaneously to the second input of the masking block 20 relevant for the given basic block 1. Demultiplexer 18 is equipped with the input 19 of the write permit signal and the address input 17, which is interconnected with the output of the address splitter 15. The address splitter 15 is equipped with the input 16 of the address for the whole system of flags for normal operating mode with the width of K bits, where K is a positive integer number, and with the output 5 of the address signal for addressing the flag register memory 4 during normal operating mode, which is interconnected with the first address inputs of the first multiplexers 2 of all basic blocks 1. The second address inputs of the first multiplexers 2 of all basic blocks 1 are interconnected with the output 6 of the address signal for addressing the flag register memory 4 for the counter 14 initialization mode. One input of the counter 14 is interconnected with the inputs 9 of the control signal for initialization of the flag register memory 4 of the basic blocks 1 and the second input is the input of the clock signal.

[0017] Within the basic block 1, the control signal from the output 5 of the address signal for addressing the flag register memory 4 during normal operating mode, and the control signal from the output 6 of the address signal for addressing the flag register memory 4 for the initialization mode, are brought to the first multiplexer 2. The first multiplexer 2 is controlled by the signal at the input 9 of the control signal for initialization of the flag register memory 4 and its output is connected to the address input 7 of the flag register memory 4. The first multiplexer 2 serves for switching the required address of the flag register memory 4 between the initialization mode and the normal operating mode.

[0018] The circuit for write permit 3 to the flag register memory 4 creates the write signal at the input 10 of the write signal to the flag register memory 4 by logic operator OR based on the incoming control signal at the input 8 of the control signal for writing to the flag register memory 4 during normal operating mode, and the control signal at the input 9 of the control signal for initialization of the flag register memory 4.

[0019] The control signal from the input 9 of the control signal for initialization of the flag register memory 4 is, via the inverter 12 connected to the data input of the flag register memory 4, while its data output 13 indicates the completed write cycle into the selected flag.

[0020] To the input 11 of the clock signal of the flag register memory 4 is connected the clock signal.

[0021] The whole system for implementation of a hash table consists of at least one basic block 1, the corresponding number of masking blocks 20, the counter 14, address splitter 15, demultiplexer 18 and the second multiplexer 22.

[0022] The address from the input 16 of the address for the whole system of flags for normal operating mode with the width of K bits enters the address splitter 15, which splits the address into L of less significant bits, where L corresponds to the number of bits at the address inputs 7 of the flag register memories 4 in basic blocks 1, and this part is connected by the outputs 5 of the address signal for addressing the flag register memories 4 during normal operating mode of all basic blocks 1, and further to K-L of more significant bits, and this part is connected to the address input 17 of the demultiplexer 18.

[0023] When the signal is present at the input 16 of the write permit signal, the demultiplexer 18 transforms the value at address input 17 into activation of one of the outputs connected to the inputs 8 of the control signals for writing into the flag register memories 4 of individual basic blocks 1. The number of control signals at the inputs 8 of the control signals is given by the formula 2̂(K-L).

[0024] Data outputs 13 from the flag register memories 4 of the basic blocks 1 are connected to the corresponding masking blocks 20, the outputs 21 of which are connected to the inputs of the second multiplexer 22. Always only one of all the masking blocks 20 operating as an AND-type logical element is activated by the logical value 1 at the input 8 of the control signal to the flag register memory 4 from the demultiplexer 18, which causes the signal to pass from its input to the output 21. Based on the Boolean algebra rules, specifically the logical 0 neutrality in the logical sum, the second demultiplexer 22 operating as an OR-type logical element provides propagation of the value of the input from the activated masking block 20 to the output of the system of flags 23.

[0025] During the time of activation by the signal of initialization at the input 9 of the control signal for the flag register memory 4 initialization, the counter 14 sets the control signal at the output 6 of the address signal for addressing the flag register memories 4 in all basic blocks 1 for the initialization mode sequentially to all values in residual (modulo) additive group with the basis 2̂L. This ensures that the whole address range of the flag register memories 4 in the basic blocks 1 is generated. The shift between individual steps of the counter 14 is activated by the clock signal from the input 11 of the clock signal, which simultaneously activates all the basic blocks 1.

[0026] The principle of the new solution, therefore, is deployment of a different part, so-called distributed memory, of the FPGA-type integrated circuit for implementation of the system of flags of data validity in a hash table memory cells instead of using the flip-flop circuits. Distributed memory in the FPGA circuit is implemented as a LUT table (Look-Up Table) with the size equal to 2̂n, where n is the number of data inputs and typically it equals 4 or 6. This approach, for example in the case of 6 inputs, allows the creating within a single LUT table a system of flags with the range of 2̂6=64 flags. Even though it is not possible to erase the content of the whole LUT table in a single clock cycle, it is possible to erase the contents of all these distributed memories simultaneously, since they are independent. In this case, the time needed to erase the system of flags is 2̂n clock cycles, which is more than in the case of the alternative exploiting the flip-flop circuits where the erasure can be done within 1 clock cycle, but this time is in orders constant and independent of the size of the hash table.

INDUSTRIAL APPLICABILITY

[0027] The presented solution can find good industrial applicability, for example in systems implementing the LZ77 family data compression algorithms, which use hash tables that must be re-initialized at each activation of the algorithm to required values. The principle of the solution is, in particular, suitable for implementations in the FPGA-type integrated circuits with distributed memory implemented in form of the LUT tables (Look-Up Table).