تحقیق - پایان نامه - مقاله و پروژه

مقالات : استفاده از الگوریتم ژنتیک و منطق فازی برای بهینه سازی منابع بازار براساس شبکه بندی- قسمت ۱۶

گام۲:[۳]
ارائه task cluster ها و resource clusterها ورودی از الگوریتم ژنتیک به منظور نگاشت بهینه بدست آوردن نگاشت و ارسال هر task cluster به processor cluster مناسب که این عمل توسط قطعه کد زیر انجام می شود.
Phase 2()
Input dendrogram,resource_clusters
Task_clusters[1]=dendrogram()
GA(task_cluster,resource_clusters)
Send task_clusters to their respective resource_clusters
Traverse_dendrogram()
While n≤number of resource_clusters
Task_clusters[n++]=dendrogram[root].rchild
Task_clusters[n]=dendrogram[root].lchild
If n≤number of clusters
n–
traverse_dendrogram()
End if
End while
۴-۲-۳-۱ توزیع بازگشی:
این مورد در دو مرحله که هر یک از منابع به cluster معادلشان نگاشت می شوند،به صورت بازگشتی اجرامی شود:
۱-ارسال زمانبند زمانبند والد به cluster به صورت بالا به پایین که شماره task ها برابر شماره پردازنده ها می باشد.
۲-تخصیص پردازنده ها به taskها بر اساس الگوریتم ژنتیک به منظور نگاشت بهینه
۳-تخصیص نهایی taskها به پردازنده ها برای بدست آوردن نتایج از الگوریتم ژنتیک
۴-۲-۳-۲ الگوریتم ژنتیک(GAS):
الگوریتم ژنتیک یک الگوریتم بهینه و کارا برای جستجو برای مسایل محاسباتی می باشد،الگوریتم ژنتیک یک زمانبند با Tki ورودی برای گراف task cluster و نگاشت به زیرمجموعه ای از منابع Vrik راس می باشد،ما رشته ای به طول |Vrik| از taskها را برای منابع انتخاب کنیم.جمعیت اولیه تولید شده توسط این الگوریتم به صورت تصادفی تولید می شود.
تابع بازخورد Q برای ماکزیمم زمان اجرایی به صورت زیر تعریف می شود.
Q(M)=
مکانیزم انتخاب استفاده شده به صورت احتمالات از والدها وابسته به تابع fitness می باشد.
ما crossover های ساده را به صورت زیر در نظر می گیریم:[۳]
عملگرهای جهش برای جمعیت متوسط بعد از crossover به کار می روند.برای هر ژن بر اساس جهش احتمالی جداول فوق تدوین شده است.
برای تخمین بهترین جمعیت و سریع ترین همگرایی از زمانی که محدوده نگاشت مساله هنوز در بحث های تحقیقی باز قرار دارد.یافتن شرایط نهایی در الگوریتم ژنتیک واقعاً بر اساس اولویت های قبلی تعریف شده برای الگوریتم ژنتیک صورت می گیرد.
۴-۲-۴ مطالعات تجربی:
برای ارزیابی کارایی الگوریتم نگاشت ما چندین آزمایش تجربی بارکاری از مدل محاسباتی Mesh ایرودینامیک شبیه سازی شده NASA مراحل زیر طراحی شده است:
۱-زمان اجرایی (ET) که به صورت ExecM تعریف شده است.
۲-انحراف معیار:این مورد بر اساس واریانس هر پردازنده تعیین می شود.
که در ان Etav تعداد پردازنده ها می باشد.
که در آن |VP|تعداد پردازنده ها می باشد.
۳-system potential
که در آن ep زمان مورد نیاز برای محاسبه رئوس p،cp زمان مورد نیاز برای ارتباطات داخلی همه ی یالها S میانگین درجه بارکاری گراف می باشد.
۴-۳ زمانبندی task ها در گرید ها بر پایه الگوریتم Swarm[1]
روش های سنتی زمانبندی می توانند تنها تقریبی از بهینه سازی با در نظر گرفتن الگوریتم های تک وظیفه ای مستقل برای زمانبندی ارائه کند،الگوریتم particle swarm برای حل زمانبندی وظایف برای گرید های محاسباتی به کار می رود.این الگوریتم مدلی برای زمانبندی گریدهای محاسباتی ارایهمی کند.الگوریتم swarmمی تواند فضای پیوسته ای برای جستجوی منابع ارائه کند.انتخاب منابع مناسب و زمانبندی بهینه بر اساس وزن ها و مقادیر اولویت منابع با این الگوریتم صورت می گیرد.این الگوریتم در مقایسه با الگوریتم های hybrid و ژنتیک می تواند مزایایی داشته باشد که در این قسمت به آنها اشاره خواهیم کرد.
مدیریت منابع و زمانبندی taskها یکی از مدل هایی برای گریدهای محاسباتی می باشد،برای زمانبندی taskها مشکلاتی در مقیاس های کوچک وجود دارد که می تواند با روش های سنتی زمانبندی حل شود.اما زمانبندی taskها در مقیاس های بزرگ یک مساله از مرتبه NP-hard می باشد که هنوز یک روش حل و راه حل چند جمله ای برای آن یافت نشده است.با پیدایش گریدهای محاسباتی،الگوریتم های زمانبندی قدیمی سازگاری خوبی با ویژگی های منابع در محیط گریدهای محاسباتی ندارند.چگونگی تخصیص و مدیریت منابع گرید برای سرویس های گرید محاسباتی می تواند به صورت بهینه برای جست و جوی منابع محاسباتی به کار رود.الگوریتم ژنتیک دارای مشکلاتی مانند هزینه بالاتر و زمان پیاده سازی طولانی می باشد در این قسمت برای زمانبندی taskها در گرید های محاسباتی بر پایه الگوریتم particle swarm با کارآیی پیاده سازی بالاتر با تحلیل و نتایج شبیه سازی و کارآیی بالا که بهتر از الگوریتم های سنتی می باشد ارائه خواهیم کرد.
۴-۳-۱ توضیح مسئله:

در پایین درج شده است

mop