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

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

۴-۲-۱ پارامترهای نگاشت و مدل سیستم
مدل ما از سیستم شامل دو گراف می باشد،منابع گرید که با وزن های غیر مستقیم بیانمی شوند،Gp=(Vp,Ep) که ما را متوجه مدل گرافی می کند که آن شامل رئوس به صورت:Vp={p1,p2…pn}می باشد و مجموعه ای از یالها به صورت:Ep={(pi,pj)|pi,pjɛVp} هر پردازنده که نقش (راس)pi با وزن پردازش wi دارد.مدل سازی آن پردازش و هزینه هر واحد محاسباتی را دارد.هر یال دارای یک وزن مانند Ci,j است که دلالت بر ارتباطات هزینه هر واحد و ارتباطات بین پردازنده های pi و pj دارد.
وزن محاسباتی wi است که مقدار محاسباتی Vi را بر می گرداند.هر یال بین رئوس Vi و Vj ارتباط وزنی Ci,j که وابستگی داده ای بین آنها را بر می گرداند.
زمان اجرایی کاربردهای موازی شامل زمان پردازش و زمان برقراری ارتباطات می باشد.زمان پردازش taskهای Vi برای پردازنده pi به صورت Tcp[i,j] که Tcp[i,j]=wi×wj می باشد،بیان می شود.زمان ارتباطات برای راس Vi به صورت تعریف می شود.
تا بحال Va و Apb دلالت بر راس Va که همسایه راس Vi هستند و برای پردازنده pb تعیین می شود.
زمان اجرایی pj برای نگاشت M:
و زمان اجرایی کلی:
روش ما برای نگاشت M حداقل کردن ExecM می باشد،مدیریت منابع زیر ساختارهایی با گرید می تواند با درخت سلسله مراتبی مدلسازی شود.که این مورد شامل ابرزمانبند برای زمانبندی های محلی که در برگ های این درخت ذخیره شده باشند،ما فرض می کنیم که هر زمانبند دارای همبندی برای کنترل عامل ها می باشد مجموعه ای از گره های سیستم با تعدادی منابع در مناطق جغرافیایی مختلف می باشد.این درخت زمانبندی T شامل Tik گره می باشد که سطح kام درخت برای گره i شماره زمانبند را نشان می دهد.سیستم گرید برای زمانبندی Tik دلالت بر Grik دارد که Grik ساختار گرافی درخت مورد نظر می باشد که :Grik=(Vrik,Erik) در حالی که می باشد ممکن است،Erik در سطوح پایین یالها و مجموعه ای از منابع و cluster ها که در داخل گراف Gr00قرار دارند.
وقتی یک job،برای هر گره پذیرش می شود،گره مورد نظر مانند یک ابر زمانبند برای کاربردها عملمی کند.ابر زمانبند برای پردازش اولیه پاسخی ارسال می کند.سربار زمانبندهای محلی بررسی می شود.سپس توسط معماری زمانبند و ساختار آن یک نگاشت بهینه برای منابع ارائه می شود.
۴-۲-۲روش نگاشت توزیع یافته:
استراتژی نگاشت پیشنهاد شده ما سه مرحله است:
۱-task clustering (خوشه بندی taskها)که در این روش شماره هر task بر ای زمانبندی در ساختار گرافی با شماره منبع موردنظر مساوی قرار داده می شود.
۲-cluster mapping(نگاشت خوشه ها):در این مورد از الگوریتم ژنتیک برای نگاشت taskها به clusterها و منابع به کار می رود.
۳-recursive distribution:در این مورد یک توزیع بازگشتی از نگاشت taskها به cluster منابع ارائه می شود.
۴-۲-۳Task clustering(خوشهبندیtaskها)
مرحله اجرایی ابر زمانبند شامل گام های زیر است:
۱-در نظر گرفتن هر راس از taskهای گراف برای هر cluster
۲-مرتب سازی یالها به صورت صعودی بر اساس وزن یالها
۳-بدست آوردن ماکزیمم وزن یالها برای کم کردن هزینه اتصال دو cluster
۴-ذخیره سازی جزئیات در ساختار درخت باینری در جایی که راس آشکار شده و راس والد وجود داشته باشد که پیچیدگی زمانی این مرحله O(nlogn) می باشد که n تعداد یالهای ارتباطی می باشد.
۵-این فرایند تا زمانی ادامه پیدا می کند که گراف task ها برای هر task دقیقاًبا شماره cluster مورد نظر برابر باشد.
Cluster mapping:در این مرحله از الگوریتم ژنتیک برای یافتنtask cluster های مربوط به منابع به منظور نگاشت taskها به منابع استفاده می شود.
که در این مرحله شامل گام های زیر است:
گام۱:[۳]
۱-ارسال بالا به پایین شماره سطوح cluster هایی که برابر شماره منابع clusterها که به صورت قطعه کد زیر است:
Phase1()
Input task graph
Initialize each node as a cluster
Sort edges of task graph in descending order of their weights
For each edge(u,v)next in order
m=merge(u,v)where m is the new merged vertex
add_to_dendrogram(a,u,v)
End for
Merge(u,v)
Weight(u,v)=0
Weight(a)=weight(u)+weight(v)
add_to_dendrogram(a,u,v)
parent[u]=a
parent[v]=a
leftchild[a]=u
rightchild[a]=v

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

mop