یک الگوریتم جستجوی اول سطح کارامد گراف بر روی CPU و GPU
الموضوعات :پریسا کشاورزی 1 , حسین دلداری 2 , سعید ابریشمی 3
1 - دانشگاه آزاد اسلامی، واحد مشهد
2 - دانشگاه فردوسی مشهد
3 - دانشگاه فردوسی مشهد
الکلمات المفتاحية: جستجوی اول سطح پردازنده گرافیکی پردازنده مرکزی کرنل,
ملخص المقالة :
گراف‌ها نمایش داده قدرتمندی هستند که به طور گسترده در حوزه‌های متفاوتی مورد استفاده قرار می‌گیرند. در کاربردهای مبتنی بر گراف یک پیمایش قاعده‌دار از گراف مانند جستجوی اول سطح، غالباً جزء کلیدی در پردازش مجموعه داده‌های بزرگ است. در این مقاله یک روش ترکیبی ارائه شده که برای هر سطح از پیمایش گراف، بهینه‌ترین نسخه از الگوریتم‌های پیاده‌سازی شده بر روی پردازنده مرکزی و پردازنده گرافیکی را انتخاب می‌کند. این روش ترکیبی کارایی خوبی را برای هر اندازه گرافی فراهم می‌کند، در حالی که از کارایی ضعیف روی گراف‌های با میانگین درجه کم و زیاد جلوگیری می‌کند. لازم به ذکر است که این روش بهره سرعت بالاتری نسبت به کارهای پیشین ارائه می‌دهد و نتایج علمی به دست آمده این ادعا را تأیید می‌کنند.
[1] J. Nickolls and W. J. Dally, "The GPU computing era," IEEE Micro, vol. 30, no. 2, pp. 56-69, Mar./Apr. 2010.
[2] T. Coffman, S. Greenblatt, and S. Marcus, "Graph-based technologies for intelligence analysis," Communications of the ACM, vol. 47, no. 3, pp. 45-47, Mar. 2004.
[3] R. Sim and N. Roy, "Global a-optimal robot exploration in slam," in Proc. IEEE Int. Conf. on, Robotics and Automation, ICRA'05, vol. pp. 661-666, Barcelona, Spain, Apr. 2005.
[4] S. Heryrani Nobari, Scalable Data-Parallel Graph Algorithms from Generation to Management, Ph.D. Thesis, University of Singapore, 2012.
[5] U. Brandes, "A faster algorithm for betweenness centrality," the J. of Mathematical Sociology, vol. 25, no. 2, pp. 163-177, 2001.
[6] A. Lumsdaine, D. Gregor, B. Hendrickson, J. Berry, and J. W. Berry, "Challenges in parallel graph processing," Parallel Processing Letters, vol. 17, no. 1, pp. 5-20, 2007.
[7] S. Skiena, The Algorithm Design Manual, Springer, pp. 166-168, 1998.
[8] M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physiscal Review E, vol. 69, no. 2, 16 pp., Feb. 2004.
[9] L. Luo, M. Wong, and W. M. Hwu, "An effective GPU implementation of breadth-first search," in Proc. of the 47th Design Automation Conf., pp. 52-55, 2010.
[10] S. Hong, T. Oguntebi, and K. Olukotun, "Efficient parallel graph exploration on multi-core CPU and GPU," in Proc. of the 2011 Inte. Conf. on Parallel Architectures and Compilation Techniques, pp. 78-88, 2011.
[11] https://developer.nvidia.com/about-cuda
[12] P. Harish and P. J. Narayanan, "Accelerating large graph algorithms on the GPU using CUDA," in HiPC, vol. 4873, Springer, Dec. 2007.
[13] S. Xiao and W. C. Feng, "Inter-block GPU communication via fast barrier synchronization," in Proc. IEEE Int. Symp. on Parallel & Distributed Processing, IPDPS'10, 12 pp., 2010.
[14] NVidia, C Best Practices Guide, NVIDIA Corp., Santa Clara, CA, US, 2012.
[15] http://www.dis.uniroma1.it/~challenge9/
[16] Stanford Large Network Dataset Collection, Feb. 2013, http://snap.stanford.edu/data
