زمانبندی ایستای وظایف در محیط چند پردازنده ای به کمک الگوریتم رقابت استعماری

سیستم های چندپردازنده ای جهت بالا بردن سرعت سیستم و کارایی آن به وجود آمده اند. جهت رسیدن به این هدف یک سیستم زمانبند کارآمد به عنوان ی بخش مهم برای محیط چند پردازنده ای ضروری هست. سیستم زمانبندی در محیط چند پردازنده ای باید با استفاده از یک الگوریتم کارا، منابع سیستم را به شکلی به برنامه کاربر که از تعداد زیادی وظیفه مستقل از هم تشکیل شده است، تخصیص دهد با توجه به استراتژی بهینه سازی، پارامتر خواسته شده (زمان) مینیمم شود. مسئله زمانبندی ایستای وظایف در سیستم های چند پردازنده ای به دلایل استفاده بهینه از پردازنده ها و همچنین صرف زمان کمتر، دارای اهمیت فراوانی است. این مسئله از رده مسائل سخت و غیرقطعی است و به دست آوردن جواب بهینه دارای پیچیدگی زمانی بالایی است که برای حل آن نمی توان از الگوریتم های قطعی و با پیچیدگی چند جمله ای استفاده کرد بلکه باید از الگوریتم های فراابتکاری مانند الگوریتم ژنتیک، تپه نوردی، جستجوی ممنوعه، شبیه سازی سرد کردن تدریجی و سایر روش های ابتکاری استفاده کرد. در این پایان نامه برای زمانبندی وظایف در محیط چند پردازنده ای دو مدل پیشنهاد شده است مدل ا.ل استراتژی الگوریتم ژنتیک استفده شده است و مدل دوم الگوریتم رقابت استعماری به کار گرفته شده است و مقایسه این دو مدل زمانبندی نشان می دهد که زمانبند دوم (الگوریتم رقابت استعماری) نتایج بهتری برای زمانبندی دارد و زمان اتمام کل را در مزان کمتری انجام می دهد. همچنین برای سنجش کارایی مدل پیشنهادی دوم با شش الگوریتم غیر ژنتیک (ISH، HLFET، LAST، DLS، ETF و MCP) نیز مقایسه شده است نتایج نشان می دهد که مدل پیشنهادی دوم (الگوریتم رقابت استعماری) زمان اتمام کل وظایف را در زمان کمتری انجام می دهد، توانسته این مقدار را بهبود دهد. شبیه سازی مدل های پیشنهادی در محیط متلب انجام شده است.

Keywords:

زمانبندی , رقابت استعماری , چند پردازنده ای , محیط ایستا