بخشی از مقاله
زمانبندي در گريدهاي محاسباتي
فهرست مطالب
عنوان صفحه
چکیده................................... 5
مقدمه.................................. 8
طبقه بندي زمانبندها¬ي پيشين............. 11
مروري بر زمانبندهاي سيستم هاي.......... 18
توزيع شده وگريد
فهرست شکلها
عنوان صفحه
مراحل كلي اجراي يك كار داده.............. 12
موازي در يك سيستم گريد
طبقه بندي زمانبندهاي گريد................ 17
توابع هدف................................ 17
چکیده
زمانبندي در گريدهاي محاسباتي مهمترين نقش را در بهبود كارايي ايفا مي كند. زمانبندي ضعيف باعث افزايش زمان اجراي كار و در نتيجه كاهش گذردهي گريد مي شود. سيستم گريد صدها يا هزاران كار را به طور همزمان اجرا مي كند و در نتيجه تصميم گيري ضعيف در مورد مكان اجراي كار مي تواند به طور چشمگيري باعث كاهش كارآيي شود. اما زمانبندي موثر يا به عبارت ديگر تصميم گيري خوب در مورد مكان اجراي كار يك مساله بسيار دشوار و NP – Complete است كه با چالش هاي مختلفي روبروست. يكي از اين چالشها ارتباطات بين وظايف يا زير كارهاي موجود در يك كار است. علاوه بر آن محيط گريد يك محيط بسيار پوياست كه تعداد منابع، در دسترس بودن آنها، بار پردازنده و فضاي ديسك در طول زمان مداوم در حال تغييرند. از طرف ديگر كارهاي ويژگي هاي متفاوتي دارند كه اين امر زمانبندي هاي متفاوتي را طلب مي كند. به عنوان مثال بعضي از كارها نيازمند توان پردازشي بالا و بعضي نيازمند توان ارتباطي بالا بين وظايف خود هستند. در نهايت
يكي از مهمترين ويژگي هاي زمانبندي گريد كه آن را از ديگر زمانبندي ها(مانند زمانبندي كلاستر) متمايز مي كند، قابليت مقياس پذيري آن است. زمانبندي كه
بسيار ساده اي(مانند زمانبندي تصادفي، چرخشي تكراري و ...) استفاده مي كنند و زمان ارتباطات بين وظايف يك كار و همچنين زمان ارسال يك كار از يك نقطه گريد به نقطه ديگر را ناديده مي گيرند. علاوه برآن با توجه به اين كه غالب زمانبندها عمل زمانبندي را در يك سطح انجام مي دهند و با عناصر پردازنده و وظيفه سروكار دارند، معمولاً قابليت مقياس پذيري خوبي ندارند.
در اين تحقيق به منظور مقياس پذير بودن، مساله زمانبندي در دو سطح بررسي شده است. در سطح بالا كه همان زمان بندي در سطح گريد است، زمانبند با عناصر كلاستر يا سايت و كار سروكار دارد. در حقيقت گريد مجموعه اي از سايت ها در نظر گرفته شده كه هر يك نماينده يك سازمان يا فرد است . از يك تا چند صد ماشين دارد. تاكيد اصلي تحقيق نيز بر روي همين زمانبند سطح بالا است كه به آن گلوبال يا سراسري نيز گفته مي شود و وظيفه آن اختصاص كل يك كار(با تمام وظايف موجود در آن) به يك كلاستر است. سپس زمانبند سطح پايين (زمانبند سطح كلاستر) وظايف موجود در كار را بر روي نودهاي موجود در كلاستر زمانبندي و اجرا مي كند. پيشتر، زمانبندي هاي سطح كلاستر خوبي طراحي و پياده سازي شده است.
زمانبند گلوبال پيشنهادي با درنظر گرفتن از يك طرف نيازهاي ارتباطي بين وظايف يك كار، زمان مورد نياز براي انتقال يك كار از يك نقطه گريد به نقطه ديگر و علاوه برآن نياز پردازشي و محاسباتي كار و از طرف
ديگر اطلاعات راجع به بار كلاسترها(سايت ها)، ميزان ترافيك موجود در شبكه هر كلاستر و گريد، سعي در تصميم گيريهاي موثر دارد. به منظور برخورد كيفي با اين پارامترهاي مختلف از منطق فازي استفاده شده است تا تطابق بين نيازهاي كار و ورودي و ويژگي هاي فعلي هر كلاستر تعيين شود و در نهايت كار به كلاستر با بالاترين تطابق ارسال شود.
1 مقدمه
محاسبات مدرن روز به روز با بهبود توان محاسباتي ، قابليت ذخيره سازي و ارتباطات روبه رو مي شود.عليرغم اين توسعه ها شرايط بسيار زيادي وجود دارد كه منابع محاسباتي نياز ما را برآورده نمي كنند.اين امر هم در محيط هاي علمي و هم اقتصادي اتفاق مي افتد و دلايل خاص خود را دارد. به عنوان مثال ده سال پيش، زيست شناس ها مايل به محاسبه ساختار تك مولكول بودند اما امروزه آنها مي خواهند ساختار تركيبات پيچيده اي از مولكول را محاسبه كنند. بسياري از پروژه هاي علمي صدها مگابايت داده را در ظرف يك ثانيه توليد كرده و نيازمند بررسي و پردازش سريع آن ها هستند. راه حل اين مشكلات در مقوله ي جديدي به نام محاسبات گريدي نهفته است كه براي اولين بار در سال 1969 توسط Leonard Kleinrock به صورت زير توصيف شد. احتمالاً به زوری شاهد گسترش تسهیلات کامپیوتری خواهیم بود که همانند تسهیلات برق و تلفن امروزی خانه ها و ادارات را سرویس خواهد داد.
در سالیان منتهی به سال 2000 میلادی تحقیقات در حوزه محاسبات گریدی منجر به توسعه گرید توان محاسباتی شد که زیر ساختی برای محاسبات عظیم توزیع شده و موازی است. زیر ساخت گرید امکان ا شتراک و انتخاب منابعی که از نظر جغرافیایی در مکان های مختلف قرار دارند
و متعلق به سازمان های متفاوت هستند را فراهم می کند. این منابع شامل ایستگاه های کاری ، کلاسترها، سیستم های ذخیره سازی، دستگاه های خاص و غیره است.اشتراک منبع سودمند است زیرا اجازه استفاده از توان چندین منبع را می دهد. مثلاً به جاری اجرای یک برنامه محاسباتی عظیم بر روی سخت افزار خاص (مانند یک ابر کامپیوتر) می توان آن را به صورت موازی بر روی کامپیوترهای موجود در یک کلاستر که بسیار ارزان تر هستند اجرا کرد.
يک سيستم گريد محاسباتي برنامه هايي را بر روي منابع موجود در زير ساخت گريد اجرا مي کند تا يک سيستم واحد از منابع متعامل را تشکيل دهد. اين برنامه ها عمل تعامل بين منابع را آسان مي کنند. به مجموعه برنامه هايي که تعامل بين منابع را مديريت مي کنند، ميان افزار سيستم گريد گفته مي شود زيرا يک لايه نرم افزاري بالاي سيستم عامل است که عمل تعامل بين منابع موجود در گريد را کنترل مي کند. کاربر سيستم گريد مي تواند برنامه هاي کاربردي خود را بر روي منابع متنوعي از گريد اجرا کند. او اين کار را با اجراي برنامه کاربردي در بالاي لايه ميان افزاري انجام مي دهد. يک سيستم گريد مي تواند تعداد زيادي از اين برنامه هاي کاربردي ر
ا به طور همزمان اجرا کند. يک نوع ازبرنامه هاي کاربردي که معمولاً در سيستم گريد اجرا مي شوند، ساختارهاي تک برنامه چند داده (SPMD) هستند که به آنها
برنامه هاي داده-موازي نيز گفته مي شود. اين برنامه ها به چندين وظيفه تقسيم مي شوند که هر يک محاسبات را بر روي قسمت مجزايي از مجموعه داده انجام مي دهد. اين وظايف به همراه يکديگر کار مي کنند تا کل مجموعه داده را پردازش کنند و در مجموع به آنها يک کار گفته ميشود. از اين مدل برنامه معمولاً در حل مسايل محاسباتي علمي استفاده مي شود. اجراي اين کارها ممکن است چندين ساعت يا روز به طول بکشد و مي تواند مقدار زيادي از منابع سيستم را مصرف کند . اين کارها معمولاً مقدار زيادي محاسبات يا ارتباطات بين وظايف و يا هر دو را انجام مي دهند.
مطالعه فضاي پارامتر يک نوع کار است که به طور تکرار شونده حجم زيادي از محاسبات را بر روي بازه اي از پارامترهاي برنامه انجام مي دهد. مجموعه کل پارامترها را مي توان به عنوان کل مجموعه داده در نظر گرفت. هر تکرار برنامه را مي توان به طور موازي در سيستم گريد اجرا کرد و به اين طريق در مدتي بسيار کوتاهتر از زمان اجراي سريال برنامه، نتايج آن را مشاهده کرد.
يک سيستم گريد با کارايي بالا بايد تلاش کند تا گذردهي کار سيستم را ماکزيمم کرده و زمان اجراي کار را مينيمم کند. اين دو هدف گاهي در مقابل يکديگر قرار ميگيرند به عنوان مثال اگر دو کار، هر يک نيازمند P پردازنده باشند و گريد تنها بتواند 2P-1 پردازنده را فراهم کند، نمي توان کارايي بهينه را به طور همزمان براي هر دو کار بدست آورد. اگر هر دو کار به طور
همزمان اجرا شوند حداقل دو وظيفه بر روي يک پردازنده قرار مي گيرد که باعث مي شود زمان اجراي هر دو کار افزايش يابد. اما اجراي سريال دو کار گذردهي کار سيستم را پايين مي آورد.
سيستم مديريت منابع گريد استفاده از منابع را کنترل مي کند تا به هدف سيستم گريد با کارآيي بالا دست يابد. زمانبند يکي از اجزاي سيستم مديريت منابع گريد است که از اطلاعات سيستم گريد و کار استفاده مي کند تا يک انتساب از وظايف کار ورودي به ماشين ها ايجاد کند. به اين عمل انتساب، زمانبندي گفته مي شود. تصميم گيرهاي زمانبندي مؤثر معمولا تلاش در مينيمم كردن زمان اجراي كار دارند . سيستم مديريت منابع گريد تلاش دارد تا زمانبندي هاي مؤثري انجام دهد زيرا زمانبندي ضعيف باعث افزايش زمان اجراي كار مي شود و در نتيجه گذردهي كار را كاهش مي دهد. با اين وجود توليد زمانبندي مؤثر و خوب براي كارهاي گريد يك مساله بسيار دشوار است كه پيچيدگي هاي خاص خود را دارا ست.
2- طبقه بندي زمانبندها¬ي پيشين
در اين قسمت مي خواهيم يك طبقه بندي از تكنيك هاي زمانبندي ارائه دهيم . در يك طبقه بندي از زمانبندي در سيستم هاي توزيع شده ارائه گرديده كه بسياري از تعاريف را از آن گرفته ايم. به طور كلي مساله زمانبندي به روشهاي مختلفي در سيستم هاي عامل سنتي و سيستم هاي توزيع شده تعريف گرديده است . در حالت كلي اجراي يك كار داده موازي در يك سيستم گريد شامل چهار مرحله زير است (شكل1)
- پارتيشن بندي كار
- جمع آوري اطلاعات
- انتساب وظايف به نودها
- آغاز اجراي وظايف
شکل 1- مراحل كلي اجراي يك كار داده موازي در يك سيستم گريد
پارتيشن بندي كار عبارت است از تقسيم يك كار به وظايف آن . به طور كلي كارهاي موازي را مي توان به دو گروه تقسيم كرد :1. انعطاف ناپذير 2. قالب پذير .
كارهاي انعطاف ناپذير بر روي تعداد مشخصي از پردازنده ها كه معمولا توسط كاربر مشخص مي شود، اجرا مي شوند اما كارهاي قالب پذير را مي توان بر روي تعداد متفاوتي از منابع محاسباتي اجرا كرد. در سيستم هاي گريد ممكن است كاربران بخواهند تعداد پردازنده هايي كه كار بايد روي آن اجرا شود را مشخص كنند، به خصوص وقتي خود كاربر برنامه را نوشته باشد . به طور
جايگزين از ابزارهاي پارتيشن بندي خاصي نيز مي توان به منظور توليد وظايف استفاده كرد.
جمع آوري اطلاعات همان فرايند جمع آوري اطلاعات برنامه كاربردي و منابع است. از اين اطلاعات مي توان براي ساختن يك مدل ساده از برنامه كاربردي و گريد استفاده كرد. سپس در مرحله انتساب وظيفه، الگوريتم زمانبندي از مدل هاي موجود براي تخمين كارايي وظيفه و توليد انتساب وظيفه به صورت كارا استفاده مي كند . الگوريتم زمانبندي ممكن است از اطلاعات جمع آوري شده به منظور توليد انتساب كاراتر استفاده كند . سپس وظايف بر روي منابع گريد انتساب يافته و شروع به اجرا مي كنند .
از نظر زمان انجام فرايند زمانبندي مي توان ، استراتژي هاي زمانبندي را به انواع زيرتقسيم كرد . زمانبندي زمان كامپايل هنگام كامپايل برنامه كاربردي آن را زمانبندي نيز مي كند و طبيعتا از اطلاعات پوياي سيستم نمي تواند استفاده كند . از اين رو اين استراتژي مناسب براي محيط گريد كه وضعيت آن مدام در حال تغيير است، نمي باشد . به عنوان نمونه اين زمانبندي ها ممكن است وظايف را بر روي منابع غير قابل دسترس قرار دهند . زيرا اطلاعات راجع به در دسترس بودن منبع را نمي توان بيش از زمان اجرا به طور قطعي دانست .
زمانبندي زمان اجرا مي تواند اطلاعات پوياي سيستم را در تصميم گيري زمانبندي شامل كند . اين زمانبندها ، به دو صورت پويا وايستا مي توانند عمل كنند . يك زمانبند زمان اجراي پويا يك انتساب اوليه از وظايف به
ماشين ها ايجاد كرده ، اما ممكن است اين انتساب را در پاسخ به تغييرات كارايي سيستم عوض كند . اين زمانبند مقداري باركاري را در زمان اجرا تحميل مي كند زيرا بايد گريد را حين اجراي كار مونيتور كند .
يك زمانبند زمان اجراي ايستا وظايف را هنگام آغاز اجراي برنامه به منابع مي فرستد و پس از اينكه اجراي وظايف شروع شد آنها را به ماشين هاي ديگر ارسال نمي كند . با وجوديكه زمانبندهاي ايستا متحمل سربار زمان اجراي زمانبندهاي پويا نمي شوند ، اما هنوز نيازمند حجم زيادي از اطلاعات در مورد برنامه و سيستم هستند تا بتوانند يك تصميم اوليه خوبي بگيرند .
زمانبندهاي زمان اجراي ايستا معمولا به دنبال يك راه حل زير بهينه هستند زيرا يافتن راه حل بهينه براي بيش از سه منبع در زمان معقول غير ممكن است. راه حل هاي زمانبندي زير بهينه معمولا از طريق ماكزيمم كردن يك تابع سعي در ايجاد راه حل نزديك به بهينه دارند. در زمانبندهاي زير بهينه به دو نوع تخميني و اكتشافي تقسيم شده اند. يك الگوريتم تخميني زير مجموعه اي از فضاي راه حل را به منظور يافتن يك زمانبندي كه معيارهاي هزينه را برآورده كند، جستجو مي كند . يك الگوريتم اكتشافي از يك الگوريتم غير بهينه به منظور انجام زمانبنديهاي معقول استفاده مي كند . در از الگوريتم ژنتيك و در از الگوريتمهاي شبيه سازي به منظور زمانبندي اكتشافي استفاده شده است .
غالب زمانبندهاي اکتشافي زمان اجراي ايستا نيازمند حجم زيادي از اطلاعات در مورد برنامه و منبع
هستند تا يك زمانبندي نزديك به بهينه را توليد كنند. زمانبندي هاي اكتشافي قطعي پيش از اجراي برنامه نيازمند اطلاعات دقيق درباره برنامه كاربردي و منابع سيستم هستند . به طور نمونه يك برنامه كاربردي اطلاعاتي در باره زمان اجراي وظيفه بر روي يك پردازنده خاص ، توپولوژي ارتباطات و همچنين مقدار ارتباطاتي كه براي هر وظيفه انتظار مي رود ، تامين مي كند . متاسفانه برخي از برنامه هاي كاربردي ممكن است رفتار غير قطعي از خود بروز دهند و اطلاعات
راجع به رفتار برنامه ممكن است كاملا قابل پيش بيني نباشد. علاوه بر آن سيستمي که بين تعداد زيادي كاربر به اشتراك گذاشته شده است حتما رفتار غير قطعي از خود بروز خواهد داد . زماني كه رفتار برنامه كاربردي يا سيستم قطعي نيست ، يك زمانبند غير قطعي بايد بدون كمك اطلاعات دقيق در مورد برنامه كاربردي و منابع ، تصميم گيري كند .
در اين تحقيق يك زمانبند زمان اجراي ايستا در يك محيط غير قطعي پيشنهاد داده شده. اين زمانبند از اطلاعات سيستم در زمان اجرا براي تصميم گيري استفاده مي كند . بعلاوه زمانبند پيشنهادي نيازمند اطلاعات قطعي برنامه و سيستم نيست، زيرا اين اطلاعات همواره ممكن است موجود نباشد. از يك الگوريتم انتساب وظيفه اكتشافي زير بهينه به منظور زمانبندي تعداد بسياري از برنامه هاي كاربردي در يك زمان منطقي استفاده شده است . شكل 2 جايگاه اين زمانبند را در طبقه بندي ارائه شده نشان مي دهد.
2-1- توابع هدف
دو گروه عمده در محاسبات گريدي يعني مصرف کننده هاي منابع که برنامه هاي کاربردي را به گريد ارسال مي کنند و تامين کننده هاي منابع که منابع خود را به اشتراک مي گذارند، معمولا انگيزه هاي متفاوتي از ملحق شدن به گريد دارند . کاربران گريد معمولا نگران کارايي برنامه کاربردي خود مثلا زمان اتمام برنامه و هزينه پرداختي براي اجراي آن هستند، اما تامين کننده هاي منابع توجه بيشتري به کارايي و بهره وري منابع خود و در محيط هاي اقتصادي ، بالا بردن سود خود دارند.
اين واقعيت ها باعث مي شود که زمانبند هاي موجود از نظر تابع هدف به دو دسته تقسيم شوند: متمايل به برنامه کاربردي و متمايل به منبع. شکل 3 توابع هدف را براي زمانبند هاي ياد شده نشان مي دهد.
شکل 2 طبقه بندي زمانبندهاي گريد. خطوط تيره جايگاه زمانبند پيشنهادي را نشان مي دهند.
