یک الگوریتم جستجوی اول سطح کارامد گراف بر روی CPU و GPU
محورهای موضوعی : مهندسی برق و کامپیوتر
پریسا کشاورزی
1
,
حسین دلداری
2
,
سعید ابریشمی
3
1 - دانشگاه آزاد اسلامی، واحد مشهد
2 - دانشگاه فردوسی مشهد
3 - دانشگاه فردوسی مشهد
کلید واژه:
چکیده مقاله :
گراف‌ها نمایش داده قدرتمندی هستند که به طور گسترده در حوزه‌های متفاوتی مورد استفاده قرار می‌گیرند. در کاربردهای مبتنی بر گراف یک پیمایش قاعده‌دار از گراف مانند جستجوی اول سطح، غالباً جزء کلیدی در پردازش مجموعه داده‌های بزرگ است. در این مقاله یک روش ترکیبی ارائه شده که برای هر سطح از پیمایش گراف، بهینه‌ترین نسخه از الگوریتم‌های پیاده‌سازی شده بر روی پردازنده مرکزی و پردازنده گرافیکی را انتخاب می‌کند. این روش ترکیبی کارایی خوبی را برای هر اندازه گرافی فراهم می‌کند، در حالی که از کارایی ضعیف روی گراف‌های با میانگین درجه کم و زیاد جلوگیری می‌کند. لازم به ذکر است که این روش بهره سرعت بالاتری نسبت به کارهای پیشین ارائه می‌دهد و نتایج علمی به دست آمده این ادعا را تأیید می‌کنند.
Graphs are powerful data representations used in enormous computational domains. In graph-based applications, a systematic exploration of graph such as a breath first search often is a fundamental component in the processing of the vast data sets. In this paper we presented a hybrid method that in each level of processing of graph chooses the best implementation of algorithms implemented on CPU or GPU, while avoid poor performance on low and high degree graphs. Our method shows improved performance over the current state-of-the-art implementation and our results proves it.
