سال انتشار: ۱۳۸۱

محل انتشار: هشتمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۶

نویسنده(ها):

حسین میارنعیمی – دانشکده برق – دانشگاه علم و صنعت ایران
مجید نادری – دانشکده برق – دانشگاه علم و صنعت ایران
عادل رحمانی – دانشکده کامپیوتر – دانشگاه علم و صنعت ایران

چکیده:

مسئله زمانبندی برنامههای موازی با ساختار گراف جهتدار روی سیستمهای چندپردازنده، یکی از مسایل پیچیده محاسباتی است . در این مسئله یک برنامه موازی با یک گراف جهتدار بیان
میشود و هدف اختصاص مناسب پردازندهها به گرههای گراف است به طوریکه زمان اجرای کل گرهها کمینه شود . یکی از مشکلات مسایل پیچیده محاسباتی، عدم دسترسی به اطلاعات و
شکل دامنهای است که تابع هدف مورد نظر قرار است در آن بهینه شود . این مسئله سبب میشود، در استفاده از الگوریتمهای جستجو مانند الکوریتم ژنتیک که در آن لازم است جمعیت اولیه
دارای توزیعی یکنواخت روی کل دامنه باشد، مشکلاتی بوجود آید، به این ترتیب که با روشهای موجود جمعیت اولیه در گوشهای از دامنه متمرکر شده و امکان و احتمال جستجوی همه
فضای دامنه را به میزان بسیار زیادی کاهش میدهد . در این تحقیق دامنه مسئله زمانبندی گرافهای جهتدار به صورت ریاضی تحلیل شده و بر اساس آن الگوریتمی دقیق برای انتخاب جمعیت
اولیه با توزیع یکنواخت بدست داده میشود . الگوریتم بدست آمده میتواند در همه مسایلی که ورودی آنها به نوعی گرافها هستند مفید باشد .