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

Abstract

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