انجمن کامپیوتر ایران

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