بخشی از مقاله
مسأله زمانبندی ایستای کارها در سیستمهای چندپردازنده ای به دلایل استفاده بهینه از پردازندهها و همچنین صرف زمان کمتر، دارای اهمیت ویژهای است. این مساله از رده مسائل سخت است و به دست آوردن جواب بهینه دارای پیچیدگی زمانی بالایی است، بنابراین برای حل این مسایل از روشهای ابتکاری استفاده می شود. الگوریتم های ژنتیک، روش مناسبی جهت زمانبندی در سیستمهای چند پردازندهای است. در این مقاله الگوریتم ژنتیک جدیدی برای زمانبندی در سیستمهای چندپر کارها، براساس تعداد فرزندان و نوادگان (OfTSpring) آنها است. نتایج نشان می دهد الگوریتم پیشنهادی جدید در زمان قابل قبول جواب بهینه زمانبندی را نسبت به دیگر روشهای ژنتیک متداول به دست های ارایه می شود که اولویت زمانبندی انجام میآورد.
کلمات کلیدی
الگوریتم ژنتیک، زمانبندی کارها، سیستمهای چندپردازنده ای،نوادگان
۱- مقدمه
کارهای محاسباتی پیچیده نمی تواند در بازه زمانی قابل قبول بر روی یک پردازنده اجرا شوند و به همین دلیل باید به زیر کارهای
کوچک تر تقسیم شوند و با زمانبندی مناسب و اختصاص دادن آنها به یک سیستم چندپردازنده ای زمان انجام کلیه زیر کارها کاهش یابد، به عبارتی زمان انجام آخرین کار کمینه شود. برای مدل سازی ریاضی مسأله زمانبندی ایستای کارها از گراف جهت دار غیرحلقه ای (DAG)" استفاده شده است. در این گراف هر گره نشان دهندهٔ کار متناظر خود در مسأله زمانبندی است. وجود یک کمان از گره را به گره را به این نی که اجرای کار :f به اتمام نرسد، کار را نمی تواند معنی است که تا شروع به اجرا کند. مسأله زمانبندی در یک سیستم چندپردازنده ای ۱۱۰۱۷۲۱۰ ۲۲ او سیستمهای توزیع شده ناهمگن (۱۱۰۱۴) از رده مسائل سخت ۶.۱۳) است. در روش های کلاسیک، به دست آوردن جواب کاملاً بهینه یا یک زمانبندی کمینه، بسیار زمان گیر است و در بسیاری مواقع، اجرای تصادفی کارها به زمان بیشتری نیاز دارد، بنابراین از روشهای ابتکاری استفاده می شود، که در روش های ابتکاری لزوماً جواب کاملاً بهینه به دست نمیآید ولی در یک بازه زمانی معقول، جوابی نزدیک به جواب بهینه به دست می آید. روشهای ابتکاری بسیاری ارائه شده است که عبارتند از
از بهترین روشهای ابتکاری، الگوریتم ژنتیاک است [12.18.25.26.27] کارهای بسیاری در زمینه زمانبندی کارها در سیستمهای چندپردازنده ای به روش الگوریتم ژنتیک [۱۱،۱۷،۲۱،۲۲] انجام شده است برخی از آنها از روش الگوریتم ژنتیک تصادفی ۲۳۴۵ او برخی دیگر از روش الگوریتم ژنتیک و اولویت کارها براساس ارتفاع ۲۹] استفاده نموده اند. در این مقاله الگوریتم ژنتیک جدیدی براساس اجرای زودتر کارها با توجه به اولویت آنها بر اساس تعداد فرزندان و نوادگان آنها ارائه و شبیه سازی شده ا ساختار باقیمانده مقاله به صورت زیر است: در بخش دوم الگوریتم زمانبندی اولویت دهی کارها بر حسب ارتفاع بیان شده و در بخش سوم روش جدید یعنی اولویت دهی کارها بر حسب تعداد نوادگان توضیح داده شده است. در بخش چهارم مراحل انجام الگوریتم ژنتیکی پیشنهادی به طور مجزا ارایه شده است و بخش پنجم اختصاصی به شبیه سازی و نتایج حاصل از آن دارد و در بخش ششم نتیجه گیری امده است .
۲- الگوریتم زمانبندی اولویت دهی کارها بر حسب ارتفاع
هدف از زمانبندی در یک سیستم چندپردازندهای انتساب n کار به m پردازنده در یک سیستم چند پردزانده ای است تا زمان اتمام اجرای اخرین کار در این سیستم کمینه شود . برای سادگی اگر دو کار در پردازنده زمان بندی شوند هزینه ارتباطی برای ارسال دادهها بین دو کار صفر در نظر گرفته شده است. یکی از روشهای پرکاربرد در زمانبندی استفاده از اولویت دهی اجرای کارها بر اساس بر روی دو پردازنده مختلف ارتفاع آنها و به صورت زیر است:
اگر ترتیبی از یال های جهت دار از ti به tj وجود داشته باشد آنگاه ti جد tj و tj فرزند ti است. اگر (PRED(t مجموعه کارهایی است که ماقبل ti قرار گرفته اند آنگاه ارتفاع یک کار در گراف کار مطابق فرمول (۱) تعریف می شود.
