فاطمه سجادیان

فاطمه سجادیان


تاریخ انتشار : Publish : نسخه قابل چاپ Print

 

دانشکده مهندسی

گروه آموزشی کامپیوتر

 اطلاعیه دفاع از پایان‌نامه برای دریافت درجه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات گرایش شبکه‌های کامپیوتری

 عنوان:

 ارتقاء کارایی الگوریتم دستهبندی بسته ضرب مقاطع با استفاده از خوشه واحد پردازش گرافیکی

 

 

استاد راهنما:

دکتر مهدی عباسی

 اساتید ممتحن:

دکتر حاتم عبدلی

دکتر محرم منصوری‌زاده

 

پژوهشگر:

فاطمه سجادیان

 

تاریخ دفاع:

سه‌شنبه 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.

 

 

فاطمه سجادیان

Fateme.sajadiyan@gmail.com

 

 

مهارت­ها و توانمندی­ها

نرم­افزارهای شبیه­ساز و مقلد شبکه، مانند NS3، mininet، opencl

پردازش موازی، سیستم­عامل­های موازی

شبکه­های مبتنی بر نرم­افزار

CCNA، ICDL

آشنا با سیستم­عامل­های  Windows, Android, Ubuntu, Rocks, Centos

 

مقالات پذیرفته شده:

مقاله با عنوان " موازی‏سازی الگوریتم دسته­بندي بسته­ ضرب متقاطع بر روی واحد پردازنده گرافیکی و خوشه پردازنده گرافيكي" در دومین کنفرانس ملی و اولین کنفرانس بین‏المللی محاسبات نرم

مقاله با عنوان "موازی‌سازی الگوریتم‌های دسته‌بندی بسته ضرب متقاطع و اشتراک نگاشت بیتی روی واحد پردازش گرافیکی" در سومین کنفرانس ملی در مهندسی کامپیوتر و فناوری اطلاعات و پردازش داده­ها