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

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

کلیدواژه ها:

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