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

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