An FPGA-accelerated string-matching engine
FPGA ile hızlandırılmış bir dizi-eşleme donanımı
- Tez No: 920221
- Danışmanlar: PROF. DR. ŞENAN ECE SCHMİDT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Elektrik ve Elektronik Mühendisliği, Computer Engineering and Computer Science and Control, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 156
Özet
Bir dizi-eşleme donanımı, bir giriş dizisi içinde önceden tanımlanmış desen dizilerini bulur. DNA analizi ve sızma tespit sistemleri gibi çeşitli uygulamalar, yüksek performanslı dizi-eşleme donanımlarına dayanır. Bu tezde, değişken boyutlu tam dizi-eşleme için bir FPGA ile Hızlandırılmış Dizi-Eşleme Donanımı (FASTME) önerilmektedir. FASTME, yüksek verimlilik sağlamak için iyi bilinen ve durum makinesi tabanlı Aho-Corasick algoritmasının paralelleştirilmiş bir versiyonunu uygular. Çok çekirdekli bir mimariye sahip olan FASTME, her çekirdekte birden fazla donanım iş parçacığı bloğu ile FPGAlerin gerçek paralellik, deterministik yapı ve ölçeklenebilirliğinden yararlanır. FASTME, çekirdek ve iş parçacığı sayısı dahil olmak üzere tamamen konfigüre edilebilir olup, farklı desen dizisi setlerini ve performans gereksinimlerini destekler. Önerilen tasarım, içerik adreslenebilir bellekler ile rastgele erişimli bellekleri birleştirerek verimli durum geçişleri sağlar ve bir yerel ara bağlantı tarafından gerçekleştirilen optimize edilmiş bir iş parçacığı tahkim mekanizması ile desteklenir. Donanım parametrelerinin maksimum sentez frekansı ve kaynak tüketimi üzerindeki etkilerini incelemek için kapsamlı bir değerlendirme çalışması yapılmıştır. Ayrıca, farklı özelliklere sahip desen dizileri ve giriş dizileri oluşturularak, karakter başına çevrim sayısı ve elde edilen iş hacmi değerlendirilmiştir. Geleneksel uygulamalarla karşılaştırıldığında, FASTME dizi eşleme konusunda kayda değer iyileştirmeler sunmaktadır. AMD Ultrascale+ Virtex-7 FPGA üzerinde, 2,541 SNORT sızma tespit dizisi için 9.87 Gbps iş hacmine ulaşılmıştır. Azami dizi uzunluğu 100 ile sınırlandırıldığında, 3,305 SNORT dizisi için 10.55 Gbps iş hacmi sağlamıştır. Bu sınır 15 olduğunda, 12,115 SNORT dizisi için 10,15 Gbps ve 279 dizi için 181.77 Gbps iş hacmi elde edilmiştir. FASTME mimarisinin deterministik performansı, sızma tespiti gibi gerçek zamanlı dizi eşleme uygulamaları için idealdir.
Özet (Çeviri)
A string-matching engine locates predefined pattern strings within an input string. Various applications, such as DNA analysis and intrusion detection systems, depend on high-performance string-matching engines. In this thesis, we propose a hardware architecture for variable-sized exact string matching, FPGA-Accelerated String-Matching Engine (FASTME), that implements a parallelized version of the well-known, automata-based Aho-Corasick algorithm to achieve high throughput. It is a multi-core architecture with multiple hardware thread blocks on each core, exploiting parallelism, determinism, and scalability of FPGAs. FASTME is fully configurable, including the number of cores and threads, and supports different pattern string sets and performance requirements. The suggested design combines content-addressable and random-access memories for efficient state transitions, supported by an optimized thread arbitration mechanism performed by a local interconnect. A comprehensive evaluation study is conducted to study the effects of hardware parameters on the maximum synthesis frequency and resource consumption. Furthermore, pattern string sets and input strings with different characteristics are constructed to evaluate the number of cycles per character and the resulting throughput. Compared to traditional implementations, the FASTME shows notable improvements in string matching. On an AMD Ultrascale+ Virtex-7 FPGA, the system achieves throughput rates of up to 9.87 Gbps with 2,541 SNORT intrusion detection signatures. Also, it achieves a 10.55 Gbps throughput rate with 3,305 SNORT signatures when the maximum pattern length is limited to 100. When the limit is 15, FASTME achieves a throughput of 10.15 Gbps and 181.77 Gbps for 12,115 and 279 SNORT signatures. The deterministic performance of FASTME architecture makes it ideal for real-time string-matching applications like intrusion detection.
Benzer Tezler
- FPGA based hardware accelerator for euler equations with finite volume method
Euler denklemleri için sonlu hacimler yöntemi ile FPGA tabanlı donanım hızlandırıcı
EMİNE ELİF YİĞİT
Yüksek Lisans
İngilizce
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiSavunma Teknolojileri Ana Bilim Dalı
DR. ÖĞR. ÜYESİ RAMAZAN YENİÇERİ
- Custom hardware optimizations for reliable and high performance computer architectures
Güvenilir ve yüksek performanslı bilgisayar mimarileri için özel donanım optimizasyonları
HAMZEH AHANGARI
Doktora
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ÖZCAN ÖZTÜRK
- Implementation of a super-resolution algorithm using model composer
Bir yüksek çözünürlük algoritmasının model composer ile gerçeklenmesi
BERKAY UÇKUN
Yüksek Lisans
İngilizce
2023
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SIDDIKA BERNA ÖRS YALÇIN
- Implementation of a neural network application using accelerator on RİSC-V architecture in FPGA
FPGA'de RİSC-V mimarisi üzerinde hızlandırıcı kullanarak yapay sinir ağı uygulaması gerçeklenmesi
AHMET ANIL DÜNDAR
Yüksek Lisans
İngilizce
2023
Elektrik ve Elektronik MühendisliğiHacettepe ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ ZİYA ALKAR
- Hardware accelerated packet parsers and deparsers for high-throughput flow classification in computer networks: Design, implementation and evaluation
Bilgisayar ağlarında yüksek veri hacimli akış sınıflandırması için donanım hızlandırmalı paket ayrıştırıcılar ve birleştiriciler: Tasarım, uygulama ve değerlendirme
ÖMER BAYRAM DEMİR
Yüksek Lisans
İngilizce
2024
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ŞENAN ECE SCHMİDT