مشخصات مقاله:
عنوان فارسی مقاله:
روش الگوریتم موازی کروسکال با استفاده از کمک کننده بیان موضوعات
عنوان انگلیسی مقاله:
An approach to parallelize Kruskal’s algorithm using Helper Threads
کلمات کلیدی مقاله:
الگوریتم کروسکال، حداقل پوشانندگی، الگوریتم های موازی، موضوعات کمک کننده
مناسب برای رشته های دانشگاهی زیر:
ریاضی و مهندسی کامپیوتر
مناسب برای گرایش های دانشگاهی زیر:
مهندسی الگوریتم ها و محاسبات و ریاضی کاربردی
وضعیت مقاله انگلیسی و ترجمه:
مقاله انگلیسی را میتوانید به صورت رایگان با فرمت PDF از باکس زیر دانلود نمایید. ترجمه این مقاله با فرمت WORD – DOC آماده خریداری و دانلود آنی میباشد.
فهرست مطالب:
چکیده
مقدمه
مبانی الگوریتم KRUSKALS
الگوریتم موازنه شده KRUSKALS
کشف موازی در کروسکال
ایجاد کمک کننده طرح شماتیکی
C. اجرا جزئیات روش بکار برده شده
بررسی های تجربی
تنظیمات تجربی
نمودار های منبع
بررسی نتایج
کار مربوطه
نتیجه گیری – کار آینده
قسمتی از مقاله انگلیسی و ترجمه آن:
I. Introduction
The widespread adaption of multicore platforms has offered the opportunity to explore new implementation techniques for many algorithms that were initially designed for uniprocessors. By devising new parallel schemes, the programmers will be able to exploit in a more efficient way the multiple hardware contexts offered in today’s platforms. A category of problems among the most difficult to parallelize are the ones that exhibit inherently sequential characteristics. The discovery of the Single Source Shortest Path (SSSP) or the composition of the Minimum Spanning Forest (MSF) of a given graph fall into this category. Kruskal’s algorithm [12] is one of the most known algorithms that address the MSF problem. The strictly ordered examination of the graph’s edges in order to decide whether they are part of the MSF or not, prohibits the usage of well known parallel strategies, like data partitioning. Our approach attempts to overcome the restrictions imposed by the the inherently sequential nature of the algorithm, by using a Helper Threading (HT) scheme. The evaluation reveals that using HT as an offloading technique can provide speedups up to 5.5 for a graph of 1M vertices and 20M edges for 8 threads
مقدمه
انطباق گسترده سیستم عامل های چند هسته ای، فرصتی برای کشف تکنیک جدید برای اجرای الگوریتم های بسیاری است که در ابتدا برای uniprocessors طراحی شده بودند ارائه می کند. با ابداع طرح های جدید موازی، برنامه نویسان قادر به بهره برداری در راه کارآمد تری از زمینه سخت افزار ارائه شده در چند سیستم عامل امروز خواهند بود. یک دسته از مشکلات میان سخت ترین موضوعات الگوریتم های parallelize (موازی) آنهایی هستند که نمایش آن ها به صورت متوالی می باشد. تنها راه بررسی این ویژگی ها روش کوتاهترین (SSSP) و یا ترکیب حداقل پوشای جنگل (MSF) از رسم گراف داده شده این گروه های داده ای است.
الگوریتم کروسکال ]12[ یکی از الگوریتم های شناخته شده است که وظیفه آن رسیدگی به مشکل MSF است. بررسی شدت دستور داده ها و اینکه آیا از روی نمودار رسم شده می توان به منظور تصمیم گیری این که آیا بخشی از MSF هست یا نه استفاده کرد، و استفاده از استراتژی های موازی به خوبی شناخته شده، مانند پارتیشن بندی داده ها در این روش ممنوع است. در تلاش برای غلبه بر محدودیت های اعمال شده از سوی ماهیت ذاتا متوالی الگوریتم، با استفاده از یک کمک کننده طرح نخ (HT) هستیم. ارزیابی ها نشان می دهد که با استفاده از HT به عنوان یک روش تخلیه می توان تا 5/5 نقطه از یک گراف از راس 1M و لبه 20M به صورت 8 قله فراهم کرد.