دانلود مقاله درخت سلسله مراتبی و محیط جغرافیایی


Widget not in any sidebars
4-2 استفاده از الگوریتم ژنتیک برای کاربردهای وسیع در گریدهای همگن برای زمانبندی بهینه منابع[3]
محیط جغرافیایی توزیع یافته گرید برای تامین و محاسبه منابع گرید در سطح گریدهای سلسله مراتبی و توزیع یافته نیاز به platform محاسباتی قوی دارد.تا بحال بدلیل ارتباطات و سربار زمانبندی بین سایت ها و اجرای موازی مشکلاتی را ایجاد کرده است.در همان زمان بهینه منابع ارایه شده است که یکی از آنها استفاده از الگوریتم ژنتیک می باشد.
مساله نگاشت مجموعه ای از taskهای تکراری به مجموعه ای از منابع محاسباتی همگن یک مساله NP-Complete کامل می باشد.مقایسه الگوریتم آگاهانه زیاد در این زمینه نشان داده است که الگوریتم ژنتیک از سایر الگوریتم ها می تواند کارا باشد،که الگوریتم ژنتیک برای این زمانبندی بهینه نیاز به Clustering(خوشه بندی)و محدود کردن گراف task ها به منظور ارتباطات برای کاهش سربار زمانبندی مناسب است.بخش بندی همچنین می تواند به مدل های همگن بپردازد.نگرش ما تکنیک هایی در این قسمت ما به مزایای مدیریت سلسله مراتبی منابع محیط گرید برای توسعه الگوریتم نگاشت توزیع یافته می پردازیم،گریدهای محاسباتی مانند درخت ها برای خوشه بندی جغرافیایی نشان می دهد.هر cluster(خوشه) در کنترل administrative که دامنه کنترل عاملها نامیده می شود.یک دید از زمانبندی برای خوشه بندی و زمانبندی ارایه می کند که در این قسمت درخت نگاشت توزیع یافته پیشنهاد می شود.گام اول تولید task ها برای خوشه ها و ارتباطات سطح بالا برای گروهی از درخت های متداول می باشد.درخت مورد نظر از task های cluster که dendrogram نامیده می شود،تشکیل شده است.
در گام دوم از الگوریتم ژنتیک برای نگاشت خوشه برای taskهای در دسترس برای منابع cluster استفاده می شود.در گام سوم از یک زمانبند به صورت الگوریتم تکراری برای خاتمه الگوریتم استفاده می شود.
4-2-1 پارامترهای نگاشت و مدل سیستم
مدل ما از سیستم شامل دو گراف می باشد،منابع گرید که با وزن های غیر مستقیم بیانمی شوند،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،برای هر گره پذیرش می شود،گره مورد نظر مانند یک ابر زمانبند برای کاربردها عملمی کند.ابر زمانبند برای پردازش اولیه پاسخی ارسال می کند.سربار زمانبندهای محلی بررسی می شود.سپس توسط معماری زمانبند و ساختار آن یک نگاشت بهینه برای منابع ارایه می شود.
4-2-2روش نگاشت توزیع یافته:
استراتژی نگاشت پیشنهاد شده ما سه مرحله است:
1-task clustering (خوشه بندی taskها)که در این روش شماره هر task بر ای زمانبندی در ساختار گرافی با شماره منبع موردنظر مساوی قرار داده می شود.
2-cluster mapping(نگاشت خوشه ها):در این مورد از الگوریتم ژنتیک برای نگاشت taskها به clusterها و منابع به کار می رود.
3-recursive distribution:در این مورد یک توزیع بازگشتی از نگاشت taskها به cluster منابع ارایه می شود.
4-2-3Task clustering(خوشهبندیtaskها)
مرحله اجرایی ابر زمانبند شامل گام های زیر است:
1-در نظر گرفتن هر راس از taskهای گراف برای هر cluster
2-مرتب سازی یالها به صورت صعودی بر اساس وزن یالها
3-بدست آوردن ماکزیمم وزن یالها برای کم کردن هزینه اتصال دو cluster
4-ذخیره سازی جزئیات در ساختار درخت باینری در جایی که راس آشکار شده و راس والد وجود داشته باشد که پیچیدگی زمانی این مرحله O(nlogn) می باشد که n تعداد یالهای ارتباطی می باشد.
5-این فرآیند تا زمانی ادامه پیدا می کند که گراف task ها برای هر task دقیقاًبا شماره cluster مورد نظر برابر باشد.
Cluster mapping:در این مرحله از الگوریتم ژنتیک برای یافتنtask cluster های مربوط به منابع به منظور نگاشت taskها به منابع استفاده می شود.
که در این مرحله شامل گام های زیر است:
این مطلب را هم بخوانید :  منابع پایان نامه ارشد درباره رضایت مشتری و کیفیت خدمات و مفهوم وفاداری مشتری