چکیده
برنامه ریزی کارآمد بخش مهمی‌از پردازش برنامه‌های علمی‌پیچیده در محیط‌های توزیع محاسباتی است. پیچیدگی محاسباتی هم از محیط ناهمگن و هم از ساختار برنامه می‌آید که معمولا به عنوان روند کاری که شامل وظایف مربوطه متفاوتی می‌شود، نشان داده می‌شود. تکنیک‌های شناخته شده‌ی بسیاری توسط گروه‌های علمی‌مختلف پیشنهاد شده است. محبوب‌ترین آنها در فن آوری هوشمند مبتی بر لیست حریص و یا الگوریتم‌های فرا ابتکاری است.در این مقاله قابلیت اجرای الگوریتم فرا ابتکاری از پیش توسعه یافته‌ی الگوریتم ژنتیک (GCA) برای سری‌های زمان بندی در روند کاری با محدودیت شدید زمانی را بررسی می‌کنیم.
مقدمه
امروزه سیستم‌های محاسباتی پیچیده بر اساس شبکه، خوشه یا ابرهای محاسباتی نقش بسیار مهمی‌در تحقیقات علمی‌بازی میکنند، که معمولا از برنامه‌هایمرکب برای اهداف محاسباتی استفاده میکنند. برای اجرای این برنامه‌هادر محیط‌هایتوزیع آنها را به وظایف از هم جدا تقسیم میکنند، که می‌توانند در منابع مختلف با محدودیت سمت چپ بر روی وابستگی بین وظایف اجرا شوند. به طور رسمی‌این برنامه‌ها روندهای کاری نامیده می‌شود و توسط نمودار با وظایف تعریف شده بر روی گره‌ها و وابستگی‌های به عنوان لبه ارائه می‌شوند.
برنامه‌ریزی مناسب برای اجرای برنامه‌های مرکب، بر منابع موجود بخش مهمی‌از حل موثر مشکلات است، که برای ما امکان بررسی مکانیزم بهینه سازی فرآیند برنامه ریزی را به ارمغان می‌آورد. برای اهداف مختلف معیارهای بهینه سازی مختلفی را می‌توان مورد استفاده قرار داد، مانند کل زمان اجرا (makespan)، هزینه، بهره‌وری انرژی و غیره. برای محیط‌های ابر، هزینه محاسباتی اغلب مهمترین معیار است، زیرا کاربران باید برای مدت زمان استفاده از منابع هزینه پرداخت کنند. برای شبکه، محاسبه makespan روند کار مهم ترین است، چرا که نتایج اجرا منجر به پیشرفت تحقیقات و بسیاری از برنامه‌های کاربردی مرکب برای بسیاری از کاربرانی که منتظر فرصتی برای شروع اجرا هستند، می‌شود. در این کار، ما یک مشکل محاسبات فوری که مخصوصا محدودیتهای شدیدی بر زمان اجرا دارد، به نام مهلت سخت را مخاطب قرار داده ایم. برای مثال، اینها برای سیستم‌های جلوگیری از خطر جاری شدن سیل، زلزله، بیماری‌های همه گیر، آتش و غیره بسیار مهم هستند.
کارهای مرتبط
امروزه، دو روش به طور گسترده پر استفاده وجود دارد که محدودیت سخت مهلت برای توسعه سیستم‌های زمان واقعی را در نظر می‌گیرد - الگوریتم‌های نرخ یکنواخت (RM) و مهلت نخست اولیه (EDF). در (Buttazzo، 2005) مقایسه‌ای جامع از این الگوریتم‌ها به منظور کشف نقاط قوت و ضعف هر دو الگوریتم و برطرف کردن تصورات غلط مربوط به آنها انجام شد. نشان داده شده است که اگر چه RM پیاده سازی ساده تری دارد، به طور کلی اغلب خواصی که به آن نسبت داده شده است را ندارد، مانند کنترل انحراف یا قابل پیش بینی بودن در شرایط اضافه بار. EDF، از سوی دیگر، اجازه استفاده بهتری از منابع وپاسخ به فعالیتهای نامتناوب را می‌دهد. با توجه به کار ما، مفهوم RM از اختصاص دادن اولویت برای انجام وظایف برعکس دوره‌های آنها، دراصلاح HEFT برای پشتیبانی مهلت پیاده سازی شده است.
شرح مشکل
در این بخش ما مفروضات مان در مورد روندهای کاری، وظایف و منابع محاسباتی آنها، تعریف مساله و راه حل پیشنهاد مان برای آن را توصیف می‌کنیم.
روندهای کاری
معمولا روندهای کاری در قالب گراف غیر مدور و مستقیم (DAG) هستند که در آن گره‌ها برای نشان دادن وابستگی وظایف و لبه‌ها به وظایف (در اکثر موارد وابستگی داده ها) هستند. شرح مفصل این رویکرد در (Sinnen، 2007) داده شده است. در کار ما کل زمان اجرا (makespan) به عنوان پارامتر اصلی بهینه سازی، محدود شده با قید مهلت تعریف شده است. هر روند کاری می‌تواند مهلت زمانی سخت مشخص برای کاربرداشته باشد، که در آن روندهای کاری باید به همه معنا اجرا شوند. ما نمی‌توانیم اجرا را تا زمانی که همه ی مهلت‌ها در برنامه زمانی نگهداری شوند، شروع کنیم.
راه حل پیشنهادی
در این بخش الگوریتم‌های فوق ابتکاری تکاملی و الگوریتم‌های اکتشافی اصلاح شده ارائه شده است.
الگوریتم ژنتیک تکاملی مهلت سخت(HDCGA)
ما مجازی سازی را به عنوان راهی برای افزایش عملکرد زمان بندی در نظر گرفتیم. در (Butakov، 2014) مفهوم رویکرد مرسوم برای برنامه سازی در محیط‌های مجازی ناهمگن بیان شده است. این ایده در مراحل تکاملی به طور همزمان برای زمان بندی وظایف و محیط محاسباتی است. تکامل نگاشت وظایف به روش کلاسیک متقاطع، جهش و انتخاب توسط تابع تناسب سازمان یافته است. تکامل منابع توسط مدیریت منابع مجازی انجام می‌شود. در هر جامعه منابع واقعی به مجموعه‌ای از ماشین‌های مجازی تقسیم می‌شوند. این منابع تشکیل ذرات تکامل می‌دهند، که در شکل 2 نشان داده شده است . طرح اصلی الگوریتم HDCGA در شکل 3 نشان داده شده است. در هر مرحله از فرآیند پیکربندی و برنامه ریزی جمعیت ادغام می‌شوند. سپس برای هر جفت از ذرات زمان بندی ایجاد می‌کنیم، آن را با تابع تناسب ارزیابی می‌کنیم و استراتژی را بر اساس نتایج تابع تناسب اجرا می‌کنیم. در آزمایش‌های ما توجه شده بود که استفاده از این الگوریتم اجازه بهبود لیست اکتشافی، مانند HEFT، تا 84٪ را می‌دهد.
این مقاله در سال 2015 در نشریه الزویر و در مجله پروسدیا علوم کامپیوتر، توسط دانشگاه ITMO منتشر شده و در سایت ای ترجمه جهت دانلود ارائه شده است. در صورت نیاز به دانلود رایگان اصل مقاله انگلیسی و ترجمه آن می توانید به پست دانلود ترجمه مقاله زمان بندی روندکاری مقید با مهلت سخت در سایت ای ترجمه مراجعه نمایید.
