High-throughput bloom filter design: Systematic parameter selection and FPGA implementation
Yüksek veri hacimli bloom filtreleri tasarımı: Sistematik parametre seçimi ve FPGA gerçekleştirimi
- Tez No: 902327
- Danışmanlar: PROF. DR. ŞENAN ECE SCHMİDT
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, 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ı: 128
Özet
Bilgisayar biliminde temel bir kavram olan üyelik testi, bir öğenin bir kümeye ait olup olmadığının kontrol edilmesini içerir. Algoritmalarda, veri yapılarında ve çeşitli uygulamalarda çok önemli bir rol oynar. Bloom Filtreleri (BF'ler), verimli üyelik testi için kullanılan olasılıksal veri yapılarıdır. Öğeleri sabit boyutlu bir bit dizisindeki konumlara özet fonksiyonları ile eşlerler. Üyelik için test yaparken, BF'ler bir öğenin kümede yer alma ihtimalinin olup olmadığını hızlı bir şekilde belirler. Ancak özet fonksiyonlarının çoktan bire doğası nedeniyle yanlış pozitifler ortaya çıkabilir. Bu tezde, belirli uygulama parametrelerine göre BF'lerin tasarımı için ayrıntılı bir model önerilmektedir. Kümedeki dizi sayısı, dizi uzunluğu ve kabul edilebilir yanlış pozitif olasılık gibi paramtereler dikkate alınmaktadır. Yaklaşımımız, uygulama gereksinimlerini karşılarken bellek kullanımını en aza indirmeyi amaçlamaktadır. Önceki çalışmalardan farklı olarak, BF uygulamaları için yaygın olarak kullanılan Alanda Programlanabilir Kapı Dizilerinin (FPGA'ler) ayrık blok RAM yapısı hesaba katılmaktadır. Bu amaçla, tezin ilk ana katkısı, belirli bir yanlış pozitif olasılığa ve dize kümesi boyutuna sahip bir uygulamayı desteklemek için gereken minimum belleğin analitik bir hesaplamasıdır. İkinci ana katkı, belirli bir FPGA platformu için hash fonksiyonunun ve bellek kombinasyonlarının numaralandırılmasına dayanan algoritmik tasarımlı uzay araştırma yöntemidir. Üçüncü katkı ise Bölümlenmiş Bloom Filtrelerinin (PBF'ler) XOR tabanlı karma işlevleriyle yoğun biçimde ardışık düzende uygulanmasıdır. Ayrıntılı FPGA uygulama çalışmaları aracılığıyla önerilen tasarım yaklaşımı ve boruhattı mimarisi değerlendirilmiştir. Çalışmalarımız, özellikle FPGA tabanlı sistemler için verimli BF tasarımına katkıda bulunarak çeşitli alanlarda üyelik testlerinin daha hızlı yapılmasını sağlamaktadır.
Özet (Çeviri)
Membership testing, a fundamental concept in computer science, involves checking whether an element belongs to a set. It plays a crucial role in algorithms, data structures, and various applications. Bloom Filters (BFs) are probabilistic data structures used for efficient membership testing. They rely on hash functions to map elements to positions in a fixed-size bit array. When testing for membership, BFs quickly determine if an element is likely in the set or definitely not. However, false positives can occur due to the many-to-one nature of hash functions. In this thesis, we propose a detailed model for designing BFs tailored to specific application parameters. We consider factors such as the number of strings in the set, string length, and acceptable false positive probability. Our approach aims to minimize memory usage while meeting application requirements. Unlike previous work, we account for the discrete block RAM structure of Field-Programmable Gate Arrays (FPGAs), which are commonly used for BF implementations. To this end, the first main contribution of the thesis is an analytical computation for the minimum memory required to support an application with a given false positive probability and string set size. The second main contribution is an algorithmic design space exploration method based on enumerating hash function and memory combinations for a given FPGA platform. The third contribution is a heavily pipelined implementation of Partitioned Bloom Filters (PBFs) with XOR-based hash functions. We demonstrate the benefits of our design approach and pipelined architecture through detailed FPGA implementation studies. Our work contributes to efficient BF design, especially for FPGA-based systems, enabling faster membership testing across various domains.
Benzer Tezler
- Rare cell enrichment from blood by using dielectrophoresis
Dielektroforez yöntemi ile kandan ender hücre zenginleştirilmesi
GÜRHAN ÖZKAYAR
Yüksek Lisans
İngilizce
2015
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiBiyomedikal Mühendisliği Ana Bilim Dalı
PROF. DR. HALUK KÜLAH
DR. EBRU ÖZGÜR
- Sınıflandırma model performansını geliştirmede ortak karar yaklaşımı ile biyobelirteç keşfi
A consensus approach with biomarker discovery to increase performance of classification model
AYÇA PAMUKCU
Yüksek Lisans
Türkçe
2016
BiyoistatistikMimar Sinan Güzel Sanatlar Üniversitesiİstatistik Ana Bilim Dalı
YRD. DOÇ. DR. AYÇA ÇAKMAK PEHLİVANLI
- Genel amaçlı biopotansiyel kuvvetlendirici
General purposes biomedical signal amplifying
CEYHUN SEZEN
Yüksek Lisans
Türkçe
1992
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ. DR. MEHMET KORÜREK
- Biyolojik işaretlerin gelişmiş bir sayısal işaret işlemcisiyle işlenmesi
Biomedical signal processing using a high performance DSP
DERYA DEMİR
Yüksek Lisans
Türkçe
1991
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ERTUĞRUL YAZGAN
- Hacettepe Üniversitesi İç Hastalıkları Hematopoietik Kök Hücre Transplantasyonu Ünitesi transplant deneyimi 2001-2004
Başlık çevirisi yok
SALİH AKSU
Tıpta Uzmanlık
Türkçe
2004
HematolojiHacettepe Üniversitesiİç Hastalıkları Ana Bilim Dalı
DOÇ. DR. HAKAN GÖKER