کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951540 1441477 2017 39 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Modeling, analysis, and experimental comparison of streaming graph-partitioning policies
ترجمه فارسی عنوان
مدلسازی، تجزیه و تحلیل و مقایسه تجربی جریانهای سیاست پارتیشن بندی گراف
کلمات کلیدی
جریان گرافیک پارتیشن بندی سیاست، نمودارهای مقیاس بزرگ، سیستم های پردازش نمودار، تجزیه و تحلیل مدل سازی، سنجش عملکرد،
ترجمه چکیده
در سال های اخیر، بسیاری از سیستم های پردازش گراف پردازش شده برای طراحی نمودارهای مقیاس بزرگ طراحی و توسعه داده شده اند. برای همه سیستم های پردازش گراف به توزیع، نمودار های پارتیشن بندی بخش مهمی از پردازش و یک جنبه مهم برای دستیابی به عملکرد پردازش خوب است. برای نگهداری کم هزینه گرافیک های پارتیشن بندی، حتی در حال پردازش نمودار های مدرن مدرن، بسیاری از مطالعات قبلی از سیاست های پراکندگی گرافیک جریان سبک وزن استفاده می کنند. اگر چه بسیاری از این سیاست ها وجود دارد، در حال حاضر هیچ مطالعه جامعی در مورد تأثیر آنها بر تعادل بار و هزینه های ارتباطی و عملکرد کلی سیستم پردازش گراف وجود ندارد. این فقدان فکری نسبی مانع توسعه و تنظیم سیاست های جریان جدید می شود و می تواند جامعه کل تحقیق را به طبقات موجود محدود کند. ما در این کار با این مسائل روبرو هستیم. ما با مدلسازی زمان اجرای سیستم های پردازش گراف به توزیع شروع می کنیم. با تجزیه و تحلیل این مدل تحت بار ویژگی های گرافیکی واقع گرایانه، ما پیشنهاد می کنیم یک روش برای شناسایی مسائل مربوط به عملکرد مهم و سپس طراحی خطوط جدید پراکندگی گرافیک جریان برای حل آنها. با استفاده از سه نمودار معمول در مقیاس بزرگ و سه الگوریتم پردازش محبوب گراف، ما انجام آزمایش های جامع برای مطالعه عملکرد ما و بسیاری از سیاست های جایگزین جریان بر روی یک سیستم پردازش واقعی پردازش گراف. ما همچنین تاثیر در عملکرد استفاده از شبکه های مختلف دنیای واقعی و سایر مشخصات فنی دنیای واقعی را بررسی می کنیم. ما بیشتر در مورد نحوه استفاده از نتایج ما، پوشش مدل و روش ما و طراحی سیاست های پارتیشن بندی آینده بحث خواهیم کرد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In recent years, many distributed graph-processing systems have been designed and developed to analyze large-scale graphs. For all distributed graph-processing systems, partitioning graphs is a key part of processing and an important aspect to achieve good processing performance. To keep low the overhead of partitioning graphs, even when processing the ever-increasing modern graphs, many previous studies use lightweight streaming graph-partitioning policies. Although many such policies exist, currently there is no comprehensive study of their impact on load balancing and communication overheads, and on the overall performance of graph-processing systems. This relative lack of understanding hampers the development and tuning of new streaming policies, and could limit the entire research community to the existing classes of policies. We address these issues in this work. We begin by modeling the execution time of distributed graph-processing systems. By analyzing this model under the load of realistic graph-data characteristics, we propose a method to identify important performance issues and then design new streaming graph-partitioning policies to address them. By using three typical large-scale graphs and three popular graph-processing algorithms, we conduct comprehensive experiments to study the performance of our and of many alternative streaming policies on a real distributed graph-processing system. We also explore the impact on performance of using different real-world networks and of other real-world technical details. We further discuss how to use our results, the coverage of our model and method, and the design of future partitioning policies.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 108, October 2017, Pages 106-121
نویسندگان
, , , , ,