بخشی از مقاله
چکیده:
الگوریتم های محاسبات جریان داده - - work flow یکی از جنبه های مهم پردازشی در محاسبات ابری می باشد . این الگوریتم ها بصورت عمده در محاسبات علمی به صورت گراف جهت دار بدون حلقه - DAG - تشکیل می شوند.ترتیب اجرای دستورات از نقطه راس یک گراف بدون سیکل بسته، آغاز می شوند وبه ترتیب منطق اجرای برنامه ،تا سطوح پایین تر گراف ادامه پیدا می کنند.بخاطر وابستگی دستورات سطوح پایین تر،به دستورات بالاترگراف،تا انجام نشدن دستورات با مرتبه بالا،دستورات وابسته به آن درگراف،نمی توانند اجرا شوند.یکی از جنبه های مهم ارزیابی این گراف ها،یافتن زیرگراف های مستقل می باشد که بتوانند بصورت موازی اجرا شوند،تا سرعت اجرای محاسبات افزایش یابند.منابع ابری می توانند بطور موازی ، بخش های موازی شونده، این گراف را اجرا کنند.الگوریتم های متعددی در این حوزه معرفی شده اند که دراین مقاله سعی شده است به تحلیل وارزیابی آنها پرداخته شود.زمان بندی در این الگوریتم ها نقش بسیار مهمی ایفا می کنند.یک زمان بندی درست موجب می شود که یک جریان داده با کمترین تاخیر وبا کیفیت سرویس مناسب تحویل کاربران شود.این زمان بندی ها در مقاله ارایه شده بررسی وارزیابی می شوند.
.1 مقدمه
پردازش ابری وکاربردهای آن به یکی از جذاب ترین موضوعات علمی وپژوهشی مبدل شده است.امروزه به خاطر وجود برنامه ها و داده های حجیم،نیاز به منابع پردازشی قدرتمند و فضاهای حافظه ای خیلی بزرگ ،حیاتی به نظر می رسند.این پردازش های عمدتا" سنگین روی کامپیوترهای تک کاربره کاربران نمی توانند اجرا شوند ویا این که به مدت زمان زیادی برای اجرا و حجم زیادی برای ذخیره سازی نیاز دارند.منابع موجود در شبکه های سرویس دهنده محاسبات ابری می توانند در این حوزه ،سرویس های قدرتمند،سریع و با کیفیتی را به کاربران ارائه نمایند.برنامه های کاربردی بسیار متنوعی با دسته بندی های متفاوتی می توانند روی این شبکه های ابری اجراشوند.همچنین وجود منابع نا همگن که بصورت پویا دائم درحال تغییر می باشند،زمان بندی استفاده از آنها را پیچیده می نماید.یکی از کاربردهای مهم استفاده از منابع ابری،محاسبات علمی پیچیده می باشد که بصورت یک گراف بدون سیکل جهت دارطراحی می شوند،در می آیند.دراین گراف ها،ترتیب اجرای دستورات بسیار مهم می باشند.دریک گراف،دستورات به عنوان گره و رابطه بین هر عمل با عمل وابسته به آن با یک لبه نشان داده می شود.
لبه ها نتایج محاسبات را به نودهای وابسته خود ارسال می کنند.درصورتی که با یک پردازنده و بصورت ترتیبی بخواهیم یک گراف محاسبات علمی را اجرا کنیم،به مدت زمان خیلی زیادی نیاز خواهیم داشت.بنابراین با استفاده از منابع موجود یک شبکه ابری می توان بخش های موازی شونده گراف را استخراج کرد و بطور همزمان این بخش ها را اجراکرد.شکل شماره 1 مثالی از یک گراف نشان می دهد که در این گراف عملیات در راس ها انجام شده و نتایج روی لبه ها برای ارسال به بخش های وابسته قرارمی گیرند.
دراین گراف کارها درلبه ها تعریف می شوند و نتایج استخراج شده از آنها به گره های دیگری که به آن نتایج وابسته هستند ارسال می شود.به گره ارسال کننده،گره والد، وبه گره های وابسته به آن،گره فرزند اطلاق می شود.تازمانی که گره والد نتایج خود را تولید نکرده باشد،گره های فرزند نمی توانند اجرا شوند.مثلا" T5,T6 به T3 وابسته هستند.T1 و T9 نیز گره های شروع وپایانی این گراف هستند.گره شروع هیچ والدی ندارد و گره پایانی نیز فاقد فرزند می باشد.
زمان بندی این گراف ها بسورت استاتیکی انجام نمی شود.این کار بخاطر این است که از قبل نمی توان تخمین دقیقی از زمان شروع واتمام هر گره یا زیرگراف داشت.هرتخمین ایستایی،می تواند موجب شود که اولا" task ها در زمان مقرر و پیش بینی شده اجرا نشوند و یا این که زمان انتظار تلف شده ای برای گره ها،برای دریافت نتایح از والدین خود،براساس یک زمان ازقبل تعیین شده وثابت بوجود آید.به همین دلیل اغلب زمان بندی ها در این حوزه بصورت پویا و دینامیکی می باشند.
درادامه به چند الگوریتم مرتبط با جریان های کار روی محاسبات علمی است،پرداخته می شود و موردارزیابی قرار می گیرند.
-2 الگوریتم های زمان بندی روی جریان های کار
در این بخش به بررسی الگوریتم های زمان بندی در مورد گراف های جریان کار خواهیم پرداخت.این روش ها مبتنی بر الگوریتم ژنتیک،ازدحام ذرات،تبرید شبیه سازی شده ،کلونی مورچه،سلسله مراتبی ،مبتنی برمصرف توان ،سلسله مراتبی و مبتنی برداده های حجیم هستند که سعی شده است ارزیابی مناسبی از آنها ارائه گردد.
2-1زمان بندی جریان کار مبتنی بر الگوریتم ژنتیک
برخی از الگوریتم های زمان بندی مرتبط با الگوریتم های ژنتیک می باشند.این الگوریتم ها می توانند بر حسب الگوریتم ژنتیک استاندارد باشند.همچنین برخی دیگر از پژوهشگران ، با تغییر و ویرایش الگوریتم ژنتیک استاندارد،کارهای مهمی دراین زمینه انجام داده اند.در یکی از کارها [1] که مبتنی بر زمان کامل شدن task ها و توزیع بار روی منابع می باشد،درابتدا با استفاده از اولویت بندی کارهای دوطرفه ،یک جمعیت اولیه ایجاد می شود.سپس با درنظر makespan یا زمان کلی انجام کار،وپس از چندین نسل ،بهترین ومناسب ترین منابع موجود را از شبکه ابری انتخاب می کند.در جهت بهینه سازی پاسخ ها، عمل جستجو روی پاسخ های مناسب ،با استفاده از عملگر جهش انجام می شود.درحقیقت هر ماشین به صورت یک ژن در یک کروموزوم دیده می شوند و بهترین کروموزوم به عنوان بهترین انتخاب درنظرگرفته می شود .سادگی وقابلیت پیاده سازی این الگوریتم پیشنهادشده،ازمزایای این روش می باشد.
:2-2زمان بندی کارجریان داده مبتنی بر الگوریتم ازدحام ذرات
یکی از روش های زمان بندی در شبکه های پردازش ابری مبتنی بر الگوریتم ازدحام ذرات - PSO - می باشد.یکی از این الگوریتم ها که مبتنی برافزایش قابلیت اطمینان است،موجب کاهش هم زمان هزینه استفاده از منابع و makespan می باشد.[2]در این الگوریتم از یک فضای جستجوی منفصل که مناسب فضای شبکه های پردازش ابری،در جهت اجرای یک جریان کاری است، استفاده شده است.منابع محاسباتی وپردازشی در این الگوریتم به عنوان ذرات درفضای جستجو هستند.انتخاب منابع وتخصیص انها به گره های یک جریان کار بر اساس بهترین پیکره بندی ذرات به سمت بهترین موقعیت و بهترین سرعت ذره می باشند.این الگوریتم از کیفیت های سرویس متفاوتی می تواند بهره مند شود.ومتناسب با نیاز کاربر خود را تطبیق پذیر نماید.
: 2-3 زمان بندی جریان کار با استفاده ازتبرید شبیه سازی شده
تبرید شبیه سازی شده یا simulated annealing یک روش جستجوی تصادفی برای مساله بهینه سازی سراسری می باشد.که قادر به یافتن بهینه محلی نیز می باشد.بطور طبیعی مشتریان شبکه ابری مایل به کاهش زمان اجرا وهزینه task های خود هستند.
دریکی ازکارهای انجام شده [3] ازاین روش،با توجه به محدودیت های زمانی اجرای task ها جهت کاهش هزینه زمان بندی کارها وتعادل بار روی منابع استفاده شده است.دراین روش پیشنهادی هزینه وزمان اجرای task و هزینه ارتباطات ،یعنی ارسال اطلاعات یک گره به گره های فرزند کاهش می یابد.دراین روش درابتدا فضای جستجو و تابع هدف مقداردهی اولیه می شوند.ارزش تابع هدف ،مجموع زمان-هزینه می باشد..سپس دما وپارامترهای اولیه تنظیم می شوند.تعداد تکرارهای درهر زمان، داده شده وتابع شکست دما درهرزمان مشخص می شود.وقتی که دما به میزان Tk برسد،تابع هدف می تواند محاسبه شود.درهرپروسس تکراری ،میتوان تصمیم گرفت که ان دما بهینه سراسری هست یا خیر؟ اگر این پاسخ درمساله ارضا نشود ،گام به مرحله بعدی گذاشته می شود.دراین روش احتمال انتخاب محاسبه می شود ویک عدد تصادفی ایجاد می شود.واین عدد با p مقایسه می شود.اگر k<p باشد پاسخ فعلی یک پاسخ بهینه می باشد.دما بوسیله تابع فروپاشی خنک می شود واین کاربارها انجام می شود.اگر الگوریتم به تعداد دفعات تکرار مجاز خود رسیده باشد،متوقف می شود.
:2-4 زمان بندی جریان کاربا استفاده از الگوریتم بهینه سازی کلونی مورچه
درالگوریتم بهینه سازی کلونی مورچه - - ACO از ایده فرومون ریزی مورچه ها هنگام یافتن غذا و بازگشت به لانه انجام می شود.مسیرهای بهتر، از فرومون های بیشتری توسط مورچگان پر می شوند.اگر منابع موجود در شبکه را غذا و هزینه دریافت آن منابع را با فرومون تطبیق دهیم، می توان انتخاب های درستی از منابع داشت.دریکی از کارهای انجام شده [4] درصورتی که زمان انقضاء انجام بخشی از یک جریان کار ،درابر خصوصی محقق نشود،آن بخش به ابرعمومی مهاجرت داده می شود.زمان بند در ابر عمومی با استفاده از تابع فرومونی و درنظرگرفتن زمان انقضای task ،منابعی که بتواند نیاز آن جریان کار را برآرده سازد را در اختیار قرار می دهد.این کار با حداقل هزینه ممکن و انتخاب بهترین منابع که سودمندی مناسبی ارایه نمایند،انجام می شود.
همچنین در کاری دیگر[5] از الگوریتم بهینه سازی کلونی مورچه ساده برای پیداکردن منابع محاسباتی استفاده شده است.دراین روش مورچه ها به دو دسته پیش رو و عقب رو تقسیم می شوند.مورچه های پیشرو برای پیداکردن ماشین های مجازی مورد استفاده قرار می گیرند.مورچه های عقب رو این منابع را دراختیار گراف قرار می دهند.سپس کاردسته ای به گره اصلی ارسال می شوند.تااولین کار انجام شود.این گره اصلی یک زمان سنج را فعال می کند.ومورچه های پیش رو را ارسال می کند تا هرکدام به یک گره ارسال شود.
: 2-5 زمان بندی گراف چندگانه سلسله مرتبی
برای اجرای workload با هر الگوی ورودی ،زمان بندی دینامیکی به عنوان یک روش موثر تعریف می شود.دریکی از پژوهش های انجام شده [6] الگوریتمهای متعددی بر این اساس طراحی شدند.درفاز انتخاب یک task آماده ،براساس یکی از روش های زودترین زمان انقضاء، - - EDFیا اول بیشترین ارتفاع ، - - HLF ، یا کمترین فضای زمانی - LSTF - صورت می گیرد.همچنین برای انتخاب منابع ،ازروش های اولین - - FF،بهترین - - BF و بدترین انتخاب - WF - استفاده می شود.ازمایشات نشان می دهند که ترکیب EDF و BF سایر هیوریستیک ها را پشت سر قرار می دهد.درپژوهشی دیگر[7] از ایده خوشه بندی برای بهبود زمان بندی گراف چند گانه سلسله مراتبی استفاده شده است. task های واقع در ، workflow جهت تخصیص به گروههایی تقسیم می شوند.این کار موجب کاهش هزینه های ارتباطی می شود.
