Efficient Bloom filter
Implementation of a Bloom filter using multiple single-ported memory slices. A control value is combined with a hashed address value such that the resultant address value has the property that one, and only one, of the k memories or slices is selected for a given input value, a, for each bank. Collisions are thereby avoided and the multiple hash accesses for a given input value, a, may be performed concurrently. Other embodiments are also described and claimed.
1. A system comprising:
a plurality of k single-ported memory slices, wherein k is greater than or equal to 2;
a plurality of k bloom filter logic modules, each bloom filter logic module coupled to each of the k memory slices, wherein the plurality of k bloom filter logic modules each include a hash module to generate an address value and a control module to perform a control value; and
wherein the plurality of k bloom filter logic modules include a property that, for a given input value, each of the plurality of k bloom filter logic modules is to produce a combined address and control value corresponding to a unique one of the k memory slices, such that no collisions occur among the memory slices for the given input value.
2. The system of claim 1 , further comprising:
a DRAM memory module.
3. The system of claim 1 , wherein each of the plurality of k bloom filter logic modules is associated with one of k processors, wherein the k processors are included in a single chip package.
4. The system of claim 1 , wherein the plurality of k single-ported memory slices are included in the single chip package.
5. The system of claim 1 , wherein the plurality of bloom filter logic modules further include a slice size module to determine the size of the memory slices.
6. The system of claim 1 , wherein the plurality of bloom filter logic modules further include a combine module to utilize the combined outputs of control module and hash module to select an address location in selected one of the slices.
7. The system of claim 1 , further comprising:
the plurality of k bloom filter logic modules coupled to the k memory slices; and
wherein each of the plurality of k bloom filter logic modules is embodied as software logic for one of the k processors.
8. The system of claim 1 , further comprising:
the plurality of k bloom filter logic modules coupled to the memory slices; and
wherein each of the plurality of k bloom filter logic modules is embodied as a hardware circuit for one of the k processors.
9. An apparatus comprising:
a plurality of k hash circuits to each produce a first value;
a control circuit to produce a control value for each of the k first values;
a plurality of k single-ported memory slices, each coupled to each of the hash circuits, wherein k is greater than or equal to 2;
a plurality of k bloom filter logic modules, each bloom filter logic module coupled to each of the k memory slices, wherein the plurality of k bloom filter logic modules each include a hash module to generate an address value and a control module to perform the control value; and
wherein the plurality of k bloom filter logic modules include a property that, for a given input value, each of the plurality of k bloom filter logic modules is to produce a combined address and control value corresponding to a unique one of the k memory slices, such that no collisions occur among the memory slices for the given input value.
10. The apparatus of claim 9 , further comprising a multiplexer to associate the control value with a k first value such that the multiplexer selects an address in a unique of the k memory slices for a given input value, wherein the multiplexer comprises a k multiplexer.
11. The apparatus of claim 10 , wherein:
the multiplexer is coupled with one of the hash circuits to receive an output from the control circuit.
12. A method comprising:
generating a control value to select a unique one of a plurality of k single-ported memory slices of an in-location bloom filter away of a plurality of k block filter logic modules for an input value, wherein k is greater than or equal to 2, each k bloom filter logic module coupled to each of the k memory slices, wherein the plurality of k bloom filter logic modules each include a hash module to generate an address value and a control module to perform the control value, wherein the plurality of k bloom filter logic modules include a property that, for a given input value, each of the k bloom filter logic modules is to produce a combined address and control value corresponding to a unique one of the k memory slices, such that no collisions occur among the memory slices for the given input value;
computing a hashed address value in range 0 . . . M/k for the input value; and
combining the hashed address value and the control value to select a location in selected one of the k single-ported memory slices such that the selected k single-ported memory slice is not selected for any other hashed address generated for the input value.
13. The method of claim 12 , further comprising:
inserting a data value into the selected location in the selected one of the k memory slices.
14. The method of claim 12 , further comprising:
incrementing a value in the selected location in the selected one of the k memory slices.
15. The method of claim 10 , further comprising:
deleting a data value from the selected location in the selected one of the k memory slices.
16. The method of claim 12 , further comprising:
decrementing a data value in the selected location in the selected one of the k memory slices.
17. The method of claim 12 , further comprising:
querying the contents in the selected location in the selected one of the k memory slices.
18. The method of claim 12 , further comprising:
determining the size of the k memory slices.
19. A machine-accessible storage medium comprising instructions which, when executed, cause a machine to:
generate a control value to select a unique one of a plurality of k single-ported memory slices of an m-location bloom filter array of a plurality of k block filter logic modules for an input value, wherein k is greater than or equal to 2, each k bloom filter logic module coupled to each of the k memory slices, wherein the plurality of k bloom filter logic modules each include a hash module to generate an address value and a control module to perform the control value, wherein the plurality of k bloom filter logic modules include a property that, for a given input value, each of the k bloom filter logic modules is to produce a combined address and control value corresponding to a unique one of the k memory slices, such that no collisions occur among the memory slices for the given input value;
compute a hashed address value in range 0 . . . M/k for the input value; and
combine the hashed address value and the control value to select a location in selected one of the k single-ported memory slices such that the selected slice is not selected k single-ported memory for any other hashed address generated for the input value.
20. The machine-accessible storage medium of claim 19 , wherein the instructions which, when executed, further cause the machine to:
insert a data value into the selected location in the selected one of the k memory slices.
21. The machine-accessible storage medium of claim 19 , wherein the instructions which, when executed, further cause the machine to:
increment a value in the selected location in the selected one of the k memory slices.
22. The machine-accessible storage medium of claim 19 , wherein the instructions which, when executed, further cause the machine to:
delete a data value from the selected location in the selected one of the k memory slices.
23. The machine-accessible storage medium of claim 19 , wherein the instructions which, when executed, further cause the machine to:
decrement a data value in the selected location in the selected one of the k memory slices.
24. The machine-accessible storage medium of claim 19 , wherein the instructions which, when executed, further cause the machine to:
query the contents in the selected location in the selected one of the k memory slices.
25. The machine-accessible storage medium of claim 19 , wherein the instructions which, when executed, further cause the machine to:
determine the size of the k memory slices.