دانلود مقاله زمانبندی در گرید های محاسباتی

چکیده زمانبندی در گریدهای محاسباتی مهمترین نقش را در بهبود کارایی ایفا می کند.

زمانبندی ضعیف باعث افزایش زمان اجرای کار و در نتیجه کاهش گذردهی گرید می شود.

سیستم گرید صدها یا هزاران کار را به طور همزمان اجرا می کند و در نتیجه تصمیم گیری ضعیف در مورد مکان اجرای کار می تواند به طور چشمگیری باعث کاهش کارآیی شود.

اما زمانبندی موثر یا به عبارت دیگر تصمیم گیری خوب در مورد مکان اجرای کار یک مساله بسیار دشوار و NP – Complete است که با چالش های مختلفی روبروست.

یکی از این چالشها ارتباطات بین وظایف یا زیر کارهای موجود در یک کار است.

علاوه بر آن محیط گرید یک محیط بسیار پویاست که تعداد منابع، در دسترس بودن آنها، بار پردازنده و فضای دیسک در طول زمان مداوم در حال تغییرند.

از طرف دیگر کارهای ویژگی های متفاوتی دارند که این امر زمانبندی های متفاوتی را طلب می کند.

به عنوان مثال بعضی از کارها نیازمند توان پردازشی بالا و بعضی نیازمند توان ارتباطی بالا بین وظایف خود هستند.

در نهایت یکی از مهمترین ویژگی های زمانبندی گرید که آن را از دیگر زمانبندی ها(مانند زمانبندی کلاستر) متمایز می کند، قابلیت مقیاس پذیری آن است.

زمانبندی که بسیار ساده ای(مانند زمانبندی تصادفی، چرخشی تکراری و ...) استفاده می کنند و زمان ارتباطات بین وظایف یک کار و همچنین زمان ارسال یک کار از یک نقطه گرید به نقطه دیگر را نادیده می گیرند.

علاوه برآن با توجه به این که غالب زمانبندها عمل زمانبندی را در یک سطح انجام می دهند و با عناصر پردازنده و وظیفه سروکار دارند، معمولاً قابلیت مقیاس پذیری خوبی ندارند.

در این تحقیق به منظور مقیاس پذیر بودن، مساله زمانبندی در دو سطح بررسی شده است.

در سطح بالا که همان زمان بندی در سطح گرید است، زمانبند با عناصر کلاستر یا سایت و کار سروکار دارد.

در حقیقت گرید مجموعه ای از سایت ها در نظر گرفته شده که هر یک نماینده یک سازمان یا فرد است .

از یک تا چند صد ماشین دارد.

تاکید اصلی تحقیق نیز بر روی همین زمانبند سطح بالا است که به آن گلوبال یا سراسری نیز گفته می شود و وظیفه آن اختصاص کل یک کار(با تمام وظایف موجود در آن) به یک کلاستر است.

سپس زمانبند سطح پایین (زمانبند سطح کلاستر) وظایف موجود در کار را بر روی نودهای موجود در کلاستر زمانبندی و اجرا می کند.

پیشتر، زمانبندی های سطح کلاستر خوبی طراحی و پیاده سازی شده است.

زمانبند گلوبال پیشنهادی با درنظر گرفتن از یک طرف نیازهای ارتباطی بین وظایف یک کار، زمان مورد نیاز برای انتقال یک کار از یک نقطه گرید به نقطه دیگر و علاوه برآن نیاز پردازشی و محاسباتی کار و از طرف دیگر اطلاعات راجع به بار کلاستر ها(سایت ها)، میزان ترافیک موجود در شبکه هر کلاستر و گرید، سعی در تصمیم گیریهای موثر دارد.

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

1 مقدمه محاسبات مدرن روز به روز با بهبود توان محاسباتی ، قابلیت ذخیره سازی و ارتباطات روبه رو می شود.علیرغم این توسعه ها شرایط بسیار زیادی وجود دارد که منابع محاسباتی نیاز ما را برآورده نمی کنند.این امر هم در محیط های علمی و هم اقتصادی اتفاق می افتد و دلایل خاص خود را دارد.

به عنوان مثال ده سال پیش، زیست شناس ها مایل به محاسبه ساختار تک مولکول بودند اما امروزه آنها می خواهند ساختار ترکیبات پیچیده ای از مولکول را محاسبه کنند.

بسیاری از پروژه های علمی صدها مگابایت داده را در ظرف یک ثانیه تولید کرده و نیازمند بررسی و پردازش سریع آن ها هستند.

راه حل این مشکلات در مقوله ی جدیدی به نام محاسبات گریدی نهفته است که برای اولین بار در سال 1969 توسط Leonard Kleinrock به صورت زیر توصیف شد.

احتمالاً به زوری شاهد گسترش تسهیلات کامپیوتری خواهیم بود که همانند تسهیلات برق و تلفن امروزی خانه ها و ادارات را سرویس خواهد داد.

در سالیان منتهی به سال 2000 میلادی تحقیقات در حوزه محاسبات گریدی منجر به توسعه گرید توان محاسباتی شد که زیر ساختی برای محاسبات عظیم توزیع شده و موازی است.

زیر ساخت گرید امکان ا شتراک و انتخاب منابعی که از نظر جغرافیایی در مکان های مختلف قرار دارند و متعلق به سازمان های متفاوت هستند را فراهم می کند.

این منابع شامل ایستگاه های کاری ، کلاسترها، سیستم های ذخیره سازی، دستگاه های خاص و غیره است.اشتراک منبع سودمند است زیرا اجازه استفاده از توان چندین منبع را می دهد.

مثلاً به جاری اجرای یک برنامه محاسباتی عظیم بر روی سخت افزار خاص (مانند یک ابر کامپیوتر) می توان آن را به صورت موازی بر روی کامپیوترهای موجود در یک کلاستر که بسیار ارزان تر هستند اجرا کرد.

یک سیستم گرید محاسباتی برنامه هایی را بر روی منابع موجود در زیر ساخت گرید اجرا می کند تا یک سیستم واحد از منابع متعامل را تشکیل دهد.

این برنامه ها عمل تعامل بین منابع را آسان می کنند.

به مجموعه برنامه هایی که تعامل بین منابع را مدیریت می کنند، میان افزار سیستم گرید گفته می شود زیرا یک لایه نرم افزاری بالای سیستم عامل است که عمل تعامل بین منابع موجود در گرید را کنترل می کند.

کاربر سیستم گرید می تواند برنامه های کاربردی خود را بر روی منابع متنوعی از گرید اجرا کند.

او این کار را با اجرای برنامه کاربردی در بالای لایه میان افزاری انجام می دهد.

یک سیستم گرید می تواند تعداد زیادی از این برنامه های کاربردی را به طور همزمان اجرا کند.

یک نوع ازبرنامه های کاربردی که معمولاً در سیستم گرید اجرا می شوند، ساختارهای تک برنامه چند داده (SPMD) هستند که به آنها برنامه های داده-موازی[1] نیز گفته می شود.

این برنامه ها به چندین وظیفه [2] تقسیم می شوند که هر یک محاسبات را بر روی قسمت مجزایی از مجموعه داده انجام می دهد.

این وظایف به همراه یکدیگر کار می کنند تا کل مجموعه داده را پردازش کنند و در مجموع به آنها یک کار[3] گفته میشود.

از این مدل برنامه معمولاً در حل مسایل محاسباتی علمی استفاده می شود.

اجرای این کارها ممکن است چندین ساعت یا روز به طول بکشد و می تواند مقدار زیادی از منابع سیستم را مصرف کند .

این کارها معمولاً مقدار زیادی محاسبات یا ارتباطات بین وظایف و یا هر دو را انجام می دهند.

مطالعه فضای پارامتر[4] یک نوع کار است که به طور تکرار شونده حجم زیادی از محاسبات را بر روی بازه ای از پارامترهای برنامه انجام می دهد.

مجموعه کل پارامترها را می توان به عنوان کل مجموعه داده در نظر گرفت.

هر تکرار برنامه را می توان به طور موازی در سیستم گرید اجرا کرد و به این طریق در مدتی بسیار کوتاهتر از زمان اجرای سریال برنامه، نتایج آن را مشاهده کرد.

یک سیستم گرید با کارایی بالا باید تلاش کند تا گذردهی کار سیستم را ماکزیمم کرده و زمان اجرای کار را مینیمم کند.

این دو هدف گاهی در مقابل یکدیگر قرار میگیرند به عنوان مثال اگر دو کار، هر یک نیازمند P پردازنده باشند و گرید تنها بتواند 2P-1 پردازنده را فراهم کند، نمی توان کارایی بهینه را به طور همزمان برای هر دو کار بدست آورد.

اگر هر دو کار به طور همزمان اجرا شوند حداقل دو وظیفه بر روی یک پردازنده قرار می گیرد که باعث می شود زمان اجرای هر دو کار افزایش یابد.

اما اجرای سریال دو کار گذردهی کار سیستم را پایین می آورد.

سیستم مدیریت منابع گرید استفاده از منابع را کنترل می کند تا به هدف سیستم گرید با کارآیی بالا دست یابد.

زمانبند یکی از اجزای سیستم مدیریت منابع گرید است که از اطلاعات سیستم گرید و کار استفاده می کند تا یک انتساب از وظایف کار ورودی به ماشین ها ایجاد کند.

به این عمل انتساب، زمانبندی گفته می شود.

تصمیم گیرهای زمانبندی مؤثر معمولا تلاش در مینیمم کردن زمان اجرای کار دارند .

سیستم مدیریت منابع گرید تلاش دارد تا زمانبندی های مؤثری انجام دهد زیرا زمانبندی ضعیف باعث افزایش زمان اجرای کار می شود و در نتیجه گذردهی کار را کاهش می دهد.

با این وجود تولید زمانبندی مؤثر و خوب برای کارهای گرید یک مساله بسیار دشوار است که پیچیدگی های خاص خود را دارا ست.

2- طبقه بندی زمانبندها­ی پیشین در این قسمت می خواهیم یک طبقه بندی از تکنیک های زمانبندی ارائه دهیم .

در یک طبقه بندی از زمانبندی در سیستم های توزیع شده ارائه گردیده که بسیاری از تعاریف را از آن گرفته ایم.

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

در حالت کلی اجرای یک کار داده موازی در یک سیستم گرید شامل چهار مرحله زیر است (شکل1) پارتیشن بندی کار جمع آوری اطلاعات انتساب وظایف به نودها آغاز اجرای وظایف آغاز اجرای وظایف شکل 1- مراحل کلی اجرای یک کار داده موازی در یک سیستم گرید پارتیشن بندی کار عبارت است از تقسیم یک کار به وظایف آن .

به طور کلی کارهای موازی را می توان به دو گروه تقسیم کرد :1.

انعطاف ناپذیر 2.

قالب پذیر.

کارهای انعطاف ناپذیر بر روی تعداد مشخصی از پردازنده ها که معمولا توسط کاربر مشخص می شود، اجرا می شوند اما کارهای قالب پذیر را می توان بر روی تعداد متفاوتی از منابع محاسباتی اجرا کرد.

در سیستم های گرید ممکن است کاربران بخواهند تعداد پردازنده هایی که کار باید روی آن اجرا شود را مشخص کنند، به خصوص وقتی خود کاربر برنامه را نوشته باشد .

به طور جایگزین از ابزارهای پارتیشن بندی خاصی نیز می توان به منظور تولید وظایف استفاده کرد.

جمع آوری اطلاعات همان فرایند جمع آوری اطلاعات برنامه کاربردی و منابع است.

از این اطلاعات می توان برای ساختن یک مدل ساده از برنامه کاربردی و گرید استفاده کرد.

سپس در مرحله انتساب وظیفه، الگوریتم زمانبندی از مدل های موجود برای تخمین کارایی وظیفه و تولید انتساب وظیفه به صورت کارا استفاده می کند .

الگوریتم زمانبندی ممکن است از اطلاعات جمع آوری شده به منظور تولید انتساب کاراتر استفاده کند .

سپس وظایف بر روی منابع گرید انتساب یافته و شروع به اجرا می کنند .

از نظر زمان انجام فرایند زمانبندی می توان ، استراتژی های زمانبندی را به انواع زیرتقسیم کرد .

زمانبندی زمان کامپایل هنگام کامپایل برنامه کاربردی آن را زمانبندی نیز می کند و طبیعتا از اطلاعات پویای سیستم نمی تواند استفاده کند .

از این رو این استراتژی مناسب برای محیط گرید که وضعیت آن مدام در حال تغییر است، نمی باشد .

به عنوان نمونه این زمانبندی ها ممکن است وظایف را بر روی منابع غیر قابل دسترس قرار دهند .

زیرا اطلاعات راجع به در دسترس بودن منبع را نمی توان بیش از زمان اجرا به طور قطعی دانست .

زمانبندی زمان اجرا می تواند اطلاعات پویای سیستم را در تصمیم گیری زمانبندی شامل کند .

این زمانبندها ، به دو صورت پویا وایستا می توانند عمل کنند .

یک زمانبند زمان اجرای پویا یک انتساب اولیه از وظایف به ماشین ها ایجاد کرده ، اما ممکن است این انتساب را در پاسخ به تغییرات کارایی سیستم عوض کند .

این زمانبند مقداری بارکاری را در زمان اجرا تحمیل می کند زیرا باید گرید را حین اجرای کار مونیتور کند .

یک زمانبند زمان اجرای ایستا وظایف را هنگام آغاز اجرای برنامه به منابع می فرستد و پس از اینکه اجرای وظایف شروع شد آنها را به ماشین های دیگر ارسال نمی کند .

با وجودیکه زمانبندهای ایستا متحمل سربار زمان اجرای زمانبندهای پویا نمی شوند ، اما هنوز نیازمند حجم زیادی از اطلاعات در مورد برنامه و سیستم هستند تا بتوانند یک تصمیم اولیه خوبی بگیرند .

زمانبندهای زمان اجرای ایستا معمولا به دنبال یک راه حل زیر بهینه هستند زیرا یافتن راه حل بهینه برای بیش از سه منبع در زمان معقول غیر ممکن است.

راه حل های زمانبندی زیر بهینه معمولا از طریق ماکزیمم کردن یک تابع سعی در ایجاد راه حل نزدیک به بهینه دارند.

در زمانبندهای زیر بهینه به دو نوع تخمینی و اکتشافی تقسیم شده اند.

یک الگوریتم تخمینی زیر مجموعه ای از فضای راه حل را به منظور یافتن یک زمانبندی که معیارهای هزینه را برآورده کند، جستجو می کند .

یک الگوریتم اکتشافی از یک الگوریتم غیر بهینه به منظور انجام زمانبندیهای معقول استفاده می کند .

در از الگوریتم ژنتیک و در از الگوریتمهای شبیه سازی به منظور زمانبندی اکتشافی استفاده شده است .

غالب زمانبندهای اکتشافی زمان اجرای ایستا نیازمند حجم زیادی از اطلاعات در مورد برنامه و منبع هستند تا یک