کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951640 1441481 2017 54 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parallel algorithms for switching edges in heterogeneous graphs
ترجمه فارسی عنوان
الگوریتم های موازی برای تعویض لبه ها در نمودار های ناهمگن
کلمات کلیدی
سوئیچ لبه، تولید شبکه تصادفی، پویایی شبکه، توزیع چندجملهای، الگوریتم های موازی،
ترجمه چکیده
یک لبه سوئیچ عملیاتی بر روی یک گراف (یا شبکه) است که در آن دو لبه به صورت تصادفی انتخاب می شوند و یکی از اجزای پایان آنها با یکدیگر مبادله می شود. عملیات سوئیچ لبه کاربردی مهم در نظریه گراف و تجزیه و تحلیل شبکه است، مانند تولید شبکه های تصادفی با دنباله درجه، مدل سازی و تجزیه و تحلیل شبکه های پویا، و در مطالعه پدیده های مختلف پویایی در یک شبکه. رشد اخیر شبکه های دنیای واقعی الزامات الگوریتم های موازی موثر را ایجاد می کند. وابستگی ها در میان عملکردهای سوئیچ لبه پیوندی و نیاز به نگه داشتن گراف ساده (به عنوان مثال، بدون حلقه های خود و یا لبه های موازی) به عنوان لبه ها سوئیچ می شود به چالش های قابل توجهی در طراحی یک الگوریتم موازی. رفع این چالش ها نیازمند هماهنگ سازی پیچیده و ارتباطی در میان پردازنده ها است که باعث می شود مشکلاتی در دستیابی به سرعت بالا با به دست آوردن موازنه ایجاد شود. در این مقاله، الگوریتم های موازی توزیع شده حافظه را برای تعویض لبه ها در شبکه های عظیم ارائه می کنیم. این الگوریتم ها سرعت و مقیاس خوبی را به تعداد زیادی از پردازنده ها ارائه می دهند. میانگین هارمونیک صعود از 73.25 در هشت شبکه مختلف با 1024 پردازنده به دست می آید. یکی از مراحل الگوریتم سوئیچ لبه ما نیاز به محاسبه متغیرهای تصادفی چندجملهای موازی دارد. این مقاله ابتدا اولین الگوریتم موازی غیرمعمول برای این مشکل را ارائه می دهد، به دست آوردن سرعت 925 با استفاده از 1024 پردازنده.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
الگوریتم های موازی برای تعویض لبه ها در نمودار های ناهمگن
چکیده انگلیسی
An edge switch is an operation on a graph (or network) where two edges are selected randomly and one of their end vertices is swapped with each other. Edge switch operations have important applications in graph theory and network analysis, such as in generating random networks with a given degree sequence, modeling and analyzing dynamic networks, and in studying various dynamic phenomena over a network. The recent growth of real-world networks motivates the need for efficient parallel algorithms. The dependencies among successive edge switch operations and the requirement to keep the graph simple (i.e., no self-loops or parallel edges) as the edges are switched lead to significant challenges in designing a parallel algorithm. Addressing these challenges requires complex synchronization and communication among the processors leading to difficulties in achieving a good speedup by parallelization. In this paper, we present distributed memory parallel algorithms for switching edges in massive networks. These algorithms provide good speedup and scale well to a large number of processors. A harmonic mean speedup of 73.25 is achieved on eight different networks with 1024 processors. One of the steps in our edge switch algorithms requires the computation of multinomial random variables in parallel. This paper presents the first non-trivial parallel algorithm for the problem, achieving a speedup of 925 using 1024 processors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 104, June 2017, Pages 19-35
نویسندگان
, , , ,