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

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