این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
رایانش نرم و فناوری اطلاعات، جلد ۵، شماره ۳، صفحات ۳۵-۰
عنوان فارسی رهیافتی ترکیبی مبتنی بر الگوریتم بهینه‌سازی کلونی مورچه‌ها و اتوماتای یادگیر سلولی در حل مساله زمانبندی ایستای کارها در سیستم‌های چندپردازنده‌ای همگن
چکیده فارسی مقاله زمان­بندی کارها یکی از بزرگترین چالش‌ها در سیستم‌های چندپردازنده‌ای مانند سیستم‌های موازی و توزیع‌شده است. در این­گونه سیستم‌ها هر برنامه حین کامپایل به قطعات کوچکتری به نام کار شکسته می‌شود. کارها مستقل نیستند و قیود اولویت (تقدم و تاخر) بین آنها جریان دارد. بدین ترتیب، زمان لازم جهت اجرای کارها، قیود اولویت بین کارها و هزینه‌های ارتباطی بین آنها با استفاده از یک گراف جهت‌دار غیرحلقوی به نام گراف وظایف مدلسازی می‌شود. کارهای یک برنامه باید به تعداد از پیش مشخصی پردازنده به گونه‌ای نگاشت شوند که قیود اولویت بین کارها رعایت شده و زمان اتمام کل کارها (خاتمه برنامه) حداقل شود. این مساله از جمله مسایل بغرنج زمانی (NP-hard) بوده و به­دست آوردن بهترین زمان­بندی ممکن با افزایش ابعاد مساله عموماً غیرممکن است؛ لذا اعمال روش‌های اکتشافی و فوق‌اکتشافی مختلف جهت حل این مساله و در راستایِ یافتن جواب­های شبه­بهینه منطقی است.  دو فاکتور اصلی، طول زمان­بندی به­دست‌آمده از رهیافت‌های مختلف ارائه­شده جهت حل این مساله را تحت شعاع قرار می‌دهد. اول اینکه کارها به چه ترتیبی جهت اجرا انتخاب شوند (زیرمساله ترتیب) و دوم اینکه ترتیب انتخاب‌شده چگونه بر روی پردازنده‌ها پخش شود (زیرمساله انتساب). در رهیافت پیشنهادی، الگوریتم بهینه­سازی کلونی مورچه‌ها ترتیب اجرای کارها را مشخص کرده و اتوماتای یادگیر سلولی، ترتیب مشخص‌شده را روی پردازنده‌ها نگاشت می‌کند. جهت ارزیابی قسمت اول الگوریتم از شش گراف وظایف از برنامه­های واقعی استفاده می­شود که الگوریتم بهینه­سازی کلونی مورچه‌ها در تمامی موارد قادر به یافتن ترتیب اجرای بهینه­تری نسبت به روش­های سنتی موجود است. در قسمت دوم الگوریتم نیز نتایج به­دست‌آمده از اتوماتای یادگیر سلولی بهبود محسوسی نسبت به تنها رقیب سنتی خود یعنی روش کمترین زمان شروع ممکن (EST) دارد. در نهایت جهت ارزیابی عادلانه از 125 گراف وظایف تصادفی با پارامترهای ساختاری مختلف استفاده شده که نتایج حاکی از آن است که رهیافت پیشنهادی از نظر عملکرد در هر دو زمینه بسیار موفق‌تر از الگوریتم‌های سنتیِ موجود بوده و در نهایت از این روش‌ها پیشی می‌گیرد.   
کلیدواژه‌های فارسی مقاله
عنوان انگلیسی رهیافتی ترکیبی مبتنی بر الگوریتم بهینه‌سازی کلونی مورچه‌ها و اتوماتای یادگیر سلولی در حل مساله زمانبندی ایستای کارها در سیستم‌های چندپردازنده‌ای همگن
چکیده انگلیسی مقاله زمان­بندی کارها یکی از بزرگترین چالش‌ها در سیستم‌های چندپردازنده‌ای مانند سیستم‌های موازی و توزیع‌شده است. در این­گونه سیستم‌ها هر برنامه حین کامپایل به قطعات کوچکتری به نام کار شکسته می‌شود. کارها مستقل نیستند و قیود اولویت (تقدم و تاخر) بین آنها جریان دارد. بدین ترتیب، زمان لازم جهت اجرای کارها، قیود اولویت بین کارها و هزینه‌های ارتباطی بین آنها با استفاده از یک گراف جهت‌دار غیرحلقوی به نام گراف وظایف مدلسازی می‌شود. کارهای یک برنامه باید به تعداد از پیش مشخصی پردازنده به گونه‌ای نگاشت شوند که قیود اولویت بین کارها رعایت شده و زمان اتمام کل کارها (خاتمه برنامه) حداقل شود. این مساله از جمله مسایل بغرنج زمانی (NP-hard) بوده و به­دست آوردن بهترین زمان­بندی ممکن با افزایش ابعاد مساله عموماً غیرممکن است؛ لذا اعمال روش‌های اکتشافی و فوق‌اکتشافی مختلف جهت حل این مساله و در راستایِ یافتن جواب­های شبه­بهینه منطقی است.  دو فاکتور اصلی، طول زمان­بندی به­دست‌آمده از رهیافت‌های مختلف ارائه­شده جهت حل این مساله را تحت شعاع قرار می‌دهد. اول اینکه کارها به چه ترتیبی جهت اجرا انتخاب شوند (زیرمساله ترتیب) و دوم اینکه ترتیب انتخاب‌شده چگونه بر روی پردازنده‌ها پخش شود (زیرمساله انتساب). در رهیافت پیشنهادی، الگوریتم بهینه­سازی کلونی مورچه‌ها ترتیب اجرای کارها را مشخص کرده و اتوماتای یادگیر سلولی، ترتیب مشخص‌شده را روی پردازنده‌ها نگاشت می‌کند. جهت ارزیابی قسمت اول الگوریتم از شش گراف وظایف از برنامه­های واقعی استفاده می­شود که الگوریتم بهینه­سازی کلونی مورچه‌ها در تمامی موارد قادر به یافتن ترتیب اجرای بهینه­تری نسبت به روش­های سنتی موجود است. در قسمت دوم الگوریتم نیز نتایج به­دست‌آمده از اتوماتای یادگیر سلولی بهبود محسوسی نسبت به تنها رقیب سنتی خود یعنی روش کمترین زمان شروع ممکن (EST) دارد. در نهایت جهت ارزیابی عادلانه از 125 گراف وظایف تصادفی با پارامترهای ساختاری مختلف استفاده شده که نتایج حاکی از آن است که رهیافت پیشنهادی از نظر عملکرد در هر دو زمینه بسیار موفق‌تر از الگوریتم‌های سنتیِ موجود بوده و در نهایت از این روش‌ها پیشی می‌گیرد.   
کلیدواژه‌های انگلیسی مقاله
نویسندگان مقاله حمیدرضا بویری | hamidreza boveiri
آموزشکده فنی و حرفه ای سما، دانشگاه آزاد اسلامی، واحد شوشتر، شوشتر، ایران
سازمان اصلی تایید شده: دانشگاه آزاد اسلامی شوشتر (Islamic azad university of shooshtar)

نشانی اینترنتی http://jscit.nit.ac.ir/index.php/jscit/article/view/Vol.5_No.3_4
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده
نوع مقاله منتشر شده JSCIT
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات