Realizacja szybkiego wyszukiwania wzorców w układach FPGA

Niniejszy artykuł prezentuje sprzętową realizację filtracji Bloom'a w układach FPGA. Implementacja ta służy do szybkiego wyszukiwania wielu wzorców binarnych bądź znakowych w dużym zbiorze danych. Podczas filtracji Bloom'a sekwencyjnie podawane dane wejściowe są haszowane, a następnie obliczony hash jest porównywany w pamięci z podanymi wzorcami. Proces haszowania ciągu wejściowego jak i porównywanie z wzorcami odbywa się potokowo. Zaproponowana implementacja równoległa w jednym takcie zegara porównuje 16-bajtowy fragment ciągu wejściowego ze wszystkimi wzorcami. Przy uzyskanej szybkości zegara 100 MHz, szybkość przeszukiwania danych wejściowych wynosi 1.6 GB/s.

This paper presents FPGAs implementation of Bloom filters. Consequently a great number of both binary and text patters can be quickly searched for in a large database. For Bloom filters, sequencially fed input data are hashed, then addresses a special memory which output data indicates whether the input string is or is not one of paterns. The whole implementation is strongly pipelined and parallel. Consequently, 16-byte of input data are processed in a single clock cycle at clock frequency 100 MHz, therefore the search throughput is 1.6 GB/s.