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
چکیده
در این پژوهش یک روش Helper Threading (نخ کشی کمکی) را نشان میدهیم که برای موازی سازی الگوریتم درخت پوشا کمینه کراسکال مورد استفاده قرار گرفته است. این الگوریتم با ویژگی های ذاتا ترتیبی شناخته شده است. بویژه، روال ثابتی که به بررسی لبه های یک گراف می پردازد، دلیل صریح عدم موازی سازی است. روش پیشنهادی ما برای غلبه بر محدودیتهای مطرح شده تلاش میکند و عملکرد الگوریتم را بهبود می بخشد. نتایج نشان می دهند که برای محدوده ی گسترده ای از گراف های با ساختار، اندازه و تراکم مختلف، موازی سازی الگوریتم کراسکال امکان پذیر می باشد. تسریع قابل ملاحضه در این رابطه به5.5 برابر، برای اجرای 8 نخ میرسد و پتانسیل های روش ما را نشان میدهد.
1-مقدمه
سازگاری گسترده پلتفرم های چندهسته ای، فرصتی را برای بررسی و کشف تکنیکهای پیاده سازی جدید برای الگوریتم هایی مهیا میسازد که برای تک پردازنده ها طراحی شده اند. با برقراری روش های موازی جدید، برنامه نویسان قادر به بهره برداری از روشی بهینه تر خواهند بود که مفاهیم سخت افزاری متعددی را در پلتفرم های امروزه ارائه می نمایند. دسته ای از مسئله ها که ویژگی ذاتا ترتیبی دارند، دارای سخت ترین موازی سازی هستند. کشف کوتاه ترین مسیر هم مبدا (SSSP) یا ترکیب جنگل پوشای کمینه (MSF) از یک گراف در این دسته بندی جای میگیرد...