معیاری جدید برای بخش‌بندی سیستم‌های پردازش گراف مبتنی بر بلوک
محورهای موضوعی : electrical and computer engineeringمسعود ساغریچیان 1 , مرتضی علیپور لنگوری 2
1 - دانشگاه الزهرا
2 - دانشگاه مکمستر
کلید واژه: بخش‌بندی, مبتنی بر بلوک, گراف, قطر,
چکیده مقاله :
به واسطه قدرت و سادگی، سیستم‌های پردازش گراف مبتنی بر بلوک در سال‌های اخیر مورد توجه ویژه‌ای قرار گرفته‌اند. اغلب این سیستم‌ها از روش‌های بخش‌بندی عمومی و همه‌منظوره جهت تولید پارتیشن‌های مورد نیاز خود استفاده می‌کنند. همین امر منجر شده که کارایی این سیستم‌ها محدود شود. برای رفع این مشکل الگوریتم‌های خاص‌منظوره‌ای برای بخش‌بندی این دسته از سیستم‌ها ارائه شده است، اما مشکل این دسته از روش‌ها آن است که همچنان معیارهای سنتی نظیر تعداد یال برشی و تعادل بار به عنوان تابع هدف این روش‌ها مد نظر قرار گرفته است. این در حالی است که قدرت سیستم‌های پردازش گراف مبتنی بر بلوک به واسطه ویژگی‌های منحصر به فردی است که در طراحی این دسته از سیستم‌ها مد نظر قرار گرفته است. به همین جهت در این مقاله، ویژگی‌های ذاتی و اساسی این دسته از سیستم‌ها مورد توجه قرار گرفته و با توجه به این خواص، دو معیار جدید به عنوان معیار تابع هدف بخش‌بندی، معرفی شده است. بر اساس تحقیقات انجام‌گرفته، روش پیشنهادی اولین الگوریتم بخش‌بندی است که قطر گراف سطح بالا و اندازه گره‌های گراف سطح بالای حاصل از بخش‌بندی را به عنوان تابع هدف در نظر گرفته می‌گیرد. ارزیابی روش پیشنهادی بر روی مجموعه داده‌های واقعی نشان داد که روش پیشنهادی به طور مؤثری قادر به کاهش قطر گراف سطح بالای حاصل از بخش‌بندی نسبت به سایر الگوریتم‌های بخش‌بندی متداول می‌باشد. به علاوه، یال برشی حاصل از روش پیشنهادی بسیار نزدیک به یکی از معروف‌ترین روش‌های بخش‌بندی متمرکز، متیس می‌باشد. از آنجا که قطر گراف سطح بالا رابطه مستقیمی با تعداد سوپراستپ‌های مورد نیاز در سیستم‌های پردازش گراف بلوکی دارد، روش پیشنهادی با کاهش آن قادر به افزایش کارایی این دسته از روش‌ها خواهد شد.
Block-centric graph processing systems have received significant attention in recent years. To produce the required partitions, most of these systems use general-purpose partitioning methods. As a result, the performance of them has been limited. To face this problem, special partitioning algorithms have been proposed by researchers. However, these methods focused on traditional partitioning measures like the number of cutting-edges and the load-balance. In return, the power of block-centric graph processing systems is due to unique characteristics that are focused on the design of them. According to basic and important characteristics of these systems, in this paper two new measures are proposed as partitioning goals. To the best of our knowledge, the proposed method is the first work that considers the diameter and size of the high-level graph as optimization factors for partitioning purposes. The evaluation of the proposed method over real graphs showed that we could significantly reduce the diameter of the high-level graph. Moreover, the number of cutting-edges of the proposed method are very close to Metis, one of most popular centralized partitioning methods. Since the number of required supersteps in block-centric graph processing systems mainly depends on the diameter of the high-level graph, the proposed method can significantly improve the performance of these systems.