میلاد رفیعی - دانشکده فنی و مهندسی
دانشکده مهندسی
گروه آموزشی مهندسی کامپیوتر
پایاننامه برای دریافت درجه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات گرایش شبکههای کامپیوتری
عنوان:
ارتقاء عملکرد الگوریتمهای دستهبندی بسته مبتنی بر درخت تصمیم با استفاده از واحد پردازش گرافیکی
استاد راهنما:
دکتر مهدی عباسی
استاد مشاور:
دکتر محمد نصیری
اساتید داور:
دکتر محرم منصوری زاده
دکتر مهدی سخائی نیا
نگارش:
میلاد رفیعی
زمان: یکشنبه 11 بهمن ماه 94، ساعت 14:00
مکان: آمفیتئاتر دانشکده مهندسی
چکیده:
دستهبندی بستهها، پردازشی اساسی در پردازندههای شبکهای است. در این فرآیند، بستههای ورودی از طریق تطبیق با مجموعهای از فیلترها به جریانهای مشخص طبقهبندی میشوند. پیادهسازیهای نرمافزاری الگوریتمهای دستهبندی با وجود هزینه کمتر و توسعهپذیری بیشتر نسبت به پیادهسازیهای سختافزاری، سرعت پایینتری دارند. در این پژوهش، از قابلیت پردازش موازی پردازندههای گرافیکی برای تسریع الگوریتم درخت سلسلهمراتبی دستهبندی بستهها، استفاده نموده و سناریوهای متفاوتی را بر اساس معماری حافظههای سراسری و اشتراکی آنها پیشنهاد مینماییم. نتایج پیادهسازی این سناریوها، ضمن تأیید پیچیدگیهای زمانی و حافظهای محاسبه شده، نشان میدهد کارایی سناریوهایی که مجموعه فیلتر را بهصورت زیردرختهایی کوچکتر یا مساوی حافظه اشتراکی تقسیم و به آن کپی میکنند کمتر از سناریویی است که کل ساختار داده را در حافظه سراسری نگه میدارد. کارایی این سناریوها، با کاهش تعداد زیردرختها و فیلترهای تکراری افزایش مییابد علاوه بر این، سناریویی که بتواند درخت سلسلهمراتبی و مجموعه فیلترهای متناظر را، بدون افراز در حافظه اشتراکی جای دهد برترین سناریو است. نتایج آزمایش نشان میدهد که نرخ گذرداد حاصله در این سناریو نسبت به روشهای موجود بر روی یک GPU یکسان تا 1/2 برابر بهبود مییابد.
واژههای کلیدی: دستهبندی بسته، الگوریتم درخت سلسلهمراتبی، واحد پردازش گرافیکی، کودا، سلسله مراتب حافظه، پیچیدگی، کارایی
Abstract:
Packet classification is a fundamental process in network processors. In this process, input packets are classified into distinct set of flows via matching against a set of filters. Software implementation of packet classification algorithms, though having lower cost and more scalability as compared with hardware implementations, are slower. In this thesis, we use parallel processing capabilities of the graphical processors to accelerate Hierarchical-Trie packet classification algorithm and propose different scenarios based on the architecture of their global and shared memories. Results of implementing these scenarios, conforming computed time and memory complexities, show that the performance of the scenarios that divide the filter set into sub-trees, equal to/ smaller than the shared memory and copy them to it, is lower than that of a scenario which keeps the total data structure in the global memory. The performance of these scenarios increases by decreasing the number of sub-trees and duplicated filters. Moreover, a scenario that can keep hierarchical tree and corresponding filters in shared memory, without any partitioning, is the best scenario. The experimental results show that, on a same GPU, this scenario attains a throughput of approximately 2.1 times compared to the existing methods.
Keywords: Packet classification, H-trie algorithm, graphical processing unit, CUDA, memory hierarchy, complexity, performance.
مقالات
ردیف |
عنوان |
نام ناشر |
وضعیت |
سال انتشار |
5 |
روشی کارا برای پیادهسازی موازی الگوریتم دستهبندی بسته درخت سلسلهمراتبی بر روی واحد پردازش گرافیکی |
مجله مهندسی برق دانشگاه تبریز، علمی پژوهشی (ISC) |
پذیرفته شده |
1395 |
4 |
افزایش سرعت دستهبندی بستهها به روش درخت سلسلهمراتبی به کمک واحد پردازش گرافیکی |
هفتمین کنفرانس بینالمللی فناوری اطلاعات و دانش (IKT 2015)، دانشگاه ارومیه |
پذیرفته شده |
1394 |
3 |
ارائه و ارزیابی یک چارچوب برای پیادهسازی موازی الگوریتمهای ژنتیک به کمک واحد پردازش گرافیکی |
هفتمین کنفرانس بینالمللی فناوری اطلاعات و دانش (IKT 2015)، دانشگاه ارومیه |
پذیرفته شده |
1394 |
2 |
ارتقا کارایی دستهبندی بستهها در الگوریتمهای فضای چندتایی و الگوریتم فضای هرس شده با استفاده از واحد پردازش گرافیکی |
هفتمین کنفرانس بینالمللی فناوری اطلاعات و دانش (IKT 2015)، دانشگاه ارومیه |
پذیرفته شده |
1394 |
1 |
ارائه مدلی برای تشخیص نفوذ در شبکههای کامپیوتری با استفاده از الگوریتم رگرسیون منطقی |
هفتمین کنفرانس دادهکاوی ایران (IDMC 2013)- دانشگاه تهران |
پذیرفته شده |
1392 |