Data filtering using a plurality of hardware accelerators

Patent metadata

Field	Value
Publication number	US-10387403-B2
Application number	US-201514791832-A
Country	US
Kind code	B2
Filing date	Jul 6, 2015
Priority date	Mar 30, 2015
Publication date	Aug 20, 2019
Grant date	Aug 20, 2019

Abstract

Techniques are provided for data filtering using hardware accelerators. An apparatus comprises a processor, a memory and a plurality of hardware accelerators. The processor is configured to stream data from the memory to a first one of the hardware accelerators and to receive filtered data from a second one of the hardware accelerators. The plurality of hardware accelerators are configured to filter the streamed data utilizing at least one bit vector partitioned across the plurality of hardware accelerators. The hardware accelerators may be field-programmable gate arrays.

First claim

What is claimed is:

1. A method comprising:
streaming, utilizing a processor coupled to a memory, data from the memory to a first one of a plurality of hardware accelerators;
filtering the data in the plurality of hardware accelerators utilizing at least one bit vector partitioned across at least two of the plurality of hardware accelerators; and
receiving filtered data at the processor from a second one of the plurality of hardware accelerators;
wherein the plurality of hardware accelerators are daisy-chain connected to one another;
wherein filtering the data in the plurality of hardware accelerators comprises, in each of the plurality of hardware accelerators, performing a build phase and a probe phase;
wherein performing the build phase comprises:
computing one or more hashes of the streamed data; and
updating the at least one bit vector if the computed hashes are within a range of a corresponding partitioned portion of the at least one bit vector; and

wherein performing the probe phase comprises:
probing the at least one bit vector if the computed hashes are within the range of the corresponding partitioned portion of the at least one bit vector;
generating one or more probed bit values responsive to the probing; and
passing the probed bit values to a next hardware accelerator in the daisy chain; and

wherein the second hardware accelerator comprises a last one of the hardware accelerators in the daisy chain; and
wherein filtering the data in the plurality of hardware accelerators further comprises the second hardware accelerator utilizing the probed bit values passed from at least one other one of the plurality of hardware accelerators to determine whether to: (i) pass a given packet in the streamed data to the processor as part of the filtered data; or (ii) drop the given packet.

2. The method of claim 1 , wherein at least one of the plurality of hardware accelerators comprises a field-programmable gate array.

3. The method of claim 1 , wherein filtering the data in the plurality of hardware accelerators comprises, in each of the plurality of hardware accelerators, utilizing one or more hash functions to compute bit vector indices for its corresponding partitioned portion of the at least one bit vector.

4. The method of claim 1 , further comprising:
computing bit vector indices for the at least one bit vector utilizing one or more hash functions in a given one of the plurality of hardware accelerators; and
forwarding the bit vector indices for the at least one bit vector to other ones of the plurality of hardware accelerators.

5. A method comprising:
streaming, utilizing a processor coupled to a memory, data from the memory to a first one of a plurality of hardware accelerators;
filtering the data in the plurality of hardware accelerators utilizing at least one bit vector partitioned across at least two of the plurality of hardware accelerators; and
receiving filtered data at the processor from a second one of the plurality of hardware accelerators;
wherein the plurality of hardware accelerators are daisy-chain connected to one another;
wherein filtering the data in the plurality of hardware accelerators comprises, in each of the plurality of hardware accelerators:
receiving one or more packets each comprising a set of flags and a value, the set of flags comprising a phase flag and two or more match flags; and
performing one of a build phase and a probe phase responsive to the value of the phase flag;

wherein the second hardware accelerator comprises a last one of the hardware accelerators in the daisy chain; and
wherein filtering the data in the plurality of hardware accelerators further comprises the second hardware accelerator utilizing values of match flags passed from the other ones of the plurality of hardware accelerators to determine whether to: (i) pass a given packet in the streamed data to the processor as part of the filtered data; or (ii) drop the given packet.

6. The method of claim 5 , wherein the build phase comprises programming each of the plurality of hardware accelerators with a corresponding range of said at least one bit vector.

7. The method of claim 6 , wherein the probe phase comprises, for a first hardware accelerator in the daisy-chain, setting each of the match flags for a given packet to a first value.

8. The method of claim 7 , wherein the probe phase comprises, for each hardware accelerator in the daisy-chain:
hashing the value of the given packet using two or more hash functions to compute two or more indices, each index corresponding to a respective one of the match flags;
verifying whether each of the two or more indices are within the corresponding range of a current hardware accelerator of the daisy-chain; and
for each index within the corresponding range of the current hardware accelerator, modifying the corresponding match flag to a second value.

9. The method of claim 8 , wherein the probe phase comprises, for the last hardware accelerator in the daisy-chain:
determining whether each match flag for the given packet is set to the second value;
if each match flag for the given packet is set to the second value, streaming the value of the given packet to the processor as filtered data; and
if one or more match flags for the given packet is set to the first value, dropping the value of the given packet.

10. The method of claim 1 , wherein the plurality of hardware accelerators form a Bloom filter.

11. The method of claim 1 , wherein filtering the data utilizing the plurality of hardware accelerators comprises performing a database join operation.

12. The method of claim 11 , wherein the database join operation comprises a hash join.

13. The method of claim 1 , wherein filtering the data utilizing the plurality of hardware accelerators comprises performing string matching in the streamed data.

14. The method of claim 5 , wherein at least one of the plurality of hardware accelerators comprises a field-programmable gate array.

15. The method of claim 5 , wherein each of the plurality of hardware accelerators is configured to utilize one or more hash functions to compute bit vector indices for its corresponding partitioned portion of the at least one bit vector.

16. The method of claim 15 , further comprising:
computing bit vector indices for the at least one bit vector utilizing one or more hash functions in a given one of the plurality of hardware accelerators; and
forwarding the bit vector indices for the at least one bit vector to other ones of the plurality of hardware accelerators.

17. The method of claim 5 , wherein the plurality of hardware accelerators form a Bloom filter.

18. The method of claim 5 , wherein filtering the data utilizing the plurality of hardware accelerators comprises performing a database join operation.

19. The method of claim 18 , wherein the database join operation comprises a hash join.

20. The method of claim 5 , wherein filtering the data utilizing the plurality of hardware accelerators comprises performing string matching in the streamed data.

Assignees

• IBM

Inventors

• Asaad Sameh W
• Halstead Robert J
• Sukhwani Bharat

Classifications

• G06F16/24554 Primary

  Unary operations; Data partitioning operations · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/24569

  Query processing with adaptation to specific hardware, e.g. adapted for using GPUs or SSDs · CPC title