15578

15578

روشي جديد براي بخشبندي گرافهاي حجيم

كارشناسي ارشد

كامپيوتر - گرايش نرمافزار

اسفند 1395

اسفند 1395

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

چكيده امروزه شطككههاي بزرگ با حجم بسطيار زياد دادهها نقش بسطيار اساسي در جامعه و زندگي ما دارند. پرداز اين حجم وسطيع دادهها نيازمند منابع بسطيار زياد و گران ميباشطد. از اين رو نيازمند سطاختاان داده مناس براي پرداز اطلاعات هسطتيم. يكي از اين ساختاان دادهها گراف است. گراف يك مدل تاثيرگذار در ناايش رواب بين موجوديتها اسططت. براي ناونه نشططان دادن ارتكاطات شططككهاي، رواب اجتااعي، پيوند بين وبها، كانالهاي حال و نقل بين مكانها، طراحي VLSI و تركي گذاري ژنوم از گراف اسططتهاده ميشططود. در دهه اخير ما شطاهد رشطد بابل توجهاي در توانايي ذخيرهسطازي و ضطك حجم باييي از اطلاعات برخ بوديم. اين اطلاعات باعث بوجود آمدن گرافهايي در جهان وابعي شططده اسططت كه تعداد رأس و يال آنها به ميليون و يا حتي بيليون ميرسططد. به دليل حجم زياد اطلاعات، پرداز گراف به رططورت متاركز امكانپذير نخواهد بود. لذا نيازمند توزيع گراف در سطط ش شططككه و توزيع پرداز خواهيم بود. اگر براي پرداز گراف نياز به انتقال حجم زيادي از دادهها داشطته باشيم، پرداز هزينهبر خواهد بود. بدون بخشبندي گراف، ارتكاطات يك عامل محدودكننده مهم در مقياسپذيري سطيستم خواهد بود. بنابراين بخشبندي گراف بايد به گونهاي اعاال شود كه سطربار ارتكاطات بين سطيستمها كاينه باشد . هاچنين سيستمهاي متهاوتي براي پرداز گراف به رورت توزيعشططده ارا ه شططدهاند. اكثر اين سططيسططتمها، مانند Giraph ، GPS و... از مدل پردازشططي Pregel اسططتهاده ميكنند كه در اين مدل از ديد سططط ش گره براي پرداز گراف اسطططتهاده شطططده اسطططت. اما اين مدل داراي كاسطتيهايي در پرداز انواع گراف بوده است. به هاين دليل سيستمهاي پرداز بلوكي گراف ارا ه شدهاند. از جاله مهمترين اين سطيسطتمها ExPregel و Blogel است. اين سيستمها داراي ويژگيهاي خاري هستند كه با توجه به آنها فاكتورهاي مختلهي در بخشبندي آنها تأثيرگذار اسطت. در اين پژوهش سعي شده است با معرفي اين ويژگيها و مشطططخر كردن فاكتورهاي تأثيرگذار، يك رو بخشبندي براي سطططيسطططتمهاي پرداز بلوكي گراف ارا ه شود. واژههاي كليدي: گرا ، ب شبندي،پردازش بلوكي، گرا ايستا، قطر، قطر گرا ايستا، قطر گرا پويا