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

سال انتشار: 1392
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 691

فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

NCCEB01_041

تاریخ نمایه سازی: 18 خرداد 1393

چکیده مقاله:

زمانبندی بهینه کارها یکی از مهمترین چالشها در سیستم های چند پردازندهای چون سیستم های موازی و توزیع شده است. در اینگونه سیستمها، هر برنامه به تعدادی کار شکسته میشود. با توجه به وابسته بودن کارهای یک برنامه، زمان اجرای کارها، قیود اولویت بین آنها و هزینه های ارتباطی با استفاده از یک گراف غیر حلقوی جهت دار به نام گراف وظایف مدلسازی میشود. کارهای هر برنامه باید به گونه ای به پردازنده ها نگاشت شوند که قیود اولویت بین کارها رعایت شده و زمان اتمام برنامه حداقل گردد. این مساله در شکل کلی آن از جمله مسایل بغرنج بوده و یافتن بهترین زمان ممکن عموماً غیرممکن است لذا استفاده از رهیافت های هوشمند و فوق اکتشافی جهت حل این مساله منطقی خواهد بود. زمان اتمام بدست آمده از الگوریتم های مختلف به دو عامل بستگی دارد.اول اینکه کارهای موجود در گراف وظایف به چه ترتیبی جهت اجرا انتخاب شوند (ترتیب) و دوم اینکه ترتیب انتخاب شده چگونه به پردازنده ها منتسب شود (انتساب). هر چند رهیافت های مختلفی جهت انتخاب چگونگی ترتیب اجرا پیشنهاد شده اند اغلب آنهاپس از یافتن ترتیب مناسب، هر کار را به پردازندهای نگاشت میکنند که زودترین زمان اجرای ممکن را فراهم میکند. نتایج این مقاله نشان میدهد انتساب کارها به پردازنده ها به روش زودترین زمان اجرای ممکن، بهینه نبوده و در ادامه رهیافت هایی مبتنی بر اتوماتای یادگیر و اتوماتای یادگیر سلولی نامنظم ارائه میشود که میتوانند جواب های بهتری بیابند.

کلیدواژه ها:

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

نویسندگان

حمیدرضا بویری

آموزشکده فنی و حرفه ای سما، دانشگاه آزاد اسلامی واحد شوشتر

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • و نخبگان واحد شوشتر _ اسفند ماه 1392 ...
  • Kwok, Y. and Ahmad, I. "Static Scheduling Algorithms for Allocating ...
  • Wolfram, S., "Cellular Automata", Los Alamos Science, Vol. 9, pp. ...
  • Narendra, K. S. and Thathachar, M. A. _ "Learning Automata: ...
  • Thathachar, M. A. L. and Sastry, P. S., "Varieties of ...
  • Meybodi, M. R., Beigy, H. and Taherkhani, M., "Cellular Learning ...
  • Beigy, H. and Meybodi, M. R., "Cellular Learning Automata With ...
  • multiprocessor task scheduling algorithms with communication costs", Computer & Operations ...
  • Asnaashari, M. and Meybodi, M. R., "Irregular Cellular Learning Automata ...
  • _ Networks", _ Conf. _ Engineering, Vol. _ C ommunication, ...
  • Al-Mouhamed, M. A., "Lower Bound on the Number of Processors ...
  • Wu, M. Y. and Gajski, D.D., "Hypertool: A Programming Aid ...
  • نمایش کامل مراجع