تحصيلات تکميلي

نام و نام خانوادگي : محمدرضا حسيني

دانشکده : فني و مهندسي

استاد راهنما : دکتر کامران زماني فر

تاريخ دفاع : 31/3/83

رشته و گرايش : کامپيوتر-نرم افزار

استاد مشاور : -

طراحي و پياده سازي يک مکانيزم زمانبند چند پردازنده اي مبتني بر الگوريتم ژنتيک چند هدفي

چکيده

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

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

همچنين به منظور افزايش سرعت اجراي الگوريتم زمانبند، فرمي موازي از اين الگوريتم نيز ارائه گرديد.

با ازمايش الگوريتم ارائه شده بر روي يک گراف نمونه ، نشان داده شد که زمانبندهاي حاصل در اکثر مواقع در نزديکي زمانبندهاي بهينه قرار داشته و همچنين افزايش تعداد پردازنده هاي مورد استفاده در اجراي الگوريتم موازي، ميتواند باعث تسريع اجراي الگوريتم گردد.