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

نام و نام خانوادگي : اعظم حکمي

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

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

تاريخ دفاع : 27/6/80

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

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

طراحي و پياده‌سازي يك مكانيزم زمانبندي توسعه‌پذير براي مدل موازي BSP

چکيده

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

يكي از مدلهاي مطرح در محاسبات موازي، مدل BSP است. ادعا مي‌شود كه اين مدل، مي‌تواند نقش يك مدل همه منظوره در پردازش موازي را بازي كند. هدف از اين تحقيق طراحي يك مكانيزم زمانبندي ديناميكي بر روي اين مدل است. الگوريتم زمانبندي پيشنهادي همانند همه برنامه‌هاي نوشته شده تحت مدل BSP متشكل از تعدادي ابرگام است. در هر ابرگام زمانبند به زمانبندي كارها، و ساير پردازنده‌ها به اجراي كارهاي تخصيص داده شده به آنها مي‌پردازند. پردازنده زمانبند فقط در انتهاي هر ابرگام، كارها را به پردازنده‌هاي اجرايي ارسال مي‌كند، اما پردازنده‌هاي اجرايي براي بدست آوردن اطلاعات غير محلي در طول ابرگام نيز مي‌توانند به ارسال و دريافت پيغام‌ها بپردازند.

در تجزيه وتحليل الگوريتم، ملاكهاي مختلف براي تعيين طول گام زمانبندي مورد بررسي قرار گرفت و با بدست آوردن زمانهاي اجرا در حالتهاي مختلف نتيجه گرفته شده كه با توجه به محدوديت تعداد وطول پيغام‌هاي ارسالي در هر ابرگام بهترين روش براي تعيين طول گام زمانبندي تعداد كارها و تعداد پردازنده‌ها است. همچنين بررسي زمان اجراي برنامه‌ها با تغيير تعداد پردازنده‌ها بيانگر توسعه‌پذير بودن سيستم است.