چطور این مقاله مهندسی کامپیوتر و IT را دانلود کنم؟
فایل انگلیسی این مقاله با شناسه 2005701 رایگان است. ترجمه چکیده این مقاله مهندسی کامپیوتر و IT در همین صفحه قابل مشاهده است. شما می توانید پس از بررسی این دو مورد نسبت به خرید و دانلود مقاله ترجمه شده اقدام نمایید
حجم فایل انگلیسی :
701 Kb
حجم فایل فارسی :
757 کیلو بایت
نوع فایل های ضمیمه :
Pdf+Word
کلمه عبور همه فایلها :
www.daneshgahi.com
عنوان فارسي
روشی برای موازی سازی الگوریتم کراسکال با استفاده از Helper Threads (نخ کشی کمکی)
عنوان انگليسي
An approach to parallelize Kruskal’s algorithm using Helper Threads
نویسنده/ناشر/نام مجله
IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum
این مقاله چند صفحه است؟
این مقاله ترجمه شده مهندسی کامپیوتر و IT شامل 10 صفحه انگلیسی به صورت پی دی اف و 15 صفحه متن فارسی به صورت ورد تایپ شده است
چکیده
در این پژوهش یک روش Helper Threading (نخ کشی کمکی) را نشان میدهیم که برای موازی سازی الگوریتم درخت پوشا کمینه کراسکال مورد استفاده قرار گرفته است. این الگوریتم با ویژگی های ذاتا ترتیبی شناخته شده است. بویژه، روال ثابتی که به بررسی لبه های یک گراف می پردازد، دلیل صریح عدم موازی سازی است. روش پیشنهادی ما برای غلبه بر محدودیتهای مطرح شده تلاش میکند و عملکرد الگوریتم را بهبود می بخشد. نتایج نشان می دهند که برای محدوده ی گسترده ای از گراف های با ساختار، اندازه و تراکم مختلف، موازی سازی الگوریتم کراسکال امکان پذیر می باشد. تسریع قابل ملاحضه در این رابطه به5.5 برابر، برای اجرای 8 نخ میرسد و پتانسیل های روش ما را نشان میدهد.
1-مقدمه
سازگاری گسترده پلتفرم های چندهسته ای، فرصتی را برای بررسی و کشف تکنیکهای پیاده سازی جدید برای الگوریتم هایی مهیا میسازد که برای تک پردازنده ها طراحی شده اند. با برقراری روش های موازی جدید، برنامه نویسان قادر به بهره برداری از روشی بهینه تر خواهند بود که مفاهیم سخت افزاری متعددی را در پلتفرم های امروزه ارائه می نمایند. دسته ای از مسئله ها که ویژگی ذاتا ترتیبی دارند، دارای سخت ترین موازی سازی هستند. کشف کوتاه ترین مسیر هم مبدا (SSSP) یا ترکیب جنگل پوشای کمینه (MSF) از یک گراف در این دسته بندی جای میگیرد...
الگوریتم کراسکال درخت پوشای کمینه الگوریتم های موازی نخ های کمکی
:کلمات کلیدی
Abstract
In this paper we present a Helper Threading scheme used to parallelize efficiently Kruskal's Minimum Spanning Forest algorithm. This algorithm is known for exhibiting inherently sequential characteristics. More specifically, the strict order by which the algorithm checks the edges of a given graph is the main reason behind the lack of explicit parallelism. Our proposed scheme attempts to overcome the imposed restrictions and improve the performance of the algorithm. The results show that for a wide range of graphs of varying structure, size and density the parallelization of Kruskal's algorithm is feasible. Observed speedups reach up to 5.5 for 8 running threads, revealing the potentials of our approach
Keywords:
Kruskal’s Algorithm Minimum Spanning Forest Parallel algorithms Helper Threads
سایر منابع مهندسی کامپیوتر و IT-نرم افزار در زمینه پردازش موازی