میلاد رفیعی
میلاد رفیعی
دانشکده مهندسی
گروه آموزشی مهندسی کامپیوتر
پایاننامه برای دریافت درجه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات گرایش شبکههای کامپیوتری
عنوان:
ارتقاء عملکرد الگوریتمهای دستهبندی بسته مبتنی بر درخت تصمیم با استفاده از واحد پردازش گرافیکی
استاد راهنما:
دکتر مهدی عباسی
استاد مشاور:
دکتر محمد نصیری
اساتید داور:
دکتر محرم منصوری زاده
دکتر مهدی سخائی نیا
نگارش:
میلاد رفیعی
زمان: یکشنبه 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 |
به اطلاع می رساند یک شرکت دانش بنیان در اصفهان نیازمند خدمات تحقیقاتی دانش آموختگان رشته های مواد و شیمی بوده و استخدام می کند. علاقمندان جهت کسب اطلاعات بیشتر و هماهنگی با شماره 03133879868 در...
به گزارش بسنا، مراسم افتتاحیه این پروژه با حضور محمدعلی زلفیگل وزیر علوم، تحقیقات و فناوری و دکتر علیرضا قاسمیفرزاد استاندار همدان، معاونان وزارتخانههای علوم و مسئولان استانی و ریاست...
دفتر هدایت استعدادهای درخشان دانشگاه بوعلیسینا فهرست اسامی دانشجویان برگزیده آموزشی پژوهشی پانزدهمین همایش سالانه دفتر هدایت استعدادهای درخشان سال ۱۴۰۲ را منتشر کرد. اسامی دانشجویان...
بهراد توتونچی دبیر انجمن علمی دانشجویی مهندسی عمران دانشگاه بوعلی سینا، در جلسه ای با حضور نمایندگان دانشگاه های سراسر کشور، با کسب اکثریت آرا انتخابات، به عنوان دبیر...
در هشتمین نشست از دوره یازدهم هیأت ممیزه دانشگاه بوعلیسینا، آقای دکتر علیرضا حاتمی دارای مدرک دکتری در رشته مهندسی برق با ر أ ی اعضاء از مرتبه...
بدینوسیله انتخاب آقای دکتر آرش فتاح الحسینی را به عنوان پژوهشگر برگزیده دانشگاه در گروه فنی و مهندسی به ایشان و خانواده علمی دانشکده مهندسی تبریک عرض نموده و از خداوند متعال...
بدینوسیله انتخاب دو تن از دانشجویان دانشکده مهندسی مهندس راضیه چهارمحالی در مقطع دکتری رشته مهندسی مواد شاخه خوردگی و مهندسی سطح و مهندس امین نظری در مقطع...
بدینوسیله انتخاب سه عضو هیات علمی دانشکده مهندسی جناب آقایان دکتر جواد بهنامیان ، دکتر حسن علم خواه و دکتر محسن گودرزی در...
براساس اطلاعات پایگاه شاخصهای اساسی علم (ESI)، حضوردکتر محمد حسن مرادی از گروه مهندسی برق دانشکده مهندسی در زمره پژوهشگران پراستناد یک درصد برتر دنیا استمرار پیدا کرد. ...
بدینوسیله انتخاب اعضا محترم هیات علمی سرکار خانم دکتر سموئی (گروه مهندسی صنایع)، جناب آقایان دکتر بابائی (گروه مهندسی عمران)، دکتر حاتمی (گروه مهندسی برق)، دکتر ختن لو (گروه مهندسی...
بدینوسیله انتخاب چهار عضو هیات علمی دانشکده مهندسی جناب آقای دکتر جواد بهنامیان از گروه مهندسی صنایع به عنوان پژوهشگر اول برگزیده، جناب آقای دکتر حسن علم خواه از گروه...
به گزارش بسنا و به نقل از سازمان سنجش، آزمون مرحله نهایی بیست و هشتمین دوره المپیاد علمی دانشجویی کشور با حضور نفرات برگزیده آزمون کارشناسی ارشد (متمرکز) و آزمون غیرمتمرکز المپیاد در دانشگاههای...
به اطلاع دانشجویان محترم می رساند سایت کامپیوتر کارشناسی دانشکده مهندسی به دلیل انجام ثبت نام دانشجویان کارشناسی ورودی 1402 از شنبه 1402/7/22 به مدت یک هفته تعطیل می باشد.
به گزارش بسنا و به نقل از معاونت علمی فناوری ریاست جمهوری، در هشتمین دوره تجلیل از سرآمدان علمی کشور در سال ۱۴۰۲ که با حضور معاون علمی و فناوری و اقتصاد دانشبنیان رئیسجمهور و وزیر علوم...
به اطلاع دانشجویان ورودی جدید تحصیلات تکمیلی (ارشد و دکترا) می رساند، یکشنبه 23 مهر ساعت 11 الی 13 در محل آمفی تئاتر دانشکده مهندسی جلسه معارفه با هیات رییسه دانشکده برگزار می شود. ...
بر اساس اطلاعات جدید نمایه استنادی معتبر scopus ۲۰۲۳، با بررسی مقالات مربوط به ۲۰۲۲، 4 عضو هیات علمی و 1 دانش آموخته دانشکده مهندسی و با بررسی کل مقالات مربوط به سال های مختلف، 1 نفر از اعضای هیات...
نظر به مراتب تعهد، تخصص و تجارب ارزشمند جناب آقای دکتر حسن علم خواه و بنا به پیشنهاد رئیس دانشکده مهندسی، به موجب ابلاغی ایشان با حفظ سمت آموزشی به مدت 2 سال به عنوان...
در حکمی از طرف ریاست دانشگاه آقای دکتر امیرسامان خیرخواه به عنوان مدیر گروه رشته مهندسی صنایع منصوب گردید. در این حکم آمده است : « با احترام و آرزوی توفیق الهی، نظر به مراتب تعهد و تجارب...
در حکمی از طرف ریاست دانشگاه آقای دکتر صالح رازینی به عنوان مدیر گروه رشته مهندسی برق منصوب گردید. در این حکم آمده است : « با احترام و آرزوی توفیق الهی، نظر به مراتب تعهد و تجارب ارزنده...
قابل توجه دانشجویان مصاحبه دکتری: آخرین مهلت شرکت در مصاحبه دکتری برای کلیه رشته ها اعم از برق، کامپیوتر، مواد، صنایع و مکانیک برای دانشجویانی که موفق به انجام مصاحبه...