17419

17419

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

دكتري

نرم‌افزار

بهمن ماه 1395

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

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

كامپيوتر

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

1396/03/20

1/1/1900 12:00:00 AM

Abstract: Because of the existence of massive number of irregular edges, distributed processing of large-scale graphs has two main problems. Due to the poor locality of computations in graph algorithms, the first problem is the low parallelism degree. The second one is high communications between machines in the partitioned graph. These problems not only increase the network traffic of distributed graph processing systems, but also reduce the utilization of computational resources. To overcome the first problem, a new computational model for distributed processing of graphs is proposed. The main goal of this model is to maximize the utilization of local processing and information resources. The key idea of this model is that each machine continues its computation independently as much as possible. When it is inevitable, it exchanges information with other machines. To this end, the proposed system introduces a three-layered model to benefit advantages of both shared-memory and distributed-memory architectures, simultaneously. Each vertex can only communicate with a subset of graph vertices in each layer. In the first layer, each vertex communicates with vertices whose their communication costs are minimum. The most expensive communications are performed in the last layers. In addition, the proposed model tries to utilize the advantages of both shared-states and message passing communication models simultaneously. By introducing a new kind of intelligence, the proposed system aims to detect useless messages and prevents sending them through network. To cope with the second problem, a new method for partitioning graphs is proposed. This partitioning considers properties of the proposed model in addition to load-balance and edge-cut factors. In this method, graph is partitioned such that each vertex can communicate with more percentage of graph vertices in the lower layers. Evaluation of the proposed system over real-world graphs showed that ExPregel can reduce the network traffic from 80% to 99% over Pregel, 35-83% over GPS and 64-99% over Blogel. ExPregel speed up over Pregel, GPS, and Blogel are 9x, 20x, and 1.6x, respectively. Keywords: Distributed Processing, Large-Scale Graph, Locality, Parallelism Degree, Computational Model