پروژه دانشجویی مقاله زمان بندی کارها در سیستمهای چندپردازنده ای با استفاده از یک الگوریتم ژنتیک جدی

 پروژه دانشجویی مقاله زمان بندی کارها در سیستمهای چندپردازنده ای با استفاده از یک الگوریتم ژنتیک جدید اولویت بر اساس تعداد فرزندان تحت word دارای 11 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد پروژه دانشجویی مقاله زمان بندی کارها در سیستمهای چندپردازنده ای با استفاده از یک الگوریتم ژنتیک جدید اولویت بر اساس تعداد فرزندان تحت word   کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

این پروژه توسط مرکز مرکز پروژه های دانشجویی آماده و تنظیم شده است

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

---

بخشی از متن پروژه دانشجویی مقاله زمان بندی کارها در سیستمهای چندپردازنده ای با استفاده از یک الگوریتم ژنتیک جدید اولویت بر اساس تعداد فرزندان تحت word :

مسأله زمانبندی ایستای کارها در سیستمهای چندپردازنده ای به دلایل استفاده بهینه از پردازندهها و همچنین صرف زمان کمتر، دارای اهمیت ویژهای است. این مساله از رده مسائل سخت است و به دست آوردن جواب بهینه دارای پیچیدگی زمانی بالایی است، بنابراین برای حل این مسایل از روشهای ابتکاری استفاده می شود. الگوریتم های ژنتیک، روش مناسبی جهت زمانبندی در سیستمهای چند پردازندهای است. در این مقاله الگوریتم ژنتیک جدیدی برای زمانبندی در سیستمهای چندپر کارها، براساس تعداد فرزندان و نوادگان (OfTSpring) آنها است. نتایج نشان می دهد الگوریتم پیشنهادی جدید در زمان قابل قبول جواب بهینه زمانبندی را نسبت به دیگر روشهای ژنتیک متداول به دست های ارایه می شود که اولویت زمانبندی انجام میآورد.

کلمات کلیدی
الگوریتم ژنتیک، زمانبندی کارها، سیستمهای چندپردازنده ای،نوادگان

1- مقدمه
کارهای محاسباتی پیچیده نمی تواند در بازه زمانی قابل قبول بر روی یک پردازنده اجرا شوند و به همین دلیل باید به زیر کارهای
کوچک تر تقسیم شوند و با زمانبندی مناسب و اختصاص دادن آنها به یک سیستم چندپردازنده ای زمان انجام کلیه زیر کارها کاهش یابد، به عبارتی زمان انجام آخرین کار کمینه شود. برای مدل سازی ریاضی مسأله زمانبندی ایستای کارها از گراف جهت دار غیرحلقه ای (DAG)” استفاده شده است. در این گراف هر گره نشان دهنده کار متناظر خود در مسأله زمانبندی است. وجود یک کمان از گره را به گره را به این نی که اجرای کار :f به اتمام نرسد، کار را نمی تواند معنی است که تا شروع به اجرا کند. مسأله زمانبندی در یک سیستم چندپردازنده ای 11017210 22 او سیستمهای توزیع شده ناهمگن (11014) از رده مسائل سخت 6.13) است. در روش های کلاسیک، به دست آوردن جواب کاملاً بهینه یا یک زمانبندی کمینه، بسیار زمان گیر است و در بسیاری مواقع، اجرای تصادفی کارها به زمان بیشتری نیاز دارد، بنابراین از روشهای ابتکاری استفاده می شود، که در روش های ابتکاری لزوماً جواب کاملاً بهینه به دست نمیآید ولی در یک بازه زمانی معقول، جوابی نزدیک به جواب بهینه به دست می آید. روشهای ابتکاری بسیاری ارائه شده است که عبارتند از

از بهترین روشهای ابتکاری، الگوریتم ژنتیاک است [1218252627] کارهای بسیاری در زمینه زمانبندی کارها در سیستمهای چندپردازنده ای به روش الگوریتم ژنتیک [11،17،21،22] انجام شده است برخی از آنها از روش الگوریتم ژنتیک تصادفی 2345 او برخی دیگر از روش الگوریتم ژنتیک و اولویت کارها براساس ارتفاع 29] استفاده نموده اند. در این مقاله الگوریتم ژنتیک جدیدی براساس اجرای زودتر کارها با توجه به اولویت آنها بر اساس تعداد فرزندان و نوادگان آنها ارائه و شبیه سازی شده ا ساختار باقیمانده مقاله به صورت زیر است: در بخش دوم الگوریتم زمانبندی اولویت دهی کارها بر حسب ارتفاع بیان شده و در بخش سوم روش جدید یعنی اولویت دهی کارها بر حسب تعداد نوادگان توضیح داده شده است. در بخش چهارم مراحل انجام الگوریتم ژنتیکی پیشنهادی به طور مجزا ارایه شده است و بخش پنجم اختصاصی به شبیه سازی و نتایج حاصل از آن دارد و در بخش ششم نتیجه گیری امده است .

2- الگوریتم زمانبندی اولویت دهی کارها بر حسب ارتفاع
هدف از زمانبندی در یک سیستم چندپردازندهای انتساب n کار به m پردازنده در یک سیستم چند پردزانده ای است تا زمان اتمام اجرای اخرین کار در این سیستم کمینه شود . برای سادگی اگر دو کار در پردازنده زمان بندی شوند هزینه ارتباطی برای ارسال دادهها بین دو کار صفر در نظر گرفته شده است. یکی از روشهای پرکاربرد در زمانبندی استفاده از اولویت دهی اجرای کارها بر اساس بر روی دو پردازنده مختلف ارتفاع آنها و به صورت زیر است:
اگر ترتیبی از یال های جهت دار از ti به tj وجود داشته باشد آنگاه ti جد tj و tj فرزند ti است. اگر (PRED(t مجموعه کارهایی است که ماقبل ti قرار گرفته اند آنگاه ارتفاع یک کار در گراف کار مطابق فرمول (1) تعریف می شود.