10116

10116

طراحي و شبيه‌سازي الگوريتم تكاملي جهت نگاشت و زمان¬بندي در سيستم¬هاي قابل بازپيكربندي

درجه كارشناسي ارشد

رشته مهندسي برق گرايش الكترونيك

فروردين ماه 1390

فروردين ماه 1390

دكتر هادي شهريار شاه¬حسيني

چكيده زمان¬بر بودن و هزينه¬ي بالايفرآيند ساخت تراشه¬هاي خاص منظوره از يك سو و سرعت پايين پردازنده¬هاي همه منظوره از سوي ديگر موجب شده است كه به خصوص در دو دهه‌ي اخير استفاده از ساختارهايي كه از انعطاف¬پذيري نرم¬افزار وسرعت سخت¬افزار به طور همزمان بهره مي¬برند بسيار مورد توجه قرار گيرد. اين ساختارها كه سيستم¬هاي قابل بازپيكربندي نام دارند امكانپياده¬سازي و اجراي انواع الگوريتم¬هاي پردازشي را فراهم مي‌كنند. مهم‌ترين بحث در استفاده¬ي بهينه ازسخت¬افزار¬هاي محاسباتي قابل بازپيكربندي چينش و توزيع ¬كارها بين منابع پردازشي و پيكربندي آن¬ها است به نحوي كه در كم¬ترين زمان ممكن انجام شوند. انجام اين مسئوليت بر عهده‌ي الگوريتم نگاشت و زمان¬بندي است كه به دليل وجودفضاي بسيار بزرگي از راه¬حل¬ها، اين مسئله جزء مسائل NP-Complete قرار مي¬گيرد.در اين پروژه دو الگوريتم جهت نگاشت و زمان¬بندي كارها در سيستم¬هاي قابل بازپيكربندي پيشنهاد شده است كه بر مبناي الگوريتم¬هاي بهينه¬سازي طبيعي مي¬باشند. در روش اول سعي شده است تا با اعمال تغييرات و اصلاحاتي در الگوريتم تبريد تدريجي، آن را براي مسئله¬ي مورد نظر مناسب¬سازي كنيم. عمد¬ه¬ي تغييرات بر روي تابع تبريد و نحوه¬ي توليد جواب¬هاي جديد صورت گرفته است. الگوريتم پيشنهادي دوم مبتني بر الگوريتم ژنتيك است. اعمال عملگرهايي مثل ادغام و جهش ژنتيكي بر روي كروموزوم¬هاي مسائلي همچون زمان¬بندي كه در آن¬ها بحث تقدم و تاخر ژن¬ها مهم است، ممكن است منجر به فرزندان ناقص و نامعتبري شود. اين امر وجود مرحله¬اي اضافي در الگوريتم جهت اصلاح فرزندان را ضروري مي¬سازد كه منجر به سربار زماني قابل توجهي مي¬گردد. براي حل اين مشكل از نگاشت نژاد مانه به رخ مانه استفاده شده است به طوري كه از يك سو توليد جواب¬هاي نامعتبر و نياز به مرحله¬ي اصلاح حذف مي¬شود و از سوي ديگر سرعت همگرايي و كيفيت جواب¬ها افزايش مي¬يابد. جهت بررسي كارايي اين روش¬ها، شبيه‌سازي‌هاي لازم صورت گرفته و نشان داده شده است كه روش¬هاي پيشنهادي از لحاظ سرعت اجرا يا كيفيت جواب¬ها و يا هر دو، عملكرد بهتري نسبت به ساير روش‌ها داشته و در شرايط مختلف سيستم كارايي خود را حفظ مي¬كنند. واژه‌هاي كليدي:زمان¬بندي، الگوريتم ژنتيك، تبريد تدريجي، نگاشت نژادمانه به رخ¬مانه.