پردازش توزيع‌شده‌ گراف‌هاي بزرگ مقياس

دكتري

چكيده وجود يال‌هاي بسيار زياد و بي‌نظم در گراف منجر شده است پردازش توزيع‌شده‌ي گراف‌هاي بزرگ مقياس از دو مساله‌ي اساسي رنج برند. مساله‌ي اول، ميزان توازي پايين به واسطه‌ي محليت ضعيف در گراف مي‌باشد. مساله‌ي دوم، بالا بودن ميزان ارتباطات بين ماشين‌ها در گراف افراز شده مي‌باشد. اين دو مشكل نه تنها باعث شده است ميزان ترافيك شبكه در سيستم‌هاي پردازش توزيع‌شده‌ي گراف بسيار بالا باشد، بلكه كارايي اين سيستم‌ها نيز به دليل بهره‌وري ضعيف از منابع محاسباتي پايين مي‌باشد. به منظور غلبه بر مشكل اول، يك مدل محاسباتي جديد جهت پردازش توزيع‌شده‌ي گراف ارائه شده است. هدف اصلي اين مدل استفاده‌ي هر چه بيشتر از اطلاعات محلي به منظور افزايش استقلال ماشين‌ها از يكديگر و كاهش ترافيك شبكه مي‌باشد. ايده‌ي اساسي در طراحي اين مدل آن است كه هر ماشين تا حد امكان محاسبات را به صورت مستقل پيش برد و تنها زماني كه قادر به ادامه نباشد، با ماشين‌هاي ديگر تبادل اطلاعات كند. مدل پيشنهادي با بهره‌گيري توام از مزاياي معماري‌هاي موازي با حافظه‌ي مشترك و توزيع‌شده، مدلي سه لايه ارائه داده است. در هر لايه، هر گره تنها قادر به تبادل اطلاعات با زيرمجموعه‌ي خاصي از گره‌هاي گراف مي‌باشد. هر گره در اولين لايه تنها با آن دسته از گره‌هايي قادر به تبادل اطلاعات است كه كمترين هزينه را به سيستم اعمال مي‌كنند. پر هزينه‌ترين تبادل اطلاعات در سومين لايه اتفاق مي‌افتد. هدف مدل پيشنهادي كاهش ميزان تبادل اطلاعات در اين لايه مي‌باشد. از ديگر مزاياي معرفي مدل سه لايه، استفاده از مزاياي همزمان مدل‌هاي تبادل اطلاعات مبتني بر پيام و حالات مشترك است. همچنين، به منظور كاهش تعداد تبادل اطلاعات در لايه‌هاي بعدي، هر لايه روشي به منظور شناسايي پيام‌هاي غيرمفيد را به كمك روش بخاطرسپاري در خود گنجانده است. در راستاي مساله‌ي دوم، در اين رساله يك روش جديد به منظور افراز گراف ارائه شده است. در اين افراز علاوه بر درنظر گرفتن فاكتورهاي ارتباطات بين ماشين‌ها و تعادل بار، به ويژگي‌هاي مدل پيشنهادي نيز توجه شده است. به همين منظور، بخش‌بند تا حد امكان سعي مي‌كند گراف به گونه‌اي تقسيم شود كه هر گره بتواند با درصد بيشتري از گره‌ها در لايه‌هاي پايين‌تر تبادل اطلاعات نمايد. ارزيابي سيستم پيشنهادي بر روي گراف‌هاي واقعي نشان داد كه ExPregel قادر به كاهش 80 تا 99 درصد ترافيك شبكه نسبت به Pregel، 35 تا 83 درصد نسبت به GPS و 64 تا 99 درصد نسبت به Blogel مي‌باشد. افزايش سرعت ExPregel نسبت به Pregel، GPS و Blogel به ترتيب 9، 20 و 1.6 برابر مي‌باشد. واژه‌هاي كليدي: پردازش توزيع‌شده، گراف بزرگ‌مقياس، محليت، درجه‌ي توازي، مدل محاسباتي

189801

دانشگاه علم و صنعت ايران

دكتر مصطفي حق‌جو سانيجي

نرم‌افزار

دكتر حسن نادري