ارائه یک الگوریتم اجتماع مورچگان به منظور بهبود در زمان انجام کارها …

۰

شکل۳-۵٫ نمونه ای از واحدها(نشان دهنده هشت درخواست می باشد).

  • تابع ارزیابی

ارزیابی هر کدام از این واحد ها از طریق جمع هزینه های درخواست هایی که برنده شده اند حاصل می گردد. رابطه (۳-۷) بیان گر همین مطلب می باشد :
(۳-۷)

  • نحوه انتخاب والدین

واحد انتخاب کننده به منظور انتخاب دو والد(کروموزوم) برای عملیات برش[۲] می باشد. در روش انتخاب از الگوریتم انتخاب رقابتی استفاده شده است. این روش از ترکیب چند رقابت کوچک تر میان واحد ها به وجود می اید.
۳-۷- متا زمان بند ها [۳]به منظور زمان بندی برنامه های موازی در حراج های دوطرفه در شبکه‌ای های جهانی
متا زمانبند ها کارهایی مانند خوشه ها را که بخشی ازیک شبکه هستند، به منابع محاسباتی نگاشت می کنند که به نوبه خود زمانبندهای کاری محلی را دارند. هدف متا زمانبند های شبکه موجود ، متریک های سیستم محور از قبیل بهره گیری و ساخت یا اولویت بندی برنامه ها بر اساس متریک های سودمندی است که کاربران فراهم می کنند. روش سیستم محور کمتر به مصرف انفرادی کاربران اهمیت می دهد درحالیکه روش کاربر محور ممکن است اثرات منفی از قبیل عملکرد ضعیف و رفتار ناعادلانه کاربران را داشته باشد. بنابراین، این مقاله[۱۹] یک متا زمانبند جدید بر اساس مکانیسم مزایده دوطرفه معروف را پیشنهاد می کند که هدف ان براوردن نیازهای سرویس کاربران است و نیز بهره گیری متعادل منابع در شبکه را تضمین کند. در این تحقیق متریک های ارزشمندی طراحی شده است که نیازهای منابع پیچیده, برنامه های کاربر و قابلیت های منابع محاسباتی موجود را به کالا تبدیل می کند.
متا زمانبند در این مقاله مدلی را دنبال می کند که که معمولا در نصب های محاسباتی بزرگ در موسسه های تحقیقی و اموزشی یافت می شوند[۲۰] همانطور که در شکل ۲-۹ نشان داده می شوند. در این مدل، منابع در مکانهایی مختلفی توسط مدیرانی مدیریت می شوند که نیازهای کاربران محلی را فراهم می کنند. سیستم های زمانبندی دسته ای [۴]که این منابع را مدیریت می کنند بطور کلی به عنوان مجموعه ای از صف های کار قابل دسترس برای کاربر مرتب می شوند که یک صف ممکن است امکان ارائه برنامه های خاصی را فراهم کند که شاخص های خاصی را ارائه می کند (برای مثال، در یک برنامه در حداکثر اندازه) [۲۱]. سیستم مدیریت منابع (زمانبند محلی) در یک سایت ممکن است رویکردهایی از قبیل پرسازی اسان یا محافظه کارانه را بکارگیرند تا بهره گیری و پاسخگوئی را برای برنامه های کوچک ارتقاء دهند[۲۲]. ممکن است پیش دستی در اجرای برنامه ها مجاز نباشد. متا زمانبند از اطلاعاتی استفاده می کند که توسط فروشندگان و کاربران فراهم می شوند تا برنامه ها را با صف های مناسب در منابع مطابقت دهد. متا زمانبند، الگوریتم زمانبندی را در فواصل دوره ای اجرا می کند تا اهداف کاربران و فروشندگان منابع را براورده کند. ممکن است کنترلی روی تخصیص به چند یا همه پردازشگرها در یک منبع داشته باشد یا تنها امکان دسترسی به صف های خاصی را در یک منبع داشته باشد. متا زمانبند پس از تطبیق دادن برنامه ها با صف منابع، برنامه های کاربر را برای اجرا به زمانبند محلی سایت منبع منتقل می کند. بنابراین، بجز متا زمانبند، دو اصل در این سیستم شرکت دارند از جمله سایت های منبع و کاربران.

  • سایت های منبع

ما یک شبکه را با سایت های منبع m در نظر می گیریم، R1,R2…Rm با صف های کار k. سایت های منبع، اطلاعاتی را در مورد شیار های موجود، بار و زمان انتظار هر صف برای متا زمانبند در فواصل منظم فراهم می کنند. یک slot یک واحد تخصیص منبع است که یک زمان اغاز، یک زمان پایان را توصیف می کند و تعداد پردازشگرهای موجود برای ان مدت است. یک سایت منبع همچنین یک ارزیابی ابتدائی برای اجرای یک برنامه در شیار های صف خود فراهم می کند این ارزیابی ابتدائی ممکن است بر اساس پردازشگرهایی باشد که برای صف فراهم شده اند و باری که باید روی منابع توسط کارها در ان صف تولید شود. اهداف متا زمانبند توزیع کارها بین همه سایت های منبع است تا بهره گیری موثر از طریق تعادل بار و کاهش حداقل و زمان انتظار را برای برنامه ها را تضمین کند.

  • کاربر

در این مقاله، برنامه های کاربر را برای دنبال کردن یک مدل برنامه موازی محاسبه فشرده فرایندهای ارتباطی چندگانه دنبال کنیم. یک برنامه تعداد ثابتی از نیازهای پردازشگر را دارد که باید در یک سایت منبع واحد براورده شود. اکثر برنامه های موازی دارای این ماهیت هستند زیرا انها به مدت رکود انتقال پیام حساس هستند مگراینکه انها برای اجرا در منابع چندگانه طراحی شوند. اهداف این کاربران این است که برنامه های خود را تا پایان مهلت تکمیل کنند. تصور می شود که این پایان مهلت ها مشکل زا باشند یعنی، یک کاربر فقط در صورتی سود می برد که برنامه اش تا پایان مهلت اجرا شود. کاربران همچنین یک ارزیابی ابتدائی برنامه را برای متا زمانبند فراهم خواهند کرد. این ارزیابی می تواند بر اساس اهمیت برنامه برای کاربر باشد. در شکل ۳-۶ اشاره شده است.

یک مطلب دیگر:
سايت مقالات فارسی - بررسی عوامل موثر بر تمایل وارد کنندگان به استفاده از روش پرداخت ...

شکل ۳-۶٫ شمایی از رابطه میان متا زمان بند و کاربر و زمان بند های محلی موجود در سایت

یک فرایند متا زمانبند الهام گرفته از مزایده دوطرفه که در این مقاله پیشنهاد می شود و بعد از اینDAM نامیده می شود، توالی سه مرحله گسترده است که درشکل ۳-۷ نشان داده می شود. مرحله اول (جمع آوری) شامل جمع اوری اطلاعات در مورد منابع و برنامه هایی از قبیل موجودیت شیار صف و زمان انتظار برای اولی، نیازهای پردازشگر و QoS برای دومی است. در مرحله بعدی (ارزیابی)، ارزیابی ها برای همه برنامه ها ومنابع توسط متا زمانبند محاسبه می شوند. بیان این نکته مهم است که ارزیابی مخصوص متا زمانبند است و از کاربران وفروشندگان منابع مخفی است. سرانجام، اخرین مرحله از زمانبندی مطابقت دادن برنامه های کاربر با منابع موجود براساس این ارزیابی ها است. برنامه هائی که مطابق نیستند در متا زمانبند نگهداری می‌شوند. در چرخه زمانبند بعدی، ارزیابی منابع و برنامه ها با استفاده از اطلاعات جدید دوباره محاسبه می شوند و مطابقت دوباره انجام می گیرد. گروسا و همکاران [۲۳] پروتکل های تخصیص منابع را با استفاده از اولین قیمت، دومین قیمت ویکری(Vickrey) و مزایده دوطرفه (DA) مقایسه کرده اند و نتیجه گرفته اند که مزایده دوطرفه به نفع کاربران و منابع است در حالیکه مزایده اولین قیمت به سمت منابع و مزایده ویکری به سمت کاربران تمایل [ بایاس] دارد. بنابراین، ما استفاده از اصول مزایده دوطرفه را انتخاب کرده ایم که در متا زمانبند به مزایده تلفنی هم معروف است.
شکل۳-۷٫ ساختار کلی متا زمان بند
در یک مزایده تلفنی، فروشندگان و خریداران پیشنهاد ها (asks:aj , ۱ ≤ j ≤ m) و درخواستهایی (I≤ n≥۱bids:bi,) را به ترتیب به یک مزایده گذار ارائه می کنند که مدام انها را از بالاترین به پائین ترین دسته بندی می کند تا پروفایل های عرضه و تقاضا را تولید کند. ترتیب درخواستها و پیشنهادها پس از دسته بندی در رابطه ۳-۸ به این صورت است:
(۳-۸) a1 < a2 < . . . aj . . . < am
b1 > b2 > . . . bi . . . > bn
یک فروشنده اجازه دارد تا در فرایند مطابقت شرکت کند اگر am < bباشد.
از روی پروفایل ها، حداکثر کمیت مبادله شده با استفاده از مطابقت درخواست ها مشخص می شود که از پائین ترین قیمت شروع می شود و به بالا حرکت می کند در مورد مزایده از بالاترین قیمت اغاز می شود و به پائین حرکت می کند. این فرمت امکان می دهد که خریداران پیشنهاد کنند و فروشندگان ان پیشنهادها را در هر لحظه بپذیرند. مزایده گذار پس از فرایند مطابقت، در مورد مقدار پرداختی که فروشنده از کاربر دریافت کرده است بر اساس ارزش کار و مزایده تصمیم می گیرد. مزایده تلفنی یک چهارچوب کارامد برای تخصیص منابع ارائه می کند مخصوصا اگر در یک دوره زمانی طولانی انجام گیرد. باوجود این، متا زمانبند در این مقاله مطابقت را بطور داخلی بدون هیچگونه مشارکت صریح خریداران و فروشندگان انجام می دهد. همچنین، برنامه هایی که برای زمانبندی در نظر گرفته می شوند بحدی متفاوت هستند که نمی توانند با استفاده از ارزشهای واحد مقایسه و به کالا تبدیل شوند. همین مسئله در مورد منابع هم صادق است. بنابراین، مزایده تلفنی را نمی توان مستقیما برای این سناریو بکار برد. باوجوداین، ما یک مکانیسم ارزیابی را طراحی کرده ایم که به ما امکان می دهد تا از کارامدی مزایده تلفنی برای فرایند تطبیق بهره ببریم.
در مزایده های تلفنی، حداکثر مزایده با حداقل درخواست تطبیق داده می شود. در متا زمانبند، برنامه ای که زودترین پایان مهلت را دارد (و بنابراین فوری تر است) باید با سریع ترین صف تطبیق یابد که پردازشگرهای قابل دسترس کافی دارد. بنابراین، ما مکانیسم ارزیابی خودمان را ساخته ایم از این رو، ارزیابی های منابع، درخواست است و برنامه یا ارزیابی کار، مزایده هستند. ارزیابی منابع و برنامه ها به عوامل زیادی از جمله عرضه و تقاضا، بارهای منبع و پایان مهلت های کاربر بستگی دارند. ما مجبوریم این اقدامات چندگانه را با یک ارزش واحد تطبیق دهیم که بتوان برای مقایسه این ارزش ها استفاده کرد. به این منظور، ما نظریه سود چند ویژگی(MAUT) را بکار می گیریم [۲۴,۲۵,۲۶]، که یک روش منطقی، منسجم و اسان برای تعیین تنظیمات شخصی از طریق ادغام انها در یک هدف واحد را ارائه می کند. این تئوری ابتدا به شناسائی ویژگیها و تابع مطلوبیت برای هر ویژگی و سپس تجمع این تابع مطلوبیت در یک ارزش ابزار عددی واحد می پردازد.
ارزیابی منابع( درخواست) زمانبندهای کار دسته ای که منابع را مدیریت می کنند عموما به عنوان مجموعه صف هایی با ویژگیهای مختلف ساخته می شوند. بار یک صف به عنوان نسبت تعداد پردازشگرهایی که با کارها مشغول می شود به تعداد کل پردازشگرهای موجود برای صف تعریف می شود. متا زمانبند سعی می کند برای متعادل کردن بار در سایت های شبکه، در حال ارائه برنامه، تقدم را به صف هایی بدهد که کمترین بار را دارند. همچنین، فوریترین برنامه باید با سریعترین صف ها مطابق شوند. بنابراین، متریک ارزیابی صف های منابع باید طوری باشند که صفی با حداقل زمان انتظار ،کمترین ارزش درخواست را داشته باشد. متریک ارزیابی باید ارزیابی اولیه که فروشنده منبع ارائه می کند را در نظر بگیرد و همچنین سطوح عرضه و تقاضا منابع در سیستم ( که عرضه و تقاضا معنی می شود). تقاضا مجموع پردازشگرهائی است که برنامه ها برای تخصیص به ان نیاز دارند و عرضه، کل تعداد پردازشگرهای موجود در همه منابع است..فرض کنید lkt بار روی صف منابع k در زمان t باشد. فرض کنید ck,t ارزش منبع اولیه باشد که فروشنده ارائه کرده است. فرض کنید wk,t زمان انتظار برنامه برای صف k در زمان t باشد. بنا براین، تابع مطلوبیت متناسب با wk,t, ck,t ، عرضه و تقاضا وLkt هستند. از انجا که هر یک از این ویژگیها ترجیحا مستقل هستند[۲۶] بنابراین ارزش متریک را می توان با تجمع این ویژگیها در شکل افزاینده یا جمع پذیر تشکیل داد و وقتی اثرات هر متریک را روی توزیع بار روی سایت های منبع مقایسه می کنیم مشاهده می شودکه در مورد شکل جمع پذیر انحراف در بار در سایت های منبع بسیار بیشتر از انحراف در بار در شکل افزاینده است که در شکل ۳-۸ نشان داده می شود.

یک مطلب دیگر:
مقاله دانشگاهی - بررسی عوامل موثر بر تمایل وارد کنندگان به استفاده از روش پرداخت اعتبار اسنادی در ...

شکل۳-۸٫ مقایسه حالت های ضربی و جمعی در فاکتور ارزیابی

بعلاوه، وقتی بیشتر از دو ویژگی مشارکت دارند یک تجمع جمع پذیر صحیح نیاز به مبادله دقیق بین ویژگیها دارد که ممکن است ظاهر نباشد. بنابراین، ما از یک تجمع افزاینده استفاده کرده ایم تا یک متریک ارزیابی را از ویژگیهای نرمال شده، شکل دهیم که cmax, t حداکثر ارزیابی ابتدائی است که فروشنده منابع ارائه کرده است و Lmax t حداکثر بار روی منابع است. این متریک ارزیابی(t) aصف k در زمان t توسط معادله زیر ارائه می شود:
(۳-۹)
که Ok ثابت تناسب است که برای اهداف شبیه سازی ۱ گرفته می شود.
ارزیابی کار(مزایده) مثل منابع، یک برنامه کاربر ویژگیهای زیادی از قبیل تعداد CPUs ، پایان مهلت و زمان اجرا نیاز دارد. متریک ارزیابی برنامه i در زمان t به روشی طراحی می شود که حداکثر ارزش به برنامه هایی با پایان مهلت فوری اختصاص می یابد. همچنین، اگر یک برنامه در چرخه زمانبندی قبلی ترسیم نشده است مزایده مربوط به ان (ارزیابی) باید افزایش یابد. برای اینکه احتمال خالی شدن این برنامه توسط دیگران با ارزیابی بالاتر (مزایده) که همزمان به متازمانبند رسیده اند را کاهش دهیم. (di-t) نشان می دهد که کاربر چقدر زود می خواهد برنامه i اجرا شود که di پایان مهلتی است که کاربر برای برنامه i فراهم کرده است. فرض کنید sti زمان ارائه برنامه باشد همینطور برای منابع، متریک برنامه باید ارزیابی اولیه برنامه کاربر و همچنین سطوح عرضه و تقاضای منابع در این سیستم (که عرضه و تقاضا معنی می شود) را در نظر بگیرد. فرض کنید  ارزیابی اولیه برنامه باشد که کاربر ارائه می کند. بنابراین، تابع مطلوبیت متناسب با vi و sti ، عرضه و تقاضا (di-t) هستند فرض کنید dmaxوvmax و stmax به ترتیب بالاترین ارزیابی اولیه ، بزرگترین پایان مهلت و زودترین زمان اغاز باشند. متریک ارزیابی حاصله برای برنامه i در زمان t با ضرب کردن همه ویژگیهای نرمال شده به صورت رابطه ۳-۱۰ است :
(۳-۱۰)
که Hi ثابت تناسب است که برای اهداف شبیه سازی ۱ گرفته می شود. و
همانطور بیان شد، واحد کالا که از سوی سایت های منبع مطابق می شود شیاری است که یک مجموعه از پردازشگرها توسط زمان اغاز و پایان محدود می شوند. شکل ۳-۹روشی را نشان می دهد که با استفاده از ان می توان شیار ها را در یک سایت شبکه تولید کرد. در زمان t زمانبند کار محلی می تواند شیارهای زمانی را فراهم کند که درحال حاضر ازاد هستند، بنابراین، برنامه ها را می توان برای پر کردن صف در یک افق زمانی خاص Tiبا متا زمانبند زمانبندی کرد. شیار ها از اولین زمان موجود اغاز می شوند و دارای پردازشگرهای زیادی هستند که برای یک مدت خاص مشغول نیستند. شیار های S1 به S5 در شکل ۳-۹، نمونه های چنین شیار های ازاد هستند. فهرست شیار های موجود را می توان با زمانبند کار محلی با استفاده از زمان اجرای تخمین زده شده برنامه تولید کرد. همانطور که در شکل ۳-۹ نشان داده شده پس از زمان کنونی t دو پردازشگر در صف تا زمان TH آزاد هستند زیرا تخمین زده می شود که کارهای J6و J7 قبل زمان t پایان یابند. بنابرابن، شیار زمان موجود با زمان موجود TH-t است. در مورد صف کارهای J4 و J3 پس از زمان t پایان می یابند و ارزیابی می شود که در زمانهای مختلف تکمیل شوند. بنابراین، پردازشگرهای ازاد همزمان پس از زمان t منجر به دو شیار زمان می شوند که هر یک تعداد پردازشگرها و واحد زمان قابل دسترس متفاوتی دارند. به همین صورت یک شیار زمان دیگر شامل یک پردازشگر در صف نیز قابل دسترس است. این روش که شیار دارای اندازه های مختلف است توسط سینق (Singh)و همکاران[۲۷] بکار رفت. در این مورد، زمانبند محلی در سایت منبع می تواند دوباره پر شود تا بخشی را در زمانبندی کوچک کند بطوریکه اجرای برنامه در صف به تاخیر نیافتد. متا زمانبند، برنامه را در فواصل زمانی منظم زمانبندی می کند بنابراین در اغاز چرخه زمانبندی شیار صف به روز شده موجود

دانلود متن کامل این پایان نامه در سایت abisho.ir