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

زمان­بندی کارها یکی از بزرگترین چالش ها در سیستم های چندپردازنده ای مانند سیستم های موازی و توزیع شده است. در این­گونه سیستم ها هر برنامه حین کامپایل به قطعات کوچکتری به نام کار شکسته می شود. کارها مستقل نیستند و قیود اولویت (تقدم و تاخر) بین آنها جریان دارد. بدین ترتیب، زمان لازم جهت اجرای کارها، قیود اولویت بین کارها و هزینه های ارتباطی بین آنها با استفاده از یک گراف جهت دار غیرحلقوی به نام گراف وظایف مدلسازی می شود. کارهای یک برنامه باید به تعداد از پیش مشخصی پردازنده به گونه ای نگاشت شوند که قیود اولویت بین کارها رعایت شده و زمان اتمام کل کارها (خاتمه برنامه) حداقل شود. این مساله از جمله مسایل بغرنج زمانی (NP-hard) بوده و به­دست آوردن بهترین زمان­بندی ممکن با افزایش ابعاد مساله عموما غیرممکن است؛ لذا اعمال روش های اکتشافی و فوق اکتشافی مختلف جهت حل این مساله و در راستای یافتن جواب­های شبه­بهینه منطقی است.  دو فاکتور اصلی، طول زمان­بندی به­دست آمده از رهیافت های مختلف ارائه­شده جهت حل این مساله را تحت شعاع قرار می دهد. اول اینکه کارها به چه ترتیبی جهت اجرا انتخاب شوند (زیرمساله ترتیب) و دوم اینکه ترتیب انتخاب شده چگونه بر روی پردازنده ها پخش شود (زیرمساله انتساب). در رهیافت پیشنهادی، الگوریتم بهینه­سازی کلونی مورچه ها ترتیب اجرای کارها را مشخص کرده و اتوماتای یادگیر سلولی، ترتیب مشخص شده را روی پردازنده ها نگاشت می کند. جهت ارزیابی قسمت اول الگوریتم از شش گراف وظایف از برنامه­های واقعی استفاده می­شود که الگوریتم بهینه­سازی کلونی مورچه ها در تمامی موارد قادر به یافتن ترتیب اجرای بهینه­تری نسبت به روش­های سنتی موجود است. در قسمت دوم الگوریتم نیز نتایج به­دست آمده از اتوماتای یادگیر سلولی بهبود محسوسی نسبت به تنها رقیب سنتی خود یعنی روش کمترین زمان شروع ممکن (EST) دارد. در نهایت جهت ارزیابی عادلانه از ۱۲۵ گراف وظایف تصادفی با پارامترهای ساختاری مختلف استفاده شده که نتایج حاکی از آن است که رهیافت پیشنهادی از نظر عملکرد در هر دو زمینه بسیار موفق تر از الگوریتم های سنتی موجود بوده و در نهایت از این روش ها پیشی می گیرد.

کلیدواژه ها:

زمان بندی ایستای کارها ، سیستم های موازی و توزیع شده ، گراف وظایف ، الگوریتم بهینه سازی کلونی مورچه ها ، اتوماتای یادگیر سلولی