# US 10,372,700 B2 · Data filtering using a plurality of hardware accelerators > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,700 B2 - Document ID: US10372700B2 - Status: Granted - Kind: B2 - Application number: 14/672,630 - Filed: 2015-03-30 - Published: 2016-10-06 - Granted: 2019-08-06 - Earliest claimed: 2015-03-30 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Sameh W. Asaad; Robert J. Halstead; Bharat Sukhwani - Web page: https://patentgrep.com/patent/US10372700B2 ## CPC - G06F 16/2365: {Ensuring data consistency and integrity} - G06F 16/24554: {Unary operations; Data partitioning operations} - G06F 16/24569: {Query processing with adaptation to specific hardware, e.g. adapted for using GPUs or SSDs} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 An apparatus comprising: a processor; a memory; and a plurality of hardware accelerators; wherein 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; wherein 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; wherein the plurality of hardware accelerators are daisy-chain connected to one another; wherein each of the plurality of hardware accelerators is configured to perform a build phase and a probe phase; wherein 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 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, the second hardware accelerator being configured to utilize the probed bit values 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. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein at least one of the hardware accelerators comprises a field-programmable gate array. ### Claim 3 (depends on 1) The apparatus of claim 1, wherein the plurality of hardware accelerators form a Bloom filter. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein the streamed data is forwarded between respective ones of the plurality of hardware accelerators. ### Claim 5 (depends on 1) The apparatus of claim 1, 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. ### Claim 6 (depends on 1) The apparatus of claim 1, wherein a given one of the plurality of hardware accelerators is configured: to utilize one or more hash functions to compute bit vector indices for the at least one bit vector; and to forward the bit vector indices for the at least one bit vector to other ones of the plurality of hardware accelerators. ### Claim 7 An apparatus comprising: a processor; a memory; and a plurality of hardware accelerators; wherein 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; wherein 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; wherein the plurality of hardware accelerators are daisy-chain connected to one another; and wherein each of the plurality of hardware accelerators is configured: to receive 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 to perform 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, the second hardware accelerator being configured to utilize 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. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein the build phase comprises programming each of the plurality of hardware accelerators with a corresponding range of said at least one bit vector. ### Claim 9 (depends on 8) The apparatus of claim 8, wherein the probe phase comprises: for a first hardware accelerator in the daisy-chain, setting each of the match flags for the given packet to a first value; 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; for a 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. ### Claim 10 (depends on 1) The apparatus of claim 1, wherein the plurality of hardware accelerators are configured to filter the streamed data by performing a database join operation. ### Claim 11 (depends on 10) The apparatus of claim 10, wherein the database join operation comprises a hash join. ### Claim 12 (depends on 1) The apparatus of claim 1, wherein the plurality of hardware accelerators are configured to filter the streamed data by performing string matching in the streamed data. ### Claim 13 (depends on 1) The apparatus of claim 1, wherein the plurality of hardware accelerators are configured to filter the streamed data by performing a search of the streamed data. ### Claim 14 (depends on 7) The apparatus of claim 7, wherein the plurality of hardware accelerators are configured to filter the streamed data by performing a database join operation. ### Claim 15 (depends on 7) The apparatus of claim 7, wherein the plurality of hardware accelerators are configured to filter the streamed data by performing string matching in the streamed data. ### Claim 16 (depends on 7) The apparatus of claim 7, wherein the plurality of hardware accelerators are configured to filter the streamed data by performing a search of the streamed data. ### Claim 17 (depends on 7) The apparatus of claim 7, wherein at least one of the hardware accelerators comprises a field-programmable gate array. ### Claim 18 (depends on 7) The apparatus of claim 7, wherein the plurality of hardware accelerators form a Bloom filter. ### Claim 19 (depends on 7) The apparatus of claim 7, wherein the streamed data is forwarded between respective ones of the plurality of hardware accelerators. ### Claim 20 (depends on 7) The apparatus of claim 7, 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.