-
عنوان: زمانبندی گراف وظیفه با قیود زمان و هزینه در محاسبات گرید مبتنی بر پیشبینی سطح کارایی منابع
-
ارائهکننده: سمیه کیان پیشه
-
استاد راهنما: دکتر نصراله مقدم چرکری
-
استاد ناظر خارجی: دکتر محسن شریفی (دانشگاه علم و صنعت)، دکتر حسین پدرام (دانشگاه امیرکبیر)
-
استاد ناظر داخلی: دکتر بهزاد اکبری، دکتر مهدی آبادی
-
استاد مشاور: دکتر مهدی کارگهی (دانشگاه تهران)
-
نماینده تحصیلات تکمیلی: دکتر سعید جلیلی
-
مکان: دانشکده مهندسی برق و کامپیوتر، اتاق شورا
-
تاریخ: 1395/3/9
-
ساعت: 17
چکیده
یک گراف وظیفه به مجموعهای از وظایف محاسباتی اطلاق میشود که طبق ترتیب از پیش تعیین شدهای اجرا میشوند. این گرافها کاربردهای مختلفی در تحلیل تصاویر ماهوارهای، پیشبینی وقوع وقایع طبیعی، حوزه بیوانفورماتیک و پزشکی دارند. محاسبات گرید با فراهم آوردن شبکهای از منابع ناهمگن و توزیع شده بستر مناسبی را برای اجرای این گرافها مهیا میکند. زمانبندی گراف وظیفه یکی از مهمترین چالشهای سیستم مدیریت گراف وظیفه محسوب میشود. زمانبندی، نحوه تخصیص وظایف به منابع را در جهت برآوردهسازی نیارمندیهای کاربر و اهداف فراهمکنندگان سرویس بر عهده دارد. اثبات شده است که این مساله NP-Hard است. اخیرا زمانبندی گراف وظیفه در جهت برآوردهسازی قیود زمان و هزینه مورد توجه محققین قرار گرفته است. منابع گرید به دلایل مختلف نظیر اختلال نرمافزاری/سختافزاری، نوسانات برق و اختلال شبکه ممکن است دسترسناپذیر شوند. همچنین کارایی منابع به دلیل نوسانات بار کاری تغییر میکند. دسترسناپذیری و تغییر کارایی میزبان به هنگام اجرای وظیفه، ممکن است منجر به تاخیر در اجرای گراف و در بدترین حالت، شکست در اجرا شود. تاخیر در اجرای گراف میتواند منجر به نقض قید زمان شود. در صورت شکست در اجرا و یا نقض قیود فراهمکنندگان سرویس باید جریمه بپردازند. در این رساله، با بهرهگیری از پیشبینی سطح کارایی منابع، یک الگوریتم زمانبندی برای گراف وظیفه در محاسبات گرید پیشنهاد میشود. هدف یافتن یک زمانبندی است که قابلیت اطمینان اجرای گراف را بیشینه نماید و در عین حال قیود زمان و هزینه را برآورده کند. تغییرات کارایی در منبع، با یک فرایند تصادفی مدل میشود. به منظور حل مساله ناایستایی در تغییرات کارایی، الگوی گذار کارایی پیشنهاد میشود. یک زنجیره مارکوف از الگوهای گذار کارایی به صورت برخط ساخته میشود. این زنجیره مارکوف برای تحلیل فرایند تصادفیِ کارایی، استفاده میشود. از طریق تحلیل این فرایند، سطح کارایی منابع در زمان شروع اجرای وظایف به صورت احتمالی پیشبینی میشود. بر مبنای نتایج پیشبینی، زمان، هزینه و قابلیت اطمینان اجرای وظایف در منابع محاسبه میشوند. در مرحله نهایی، نگاشت وظایف به منابع با استفاده از سیستم کلنی مورچگان انجام میشود. سه ابتکار پیشنهاد میشود. دو ابتکار در جهت هدایت مورچگان به سمت یافتن زمانبندی ممکن و یک ابتکار دیگر در راستای افزایش قابلیت اطمینان عمل میکند. نتایج شبیهسازی، نشاندهنده افزایش دقت پیشبینی سطح کارایی منابع، نسبت زمانبندیهای ممکن و قابلیت اطمینان اجرای گراف در روش پیشنهادی است. همچنین در زمان اجرا، نسبت اجرای موفق گراف و نسبت برآوردن قیود زمان و هزینه افزایش و میزان جریمه کاهش یافته است.
کلمات کلیدی
8 خرداد 1395 / تعداد نمایش : 4884