مقاله محاسبه کوتاهترین مسیر در گراف با پردازش موازی
 مقاله محاسبه کوتاهترین مسیر در گراف با پردازش موازیمطالعه پیاده سازی و تحلیل الگوریتمهای کوتاهترین مسیر شامل دو مقاله و ترجمه آن به همراه فایل doc می توان الگوریتمهای کوتاهترین مسیر را به دو نوع تقسیم بندی کرد: کوتاهترین مسیر تک منبع و همه کوتاهترین مسیرهادر این مقاله بر آن هستیم تا از هر نوع یک الگوریتم را مورد بررسی و تحلیل قرار دهیم.در بحث الگوریتم همه کوتاهترین مسیرها، الگوریتمهای فراوانی برای یافتن همه کوتاهترین مسیرها وجود دارد. الگوریتم فلوید-وارشال یکی از متداول ترین و کارآمدترین آنها میباشد. در این مقاله یک نسخه موازی از این الگوریتم با توجه به تجزیه اصولی یک بعد ردیف ماتریس مجاورت ارائه میگردد. این الگوریتم با هر دو MPI و OpenMP پیاده سازی شده است. از نتایج بدست آمده چنین برمی آید که الگوریتم موازی بطور قابل ملاحظه ای برای گراف با اندازه بالا موثر بوده و پیاده سازی MPIاز نظر عملکرد پیاده سازی OpenMP الگوریتم موازی برتری دارد. هم چنین در بحث الگریتم تک منبع به الگوریتم دایجکسترا میپردازیم که الگوریتمی شناخته شده در بحث یافتن کوتاهترین مسیرsingle-source(تک منبع)در گراف میباشد.پس از معرفی الگوریتم موازی و ترتیبی دایجکسترا، میزان بهره وری اجرای موازی را مورد تحلیل قرار میدهیم و در پایان اجرای ترتیبی و موازی را با 4پیکربندی مختلف - که بر پایه پردازندههای Dual Core و i5 شکل گرفته است - از نظر مدت زمان اجرا مورد مالعه قرار میدهیم. نتایج به دست آمده به خوبی نشان میدهد که اجرای موازی الگوریتم دایجکسترا نسبت به اجرای ترتیبی دارای سرعت بیشتری در اجرا میباشد. سرانجام، همانطور که دادهها نشان خواهند داد، به دلیل آنکه الگوریتم دایجکسترا ذاتا یک الگوریتم ترتیبی است و اجرای موازی آن مشکل است، تنها 10درصد سرعت اجرای الگوریتم به صورت موازی نسبت به اجرای ترتیبی مزیت دارد.که به دلیل استفاده گسترده از این الگوریتم این میزان بهره وری در سرعت اجرا، یک نقطه ضعف بزرگ برای این الگوریتم به حساب میآید. |
