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

Abstract

<strong>چکیده:</strong> دسته­بندی بسته­ها، پردازشی اساسی در پردازنده­های شبکه­ای است. در این فرآیند، بسته­ها­ی ورودی از طریق تطبیق با مجموعه­ای از فیلترها به جریان­های مشخص طبقه­بندی می­شوند. پیاده‌سازی‌های نرم‌افزاری الگوریتم­های دسته­بندی با وجود هزینه کم‌تر و توسعه‌پذیری بیش‌تر نسبت به پیاده‌سازی­های سخت‌افزاری، سرعت پایین‌تری دارند. در این مقاله، از قابلیت پردازش موازی پردازنده‌های گرافیکی برای تسریع الگوریتم درخت سلسله‌مراتبی دسته­بندی بسته­ها، استفاده نموده و سناریوهای متفاوتی را بر اساس معماری حافظه‌های سراسری و اشتراکی آن‌ها پیشنهاد می­نماییم. نتایج پیاده‌سازی این سناریوها، ضمن تأیید پیچیدگی­های زمانی و حافظه­ای محاسبه­شده، نشان می­دهد کارایی ­سناریوهایی که مجموعه فیلتر را به‌صورت زیردرخت­هایی کوچک‌تر یا مساوی حافظه اشتراکی تقسیم و به آن کپی می­کنند کم‌تر از سناریویی است که کل ساختار داده را در حافظه سراسری نگه می­دارد. کارایی این سناریوها، با کاهش تعداد زیردرخت­ها و فیلترهای تکراری افزایش می­یابد علاوه بر این، سناریویی که بتواند درخت سلسله‌مراتبی و مجموعه فیلترهای متناظر را، بدون افراز در حافظه اشتراکی جای دهد برترین سناریو است. نتایج آزمـایش نـشان می­دهد که نرخ گذرداد حاصله در این سناریو نسبت به روش­های موجود بر روی یک GPU یکسان تا 1/2 برابر بهبود می­­یابد.