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

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