در این روش[۱۸] بخش های مرتبط با الگوریتم ژنتیک به صورت زیر فرض و پیاده سازی شده اند :

• • نحوه نشان دادن هر کدام از واحد ها(کروموزوم ها)

یک کروموزوم به وسیله یک وکتور باینری با اندازه تعداد درخواست ها مشخص می شود. اگر هر عضو کروموزوم یک باشد به این معنا است که قبول شده است و اگر برابر با صفر باشد یعنی با این درخواست موافقت صورت نگرفته است. شکل ۳-۵ نشان دهنده یکی از این واحد ها می باشد:

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

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

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

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

واحد انتخاب کننده به منظور انتخاب دو والد(کروموزوم) برای عملیات برش^[۲] می باشد. در روش انتخاب از الگوریتم انتخاب رقابتی استفاده شده است. این روش از ترکیب چند رقابت کوچک تر میان واحد ها به وجود می اید.

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

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

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

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

• • کاربر

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

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

یک فرایند متا زمانبند الهام گرفته از مزایده دوطرفه که در این مقاله پیشنهاد می شود و بعد از اینDAM نامیده می شود، توالی سه مرحله گسترده است که درشکل ۳-۷ نشان داده می شود. مرحله اول (جمع آوری) شامل جمع اوری اطلاعات در مورد منابع و برنامه هایی از قبیل موجودیت شیار صف و زمان انتظار برای اولی، نیازهای پردازشگر و QoS برای دومی است. در مرحله بعدی (ارزیابی)، ارزیابی ها برای همه برنامه ها ومنابع توسط متا زمانبند محاسبه می شوند. بیان این نکته مهم است که ارزیابی مخصوص متا زمانبند است و از کاربران وفروشندگان منابع مخفی است. سرانجام، اخرین مرحله از زمانبندی مطابقت دادن برنامه های کاربر با منابع موجود براساس این ارزیابی ها است. برنامه هائی که مطابق نیستند در متا زمانبند نگهداری می‌شوند. در چرخه زمانبند بعدی، ارزیابی منابع و برنامه ها با بهره گرفتن از اطلاعات جدید دوباره محاسبه می شوند و مطابقت دوباره انجام می گیرد. گروسا و همکاران [۲۳] پروتکل های تخصیص منابع را با بهره گرفتن از اولین قیمت، دومین قیمت ویکری(Vickrey) و مزایده دوطرفه (DA) مقایسه کرده اند و نتیجه گرفته اند که مزایده دوطرفه به نفع کاربران و منابع است در حالیکه مزایده اولین قیمت به سمت منابع و مزایده ویکری به سمت کاربران تمایل [ بایاس] دارد. بنابراین، ما استفاده از اصول مزایده دوطرفه را انتخاب کرده ایم که در متا زمانبند به مزایده تلفنی هم معروف است.

شکل۳-۷٫ ساختار کلی متا زمان بند
در یک مزایده تلفنی، فروشندگان و خریداران پیشنهاد ها (asks:a_j , ۱ ≤ j ≤ m) و درخواستهایی (I≤ n≥۱bids:b_i,) را به ترتیب به یک مزایده گذار ارائه می کنند که مدام انها را از بالاترین به پائین ترین دسته بندی می کند تا پروفایل های عرضه و تقاضا را تولید کند. ترتیب درخواستها و پیشنهادها پس از دسته بندی در رابطه ۳-۸ به این صورت است:
(۳-۸) a₁ < a₂ < . . . a_j . . . < a_m
b₁ > b₂ > . . . b_i . . . > b_n
یک فروشنده اجازه دارد تا در فرایند مطابقت شرکت کند اگر a_m < b_n باشد.
از روی پروفایل ها، حداکثر کمیت مبادله شده با بهره گرفتن از مطابقت درخواست ها مشخص می شود که از پائین ترین قیمت شروع می شود و به بالا حرکت می کند در مورد مزایده از بالاترین قیمت اغاز می شود و به پائین حرکت می کند. این فرمت امکان می دهد که خریداران پیشنهاد کنند و فروشندگان ان پیشنهادها را در هر لحظه بپذیرند. مزایده گذار پس از فرایند مطابقت، در مورد مقدار پرداختی که فروشنده از کاربر دریافت کرده است بر اساس ارزش کار و مزایده تصمیم می گیرد. مزایده تلفنی یک چهارچوب کارامد برای تخصیص منابع ارائه می کند مخصوصا اگر در یک دوره زمانی طولانی انجام گیرد. باوجود این، متا زمانبند در این مقاله مطابقت را بطور داخلی بدون هیچگونه مشارکت صریح خریداران و فروشندگان انجام می دهد. همچنین، برنامه هایی که برای زمانبندی در نظر گرفته می شوند بحدی متفاوت هستند که نمی توانند با بهره گرفتن از ارزشهای واحد مقایسه و به کالا تبدیل شوند. همین مسئله در مورد منابع هم صادق است. بنابراین، مزایده تلفنی را نمی توان مستقیما برای این سناریو بکار برد. باوجوداین، ما یک مکانیسم ارزیابی را طراحی کرده ایم که به ما امکان می دهد تا از کارامدی مزایده تلفنی برای فرایند تطبیق بهره ببریم.