Realizacja szybkiego wyszukiwania wzorców w układach FPGA

• Autorzy: Machaczek K. , Russek P. , Jamro E. , Wiatr K.

Warianty tytułu

EN

FPGA implementation of fast patterns search

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

FPGA; filtr Blooma; wyszukiwanie wzorców

EN

FPGA; Bloom Filter; patterns search

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2008
• Tom: R. 54, nr 8
• Strony: 540--542
• Opis fizyczny: Bibliogr. 7 poz., rys., tab., wzory

Twórcy

autor

Machaczek K.

autor

Russek P.

autor

Jamro E.

autor

Wiatr K.

• Katedra Elektroniki, Akademia Górniczo-Hutnicza w Krakowie,

Bibliografia

• [1] Cheng-Hung Lin, Chih-Tsun Huang, Chang-Ping Jiang, Shih-Chieh Chang, Optimization of Pattern Matching Circuits for Regular Expression on FPGA, IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 15, NO. 12, pp. 1303-1310, Dec. 2007.
• [2] I. Sourdis, J. Bispo, et. al. Regular Expression Matching in Reconfigurable Hardware, Int. Journal of Signal Processing Systems for Signal, Image, and Video Technology (Springer), 2007.
• [3] B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, July 1970.
• [4] S. Dharmapurikar, P. Krishnamurthy, T. Sproull, J. Lockwood, Deep Packet Inspection Using Parallel Bloom Filters , (HOTI'03): Hot Interconnects 11: Stanford, CA, 8/03, 2003.
• [5] D. C. Suresh , Z. Guo, B. Buyukkurt, W.A. Najjar Automatic Compilation Framework for Bloom Filter Based Intrusion Detection, Automatic Compilation Framework for Bloom Filter Based Intrusion Detection. ARC 2006 - Lecture Notes in Computer Science, Volume 3985: pp. 413-418, 2006.
• [6] A. Jacob, M. Gokhale, Language classification using n-grams accelerated by FPGA-based Bloom filters, Conference on High Performance Networking and Computing, Reno, Nevada pp. 31-37, November 11 - 11, 2007.
• [7] Silicon Graphics, Inc., Reconfigurable Application-Specific Computing User’s Guide, Ver. 004, Mar 2006, SGI.