فاطمه سجادیان
فاطمه سجادیان
دانشکده مهندسی
گروه آموزشی کامپیوتر
اطلاعیه دفاع از پایاننامه برای دریافت درجه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات گرایش شبکههای کامپیوتری
عنوان:
ارتقاء کارایی الگوریتم دستهبندی بسته ضرب مقاطع با استفاده از خوشه واحد پردازش گرافیکی
استاد راهنما:
دکتر مهدی عباسی
اساتید ممتحن:
دکتر حاتم عبدلی
دکتر محرم منصوریزاده
پژوهشگر:
فاطمه سجادیان
تاریخ دفاع:
سهشنبه 8/12/96 ساعت 16
مکان:
آمفی تئاتر دانشکده مهندسی
Bu-Ali Sina University
Faculty of Engineering
Department of Computer Engineering
Thesis submitted for Master of Science in Information Technology Engineering - Computer Networks
Title
Enhancing the performance of cross product packet classification algorithm using GPU Cluster
Supervisor:
Mahdi Abbasi (Ph. D)
By:
Fateme Sajjadian
February, 27, 2018
چكيده:
از مهمترین پردازشها در پردازندههای شبکهای، دستهبندی بستههاست. این پردازش، بستههای ورودی را با مجموعهای از فیلترها مطابقت میدهد و آنها را به جریانهای مشخص طبقهبندی میکند. پیادهسازیهای سختافزاری الگوریتمهای دستهبندی نسبت به پیادهسازیهای نرمافزاری سرعت بالاتری دارند، اما این راهحلها هزینه بالا و توسعهپذیری کمی دارند. به همین دلیل باید به دنبال روشهایی برای تسریع الگوریتمهای نرمافزاری دستهبندی بستهها بود. یکی از روشهای تسریع این نوع الگوریتمها موازیسازی آنهاست. الگوریتمهای مبتنی بر تجزیه ازجمله روشهای نرمافزاری دستهبندی بستههاست که قابلیت موازیسازی بالایی دارند. بنابراین در این پژوهش، دو الگوریتم مبتنی بر تجزیه ضرب متقاطع و اشتراک نگاشت بیتی با بهکارگیری توانایی پردازش موازی پردازندههای گرافیکی، روی واحد پردازش گرافیکی موازیسازی شده است. موازیسازی الگوریتم اشتراک نگاشت بیتی به دو مدل مختلف و در پنج فیلد صورت گرفته است. در مدل دوم موازیسازی با افزایش سطح موازات و ایجاد تعادل در دسترسی به خانههای مشترک حافظه کارایی الگوریتم بهبود یافته است. در نهایت کارایی دو الگوریتم در شرایط مختلف با هم مقایسه شده است. در ادامه به منظور افزایش موازات، الگوریتمهای مذکور علاوه بر واحد پردازش گرافیکی، بر روی خوشه پردازنده گرافیکی نیز موازیسازی و پیادهسازی شدهاند. در نتیجه میزان تسریع و گذرداد به طور قابل ملاحظهای افزایش یافته است. نتایج آزمایش نشان میدهد که تسریع در موازیسازی روی خوشه پردازنده گرافیکی نسبت به پیادهسازی روی پردازنده مرکزی در الگوریتم ضرب متقاطع برابر با 371، در مدل اول موازیسازی الگوریتم اشتراک نگاشت بیتی برابر با 284 و در مدل دوم موازیسازی الگوریتم اشتراک نگاشت بیتی برابر با 538 است. همچنین نتایج آزمایش نشان میدهد که در مقیاس موازیسازی خوشه پردازنده گرافیکی در تعداد بستههای کمتر یا مساوی با k128 کمترین زمان دستهبندی و بهترین گذرداد مربوط به مدل دوم موازیسازی الگوریتم اشتراک نگاشت بیتی است. در تعداد بستههای بیشتر از k128 کمترین زمان دستهبندی و بهترین گذرداد مربوط به پیادهسازی موازی الگوریتم ضرب متقاطع است. مدل دوم موازیسازی الگوریتم اشتراک نگاشت بیتی در تمام شرایط حافظه مصرفی کمتری نسبت به نسخه موازی الگوریتم ضرب متقاطع دارد.
واژههای کلیدی: دستهبندی بسته، الگوریتم ضرب متقاطع، واحد پردازش گرافیکی، خوشه پردازنده گرافیکی، کودا، کارایی
Abstract:
Packet classification is one of the most fundamental processes in network processors. In this process, input packets are classified into distinct set of flows via matching against a set of filters. Although hardware implementations of classification algorithms are faster than software implementations, these solutions have a high cost and low extensibility. For this reason, it is necessary to look for methods to accelerate the software algorithms of packets classification. Parallelizing is one method of accelerating these types of algorithms. Decomposition-based algorithms are among software methods of packets classification that have high parallelism. Therefore, in this research, two decomposition-based packet classification algorithm, cross product and intersection bitmap, have been parallelized on the GPU, using parallel processing capabilities of the graphical processors. Bitmap intersection algorithm has been parallelized in two different models and in five fields. In the second model, the efficiency of the algorithm has been improved by increasing the level of parallelism and equilibrium in access to shared parts of memory. Finally, the efficiency of the two algorithms has been compared in different situations. In the following, in order to increase the parallelism, the algorithms have been parallelized and implemented on the GPU cluster, in addition to the graphical processing unit. As a result, the amount of expedition and throughput has increased considerably. The results of the experiment show that expedition in parallelization on the GPU cluster compared to the implementation on the CPU, in the cross product algorithm equals 371, in the first model of parallelism of the bitmap intersection algorithm equals 284, and in the second model of parallelism of the bitmap intersection algorithm equals 538. Also, the results of the experiment show that in the scale of parallelism of the GPU cluster, in the number of packets less than or equal to 128 k, the shortest packet classification time and the best throughput is related to the second model of parallelism of the bitmap intersection algorithm. In the number of packets greater than 128 k, the shortest packet classification time and the best throughput is related to the parallel implementation of the cross product algorithm. The second model of parallelism of the bitmap intersection algorithm has less memory consumption than the parallel version of the cross product algorithm, in all conditions.
Key Words: Packet classification, cross prod algorithm, Graphical Processing Unit, GPU cluster, CUDA, performance.
فاطمه سجادیان
مهارتها و توانمندیها
نرمافزارهای شبیهساز و مقلد شبکه، مانند NS3، mininet، opencl
پردازش موازی، سیستمعاملهای موازی
شبکههای مبتنی بر نرمافزار
CCNA، ICDL
آشنا با سیستمعاملهای Windows, Android, Ubuntu, Rocks, Centos
مقالات پذیرفته شده:
مقاله با عنوان " موازیسازی الگوریتم دستهبندي بسته ضرب متقاطع بر روی واحد پردازنده گرافیکی و خوشه پردازنده گرافيكي" در دومین کنفرانس ملی و اولین کنفرانس بینالمللی محاسبات نرم
مقاله با عنوان "موازیسازی الگوریتمهای دستهبندی بسته ضرب متقاطع و اشتراک نگاشت بیتی روی واحد پردازش گرافیکی" در سومین کنفرانس ملی در مهندسی کامپیوتر و فناوری اطلاعات و پردازش دادهها
به گزارش بسنا، مراسم افتتاحیه این پروژه با حضور محمدعلی زلفیگل وزیر علوم، تحقیقات و فناوری و دکتر علیرضا قاسمیفرزاد استاندار همدان، معاونان وزارتخانههای علوم و مسئولان استانی و ریاست...
دفتر هدایت استعدادهای درخشان دانشگاه بوعلیسینا فهرست اسامی دانشجویان برگزیده آموزشی پژوهشی پانزدهمین همایش سالانه دفتر هدایت استعدادهای درخشان سال ۱۴۰۲ را منتشر کرد. اسامی دانشجویان...
بهراد توتونچی دبیر انجمن علمی دانشجویی مهندسی عمران دانشگاه بوعلی سینا، در جلسه ای با حضور نمایندگان دانشگاه های سراسر کشور، با کسب اکثریت آرا انتخابات، به عنوان دبیر...
در هشتمین نشست از دوره یازدهم هیأت ممیزه دانشگاه بوعلیسینا، آقای دکتر علیرضا حاتمی دارای مدرک دکتری در رشته مهندسی برق با ر أ ی اعضاء از مرتبه...
بدینوسیله انتخاب آقای دکتر آرش فتاح الحسینی را به عنوان پژوهشگر برگزیده دانشگاه در گروه فنی و مهندسی به ایشان و خانواده علمی دانشکده مهندسی تبریک عرض نموده و از خداوند متعال...
بدینوسیله انتخاب دو تن از دانشجویان دانشکده مهندسی مهندس راضیه چهارمحالی در مقطع دکتری رشته مهندسی مواد شاخه خوردگی و مهندسی سطح و مهندس امین نظری در مقطع...
بدینوسیله انتخاب سه عضو هیات علمی دانشکده مهندسی جناب آقایان دکتر جواد بهنامیان ، دکتر حسن علم خواه و دکتر محسن گودرزی در...
براساس اطلاعات پایگاه شاخصهای اساسی علم (ESI)، حضوردکتر محمد حسن مرادی از گروه مهندسی برق دانشکده مهندسی در زمره پژوهشگران پراستناد یک درصد برتر دنیا استمرار پیدا کرد. ...
بدینوسیله انتخاب اعضا محترم هیات علمی سرکار خانم دکتر سموئی (گروه مهندسی صنایع)، جناب آقایان دکتر بابائی (گروه مهندسی عمران)، دکتر حاتمی (گروه مهندسی برق)، دکتر ختن لو (گروه مهندسی...
بدینوسیله انتخاب چهار عضو هیات علمی دانشکده مهندسی جناب آقای دکتر جواد بهنامیان از گروه مهندسی صنایع به عنوان پژوهشگر اول برگزیده، جناب آقای دکتر حسن علم خواه از گروه...
به گزارش بسنا و به نقل از سازمان سنجش، آزمون مرحله نهایی بیست و هشتمین دوره المپیاد علمی دانشجویی کشور با حضور نفرات برگزیده آزمون کارشناسی ارشد (متمرکز) و آزمون غیرمتمرکز المپیاد در دانشگاههای...
به اطلاع دانشجویان محترم می رساند سایت کامپیوتر کارشناسی دانشکده مهندسی به دلیل انجام ثبت نام دانشجویان کارشناسی ورودی 1402 از شنبه 1402/7/22 به مدت یک هفته تعطیل می باشد.
به گزارش بسنا و به نقل از معاونت علمی فناوری ریاست جمهوری، در هشتمین دوره تجلیل از سرآمدان علمی کشور در سال ۱۴۰۲ که با حضور معاون علمی و فناوری و اقتصاد دانشبنیان رئیسجمهور و وزیر علوم...
به اطلاع دانشجویان ورودی جدید تحصیلات تکمیلی (ارشد و دکترا) می رساند، یکشنبه 23 مهر ساعت 11 الی 13 در محل آمفی تئاتر دانشکده مهندسی جلسه معارفه با هیات رییسه دانشکده برگزار می شود. ...
بر اساس اطلاعات جدید نمایه استنادی معتبر scopus ۲۰۲۳، با بررسی مقالات مربوط به ۲۰۲۲، 4 عضو هیات علمی و 1 دانش آموخته دانشکده مهندسی و با بررسی کل مقالات مربوط به سال های مختلف، 1 نفر از اعضای هیات...
نظر به مراتب تعهد، تخصص و تجارب ارزشمند جناب آقای دکتر حسن علم خواه و بنا به پیشنهاد رئیس دانشکده مهندسی، به موجب ابلاغی ایشان با حفظ سمت آموزشی به مدت 2 سال به عنوان...
در حکمی از طرف ریاست دانشگاه آقای دکتر امیرسامان خیرخواه به عنوان مدیر گروه رشته مهندسی صنایع منصوب گردید. در این حکم آمده است : « با احترام و آرزوی توفیق الهی، نظر به مراتب تعهد و تجارب...
در حکمی از طرف ریاست دانشگاه آقای دکتر صالح رازینی به عنوان مدیر گروه رشته مهندسی برق منصوب گردید. در این حکم آمده است : « با احترام و آرزوی توفیق الهی، نظر به مراتب تعهد و تجارب ارزنده...
قابل توجه دانشجویان مصاحبه دکتری: آخرین مهلت شرکت در مصاحبه دکتری برای کلیه رشته ها اعم از برق، کامپیوتر، مواد، صنایع و مکانیک برای دانشجویانی که موفق به انجام مصاحبه...
بدینوسیله فرزندان افتخار آفرین دانشکده مهندسی در سال 1401 را معرفی نموده و با عرض تبریک برای این عزیزان موفقیت روزافزون مسالت می نماید. ...