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

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