تحقیق زمانبندی گراف وظایف با هدف دستیابی به نزدیکترین زمان شروع اجرا برای گره ها

انجام زمانبندی خوب برای برنامه های موازی بهترین و مهمترین راه افزایش سرعت اجرا در سیستم های موازی می باشد. ازاین رو تلا ش های زیادی برای طراحی الگوریتمهای زمانبندی مناسب انجام شده است . در این مقاله الگوریتمی برای زمانبندی برنامه های موازی روی سیستم های چند کامپیوتری با تعداد نامحدود پردازنده ی همسان که در یک شبکه به طور کامل با هم ارتباط دارند، ارائه شده است . الگوریتم پیشنهادی از نوع الگوریتم های خوشه بندی بوده و با هدف جلو کشیدن زمان شروع اجرای گره های گراف وظایف به توزیع گره ها در بین خوشه ها می پردازد. این الگوریتم در مسیر رسیدن به جواب ، تمام جوانب را در نظر گرفته و درمقایسه با الگوریتم های دیگر توازن بهتری بین جنبه های مختلف یک الگوریتم زمانبندی برقرار نموده است.

سیستم های موازی با هدف افزایش کاریی و بالا بردن سرعت درانجام محاسبات پیچیده روی داده های زیاد به وجود آمده اند. در این سیستم ها چندین پردازنده همزمان باهم کار پردازش داده ها را انجام1 یا MIMD-DM می دهند. در بین انواع سیستم های موازی مدل سیستم چند کامپیوتری 2 قدرتمندترین مدل کامپیوتر موازی می باشد که بیشترین کاربرد های صنعتی را به خود اختصاص داده .در این مدل هر پردازنده یک حافظه ی محلی مخصوص به خود داردو یک بخش از برنامه ی موازی را روی داده های مربوط به خود اجرا.[ می کند [ 1در سیستم های

و.............. با تخفیف ویژه

معماری کامپیوتر پیشرفته و پردازش موازی

کتاب

 معماری کامپیوتر پیشرفته و پردازش موازی

advanced_computer_architecture_and_parallel_processing

(به زبان اصلی)

287 صفحه

مقاله محاسبه کوتاهترین مسیر در گراف با پردازش موازی

مطالعه پیاده سازی و تحلیل الگوریتمهای کوتاهترین مسیر

شامل دو مقاله و ترجمه آن به همراه فایل doc 

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