عنوان
طراحي و شبيه‌سازي الگوريتم نگاشت و زمان‌بندي بهينه وظايف در سيستم‌هاي چند پردازنده‌اي
نويسنده اصلي
فرزام درستكار
مقطع تحصيلي
كارشناسي ارشد
چكيده
يكي از چالش‌هاي اصلي برنامه‌نويسي براي سيستم‌هاي چند پردازنده‌اي تصميم‌گيري درباره‌ي چگونگي توزيع بخش‌هاي مختلف يا همان وظايف يك برنامه بين پردازنده‌هاي موجود است. انتخاب مناسب‌ترين پردازنده براي اجراي يك وظيفه اصطلاحا نگاشت ناميده شده و تعيين زمان آغاز اجراي هر وظيفه نيز زمان‌بندي ناميده مي‌شود. در اين پايان‌نامه به بررسي مسئله‌ي نگاشت و زمان‌بندي ايستاي وظايف در سيستم‌هاي محاسباتي ناهمگن با هدف كمينه كردن زمان اجراي برنامه مي‌پردازيم و براي حل آن سه الگوريتم ابتكاري نوين از نوع الگوريتم‌هاي برنامه‌ريزي فهرستي با اولويت‌بندي ايستا پيشنهاد مي‌كنيم.
نخستين الگوريتم ارائه شده در اين پايان‌نامه الگوريتم مسيرِ داراي ارتباطات شديد بر روي يك پردازنده نام دارد و انگيزه‌ي ارائه‌ي آن پيشنهاد راهكارهايي براي بهبود عملكرد الگوريتمي كلاسيك به نام الگوريتم مسير بحراني بر روي يك پردازنده است. تغييرات پيشنهادي با ايجاد هماهنگي بيشتر بين بخش‌هاي مختلف اين الگوريتم كيفيت برنامه‌ريزي‌هاي زماني حاصل را بهبود مي‌بخشند. دومين الگوريتم ارائه شده در اين پايان‌نامه الگوريتم زودترين زمان اتمام سودمند نام دارد و انگيزه‌ي ارائه‌ي آن پيشنهاد معياري پويا براي پيش‌بيني گلوگاه‌هاي پردازشي يك برنامه‌ي موازي است. بدين منظور ايده‌ي نوين ”زمان قابل صرفه‌جويي“ را ارائه كرده و آن را در قالب يك جدول فرموله مي‌كنيم. اين جدول در عين دارا بودن پيچيدگي زماني مرتبه‌ي دوم قابليت پيش‌بيني را فراهم مي‌كند اما يك ضعف ذاتي دارد و آن اين است كه در تشكيل آن، در دسترس بودن پردازنده‌ها در نظر گرفته نمي‌شود و در نتيجه ممكن است در مواقعي به پيش‌بيني‌هايي با دقت پايين بيانجامد. سومين الگوريتم ارائه شده در اين پايان‌نامه الگوريتم زودترين زمان اتمام سودمند وزن‌دهي شده نام دارد و انگيزه‌ي ارائه‌ي آن پيشنهاد راهكاري براي به حداقل رساندن اين ضعف است. اين الگوريتم مي‌كوشد تا با اختصاص وزن‌هايي گوناگون به وظايف، پيش‌بيني‌هايي كه احتمالا دقت پاييني دارند را تضعيف كند تا اثرگذاري آنها بر تصميمات الگوريتم كاهش يابد. پيچيدگي زماني هر سه الگوريتم پيشنهادي برابر با حداقل مرتبه‌ي پيچيدگي زماني در ميان الگوريتم‌هاي فهرستي شناخته شده است.
شبيه‌سازي‌هايي متنوع تأثير مثبت پيشنهادات ارائه شده در نخستين الگوريتم را تأييد مي‌كنند. همچنين شبيه‌سازي‌هايي گسترده برتري دومين و سومين الگوريتم ارائه شده بر شناخته شده‌ترين الگوريتم‌هاي زمان‌بندي فهرستي را نشان مي‌دهند.
شماره ركورد
194856
دانشگاه
دانشگاه علم و صنعت ايران
رشته تحصيلي
سيستم‌هاي الكترونيك ديجيتال
استاد راهنما
دكتر ستار ميرزاكوچكي