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

چکیده: دسته بندی بسته ها، پردازشی اساسی در پردازنده های شبکه ای است. در این فرآیند، بسته های ورودی از طریق تطبیق با مجموعه ای از فیلترها به جریان های مشخص طبقه بندی می شوند. پیاده سازی های نرم افزاری الگوریتم های دسته بندی با وجود هزینه کمتر و توسعه پذیری بیشتر نسبت به پیاده سازی های سخت افزاری، سرعت پایین تری دارند. در این مقاله، از قابلیت پردازش موازی پردازنده های گرافیکی برای تسریع الگوریتم درخت سلسله مراتبی دسته بندی بسته ها، استفاده نموده و سناریوهای متفاوتی را بر اساس معماری حافظه های سراسری و اشتراکی آن ها پیشنهاد می نماییم. نتایج پیاده سازی این سناریوها، ضمن تأیید پیچیدگی های زمانی و حافظه ای محاسبه شده، نشان می دهد کارایی سناریوهایی که مجموعه فیلتر را به صورت زیر درخت هایی کوچک تر یا مساوی حافظه اشتراکی تقسیم و به آن کپی می کنند کم تر از سناریویی است که کل ساختار داده را در حافظه سراسری نگه می دارد.

کارایی این سناریوها، با کاهش تعداد زیر درخت ها و فیلترهای تکراری افزایش می یابد علاوه بر این، سناریویی که بتواند درخت سلسله مراتبی و مجموعه فیلترهای متناظر را، بدون افراز در حافظه اشتراکی جای دهد برترین سناریو است. نتایج آزمایش نشان می دهد که نرخ گذرداد حاصله در این سناریو نسبت به روش های موجود بر روی یک GPU یکسان تا ۲/۱ برابر بهبود می یابد.

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

واژه های کلیدی: دسته بندی بسته، الگوریتم درخت سلسله مراتبی، واحد پردازش گرافیکی، کودا، سلسله مراتب حافلد، پیچیدگی، کارایی