پروپوزال زمان بندی منابع در محاسبات ابری (docx) 34 صفحه
دسته بندی : تحقیق
نوع فایل : Word (.docx) ( قابل ویرایش و آماده پرینت )
تعداد صفحات: 34 صفحه
قسمتی از متن Word (.docx) :
موسسه آموزش عالی غیردولتی غیرانتفاعی میرداماد گرگان
پايان‌نامه جهت دريافت درجه كارشناسي ارشد(M.Sc)
رشته مهندسي كامپيوتر گرايش نرم‌افزار
زمان بندی و انتخاب منابع در محیط محاسبات ابری با استفاده از الگوریتم ژنتیک و شبکه عصبی
پژوهش و نگارش:
مهدی معنوی
استاد راهنما:
دکتر حسین مومنی
1393
تقديم به مهربان فرشتگانی كه؛
لحظات ناب باور بودن, لذت و غرور دانستن, جسارت خواستن, شکوه توانستن, عظمت رسيدن و تمام تجربه‌های يکتا و زيبای زندگيم, مديون حضور سبز آنهاست
چکیده
امروزه شبکه محاسبات ابری به عنوان یکی از مهم ترین ابزارهای توزیع شده برای انجام پردازش و ذخیره سازی داده ها در بستر اینترنت مطرح شده است تا جایی که سال 2010 را بعنوان سال محاسبات ابری نامیدند از جمله ویژگی های بارز این مدل توزیع شده می توان به کاهش چشمگیر هزینه ها و قابلیت اطمینان بالای آن و همچنین میزان پایین در آلودگی محیط زیست اشاره کرد.با رشد روز افزون این شبکه نیاز به زمان بندی کارها بمنظور استفاده ی بهینه از شبکه و پاسخگویی مناسب به کارها بشدت مورد توجه قرار گرفته است و در این زمینه تلاش های زیادی در حال انجام می باشد و به دلیل اینکه محیط محاسبات ابری محیطی بسیار بزرگ و دارای تعداد زیادی کارهای ورودی به شبکه می باشد الگوریتم های قطعی نتیجه ی مناسبی ندارند و بهترین گزینه برای این مدل از شبکه ، الگوریتم های اکتشافی می باشند ولی یکی از مشکلات اکثر روش های ارائه شده عدم جامعیت نسبی برای ارائه یک راهکار کلی در برقراری توازن در بین پارامترهای شبکه محاسبات ابری می باشد همچنین در اکثر کارهای ارائه شده بحث عدالت در اختصاص منابع به کارها نادیده گرفته شده است یعنی برای بسیاری از کارها امکان وقوع گرسنگی وجود دارد.ما برای بهینه سازی پارمترهای زمان اجرا و زمان پاسخگویی و هزینه و بهره وری سیستم الگوریتمی ترکیبی ارائه داده ایم که ما در راهکار ارائه شده برای بحث عدالت برای کارهای وارد شده به شبکه و جلوگیری از گرسنگی آنها چاره ای اندیشیده ایم.در N2TC(Neural Network Task Classification) که بر اساس شبکه عصبی می باشد کارهای جدید و کارهایی که در صف انتظار قرار دارند وارد شبکه شده و به آنها اولویت داده می شود کارهایی که دارای اولویت بالاتری می باشند به GaTa(Genetic Algorithm Task assignment) که مبتنی بر الگوریتم ژنتیک می باشد ارسال شده تا مجموعه ای بهینه از کارها به منابع موجود در شبکه اختصاص یابد. راهکار پیشنهادی بطور میانگین 10% بهبود در زمان اجرا و 25% در بخش بهره وری شبکه محاسبات ابری و 50% در بخش هزینه و 5% بهبود در زمینه زمان پاسخگویی را بیان می کند هم با توجه به سرعت بالا در همگرایی در GaTa باعث افزایش سرعت اجرای زمان بندی شده است.
کلمات کلیدی: انتخاب و زمان بندی منابع، شبکه محاسبات ابری ، الگوریتم ژنتیک، شبکه عصبی، الگوریتم اکتشافی
فهرست مطالب صفحه
فصل اول-مقدمه
1-1-مقدمه.............................................................................................................................................................................1
1-2-بیان مسئله......................................................................................................................................................................2
1-3-اهمیت و ضرورت انجام تحقیق......................................................................................................................................2
1-4-اهداف............................................................................................................................................................................2
1-5-فرضیه............................................................................................................................................................................3
1-6-جمع بندی......................................................................................................................................................................3
فصل دوم-ادبیات و پیشینه تحقیق.
2-1-مقدمه.............................................................................................................................................................................5
2-2-محیط محاسبات ابری.....................................................................................................................................................5
2-2-1-عناصر پایه ای.......................................................................................................................................................5
2-2-2-معماری.................................................................................................................................................................6
2-2-3-انواع ابر...............................................................................................................................................................11
2-2-4-کاربردها..............................................................................................................................................................11
2-2-5-چالش ها.............................................................................................................................................................12
2-3-انتخاب منابع و زمان بندی...........................................................................................................................................14
2-3-1-انتخاب منابع.......................................................................................................................................................14
2-3-2-زمان بندی...........................................................................................................................................................15
2-4-الگوریتم ژنتیک...........................................................................................................................................................15
2-4-1-کروموزم.............................................................................................................................................................16
2-4-2-جمعیت...............................................................................................................................................................16
2-4-3-تابع برازندگی......................................................................................................................................................16
2-4-4-عملگر انتخاب.....................................................................................................................................................17
2-4-5-عملگر آمیزش.....................................................................................................................................................17
2-4-6-عملگر تلفیق........................................................................................................................................................17
2-4-7-عملگر جهش.......................................................................................................................................................18
2-5-شبکه عصبی.................................................................................................................................................................19
2-6-پیشینه تحقیق................................................................................................................................................................20
2-6-1-کارهای مرتبط در محیط محاسبات ابری...............................................................................................................20
2-6-2-کارهای مرتبط در سایر محیط های توزیع شده.....................................................................................................27
فصل سوم- روش تحقیق
3-1-مقدمه...........................................................................................................................................................................34
3-2-مدل پیشنهادی..............................................................................................................................................................34
3-2-1-شبکه عصبی........................................................................................................................................................35
3-2-2-الگوریتم ژنتیک....................................................................................................................................................37
3-3-معماری مدل پیشنهادی.................................................................................................................................................38
3-4-الگوریتم پیشنهادی.......................................................................................................................................................39
فصل چهارم- نتایج تحقیق
4-1-مقدمه...........................................................................................................................................................................43
4-2-سناریو اجرا..................................................................................................................................................................43
4-3-ارزیابی راهکار پیشنهادی.............................................................................................................................................43
فصل پنجم-نتیجه گیری و کارهای آینده
5-1-مقدمه...........................................................................................................................................................................56
5-2-جمع بندی....................................................................................................................................................................56
5-3-نتیجه گیری..................................................................................................................................................................56
5-4-کارهای آینده...............................................................................................................................................................58
مراجع...................................................................................................................................................................60
پیوست ها.............................................................................................................................................................66
فصل 1 مقدمه
مقدمه
در سال 1961 مصادف با صدمین سال تاسیس MIT آقای جان مک کارتی در سخنرانی خود گفت که کامپیوتر می تواند ابزاری اساسی برای صنعتی مهم و جدید باشد این سخن بر مفهوم پایه ای ابرتاکید میکند.اولین معرفی از ابر توسط اریک اشمیت در کنفرانس استراتژی های موتورهای جستجو در سال 2006مطرح شد. [1]
تعریف موسسه جهانی استاندارد و تکنولوژی از محاسبات ابری به شرح زیر است:
شبکه محاسبات ابری مدلی است برای دسترسی به شبکه بر اساس تقاضا برای به اشتراک گذاری مجموعه ای از منابع پیکره بندی شده نظیر شبکه و سرور و محل ذخیره سازی وبرنامه ها و سرویس ها که با میزان سرعت قابل کنترل و با حداقل مدیریت و تعامل با ارائه دهنده سرویس منتشر می شود[2]. همانطور که در شکل 1 می بینید 51% از کاربران بدلیل کارایی بالای شبکه محاسبات ابری از آن استفاده می کنند و 41%به دلیل در دسترس بودن داده ها بدون وابستگی به مکان و محدودیت ناحیه ای می باشد[3]
شکل SEQ شکل \* ARABIC 1- دلایل استفاده از شبکه ابر
مزیت های استفاده از شبکه محاسباتی عبارتند از: 1-هزینه پایین 2- سطح خدمات مناسب 3- شفافیت در دسترسی 4-پشتیبانی از کاربران راه دور[4] 5- بر آورده شدن نیاز های کسب و کار 6- صرفه جویی در انرژی [1]
مطابق با تعریف NIST ویژگی های محاسبات ابری که باعث برتری این تکنولوژی بر تکنولوژی های مشابه می شود عبارتند از: 1-سلف سرویس بودن بر اساس تقاضا 2-دسترسی وسیع به اینترنت 3- مجموعه منابع 4-انعطاف پذیری سریع 5- قابل اندازه گیری بودن خدمات[5].
بیان مساله
یکی از مهم ترین چالش های شبکه محاسبات ابری بحث انتخاب منابع و زمان بندی کارها می باشد. حجم وسیع بار بر روی این شبکه و استقبال زیاد کاربران باعث شده است که کاربران زمان زیادی در انتظار بمانند تا بار شبکه کم شود و منابع مورد نیاز خود را در اختیار بگیرند حال ما قصد داریم با استفاده از الگوریتم های اکتشافی روشی نوین در این زمینه ارائه کنیم که زمانی که کارها به شبکه وارد می شوند منابع را به شیوه ای بهینه و مناسب به آنها اختصاص دهیم تا شبکه هم از نظر سرعت اجرای زمانبندی و هم از نظر دقت در انتخاب کارها به خوبی کار خود را انجام دهد.
اهمیت و ضرورت انجام تحقیق
از آنجایی که روش های فعلی زمانبندی از قبیل Round –Robin و FiFo و ... که در شبکه محاسبات ابری استفاده می شود اگر چه دارای پیاده سازی راحت تری نسبت به راهکار پیشنهادی ما می باشند ولی در زمینه بهبود پارامترهای مهم در شبکه کار چندانی انجام نمی دهند و همچنین بعضی این الگوریتم ها دارای سرعت اجرایی مناسبی نیستند همچنین کاربران شبکه محاسبات ابری همواره بدنبال این هستند که کارهایشان در زمان کوتاه و با هزینه مناسب انجام گیرد از طرفی ارائه دهندگان سرویس نیز به بدنبال افزایش حداکثری بهره وری منابع خود می باشند تا بتوانند سودی بیشتر کسب کنند این در حالی است که در بین الگوریتم های موجود روشی وجود ندارد که بتواند این تعادل را تا حد ممکن در بین نیازهای مشتری و ارائه دهنده سرویس فراهم کند.
اهداف
هدف از ارائه راهکار پیشنهادی که شامل الگوریتم های N2TC وGaTa می باشد بهینه سازی پارامترهایی است که در ادامه آنها را توضیح می دهیم.زمان اجرای کارها یکی از پارامترهای بسیار مهم در شبکه محاسبات ابری است.زمان پاسخگویی نیز پارامتری است که باید فاصله زمانی میان ارسال کار به شبکه و دریافت اولین پاسخ از شبکه به کاربر را کوتاه کنیم.هزینه یکی از مهمترین چالش ها در شبکه محاسبات ابری می باشد که باید تا حد ممکن کاهش یابد.بهره وری سیستم پارامتر بعدی می باشد که یکی از مسائل مهمی است که رائه دهندگان سرویس ها در شبکه محاسبات ابری با آن دست و پنجه نرم می کنند تا بتوانند بیشترین بهره وری را از منابع خود داشته و درآمد بیشتری کسب کنند.پارامتر آخر بحث عدالت برای کارهای ارائه شده است این پارامتر در اغلب -الگوریتم های پیشنهادی در نظر گرفته نشده است و به کارهایی که از نظر پارامتری در حد مطلوبی نمی باشند هیچگاه منابع اختصاص داده نمی شود همین امر باعث کاهش تعداد مشتریان شبکه می شود که در نهایت باعث کاهش درآمد ارائه دهندگان سرویس در شبکه محاسبات ابری می شود ولی با در نظر گرفتن عدالت امکان دریافت منابع توسط این کارها را فراهم می کنیم.
فرضیه ها
در راهکار ارائه شده برای پیاده سازی N2TC از نرم افزار Matlab 2014 استفاده شده است و برای GaTa از نرم افزار Visua studio 2013 و زبان برنامه نویسی C# بهره برده شده است.در این راهکار فرضیات زیر در نظر گرفته شده است:
تعداد منابع: تعداد منابع در دسترس در شبکه محاسبات ابری N می باشد.
تعداد کارهای ورودی: تعداد کارهای ورودی در زمان مشخص به شبکه محاسبات ابری Mمی باشد و M>N می باشد
کارهای وارد شده در این نوع شبکه بصورت قبضه ناپذیر می باشد این بدان معنا است که وقتی کاری وارد سرور می شود زمانی از آن خارج می شود که کار به اتمام رسیده باشد.
کارهای وارد شده به شبکه محاسبات ابری مورد نظر از یکدیگر مستقل می باشند و وابسته نیستند.
جمع بندی
در این فصل به تبیین مسئله اختصاص منابع در شبکه محاسبات ابری پرداختیم سپس اهمیت و ضرورت انجام این تحقیق را بیان کردیم در مرحله بعد اهداف این تحقیق را ارائه نمودیم و در انتها فرضیاتی که تحقیق خود را بر آن بنا نهاده ایم مطرح کردیم.
روش تحقیق
مقدمه
با توجه به مطالب ارائه شده در فصل قبل، مشاهده مي‌شود كه بمنظور ارائه يك روش خوب و جامع برای انتخاب منابع در شبکه محاسبات ابری از پارامترهای زیر استفاده می شود
1-هزینه 2-زمان اجرا 3-زمان پاسخگویی 4-بهره وری سیستم 4-عدالت
در اين فصل به ارائه مدل پيشنهادي جهت انتخاب منابع در شبکه محاسبات ابری مي‌پردازيم. مدل پيشنهادي با توجه به بزرگ بودن محیط محاسبات ابری و حجم بالای کارهای ورودی به این شبکه بر پايه الگوریتم های اکتشافی مي‌باشد. در ادامه به شرح مدل پيشنهادي مي‌پردازيم. سپس معماری مورد نظر خود را بیان می کنیم و در انتها شبه کد های N2TC و GaTa رابیان می کنیم.
مدل پیشنهادی
همانطوری که در شکل 14 مشاهده می کنید در ابتدا کارهایی که وارد شبکه شده و کارهایی که در صف انتظار قرار گرفته اند ادغام می شوند سپس برای هر یک از کارها پارمترهای بیان شده در بالا اندازه گیری می شود و تمام کارها با توجه به نیاز مسئله تعیین پارامتر می شوند. در مرحله بعد کارها به شبکه عصبی آموزش داده شده ارسال می شود تا با توجه به خاصیت تشخیص الگو در شبکه عصبی کارها کلاس بندی شود و به کارها اولویت داده شود در مرحله بعد کارهای دارای اولویت بالا به الگوریتم ژنتیک ارسال شده و در آنجا مجموعه ای از بهینه ترین کارها برای اختصاص منابع به زمانبند معرفی می شود و کارهایی که منابع به آنها اختصاص داده نشده است در صف انتطار باقی مانده تا در مرحله بعد شانس خود را برای دریافت منابع امتحان کنند.
شکل14 - نمودار گردش کار
مدل پيشنهادي بر پايه الگوریتم های اکتشافی بنا شده است. مدل پيشنهادي داراي بخش‌هاي زير مي‌باشد:
بخش تعیین میزان پارامترها برای کارها
ارائه کارها برای تعیین اولویت به شبکه عصبی
ارائه کارهای دارای اولویت بالاتر به الگوریتم ژنتیک
همان طور که اشاره شد بر اساس نیاز هایی که برای اجرای کارها وجود دارد مقادیری برای پارامترهای مورد نظر لحاظ شده تا بتوان بر اساس آنها کارهای مناسب را انتخاب و به خروجی ارسال کرد.
به این دلیل از مدل ترکیبی شبکه عصبی و الگوریتم ژنتیک اسفاده شده است که شبکه عصبی به تنهایی دارای مقداری خطا می باشد و اگر قرار باشد از این شبکه به تنهایی استفاده شود باعث کاهش دقت الگوریتم می شود همچنین اگر از الگوریتم ژنتیک به تنهایی استفاده شود به دلیل ازیاد کارها زمان اجرای الگوریتم زیاد خواهد شد و احتمال رسیدن به جواب بهینه نیز کمتر می شود ترکیب این دو الگوریتم مناسب ترین راهکار برای بهینه کردن زمان و دقت الگوریتم می باشد.
شبکه عصبی
در مرحله اول به ویژگی های شبکه عصبی پیاده شده می پردازیم . مدل سلول عصبی در این پروژه بصورت شکل 15 می باشد
شکل 15- مدل شبکه عصبی
آماده سازی داده ها
در اولین مرحله به بخش بندی داده ها می پردازیم در N2TC از تابع DevidRand استفاده میکنیم تا داده ها برای بخش های آموزش و اعتبارسنجی و تست بصورت تصادفی انتخاب شوند که این تابع باعث می شود در هر سه مرحله آموزش و اعتبار سنجی و تست ، شاهد افزایش کارایی شبکه می باشیم.
تابع انتقال
از آنجايی که تابع انتقال لگاريتمی سيگموئيد، يک تابع مشتق پذير است، عموماً از آن در شبکه های چند لايه ای استفاده می شود که با استفاده از الگوريتم پس انتشار خطا ( Backpropagation ) آموزش می پذيرند. نمونه ای از اين تابع به صورت رابطه 2-1 است:
(2-1)
مطابق رابطه 2-1، ورودي اين تابع انتقال مي تواند هر مقداري بين منفي بينهايت تا مثبت بينهايت باشد در حاليکه خروجي آن در بازه صفر و 1 محدود شده است.شکل این تابع بصورت شکل 16 می باشد
شکل 16 - تابع انتقال سیگموئید
تابع سیگمویید بهترین گزینه از توابع انتقال ، برای تشخیص الگو در شبکه عصبی می باشد به همین دلیل از این تابع استفاده می کنیم.
تابع آموزش
تابع مورد استفاده trainscg نام دارد دلیل انتخاب این تابع این است که معمولا در شبکه های بزرگ که داده های زیادی وجود دارد از این تابع استفاده می شود و از trainlm و trainlp بهتر عمل می کندو همچنین حافظه مورد نیاز این تابع نسبتا کم است و همچنین از الگوریتم های نظیر گرادیان نزولی استاندارد سریع تر عمل می کند.
تابع کارایی
از تابع mse برای تعیین کارایی شبکه استفاده می کنیم.این تابع بدین شکل کار میکند که مجذور میانگین خطاهای موجود بین خروجی و هدف را محاسبه می کند.یکی از توقف زودتر از اتمام آموزش شبکه کاهش کارایی شبکه می باشد که در صورتی که مقدار اختلاف بین خروجی و هدف زیاد باشد آموزش شبکه متوقف می شود.
از ویژگی های دیگری که در این شبکه مورد نظر قرار گرفته memoryReduction است که باعث افزایش سرعت اجرای شبکه می گردد و از ویژگی Earlystop برای بهبود تولیدات شبکه نیز استفاده شده است و 70% داده های اولیه صرف آموزش 15% صرف اعتبار سنجی و 15% صرف تست اولیه شبکه می شود تا نشان دهد شبکه اموزش داده شده چقدر توان پاسخگویی درست به داده های ورودی را دارد. تعداد لایه های پنهانی در شبکه عصبی را 20 در نظر می گیریم هر چه این تعداد بیشتر باشد دقت شبکه بالاتر رفته و به همان نسبت سرعت اجرا پایین و زمان آن بالا می رود.
ما در شبکه عصبی کارها را به سه دسته تقسیم میکنیم , کارهای با اولویت اول و کارهای با اولویت دوم و در نهایت کارهای با اولویت سوم که بهترین دسته از کارها گروه اول می باشند که آنها را به الگوریتم ژنتیک ارسال میکنیم.
معیار طبقه بندی کارها در شبکه عصبی زمان اجرا و هزینه و بهره وری سیستم می باشد .این شبکه عناصری را که دارای مقادیر بهینه در این زمینه باشند در دسته کارهای با اولویت اول قرار داده و به الگوریتم ژنتیک ارسال می کند همچنین الگوریتم برای کارهایی که از دوره های قبل زمانبندی در صف انتطار باقی مانده اند راهکاری را اندیشیده ایم تا آن کارها هم بتواند اجرا شوند و آن راهکار این است که اولویت این کارها در آخر دسته بندی یک رده بهبود داده می شود مثلا اگر کاری در رده اولویت دوم قرار داشته باشد و در صف انتظار قرار داشته باشد آنگاه اولویت آن به اولویت اول تغییر پیدا کرده و به الگوریتم ژنتیک ارسال می گردد.این کار باعث می شود تا به اینگونه کارها نیز فرصت اجرا در شبکه محاسبات ابری داده شود همچنین اگر تعداد کارهای با اولویت اول در این مرحله کمتر از منابع موجود باشدکارهای با اولویت دوم را نیز به الگوریتم ژنتیک ارسال می کنیم تا استفاده حداکثری از منابع موجود در شبکه انجام گیرد و کارایی شبکه کاهش نیابد.
الگوریتم ژنتیک
نمایش کروموزوم در الگوریتم ارائه شده بصورت شکل17 ارائه می شود:
674588561947910424312
شکل17 - نمایش کروموزوم
که همانطور که در شکل 17 دیده می شود تعداد عناصر کروموزوم در این الگوریتم 10 تا در نظر گرفته شده است و بجای استفاده از نمایش دودویی که باعث افزایش حجم ذخیره سازی می شود از شماره هرکدام از عناصر استفاده شده است.
در این مرحله جمعیت اولیه از کروموزوم ها ایجاد می شود که ما تعداد تولیدکروموزوم ها در این مرحله را 100 در نظر گرفته ایم. حال میزان شایستگی این کروموزوم ها را محاسبه می کنیم پارامترهای لحاظ شده در تابع شایستگی ، زمان پاسخگویی و هزینه می باشند. برای انتخاب والدین به منظور تولید فرزندان از روش نخبه سالاری استفاده شده است و کروموزوم هایی که دارای شایستگی بیشتری می باشند انتخاب می شوند. برای تقاطع و تولید فرزند از تقاطع دو نقطه ای استفاده می شود که باعث ایجاد فرزندانی مطلوب تر از روش تقاطع تک نقطه ای می شود.بعد از این مرحله نوبت به جهش در بین فرزندان تولید شده می رسد ، احتمال جهش 5 %در نظرگرفته شده است برای بهبود این بخش از الگوریتم ژنتیک پس از آن که مقدار جدید عنصر جهش یافته انتخاب شد یک جستجوی محلی در اطراف مقدار جدید انجام میگیرد که اگر مقدار بهتری از نظر شایستگی موجود باشد آن انتخاب شود حال میزان شایستگی عنصر بعد از جهش با عنصر قبل از جهش با هم مقایسه شده اگر از نظر شایستگی بهبودی دیده شد عنصر جدید جایگزین عنصر قدیمی می شود در غیر این صورت عنصر قبل از جهش در سر جای خود باقی می ماند.در مرحله بعد میزان شایستگی هرکدام از عناصر تولید شده محاسبه می شود و این چرخه تا زمانی ادامه پیدا می کند که یا به میزان شایستگی دلخواه خود برسیم یا به تعداد تکرار هایی که در الگوریتم در نظر گرفته شده است برسیم تعداد تکرار چرخه در این الگوریتم 100 در نظر گرفته شده است.در راستای استفاده از پارامتر عدالت که در بخش شبکه عصبی لحاظ شده است در این الگوریتم نیز با توجه به اینکه عنصری در صف بوده یا خیر به میزان 10% به شایستگی آن عنصر اضافه می کنیم تا شانس آنها برای انتخاب شدن بالاتر رفته و بتوانند کار خود را به اتمام برسانند.
معماری مدل پیشنهادی
در این بخش معماری پیشنهادی خود را معرفی میکنیم. در شکل 18 معماری ارائه شده را مشاهده می کنید
شکل 18-معماری پیشنهادی
در این معماری کارها از طریق بستر اینترنت به ماژول RAM(Resource Alocation Madule) از شبکه محاسبات ابری متصل می شود. ابتدا از بخش Resource table تعداد منابع خالی و آماده استفاده تعیین می گردد و عدد مورد نظر به بخش schedule منتقل می شود در بخش schedule با توجه به تعداد منابع در دسترس و بوسیله N2TC و GATA کارهای مناسب را انتخاب شده و این کار ها بهمراه مشخصات منابع آزاد به بخش dispatcher منتقل می شود این بخش کارهای دریافتی را به منبع مورد نظر انتقال می دهد .وظیفه dispatcher ارسال کار به منبع و اطمینان از دریافت کار توسط منبع مورد نظر می باشد.پس از گرفتن پاسخ از منبع مبنی بر دریافت کار مورد نظر جدول منابع بروز رسانی می شود. در انتهای کار ،منبع dispatcher را از اتمام کار آگاه کرده و dispatcher جدول منابع را بروز رسانی می کند و منتظر ارائه کار بعدی از طرف RAM می باشد همچنین منابع در این معماری دارای ماشین مجازی می باشند تا سرعت اجرای کارها توسط آنها افزایش یابد.
الگوریتم پیشنهادی
در ابتدا شبه کد مربوط به N2TC را بیان می کنیم که در شکل 19 می بینید
شکل 19-الگوربتم N2TC
در N2TC ابتدا پارامتر بندی کارها را انجام می دهیم سپس شبکه را ساخته و مراحل پیکره بندی مربوط به آن را انجام می دهیم سپس برای کارها وزن در نظر میگیریم وشبکه را آموزش می دهیم سپس از شبکه را ارزیابی می کنیم در انتها هم از شبکه آموزش یافته به منظور تعیین اولویت برای کارها استفاده می کنیم. کارهای با اولویت بالا به الگوریتم ژنتیک ارسال می شود و اولویت کارهایی که از دوره قبل در صف انتظار مانده باشند یک رده بهبود داده می شود.
حال به بررسی الگوریتم GaTa می پردازیم. همانطور که در شکل 20 می بینید
شکل 20-الگوریتم GaTa
ابتدا مجموعه اولیه از کروموزوم ها ساخته می شود برای هر کدام از کروموزوم ها تابع شایستگی محاسبه می شود و این مجموعه بر اساس شایستگی آنها مرتب می شود سپس از والدین برای تولید فرزندان استفاده می شود و عملگر تقاطع اعمال می شود سپس عملگر جهش اعمال می شود و شایستگی آنها محاسبه می شود و این کار تا زمانی که به نتیجه مطلوب برسیم یا به بیشترین تعداد تکرار برسیم ادامه پیدا می کند.
مراجع
[1] Ling Qian, Zhiguo Luo, Yujian Du, and Leitao Guo," Cloud Computing: An Overview", CloudCom 2009, Beijing, China, December 1-4, 2009
[2]P. Mell and T. Grance, “The NIST definition of cloud computing (v15),”
National Institute of Standards and Technology, Tech. Rep., 2009.
[3]Saira Begum , Muhammad Khalid Khan , "Potential of Cloud Computing Architecture",Information and Communication Technologies (ICICT), 2011
[4]M.Malathi , " Cloud Computing Concepts", 3rd International Conference, 2011
[5]Abdeladim ALFATH, Karim BAI A, Salah BArNA , "Cloud Computing Security: Fine-grained analysis and Security approaches" , (IEEE)Security Days (JNS3), 2013
[6]Schmidt, " Conversation with Eric Schmidt hosted by Danny Sullivan" , Search
Engine Strategies Conference , 2006
[7] Dean, J., Ghemawat, " Simplifed Data Processing on Large Clusters" , OSDI ,2004
[8]Gurudatt Kulkarni1, Nikita Chavan2, Ruchira Chandorkar3,Rani Waghmare4, Rajnikant Palwe5," Cloud Security Challenges",7th International Conference on Telecommunication Systems, Services, and Applications (TSSA),2012
[9]Iulian Neamtiu , Tudor Dumitras ," Cloud Software Upgrades: Challenges and Opportunities",IEEE , 2011
[10]C.N. Hoefer and G. Karagiannis ," Taxonomy of cloud computing services",IEEE Globecom Workshop on Enabling the Future Service-Oriented Internet , 2010
[11] T. Xia, Z. Li, and N. Yu, “Research on cloud computing based on deep
analysis to typical platforms,” in CloudCom ’09: Proceedings of the 1st
International Conference on Cloud Computing. Berlin, Heidelberg: Springer-Verlag, 2009
[12] OpenNebula Project. [Online]. Available: http://www.opennebula.org
[13] C. Edwards, “The Tech Beat: Games in the Cloud?” ,Feb2009
[14]Wei-Tek Tsai*, Xin Sun, Janaka Balasooriya," Service-Oriented Cloud Computing Architecture",Seventh International Conference on Information Technology,2010
[15]Liang-Jie Zhang and Qun Zhou , "CCOA: Cloud Computing Open Architecture",IEEE International Conference on Web Services , 2009
[16] Rochwerger B et al., "The RESERVOIR Model and Architecture for,"
IBM Systems Journal, 2009.
[17]Christian Vecchiola, Xingchen Chu, and Rajkumar Buyya, "Aneka: A
Software Platform for.NET-based Cloud Computing," in High Speed and
Large Scale Scientific Computing, 2010
[18]Rajkumar Buyya and Chee Shin Yeo, "Cloud Computing and Emerging
IT Platforms: Vision, Hype, and Reality for Delivering Computing as the
5th Utility," Future Generation Computer Systems, pp. 599-616, 2009.
[19]Ying Huang et al., "A Framework for Building a Low Cost, Scalable and Secured Platform for Web-Delivered Business Services," , 2009.
[20]Tharam Dillon, Chen Wu and Elizabeth Chang, " Cloud Computing: Issues and Challenges " , 24th IEEE International Conference on Advanced Information Networking and Applications,2010
[21] Issa M. Khalil, Abdallah Khreishah," Security Concerns in Cloud Computing ", 10th International Conference on Information Technology: New Generations, 2013
[22] Bhaskar Prasad Rimal , Eunmi Choi , Ian Lumb , "A Taxonomy and Survey of Cloud Computing", Fifth International Joint Conference on INC, IMS and IDC, 2009
[23] Krešimir Popović, Željko Hocenski, "Cloud computing security issues and challenges",MIPRO, Proceedings of the 33rd International Convention ,2010
[24]Minqi Zhou, Rong Zhang, Wei Xie†, Weining Qian, Aoying Zhou," Security and Privacy in Cloud Computing: A Survey",Sixth International Conference on Semantics, Knowledge and Grids,2010
[25]Huaglory Tianfield , "Security Issues In Cloud Computing" , IEEE International Conference on Systems, Man, and Cybernetics,2012
[26]Peter Mell, Tim Grance , " Perspectives on Cloud Computing and Standards", NIST, Information Technology Laboratory
[27]Wenying Zeng , Yuelong Zhao, Kairi Ou, Wei Song," Research on Cloud Storage Architecture and Key Technologies",ICIS , 2009
[28]Sanjeev Dhiman1, Harwant Singh2," A METHODOLOGY ON SCHEDULING IN CLOUD COMPUTING AND ITS TECHNIQUES ", INTERNATIONAL JOURNAL OF DATA & NETWORK SECURITY Vol 3, No.1, JUNE 2013
[29]Patricia Takako Endo, André Vitor de Almeida Palhares, Nadilma Nunes Pereira, Glauco Estácio Gonçalves, Djamel Sadok, Judith Kelner," Resource Allocation for Distributed Cloud: Concepts and Research Challenges",IEEE Network , July/August 2011
[30]Eman Elghoneimy,Othmane Bouhali , Hussein Alnuweiri," Resource Allocation and Scheduling in Cloud Computing",IEEE , 2012
[31] Ronak Patel, Sanjay Patel*," Survey on Resource Allocation Strategies in Cloud Computing", International Journal of Engineering Research & Technology (IJERT)Vol. 2 Issue 2, February- 2013
[32]Vijindra,Sudhir Shenai," Survey on Scheduling Issues in Cloud Computing",International Conference On Modeling Optimazation And Computing,2012
[33] Chun-Wei Tsai , Joel J. P. C. Rodrigues ," Metaheuristic Scheduling for Cloud: A Survey", IEEE SYSTEMS JOURNAL IEEE,2013
[34]Djamila Ouelhadj,Sanja Petrovic," SURVEY OF DYNAMIC SCHEDULING
IN MANUFACTURING SYSTEMS", Journal of Scheduling Springer,2009
[35] Joao Nuno Silva,Luis Veiga,Paulo Ferreira," Heuristic for resources allocation on utility computing infrastructures",ACM,2008
[36]Lifeng Ai, Maolin Tang1 and Colin Fidge," Resource Allocation and Scheduling of Multiple Composite Web Services in Cloud Computing Using Cooperative coevolution",Springer,2011
[37]Jinn-TsongTsai a,n, Jia-CenFang a, Jyh-HorngChou," Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm ",Elsevier,2013
[38]Jianhua Gu, Jinhua Hu, Tianhai Zhao, Guofei Sun," A New Resource Scheduling Strategy Based on Genetic Algorithm in Cloud Computing Environment",JOURNAL OF COMPUTERS, VOL. 7, NO. 1,2012
[39] Zhongni Zheng ,Rui Wang, Hai Zhong, Xuejie Zhang," An Approach for Cloud Resource Scheduling Based on Parallel Genetic Algorithm",IEEE,2011
[40]Shaminder Kaur, Amandeep Verma," An Efficient Approach to Genetic Algorithm for Task Scheduling in Cloud Computing Environment", I.J. Information Technology and Computer Science,2012
[41]Chenhong Zhao, Shanshan Zhang, Qingfeng Liu ,"Independent Tasks Scheduling Based on Genetic Algorithm in Cloud Computing", ,2009
[42] GAN Guo-ning, HUANG Ting-Iei, GAO Shuai," Genetic Simulated Annealing Algorithm for Task Scheduling based on Cloud Computing Environment ", IEEE,2010
[43] Eleonora Maria Mocanu, Mihai Florea, Mugurel Ionuţ Andreica, Nicolae Ţăpuş," Cloud Computing Task Scheduling based on Genetic Algorithms ",-1-4673-0750-5/12/$31.00 © IEEE, 2012
[44] M. Mezmaza,∗, N. Melabb, Y. Kessaci b, Y.C. Lee c, E.-G. Talbi b,d, A.Y. Zomayac, D. Tuyttens," A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems",J. Parallel Distrib. Comput. 71 1497–1508,2011
[45]Zne-Jung Lee a, Chou-Yuan Lee," A hybrid search algorithm with heuristics for resource allocation problem ", Information Sciences 173,2005
[46] Andrew J. Page a, Thomas M. Keanea, Thomas J. Naughtonb," Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system ", J. Parallel Distrib. Comput Elsevier,2010
[47]Yuan-Shun Dai_, Xiao-Long Wang," Optimal resource allocation on grid systems for maximizing service reliability using a genetic algorithm ", Reliability Engineering and System Safety 91 ,2006
[48]Yang Gao , Hongqiang Rongb, Joshua Zhexue Huangc," Adaptive grid job scheduling with genetic algorithms ", Future Generation Computer Systems 21,2005
[49]Golnar Gharooni-fard, Fahime Moein-darbari, Hossein Deldari, Anahita Morvaridi," Scheduling of scientific workflows using a chaos-genetic algorithm ", International Conference on Computational Science, ICCS,2010
[50]Jie Zhu , Xiaoping Li ,Weiming Shen," Effective genetic algorithm for resource-constrained project scheduling with limited preemptions ", Int. J. Mach. Learn. & Cyber.,2011
[51]Wei Wang,Guosun Zeng, Daizhong Tang, Jing Yao," Cloud-DLS: Dynamic trusted scheduling for Cloud computing",Expert system with applications,2011
[52] Dorian Minarolli, Bernd Freisleben," Distributed Resource Allocation to Virtual Machines via Artificial Neural Networks",22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing IEEE,2014
Mirdamad institue of
higher education
Resource allocation in cloud computing using Genetic algorthim and Neural Network
A Thesis Submitted in Partial Fulfillment of the Requirements
for the Degree of Master of Science in Computer Engineering
By:
Mahdi Manavi
Supervisor:
Dr. Hossein Momeni
January 2015
Abstract
Today, cloud computing networks as an important tool for distributed processing and storage of data on the Internet as far as 2010 has been named as the year of cloud computing The distinguishing feature of this model can be distributed to a significant reduction in cost and high reliability as well as low levels of environmental pollution on. With the growth of the network needs to schedule tasks for efficient use of the network and the appropriate response is to work seriously considered: And ongoing efforts in this area and because the cloud computing environment is very large and has a lot of work input to the network: Deterministic algorithms have a good result and the best option for this type of network, heuristic algorithms are But one of the problems presented by a lack of relative recall to provide an overall approach to cloud computing is a balance between network parameters The majority of the works presented in the discussion of justice in the allocation of resources to the tasks that have been ignored for so many things, there is the possibility of hunger We runtime parameters to optimize response time and system cost and efficiency we provide an algorithm combination We presented the solution for the issue of justice for entering the network and prevent hunger things they think are choice In N2TC (Neural Network Task Classification) neural network is based on new tasks and jobs that are waiting in line to enter the network and they are given priority Things that are a higher priority to GaTa (Genetic Algorithm Task assignment) is based on a genetic algorithm to optimize the collection of works devoted to resources on the network. The proposed solutions on average 10% improvement in execution time and 25% in network efficiency of cloud computing and 50% in costs and a 5% improvement in response time tells Due to the high speed of convergence in GaTa speeding execution is scheduled.
Keywords:Resource Allocation and scheduling , Cloud Computing , Genetic Algorithm.Neural Network , Heuristic Algorithm
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
