Geri Dön

Design and implementation of a lightweight Bloom filter accelerator for internet of things applications

Nesneleriın interneti uygulamalarına yönelik kaynak verimli bir Bloom filtre hızlandırıcısı tasarımı ve gerçeklemesi

  1. Tez No: 864160
  2. Yazar: HÜSEYİN AYDIN SEYMEN
  3. Danışmanlar: PROF. DR. MÜŞTAK ERHAN YALÇIN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2024
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Elektronik Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Nesnelerin İnterneti (IoT), günlük hayatımızın çeşitli yönlerini etkileyen etkin bir teknoloji olarak ortaya çıkmıştır. Dünya ile etkileşimimizi geliştirmiş, sensörler, giyilebilir cihazlar ve denetleyiciler gibi akıllı cihazların önemli bir rol oynadığı interaktif bir ortam oluşturmuştur. Bu cihazlar değerli bilgi alışverişi ile verimliliği artıracak yeni uygulamaların doğmasını sağlamıştır. Örneğin gerçek zamanlı izleme, otomatik karar verme ve veri analizi gibi teknikler uygulandıkları alanlarda verimliliği artıran etkiler göstermektedir. Bu etki ulaşım, imalat, tarım, sağlık, eğlence ve daha birçok farklı alanda IoT uygulamalarının geliştirilmesine ve uygulanmasına olanak sağlamıştır. Ancak mühendislikteki diğer prensiplere benzer şekilde, IoT de avantajlarının yanında birçok zorluk ve problemi beraberinde getirmiştir. Güvenlik zafiyetleri, gizlilik sorunları, bant genişliği kısıtlamaları, artan karmaşıklık ve cihaz sayısı gibi birçok sorunun ortaya çıktığı görülmektedir. Dolayısıyla bu teknolojinin potansiyeline erişebilmesi, mevcut sorunların kapsamlı ve akılcı çözümlerle aşılmasına bağlıdır. IoT kapsamında ele alınan uygulamaların birçoğu, darboğaza neden olmadan çalışabilmek için hızlı üyelik testlerine ihtiyaç duymaktadır. Güvenli iletişim, veri önbellekleme, tanıma-tanıtma, uç bilişim, öge takibi ve ağ güvenliği gibi uygulamalar üyelik testi ihtiyacını literatürde var olan çeşitli algoritmaları kullanarak karşılamaktadır. Ancak, ağdaki cihaz sayısının artmasıyla bu gereksinimi karşılamak zorlaşmaktadır. IoT cihazlarının pil ömrü, işlem gücü ve bellek alanı; cihaz sayısı ile ölçeklenemediği için algoritmaların daha etkili hale gelmesi gerekmektedir. Bu nedenle Bloom Filtreleri gibi hızlı ve kaynak verimli olasılıksal veri yapılarının değerlendirilmesi, IoT alanına uyarlanması zorunluluğu doğmuştur. Bloom Filtresi, bir elemanın bir küme içerisinde olup olmadığını kontrol etmek için kullanılan düşük kaynak kullanımlı, güç verimli, olasılıksal bir algoritmadır. Olasılıksal bir algoritma olması, hatalı sonuçlar üretebileceği anlamına gelmektedir. Buna karşılık, çok hızlı sorgular yapılabilmesini ve bellek kullanımının önemli ölçüde azaltılmasını sağlamaktadır. Olasılıksal olmayan eşleme yöntemlerine göre ise görece daha az güç tüketmektedir. Algoritma, kümelerin içerdiği öğeleri özet (hash) fonksiyonlarından geçirerek onlara ait birer imza oluşturmaktadır. Bu imzaları da yeni bir tanım kümesi içerisine rastgele olarak dağıtmaktadır. Özetlenmiş öğeler, orijinallerinden küçük olduğu için yeni tanım kümesi asıl veri kümesinden daha az yer kaplamaktadır. Belirtilen adımlarla filtre oluşturulduktan sonra üyelik sorguları aynı özet fonksiyonları kullanılarak yapılmaktadır. Sorgulanan öğelere ait imzalar, bellekte önceden depolanan yeni tanım kümesi adreslenerek kontrol edilmektedir. Adreslenen bellek kısımlarının tamamı orijinal küme öğeleri tarafından halihazırda doldurulmuş ise sorgu olumlu olarak algılanmaktadır. Herhangi bir bellek pozisyonunun boş olması durumu ise negatif sorgu, yani sorgulanan öğenin küme içerisinde olmadığı anlamına gelmektedir. Bu tür algoritmaları hızlandırmak için ASIC'lar (Uygulamaya Özel Entegre Devreler) veya FPGA'lar (Alan Programlanabilir Kapı Dizileri) kullanılmaktadır. Bu araçlar, genellikle yüksek güç veya yüksek maliyetli cihazlardır. Gerçekte ASIC'ler FPGA'lara göre daha güç verimlidir ancak uygulanması, gerçeklenmesi çok maliyetlidir. Ayrıca, esneklikleri FPGA'lara göre çok düşüktür. Bu nedenlerle FPGA'lar, daha yüksek güç tüketimine sahip olmalarına rağmen hızlandırıcı olarak tercih edilebilmektedir. Özellikle birkaç Watt'a kadar güç tüketimine izin verebilen IoT uygulamaları için düşük veya orta seviye FPGA'lar popüler hale gelmeye başlamıştır. Bloom Filtresi birçok açıdan etkili ve verimli bir yöntem olmasına rağmen, IoT uygulamalarına özel olarak eniyilenmelidir. Uç ağ cihazlarına ve IoT sunucularına uygun olabilmesi için bu alana göre eniyilenmiş özet fonksiyonları geliştirilmeli veya tercih edilmelidir. Ancak son zamanlarda yayınlanan çalışmaların çoğu, yanlış pozitif olasılığının düzenlenmesine, uygulamalara özgü iyileştirmelere veya diğer uygulamaları geliştirmek için Bloom Filtrelerinden faydalanılmasına odaklanmaktadır. Bu tasarımlar, genellikle yüksek performanslı, yüksek güç tüketimli sunucularda veya FPGA'larda gerçeklenmektedir. Ancak belirtilen yaklaşımlar IoT uygulamalarına uygun değildir. Bu nedenle tez çalışmasında FPGA tabanlı, düşük güç ve kaynak tüketimini hedefleyen bir Bloom Filtresi hızlandırıcısı tasarımı sunulmuş ve detaylandırılmıştır. Çalışmanın akışı burada belirtildiği şekildedir. İlk olarak Bloom Filtresi ve literatürde belirtilen üstün özelliklerinden dolayı seçilmiş olan MURMUR3 özet fonksiyonunu açıklanmıştır. MURMUR3 özet fonksiyonunun çalışma ilkeleri verildikten sonra yine literatürde mevcut olan Bloom Filtresi hızlandırıcıları paylaşılmıştır. Filtrenin IoT uygulamalarındaki kullanım alanları da örnek çalışmalar gösterilerek vurgulanmıştır. Bu çalışmalardan uygun olanları belirlenmiş, sonraki bölümlerde yapılan karşılaştırmalarla detaylı şekilde incelenmiştir. Ardından tasarımda kullanılan tüm araç ve uygulamalar tanıtılmıştır. Belirlenen özet fonksiyonu ile birlikte önerilen filtre tasarımı tüm adımlarıyla anlatılmış, nispeten düşük kaynağa sahip olan Nexys A7 geliştirme kartı üzerindeki gerçeklemesi detaylandırılmıştır. Ek olarak genel sistem mimarisi, arayüz bilgileri, bellek türü seçimi gibi bilgiler de tasarımın daha iyi anlaşılabilmesi için paylaşılmıştır. Sonrasında tasarımın performans limitlerini ölçebilmek için kurgulanan test sistemi verilmiştir. Tasarım alt parçaları da dikkate alınarak, sistem performansını yansıtan bir formül oluşturulmuş; testler ve analizlerden elde edilen performans, kaynak tahsisi ve güç tüketimi verileri paylaşılmıştır. Ardından sunulan hedeflerden uzaklaşmadan, daha iyi performans elde edebilmek için bazı iyileştirmeler önerilmiş, oluşturulan formülle başarımları tahmin edilmiştir. Toplanan verileri zenginleştirebilmek için, güçlü bir bilgisayar üzerinde gerçeklenen Bloom Filtresi ve performans testlerinin sonuçları paylaşılmıştır. Sonrasında, elde edilen test sonuçlarını ve literatürdeki çalışmaları içeren bir karşılaştırma verilmiştir. Bu kıyasla ilgili detaylar paylaşılarak çalışmaların IoT uygulamalarına uygunlukları değerlendirilmiştir. Güç verimliliği hesaplanabilen çalışmaların tablo şeklinde sunulması ile önerilen tasarımın IoT uygulamalarına en uygun yaklaşımlardan biri olduğu görülmüştür. Yapılan kıyasta, tezde önerilen tasarıma göre kayda değer şekilde yüksek güç verimliliği sunan tek bir çalışma dikkat çekmiştir. Ancak ilgili çalışmanın maliyet etkinliğinin olmadığı, fiziksel büyüklüğünün ve statik güç tüketiminin görece çok fazla olduğu görülmüştür. Bu bilgiler yardımıyla, tezde detaylandırılan çalışmanın, Nesnelerin İnterneti uygulamaları kapsamına en uygun tasarım olduğu sonucuna varılmıştır. Ayrıca tasarım ve açıklanan sonuçlar, hızlı Bloom Filtrelerinin düşük maliyetli FPGA'lar ile IoT alanına uygulanabileceğini göstermektedir. Hızlandırıcılar, yüksek hızlı ağ uygulamalarında sıkça kullanılmasına rağmen, özellikle güç ve kaynak kısıtlarına sahip IoT uygulamalarında henüz yaygın olarak kullanılmamaktadır. Bu nedenle elde edilen sonuçlar, algoritmanın uygunluğunu göstermesi açısından önemlidir. Ayrıca, IoT kapsamında Bloom Filtrelerini iyileştirmeyi veya değiştirmeyi amaçlayan çalışmalar için de bir referans olacaktır. Son olarak, bellek seçiminin filtre performansına etkisi de bu çalışma ile sunulmuştur. Algoritmadaki bellek erişimlerinin rastgele olması bu seçimde belirleyicidir. Nispeten yavaş, rastgele erişimli dış belleklerin yerine çok hızlı kırmık üstü belleklerin kullanılmasının başarımı nasıl etkilediği vurgulanmıştır. Önerilen hızlandırıcı ile sağlanan bellek seçim esnekliği, tasarıma hız ve ölçeklenebilirlik arasındaki ödünleşmeyi yönetme şansı vermiştir.

Özet (Çeviri)

Today, the Internet of Things (IoT) has emerged as a dominant technological framework that significantly impacts various aspects of our everyday lives. It revolutionizes our interactions by integrating smart devices like sensors, wearables, assistants, actuators, and controllers, creating an interconnected environment. This environment facilitates real-time monitoring, automated decision-making, and data analytics through the continuous exchange of valuable information to increase overall effectiveness. While IoT brings numerous advantages, it also introduces new challenges such as increasing network complexity, security vulnerabilities, privacy concerns, and limited bandwidth. Addressing these concerns comprehensively is essential to fully harness the potential of IoT across various fields like manufacturing, transportation, healthcare, etc. To overcome the aforementioned challenges, techniques such as secure communication, data caching, user identification, edge computing, and network attack prevention are employed. Many of these techniques necessitate rapid membership queries to fulfill specified functions without causing any bottlenecks. However, the increasing number of devices within networks poses challenges due to limitations in IoT devices' battery life, processing power, and memory space. Therefore, power and resource-efficient probabilistic data structures like Bloom Filters should be evaluated and implemented. Although the Bloom Filter serves as a powerful algorithm for various purposes, it requires optimization for IoT applications like every other algorithm adopted from high-speed core networks. Developing lightweight implementations with optimized hashing functions is necessary. Also, these algorithms running on conventional IoT processors are not enough to meet the increasing performance demands. Therefore, to accelerate these algorithms, specific devices like ASICs (Application Specific Integrated Circuits) or FPGAs (Field Programmable Gate Arrays) should be utilized. Despite their potential, these devices often come with high power consumption or cost. ASICs are mostly power-efficient devices but they are very costly if not produced in very high volumes. Moreover, they are not as flexible as FPGAs so in some IoT applications, tolerating a few Watts of power consumption, cost-effective FPGAs might be preferred. On the contrary, if large-scale usage is planned ASIC is a better alternative. Despite the growing interest in Bloom Filter accelerators and the usage of FPGAs for IoT functions, most of the existing studies in the literature revolve around algorithms implemented on high-performance servers and FPGAs. Therefore, in this thesis, a Bloom Filter accelerator running on a low-cost, low-resource FPGA is presented to demonstrate its applicability in the context of IoT. Also, the study explores the Bloom Filter theory, the design of the proposed accelerator, and its performance evaluation. The flow of the study adheres to the outline presented herein. Initially, the Bloom Filter and the MURMUR3 hash function are explained. After outlining the principles of the MURMUR3 hash function which is selected due to its superior features, existing Bloom Filter accelerators in the literature are presented. The usage of the filter in IoT applications is emphasized, showing example studies. Suitable ones among these studies are identified and thoroughly examined for comparisons in the following sections. Subsequently, all tools and software employed in the design of the accelerator are provided. The working principles and implementation details of the proposed architecture are described. Additionally, information about the utilized development board (Nexys A7), system architecture, interfaces, and memory type selection is given for better comprehension of the design. Afterward, a test system devised to measure the performance limits of the accelerator is presented. A formula approximating the system performance, considering the design details, is constructed. Processing rate, resource allocation, and power consumption obtained from tests and analyses are provided. Also, some improvements are proposed without deviating from the main objectives, and the effects of these alterations are estimated using the formulated approach. To enrich the collected data, the test results of a Bloom Filter running on a powerful computer are shared. Then, a comprehensive comparison involving the gathered results and studies in the literature is presented. It is aimed to evaluate their suitability for IoT applications. Also, to support these results, power efficiency metrics are summarized in a table which makes it clear that the proposed design is one of the most suitable approaches for IoT applications. In the comparison, only one study showed considerably higher power efficiency than the design proposed in this thesis. However, it was found that this study lacked cost-effectiveness and had a relatively larger physical size. Moreover, the static power consumption of this design is not included in the published metrics. Hence, it is safe to conclude that the accelerator presented in this thesis is the most suitable one among the examined studies for Internet of Things applications. Furthermore, the results achieved in this work indicate that rapid Bloom Filters can be utilized in IoT applications with low-cost FPGAs. Although accelerators for the algorithm are widely used in high-speed network applications, they are not yet commonly utilized for IoT functions, due to power and resource constraints. Therefore, the work is crucial in demonstrating the algorithm's suitability and may serve as a reference for future studies aiming to enhance or modify Bloom Filters in the scope of IoT. Lastly, this study presents how the choice of memory technology affects the filter performance by pointing to the characteristics of memory accesses. Also, the flexibility provided by the accelerator is emphasized, designed to manage the trade-off between speed and scalability of the Bloom Filters.

Benzer Tezler

  1. Tez No

    964700

    Blokzincir tabanlı ıot sağlık platformu ile hasta verilerinin güvenli paylaşımı ve izlenmesi

    Secure sharing and monitoring of patient data through a blockchain-based iot healthcare platform

    GALAL ABDULRAHEEM ALI AHMED

    Yüksek Lisans

    Türkçe

    Türkçe

    2025

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. ÜNAL ÇAVUŞOĞLU

  2. Tez No

    455593

    Design and implementation of a lightweight and modular biped robot for human-like locomotion

    İnsan benzeri hareket için hafif ve modüler iki bacaklı robot tasarımı ve uygulaması

    TOLGA OLCAY

    Doktora

    İngilizce

    İngilizce

    2016

    Mekatronik MühendisliğiDokuz Eylül Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. AHMET ÖZKURT

  3. Tez No

    935643

    Kaos tabanlı hafif sıklet bir şifreleme algoritmasının tasarlanması ve uygulanması

    Design and implementation of a chaos-based lightweight encryption algorithm

    YASİN KAYA

    Doktora

    Türkçe

    Türkçe

    2025

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Üniversitesi-Cerrahpaşa

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ GÜLSÜM ZEYNEP GÜRKAŞ AYDIN

    PROF. DR. AKİF AKGÜL

  4. Tez No

    392230

    Design, control and implementation of CoCoA: A human-friendly autonomous service robot

    Güvenli servis robotu CoCoA'nın insan uyumlu tasarımı, kontrolü ve hayata geçirilmesi

    GÖKAY ÇORUHLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Makine MühendisliğiSabancı Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. VOLKAN PATOĞLU

  5. Tez No

    970268

    An embedded-system and implementation of a telescopic glass for visually impaired

    Görme kaybı olan bireyler için teleskopik gözlük ve gömülü sistem tasarımı ve uygulaması

    TAYLAN PARLAK

    Yüksek Lisans

    İngilizce

    İngilizce

    2025

    Elektrik ve Elektronik Mühendisliğiİstanbul Bilgi Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. YİĞİT DAĞHAN GÖKDEL

Geri Dön