دانشكده فني مهندسي

گروه مهندسي کامپیوتر

 

 جلسه دفاعیه پایان نامه جهت دريافت درجه كارشناسي ارشد در رشته مهندسی کامپیوتر

گرايش شبکه‏های کامپیوتری

 

عنوان:

ارتقا کارایی دسته‌بندی بسته ‏ها در الگوریتم‌های فضای چندتایی با استفاده از واحد پردازش گرافیکی

 

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

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

 

داوران:

دکتر محمد نصیری

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

 

نگارش:

علی نجفی

 

زمان: یک شنبه  5 مهر ماه 94 ، ساعت 19:30

مکان: آمفی تئاتر دانشکده مهندسی

چكيده:

دسته‌بندي بسته‌ها يکي از پردازش‌هاي اساسی در مولفه­هاي متنوع شبکه­اي است که اغلب توسط پردازنده‌هاي شبکه‌اي اجرا مي­گردد. اين فرايند خودکار جريان­هاي ترافيکي شبکه را  براساس پارامترهاي متعدد از جمله شماره درگاه و آدرس فرستنده و گيرنده دسته­بندي مي­نمايد. هرچند، تسريع الگوريتم­هاي دسته‌بندي بسته­ها از طريق پياده‌سازي سخت‌افزاري آن‏ها ممکن است، اين راه‌حل‌ هزينه­ بالا و توسعه‌پذيري محدودي دارد. در مقابل، روش‌هاي نرم‌افزاري که اين مشکلات را برطرف مي‌کنند سرعت پائيني دارند. يک ايده کليدي براي رفع اين مشکل، موازي‏سازي دسته­بندي بسته‏ها روي واحدهاي پردازش گرافيکي است. در اين پژوهش، فرم‏هاي موازي الگوريتم­هاي جستجوي فضاي چندتايي و فضاي هرس شده  براي دسته‏بندي بسته‏ها بر روي پردازنده‏هاي گرافيکي با بهره­گيري از بستر نرم‏افزاري کودا بررسي شده است. براي استفاده از بالاترين سطح موازات ارائه شده توسط کودا، موازاتي ريزدانه مورد توجه قرار گرفته است. در فرم پيشنهادي، پس از انتقال جريان بسته‏ها از حافظه ميزبان به حافظه سراسری پردازنده گرافيکي، هر بسته به يک پردازش نخي منتسب مي­شود تا دسته‏بندي شود. همچنين، کارايي پياده سازي­ موازي الگوريتم­هاي مذکور با درنظر گرفتن پنج سناريوي ممکن براي ذخيره­سازي قوانين دسته‏بندي و سرآيند بسته­ها درحافظه­هاي متفاوت واحد پردازش گرافيکي ارزيابي شده است. نتايج نشان مي­دهد، نسخه­هاي موازي شده الگوريتم­ها روي واحد پردازش گرافيکي، از نظر سرعت و گذرداد نسبت به نسخه متوالي ­متناظر روي واحد پردازش مرکزي برتر هستند. همچنين، بالاترين کارايي الگوريتم موازي شده زماني حاصل مي­شود که حافظه تسهيم شده واحد پردازش گرافيکي براي ذخيره­سازي مجموعه قوانين و سرآيند بسته­ها استفاده شود. علاوه بر این، الگوریتم­های جستجوی فضای چندتایی و فضای هرس شده به چهار روش ممکن در سیستم‏های چند پردازنده‏ها  موازی‏‏سازی شدند. مقایسه نتایج ارزیابی­ها نشان می‏دهد، نسخه موازی شده الگوریتم‏ها روی واحد پردازش گرافیکی نسبت به نسخه موازی  متناظر روی سیستم­های چند پردازنده‏ها، از نظر سرعت و گذرداد عملکرد بهتری را دارد.

واژه­های کلیدی: دسته‎بندی بسته‎ها، جستجوی فضاي چندتايي، فضای هرس شده، واحد پردازش گرافیکی، پردازش موازی، چندپردازنده، كارايي

Abstract: packet classification is one of the primary processes in diverse network elements which often is run by network processors. This automatic process classifies network traffic flows based on several parameters including port number and address of the source and des­tination. Though it is possible to accelerate packet classification algorithms through their hardware implementation, this solution has a high cost and a limited extensibility­. On the other hand, software methods which solve these problems suffer from low speed. A key idea to solve this problem is to parallelize packet classification on graphical processing units (GPUs).  In this paper, we study parallel forms of tuple space search and tuple pruning algorithms to classify packets on GPUs using CUDA platform. To achieve the highest level of parallelism offered by CUDA, a fine-grain parallelism is considered. ­In the proposed form, after transferring packets from the host memory to the general memory of GPU, each packet is assigned to a thread to be classified. In addition, the performance of parallel implementation of aforementioned algorithms is evaluated considering five possible scenarios of storing classification rules and packet headers in different memory modules of GPU. Results show that parallel versions of algorithms on GPU, are superior to their corresponding sequential versions on CPU, in speed and throughput. In addition, the highest performance of the parallel algorithm is achieved when the shared memory of GPU is used to store the rule-set and packet headers. Moreover, we are parallelized Tuple Space Search and Tuple Pruning algorithms  on multiprocessor  systems via four possible methods. Comparing vluation results shows that the parallel versions of these algorithms on GPU are better than corresponding parallel versions on multiprocessor systems in speed and throughput.

Key Words: Packet Classification, Tuple Space Search, Tuple Pruning, GPU, Parallel Process, High-Performance

 

مشخصات فردی

 

 

 

v    نام پدر:               باقر

v    تاریخ تولد:           31/3/1369

v    آدرس:                 همدان، چهار راه پژوهش، خوابگاه پژوهش

v    امکان‌ ارتباطی:

Ø       آدرس پست الکترونیک: ali.najafi1369@yahoo.com    

 

سوابق تحصیلی

 

 

v    دیپلم:                         ریاضی فیزیک ، دبیرستان شاهد 13

v    کارشناسی:                   فناوری اطلاعات ، دانشگاه پیام نور شیراز

v    کارشناسی ارشد:           فناوری اطلاعات (IT) ،گرایش شبکه‌های کامپیوتری، دانشگاه بوعلی سینا همدان

 

مقالات

 

 

v    علی نجفی، میلاد رفیعی، مهدی عباسی، ارتقا کارایی دسته‏بندی بسته‏ها در الگوریتم‏های فضای چندتایی و الگوریتم فضای هرس شده با استفاده از واحد پردازش گرافیکی، هفتمین کنفرانس بین‏المللی فناوری اطلاعات و دانش، دانشگاه ارومیه، 5-7 خرداد 1394

v    میلاد رفیعی، علی نجفی، مهدی عباسی، محمد نصیری، افزایش سرعت دسته‏بندی بسته‏ها به روش درخت سلسله‏مراتبی به کمک واحد پردازش گرافیکی، هفتمین کنفرانس بین‏المللی فناوری اطلاعات و دانش، دانشگاه ارومیه، 5-7 خرداد 1394