اجرای موازی الگوریتم کوتاهترین مسیر دایجسترا

این مقاله مشکل موازی سازی الگوریتم دایجسترا که یک الگوریتم خوب برای محاسبه کوتاهترین مسیر یک منبعی ، در یک گراف است را معرفی می نماید . الگوریتم دایجسترا می تواند برای گرافهای دارای تعداد متفاوتی از راس ها و یال ها بکار رود . الگوریتم کوتاهترین مسیر دایجسترا پیاده سازی شده و ارائه گشته است و کارآیی های اجرای موازی و سریال آن مقایسه شده اند . پیاده سازی این الگوریتم با استفاده از استانداردهای Open CL (زبان محاسباتی باز) و Open MP (چند پردازنده باز) موازی شده بود . کارآیی های آن در چهار تنظیمات متفاوت براساس هسته دوگانه و پردازنده های i5 محاسبه شده بودند . نتایج آزمایشی نشان دادند که اجرای موازی این الگوریتم ، کارآیی های خوبی در مورد نسبت افزایش سرعت ، را در مقایسه با اجرای سریال آن دارا است . در پایان نتایج نشان دادند که به دلیل اینکه الگوریتم دایجسترا ترتیبی است و موازی سازی اش دشوار می باشد ، میانگین نسبت افزایش سرعت حاصل شده توسط موازی سازی تنها 10% است . این امر یک اشکال عمده از این الگوریتم را اثبات کرد زیرا کاربرد آن وسیع است و افزایش کارآیی آن تاثیر بزرگی در بسیاری از کاربردها دارد .

کلیدواژه ها:

الگوریتم دایجسترا ، کوتاهترین مسیر یک منبعی ، الگوریتم موازی ، Open ML ، Open CL