دانشکده‌ي مهندسي برق و کامپيوتر
پايان‌نامه كارشناسي ارشد در رشتهي
مهندسي کامپيوتر (نرم‌افزار)
بررسي الگوريتم هاي تخصيص مجدد در گريدهاي محاسباتي و ارائه يک الگوريتم کارا
به کوشش:
سهيلا رئيسيان
استاد راهنما:
دکتر غلامحسين دستغيبي فرد
اسفند ماه 1392

ماحصل آموخته هايم را تقديم مي کنم به آنان که مهر آسماني شان آرام بخش آلام زميني ام است
به استوارترين تکيه گاهم، دستان پرمهر پدرم به سبزترين نگاه زندگيم، چشمان مهربان مادرم
که هرچه آموختم در مکتب عشق شما آموختم و هرچه بکوشم قطره اي از درياي بي کران مهربانيتان را سپاس نتوانم بگويم.
امروز هستي ام به اميد شماست و فردا کليد باغ بهشتم رضاي شما
ره آوردي گران سنگ تر از اين ارزان نداشتم تا به خاک پايتان نثار کنم، باشد که حاصل تلاشم نسيم گونه غبار، خستگيتان را بزدايد.
بوسه بر دستان پرمهرتان.
سپاسگزاري
از خداوند بزرگ سپاسگزارم که در تمام مراحل زندگي همواره همراهم بوده، در رسيدن به موفقيتهايم ياري رسانم بوده، در مشکلاتم قوت قلبم بوده و اکنون نيز ياري رسانم بوده تا به اين هدف خود برسم.
از استاد ارجمند و بزرگوارم جناب آقاي دکتر غلامحسين دستغيبيفرد که همواره در مدت اين پروژه مشوق و راهنمايم بوده کمال تشکر و قدرداني را دارم. براي ايشان آرزوي سلامتي و بهروزي دارم و اميدوارم در تمام مراحل زندگي به ياري خداوند بزرگ همينطور موفق و با نشاط باشند.
از استاد بزرگوار جناب آقاي دکتر فرشاد خونجوش که در اين مدت از راهنمايي ايشان نيز بهره بردم سپاسگزارم. از استاد فرزانه، جناب آقاي دکتر فخراحمد که زحمت داوري اين رساله را متقبل شدند؛ کمال تشکر و قدرداني را دارم. همچنين از ياري خانوادهام و دوستانم که همواره پشتيباني برايم بودهاند و باعث دلگرمي من بودهاند سپاسگزارم.
چکيده
بررسي الگوريتم هاي تخصيص مجدد در گريدهاي محاسباتي و ارائه يک الگوريتم کارا
به کوشش
سهيلا رئيسيان
شبکههاي تورين محاسباتي (گريد) زمينه‌اي را فراهم آورده است که بتوان از منابع ناهمگن در نقاط مختلف جغرافيايي براي حل مسائل پيچيده علمي، مهندسي و تجارت استفاده کرد. عمليات زمانبندي نقش کليدي در عملکرد گريد ايفا ميکند. بدليل پويايي منابع و تخمين نادقيق زمان اجرايي و … عمليات زمانبندي بايد مکانيسم هايي را براي پشتيباني از تحمل خطا، افزايش بهره وري از منابع و کاهش زمان اتمام کارها استفاده کند، که به آن زمانبندي مجدد گويند. در اين پايان نامه دو الگوريتم زمانبندي کارهاي مستقل و يک الگوريتم زمانبندي جريان کارها با در نظر گرفتن پويايي محيط ارائه شده که اهداف آنها کاهش زمان اجرا، افزايش بهرهوري از منابع، ايجاد توازن بار و پشتيباني از تحمل خطا مي باشد.
کليد واژه: گريد محاسباتي، زمانبندي، زمانبندي مجدد، جريان کار.
فهرست مطالب
عنوان صفحه
1- مقدمه 1
1-1 مقدمه 1
1-2 ضرورت اجرا 2
1-3 هدف از اجراي پاياننامه 3
1-4 مراحل انجام پاياننامه 4
1-5 ساختار پاياننامه 4
2- مفاهيم اوليه زمانبندي و مروري بر کارهاي گذشته5
2-1 مقدمه 5
2-2 ساختار متمرکز 7
2-3 ساختار غير متمرکز و يا توزيعي 8
2-4 فرايند زمانبندي گريد و اجزاي آن 10
2-5 انواع زمانبند 11
2-6 انواع کارها 12
2-7 نحوهي زمانبندي 14
2-8 وظايف فرازمانبند 14
2-8-1 نگاشت کار 15
2-9 گذري بر تحقيقات پيشين 17
2-9-1 مفاهيم اوليه 17
2-9-2 الگوريتم ETF 19
2-9-3 الگوريتم Myopic 19
2-9-4 الگوريتم کمترين کمترين، بيشترين کمترين، حق راي 19
2-9-5 الگوريتم HLEFT 20
2-9-6 الگوريتم hybrid 20
2-9-7 الگوريتم GRASP 21
2-9-8 الگوريتم CPOP 21
2-9-9 الگوريتم PETS 22
2-9-10 الگوريتم HLEFT با نگاه به جلو 23
2-9-11 الگوريتم FTBAR 23
2-9-12 الگوريتم TSB 24
2-10 جمع بندي 24
3- الگوريتمهاي پيشنهادي 25
3-1 مقدمه 25
3-2 الگوريتم Asuffrage 27
3-3 الگوريتم MaxSuffrage 28
3-4 الگوريتم DHLEFT30
4- نتايج حاصل از ارزيابي و مقايسه الگوريتم هاي پيشنهادي 34
4-1 مقدمه 34
4-2 محک ارزيابي براون34
4-3 ارزيابي الگوريتم Asuffrage36
4-4 ارزيابي الگوريتم MaxSuffrage38
4-5 ارزيابي زمانبند الگوريتم پيشنهادي براي جريان کار40
4-6 ارزيابي الگوريتم DHLEFT43
4-7 نتيجه گيري و پيشنهادات براي آينده 49
5- منابع50
فهرست جدولها
عنوان صفحه
جدول 4-1 حالات ماتريس ETC36
جدول 4-2 نتايج زمان اتمام آخرين کار الگوريتم Asuffrage37
جدول 4-3 نتايج درصد بهرهوري از منابع الگوريتم Asuffrage37
جدول 4-4 نتايج زمان اتمام آخرين کار الگوريتم MaxSuffrage39
جدول 4-5 نتايج درصد بهرهوري از منابع الگوريتم MaxSuffrage39
جدول 4-6 مقادير پارامتر N41
جدول 4-7 مقادير پارامتر Fat41
جدول 4-8 مقادير پارامتر Density41
جدول 4-9 درصد خطا در تخمين زمان اجرايي42
جدول 4-10 زمان رخداد رويداد43
جدول 4-11 ميانگين نتايج زمان اتمام آخرين کار الگوريتم DHLEFT48
جدول 4-12 ميانگين نتايج درصد بهرهوري از منابع الگوريتم DHLEFT48
فهرست شکلها
عنوان صفحه
شکل‏2-1 معماري زمانبندي متمرکز 7
شکل‏2-2 معماري زمانبندي سلسله مراتبي 9
شکل ‏2-3 معماري زمانبندي غيرمتمرکز 9
شکل ‏2-4 معماري زمانبندي گريد 10
شکل ‏2-5 جريان کار 13
شکل ‏2-6 نمونه ماتريس ETC 14
شکل ‏2-7 گراف جهت دار بدون دور(DAG) 18
شکل ‏2-8 جدول زمان اجرايي تخميني 18
شکل 3-1 شبه کد الگوريتم DHLEFT 33
شکل 4-1 نتايج زمان اتمام آخرين کار الگوريتم DHLEFT با Fat=0.144
شکل 4-2 نتايج زمان اتمام آخرين کار الگوريتم DHLEFT با Fat=0.345
شکل 4-3 نتايج زمان اتمام آخرين کار الگوريتم DHLEFT با Fat=0.545
شکل 4-4 نتايج زمان اتمام آخرين کار الگوريتم DHLEFT با Fat=0.746
شکل 4-5 نتايج درصد بهرهوري از منابع الگوريتم DHLEFT با Fat=0.146
شکل 4-6 نتايج درصد بهرهوري از منابع الگوريتم DHLEFT با Fat=0.347
شکل 4-7 نتايج درصد بهرهوري از منابع الگوريتم DHLEFT با Fat=0.547
شکل 4-8 نتايج درصد بهرهوري از منابع الگوريتم DHLEFT با Fat=0.748

فصل اول
1- مقدمه
1-1 مقدمه
اصطلاح “گريد” در اواسط دهه 1990 مطرح شده و زير ساخت محاسبات گريد (محاسبات شبکه) در زمينه علم و مهندسي پيشرفته پيشنهاد شد [1]. ايده اصلي محيط گريد به اشتراک گذاري منابع محاسباتي است. امروزه، اکثر مردم بيشتر از حد نياز، قدرت محاسباتي بر روي سيستمهاي کامپيوتري خود دارند. از اين رو کشف منابع محاسباتي توزيع شده در سطح جغرافيايي و استفاده از آنها براي حل برنامههاي کاربردي که قدرت محاسباتي بالايي نياز دارند و بايد در مدت زمان معين با هزينه مشخص اجرا شوند، ترويج پيدا کرد. چنين زير ساخت هايي گريد محاسباتي ناميده مي شود، و منجر به محبوبيت حوزهاي به نام محاسبات گريد شده است [1].
از اتصال منابع محاسباتي مانند رايانههاي شخصي، ايستگاههاي کاري، خوشهها، سرويس دهندهها، ابررايانهها و …، توزيع شده در مناطق مختلف جغرافيايي شبکههاي تورين محاسباتي (گريد) پديد آمده است که به عنوان يک سکوي محاسبات براي حل مسائل مقياس بزرگ در دانشگاه، پژوهش و صنعت مورد استفاده قرار ميگيرد[2].
يکي از عمليات اصلي تضمين کنندهي کارايي در شبکههاي تورين محاسباتي، تخصيص منابع به کارها ميباشد. عمليات تخصيص منابع بايد مکانيسمهايي را براي پشتيباني از تحمل خطا، اطمينان از اجراي حتمي کارها، افزايش بهرهوري از منابع و کاهش زمان اتمام کارها ارائه دهد. زمانبندي در محيط گريد، با توجه به توزيع جغرافيايي منابع و کاربران، نوسانات منابع، الزامات کيفيت سرويس از برنامههاي کاربردي و محدوديتهاي اعمال شده توسط صاحبان منابع، جزء مسائل NP-complete مي باشد[3].
در زمانبندي وظايف مستقل، هدف افزايش عملکرد کل سيستم و در زمانبندي وظايف با وابستگي، هدف کاهش زمان اجرا کارها، بدون نقض محدوديت اولويت آنها ميباشد. با کم کردن زمان اجرا کارها، باعث افزايش بهرهوري از منابع شده، در نتيجه بهبود در عملکرد کل سيستم را خواهيم داشت.
در دهه گذشته زمانبندي کارها (وظايف با وابستگي و مستقل) درون محيط گريد توجه بسياري از محققين را به خود جلب کرده است. به دليل پويايي محيط گريد، عمليات زمانبندي بايد مرتبا با بررسي کردن حالت جاري سيستم، اقدام به بروزرساني زمانبند خود نمايد. عمليات بروزرساني با رخداد رويدادي در گريد به دليل تخمين نادقيق زمان اجرايي، اضافه يا حذف شدن منابع، رخ مي دهد. در واقع هدف اصلي از اعمال زمانبندي مجدد افزايش بهره وري از منابع، اجراي قطعي و کاهش زمان اتمام کارها مي باشد به اين صورت که در ابتدا براساس وضعيت جاري منابع و کارها زمانبندي صورت مي پذيرد و در صورت رخداد رويدادهاي فوق زمانبندي مجدد براساس منابع موجود و وضعيت کارهاي باقي مانده صورت مي پذيرد.
1-2 ضرورت اجرا
پژوهشهاي زيادي بر روي رابطهي بين تخمينهايي که توسط کاربر به سيستم مديريت منبع ميدهد و زمان واقعي اجراي کارها صورت گرفته است و نشان داده شده که تخمينهايي که توسط کاربر فراهم ميشوند در اغلب موارد از دقت کافي برخوردار نيستند. دليل اين موضوع را ميتوان چنين دانست که در سيستمهاي مديريت منابع محلي، هنگامي که زمان اجراي تخمين زده شده کار به پايان برسد، کار خاتمه مييابد (فسخ ميشود)، بنابراين کاربران اصولا زمان اجراي کار را بيش از حد واقعي تخمين مي زنند تا از اتمام کامل کار مطمئن باشند. در پژوهشهاي مختلفي تأثير تخمينهاي کاربر بر روي کارائي سيستم ارزيابي شده است و نتايج حاکي از آن است که تخمينهاي غيرصحيح کاربر باعث کاهش کارائي سيستم ميشود. علاوه بر اين در مقاله [4] که در سال 2009 ارائه شد، نويسندگان نشان دادند که سيستمهاي مديريت منابع محلي توانايي کنار آمدن و کنترل حجم زيادي از واگذاريها را ندارند. در مقاله]5[ که در سال 2009 ارائه شد تاثير تغيير پذيري مجموعه کاريها بر روي سيستم مديريت منابع محلي مورد بررسي قرار گرفت و نتايج نشان داد که اين تغيير پذيري باعث تصميمات زمانبندي بدتر مي شود. زمانبندي مجدد سه هدف اساسي را دنبال ميکند: افزايش کارايي زمانبند، کاهش زمان اجرايي و ارائه تحمل خطا.
زمانبندي در محيط گريد بدليل پويايي از دو مرحله تشکيل ميشود در مرحله اول زمانبند براساس حالت جاري منابع، و زمان اجرايي تخميني يک نگاشت از کارها روي منابع را بوجود ميآورد. در مرحله دوم با رخداد يک رويداد، زمانبند، زمانبندي مجددي را براساس کارها، منابع و وابستگي هاي موجود بين کارها، صورت ميدهد و نگاشت جديدي را توليد مي کند.
1-3 هدف از اجراي پايان نامه
با توجه به اينکه منابع گريد غير اختصاصي بوده و تخمينهاي نادقيق ارائه شده توسط کاربران در عملکرد گريد تاثير بسزايي دارد زيرا کارهايي که بين آنها وابستگي داده وجود دارد (داده توليد شده توسط اين کار، نياز کار ديگري جهت شروع ميباشد) و اگر در اينجا نتوانيم اجراي قطعي کار را تضمين کنيم (بدليل خرابي منبع) اجراي کارهاي پيشرو نيز امکان پذير نميباشد همچنين اين تخمينهاي نادقيق نيز باعث کاهش کارايي گريد ميگردد به همين دليل نياز به نظارت بر وضعيت منابع و کارها و اعمال نگاشت جديد (زمانبندي مجدد) با رخداد رويدادي در گريد (تغييري در وضعيت منابع و يا زمان اجرايي کار) ميباشد.
اهداف زمانبند و زمانبند مجدد گريد افزايش بهرهوري از منابع، کاهش زمان اتمام آخرين کار، افزايش کارايي، قطعيت در اجراي کارها و ايجاد توازن بار ميباشد در اين پايان نامه نيز سعي در ارائه يک الگوريتم زمانبند مناسب با توجه به همين اهداف داريم.
1-4 مراحل انجام پايان نامه
براي انجام پايان نامه در ابتدا مفاهيم گريد و مکانيزم زمانبندي و زمانبندي مجدد (تخصيص مجدد) موجود در محيط گريد بررسي شدند و بعد از ارزيابي روشهاي موجود، روشي که بهتر بوده است انتخاب و بهبود داده شده است.
1-5 ساختار پايان نامه
در فصل دوم مفاهيم اوليه زمانبندي و گذري بر تحقيقات پيشين را مورد بررسي قرار داده و در فصل سوم الگوريتمهاي پيشنهادي در ارائه شده است و در فصل چهارم نتايج حاصل از ارزيابي و مقايسه الگوريتم پيشنهادي آورده شده است.
فصل دوم

مفاهيم اوليه زمانبندي و مروري بر کارهاي گذشته
2-1 مقدمه
در اين فصل ابتدا مفاهيم و محدوديتهايي که در گريد وجود دارد را شرح ميدهيم. سپس زمانبندي و انواع آن را بررسي ميکنيم. در آخر مروري بر کارهاي گذشته داريم.
شبکههاي تورين محاسباتي (گريد)، يك فن آوري جديد است كه با استفاده از زيرساختهاي ارتباطي و شبكههاي كامپيوتري و نيز با اتصال منابع محاسباتي ناهمگون در فواصل جغرافيايي مختلف، امكان دسترسي به انواع مختلف منابع را از راه دور ميدهد[6]. امروزه ميتوان با استفاده از اين فن آوري، برنامههاي كاربردي بسيار پيچيده و بزرگ را كه به توان پردازشي بسيار بالا و به حجم عظيمي از دادههاي ورودي نياز دارند در شبکههاي گريد اجرا كرد.
شبکههاي محاسباتي گريد از لحاظ کاربرد، داراي تقسيم بنديهاي متفاوتي ميباشند و عبارتند از: گريد اطلاعاتي، گريد محاسباتي و . . . که در هر کدام هدف و نحوهي اختصاص منابع به کاربران متفاوت ميباشد.
يکي از چالش هاي اصلي در گريد هاي محاسباتي نگاشت کارهاي درخواستي کاربر به
منابع با توجه به سياستهاي زمانبندي ميباشد. زمانبندي، عمل واگذاري برنامههاي كاربردي به منابع محاسباتي به نحوي كه نيازمنديهاي برنامههاي كاربردي مانند: تعداد پردازنده، زمان اجرا و … تامين گردد.
مسئله زمانبندي جزء مسائلNp-complete مي باشد[3] و بيشتر الگوريتمهاي ارائه شده اکتشافي ميباشد.
يك زمانبند گريد پيوسته كارهاي ورودي جديد را دريافت ميكند، منابع موجود در دسترس را بررسي ميكند و منبع مناسب را با توجه به معيارهايي انتخاب ميكند. مفاهيم و محدوديتهايي که در اين راستا وجود دارند در ادامه توضيح داده ميشوند.
کار : يک برنامه کاربردي است که نياز به قابليتهاي پردازشي متفاوت (مانند تعداد پردازنده، حافظه، زمان لازم و ….) و محدوديتهاي متفاوت داشته باشد. كه معمولاً با توضيحات بخصوص كار نشان داده ميشود.
منبع : منبع يك مولفه محاسباتي است (يك ابزار يا يك سرويس محاسباتي) كه کارها در آن زمانبندي، تخصيص و پردازش ميشوند. منابع ويژگيهاي بخصوص مانند حافظه، نرم افزار و غيره دارند. پارامترهاي مختلفي در مورد منابع مطرح ميشود مانند سرعت پردازش و باركاري كه در طي زمان تغيير ميكند. علاوه بر آن از آنجايي كه منابع ميتوانند به محيط هاي مديريتي مختلف تعلق داشته باشند، سياستهاي مختلفي روي آنها براي دسترسي و استفاده اعمال ميگردند.
دلال منبع : يک برنامه نرم افزاري است که از ميانافزارها و سرويسها استفاده ميکند تا مديريت منابع، زمانبندي کارها و کنترل را انجام دهد. دلال منبع بين توليد کننده و مصرف کننده قرار ميگيرد[7].
سيستم مديريت منابع : يک برنامه نرم افزاري است که مجموعهاي از منابع را مديريت مي‌کند به طوري که کارايي سيستم را بهينه کند[8].
تعريف زمانبندي : نگاشتي از کارها به منابع مي باشد. يک مساله ي زمانبندي با
مجموعهاي از منابع، مجموعهاي از کارها، ملاکي براي بهينه بودن، مشخصات محيط و محدوديتهاي ديگر تعريف ميشود.
سطوح مختلفي براي زمانبندها وجود دارند که عبارتند از زمانبند گريد، زمانبند خوشه و زمانبند محلي. در ادامه توضيح مختصري در مورد آنها آورده شده است.
زمانبندي گريد : يک زمانبند پيشرفته است که با توجه به پويا بودن محيط گريد، هدف آن نگاشت کار به منابع در محيط گريد با اهداف خاص ميباشد.
زمانبندي در گريد را ميتوان بر مبناي معيارهاي مختلفي نظير کارآيي يا مقياس پذيري در ساختارهاي مختلفي سازماندهي کرد. براساس يک تقسيمبندي کلي سه مدل زمانبندي متمرکز، سلسه مراتبي و توزيع شده وجود دارد[9]:
2-2 ساختار متمرکز
شکل‏2-1 معماري زمانبندي متمرکز [10]

در مدل متمرکز (شکل 2-1) تمام ماشين هاي موازي توسط يک زمانبند مرکزي زمانبندي مي شوند. اطلاعات وضعيت سيستم هاي موجود بايد توسط زمانبند جمع آوري شود. اين مدل با افزايش اندازه گريد محاسباتي مقياس پذير نيست و ممکن است منشا تنگنا در بعضي از موارد شود (اگر خطاهاي شبکه باعث جدايي زمانبند از منابع شود، دسترسي و عملکرد سيستم تحت تاثير قرار مي گيرد) از مزاياي اين روش زمانبندي کارايي زياد آن است، زيرا زمانبند مرکزي تمام اطلاعات منابع موجود را دارد.
در اين سناريو کارها به زمانبند مرکزي ارسال ميشوند و کارهايي که نميتوانند به سرعت انجام شوند، بعد از واگذاري در صف کار مرکزي ذخيره ميشوند.
اين نمونه زمانبندي براي زير ساختهاي گريد سازماني مناسب ميباشد. گريد سازماني امکان به اشتراک گذاري منابع گوناگون را به منظور بهبود همکاري داخلي و دستيابي به بازدهي بهتر از سرمايه هاي فناوري اطلاعات، مهيا ميسازد. در نتيجه با استفاده از فناوري گريد بهره برداري از منابع موجود در يک شرکت بهتر ميشود و سربار اداري کاهش مييابد.

در مدل سلسله مراتبي (شکل 2-2) همه کارها به يک زمانبند مرکزي واگذار ميشود، در حالي که هر ماشين از يک زمانبند مجزا براي زمانبندي استفاده ميکند.
اگر چه اين ساختار مشخصات زمانبندي متمرکز و غير متمرکز را نشان ميدهد، از آنجاييکه يک زمانبند مرکزي وجود دارد که کارها به آن واگذار ميشوند، به عنوان يک سيستم متمرکز در نظر گرفته ميشود.
مزيت اصلي اين نوع ساختار استفاده از سياستهاي متفاوت براي زمانبندي سطوح مختلف است. اين نوع ساختار براي گريد عمومي مناسب ميباشد. سازمانها گريد را به عنوان راهي اصلي براي اداره کردن تغييرات نياز هاي خدماتي در يک سازمان يافتهاند. آنها براي رسيدن به بازدهي بهتر از سرمايه هاي فناوري اطلاعات خود و فراهم کردن منابع خارجي براي برآورده کردن درخواستهاي سطح بالا، مايل به به اشتراک گذاري منابع خانگي شدهاند.

2-3 ساختار غير متمرکز و يا توزيعي
در سيستم هاي توزيع شده، زمانبندهاي توزيع شده (شکل 2-3) با يکديگر در ارتباط هستند و کارها را به سيستم هاي راه دور ارسال ميکنند. هيچ نمونه مرکزي وجود ندارد، بنابراين اطلاعات مربوط به وضعيت تمام سيستمها در يک نقطه جمع نميشود. از اين رو گلوگاه ارتباطي زمانبندي متمرکز در اين ساختار وجود ندارد و باعث مقياس پذيري ميشود. علاوه براين شکست يکي از اجزا روي کل سيستم تاثير نميگذارد و خاصيت تحمل شکست1و قابليت اعتماد2را ايجاد ميکند. کمبود زمانبندي سراسري گاهي باعث زمانبنديهاي نيمه بهينه ميشود. با اين حال سياستهاي زمانبندي متفاوتي را مي توان در ايستگاههاي محلي استفاده کرد. در ادامه دو نوع معماري توزيع شده، ارتباط مستقيم و ارتباط از طريق يک استخر کار مرکزي توضيح داده ميشود.
شکل‏2-2 معماري زمانبندي سلسله مراتبي [10]
(الف)(ب)شکل ‏2-3 معماري زمانبندي غيرمتمرکز[10].
نمونه اي از محيط هاي محاسباتي ناهمگن محيط گريد ميباشد. در اين فصل فرايند زمانبندي و انواع سطوح زمانبندي در گريد شرح داده مي شود.

2-4 فرايند زمانبندي گريد و اجزاي آن
فرايند زمانبندي از سه بخش تشکيل شده است: کشف و پالايش کردن منابع، انتخاب منبع و زمانبندي بر اساس هدف هاي خاص و واگذاري کار[11]. شکل ‏2-4 مدلي از سيستم هاي زمانبندي گريد را نشان مي دهد.
شکل ‏2-4 معماري زمانبندي گريد [11]

همان طور که در شکل 2-4 ديده مي شود اجزاي اصلي از طريق دو نوع جريان داده با يکديگر در ارتباط هستند: جريان اطلاعات منبع يا برنامه کاربردي و جريان فرمان زمانبندي کار. در اين نوع معماري دو سطح زمانبندي ديده مي شود: زمانبند گريد (فرازمانبند) و مديريت منابع محلي.
به طور کلي، يک زمانبند گريد3 کار (ها) و مشخصات آن را از کاربران دريافت کرده، منابع مناسب براي اجراي کار را بر اساس اطلاعات به دست آمده از ماژول سرويس اطلاعات گريد (GIS)4 انتخاب و کار را بر اساس تابع هدف مورد نظر و کارايي پيش بيني شده منبع، به منبع انتخابي نگاشت مي کند. اطلاعات مربوط به منابع در دسترس به ويژه در محيط هاي ناهمگن و پويا به منظور زمانبندي مناسب براي زمانبند گريد بسيار مهم هستند. وظيفه GIS جمع آوري و پيش بيني اطلاعات وضعيت منابع، از جمله ظرفيت هاي پردازنده ها، اندازه حافظه، پهناي باند، نرم افزار هاي در دسترس، و بار گره در يک دوره مشخص، مي باشد. سيستم کشف و نظارت 5Globus [12] نمونه اي از GIS مي باشد. نگاشت کار به منبع مورد نظر بر اساس معيارهاي متفاوتي از جمله زمان تکميل کار، هزينه اجراي کار، بهره وري بهينه از منابع و … صورت مي گيرد که تابع هدف را مشخص مي کند.
2-5 انواع زمانبند
تقسيم بندي زمانبندها به شرح زير است[13]:
زمانبند گريد: يکي از اجزاي نرمافزاري است که مسئوليت محاسبهي يک نگاشت از کارها به منابع گريد تحت ملاکهاي مختلف و تنظيمات محيط گريد را دارد. سطوح مختلفي در درون زمانبند گريد در مقايسههاي مختلف ادبيات محاسبات گريد در نظر گرفته شده است که شامل ابرزمانبند6، فرازمانبند7، زمانبند محلي8 و زمانبند کسب و کار 9ميباشد. به عنوان يک جزء اصلي از گريد، زمانبند گريد10 با اجزاء ديگر گريد، از قبيل سيستم اطلاعات گريد، سيستم مديريت منبع محلي و سيستم مديريت شبکه در تعامل است. همچنين بايد اين نکته را در نظر گرفت که در محيط گريد، انواع زمانبندها بايد در کنار يکديگر همزيستي11 داشته باشند. حتي ممکن است که آنها داراي هدفهاي مختلفي باشند، اما بايد براي اجراي کارها با يکديگر در تعامل باشند.
ابرزمانبند: اين نوع از زمانبند مربوط روش متمرکز در زمانبندي است که در آن، زمانبندهاي محلي براي رزرو و انتساب کار به منابع استفاده ميشوند. زمانبندهاي محلي پردازش صف کار را مديريت ميکنند. ابر زمانبند بيشتر براي مديريت رزرو، مذاکره و توافقات سطح سرويس استفاده ميشود. همچنين کارها به طور کامل در منابع منحصر به فرد به اتمام ميرسند.
فرازمانبند: اين زمانبند در مواقعي که يک کار تک، به بيشتر از يک منبع در سيستم هاي مختلف انتساب داده ميشود، استفاده مي شود. به عنوان حالتي از ابرزمانبند، فرازمانبند از زمانبندهاي محلي براي سيستمهاي خاصي استفاده ميکند. بنابراين، فرازمانبند، زمانبندهاي محلي را براي محاسبهي زمانبندي کلي هماهنگ ميکند. اعمال توازن بار در ميان سيستمهاي مختلف هدف اصلي اين زمانبند ميباشد.
زمانبند محلي: اين زمانبند براي انتساب کارها به يک منبع استفاده ميشود و به عنوان يک زمانبند “نزديک به منبع” شناخته ميشود.
زمانبند کسب وکار: اين زمانبند در کسب و کارهاي بزرگ که در آن منابع محاسباتي در حوزههاي مختلفي توزيع شدهاند، استفاده ميشود. همچنين از زمانبندهاي محلي مختلف که به حوزهي يکساني تعلق دارند استفاده ميکند.
2-6 انواع کارها
کارهاي ارجاعي به محيط گريد به دو دسته تقسيم ميشود[13[:
کارهاي مستقل12: مابين اين نوع کارها وابستگي داده اي و همچنين تقدم اولويت وجود ندارد. و اجراي هر کار مجزا از بقيه کارها مي باشد.
کارهاي جريان کاري13: مابين اين نوع کارها وابستگي داده اي وجود دارد به عبارتي شروع اجرا کار وابسته به اتمام يک يا بيشتر کارهاي پيشنياز ميباشد اين نوع کارها را توسط گرافهاي جهتدار بدون دور نمايش داده مي شود که يال هاي وارد شده به هر گره نشان دهنده تعداد کارهاي پيشنياز مي باشد و تا زماني که کليه کارهاي پيشنياز اجرا نشده است آن کار قادر به اجرا نمي باشد. شکل 2-5 نمونهاي از جريان کارها مي باشد. اين هماهنگي در
ترتيب اجرا کارها و با توجه به خطاهاي قابل رخداد در محيط گريد اعمال زمانبندي مجدد الزامي مي باشد چرا که در صورت اضافه شده منابع و عدم بهره وري از آن ها، باعث ايجاد تاخير در اجرا کارهاي پيشنياز مي شود و در نتيجه کارايي زمانبند کاهش مي يابد[14, 15]. گذشته از کارائي، در يک جريان کار، مقاومت در برابر خطا نيز بايد در نظر گرفته شود. مطمئنا اگر يک جريان کار گريد براي يک دورهي زماني زياد اجرا شود، احتمال خطا در فرايند را افزايش ميدهد. در نتيجه باعث خطا در کل جريان کار مي شود. بنابراين در چنين مواردي بايد حتما از زمانبندي مجدد جهت رفع خطا و همچنين قطعيت در اجرا کارها استفاده گردد.
2-7 نحوهي زمانبندي (ايستا و پويا)
ايستا: در اين حالت اطلاعات کامل منابع و کارها، هنگامي که زمانبندي انجام ميشود در دسترس است (کارها به صورت دستهاي ميباشند). يکي از مزاياي زمانبندي ايستا برنامهي ساده آن از ديد زمانبندها ميباشد. در زمان شروع تمام منابع و کارها جهت پردازش در دسترس ميباشند. زمان مورد انتظار پردازش براي هر کار روي هر منبع، در ماتريس ETC قرار دارد. ماتريس ETC يک ماتريس n*m ميباشد که n تعداد کارها و m تعداد ماشينها ميباشد. شکل 2-6 يک نمونه از ماتريس ETC را نشان ميدهد.
کار اولکار دومکار سومکار چهارممنبع اول10527منبع دوم6354منبع سوم9486شکل ‏2-6 نمونه ماتريس ETC
پويا: در زمانبندي پويا تخصيص کارها به صورت برخط14 انجام ميشود و در همان لحظه کار براي اجرا به يک منبع فرستاده ميشود. اين زمانبندي معمولا زماني استفاده ميشود که تخمين هزينه ي کارها سخت است و يا کارها به صورت برخط فرستاده ميشوند [16[.
2-8 وظايف فرازمانبند
فرا زمانبندها در سطح گريد دو نقش اساسي ايفا مي کنند: نگاشت (انتساب) کارها به گره هاي محاسباتي و انتقال کار به منظور بهبود توازن بار بين گره هاي محاسباتي و کاهش زمان تکميل کارها.
2-8-1 نگاشت کار
در محيط گريد درخواست اجراي کار کاربران همراه با پارامترهاي لازم به فرازمانبند ارسال مي شود. فرازمانبند بر اساس تابع هدف الگوريتمي را براي مشخص کردن ماشين مناسب اجرا مي کند و گره مناسب را انتخاب مي کند. در چنين مواردي اگر اطلاعاتي از گره محاسباتي موجود نباشد از الگوريتم تصادفي15 (انتخاب ماشين به صورت تصادفي) و چرخشي (ماشين ها يکي پس از ديگري انتخاب مي شوند) مي توان استفاده کرد، و در صورتي که نظارت بر ماشين هاي موجود امکان پذير باشد مي توان از الگوريتم هاي حريصانه بر خط و برون خط استفاده کرد که در اين حالت معمولا ماشيني انتخاب مي شود که در کمترين زمان، کار را به پايان مي رساند. در زير نمونه اي از الگوريتم هاي برخط و برون خط آورده شده است.
الگوريتم بر خط
حداقل زمان اجرا 16: در اين مکانيزم کار به ترتيب ورود به ماشيني ارسال مي شود که کمترين زمان اجرا را براي کار ايجاد کند. اين روش ممکن است باعث طولاني شدن برخي از صف ها و عدم توازن بار در ماشين ها شود.
حداقل زمان اتمام17: در اين مکانيزم کار به ترتيب ورود به ماشيني ارسال مي شود که کمترين زمان تکميل را براي آن ايجاد کند. در اين روش ممکن است ماشيني انتخاب شود که بهترين زمان اجرا را نداشته باشد.
الگوريتم برون خط
کمترين کمترين18: اين الگوريتم با مجموعه U از کارهاي نگاشت نشده شروع مي شود. سپس، براي هر کاري عضو مجموعه U مجموعه اي از کمترين زمان تکميل آن کار بر روي تمام ماشين ها را محاسبه مي کند.
M = {min0?j<µ (ct(ti, mj)), for each ti€U, }
که µ برابر است با تعداد ماشين ها، ti برابر است با کارi ام و mj برابر است با ماشين j ام مي باشد و ct(ti, mj) برابر است با زمان اتمام کار iام بر روي ماشين jام مي باشد.
در مرحله بعد، کاري که کمترين زمان تکميل در مجموعه M را دارد، انتخاب شده و به ماشين مورد نظر نگاشت مي شود. در پايان کار نگاشت شده از مجموعه U حذف مي شود و فرايند گفته شده تا زماني که تمام کارها نگاشت شود (U خالي شود) ادامه مي يابد.
بيشترين کمترين19: اين الگوريتم بسيار شبيه به مکانيزم کمترين کمترين مي باشد. الگوريتم بيشترين کمترين هم با مجموعه U حاوي کارهاي نگاشت نشده شروع مي شود. سپس، براي هر کاري عضو مجموعه U مجموعه اي از کمترين زمان تکميل آن کار بر روي تمام ماشين ها محاسبه مي شود. در مرحله بعد، کاري که بيشترين زمان تکميل در مجموعه M را دارد، انتخاب شده و به ماشين مورد نظر نگاشت مي شود. در پايان کار نگاشت شده از مجموعه U حذف مي شود و فرايند گفته شده تا زماني که تمام کارها نگاشت شود (U خالي شود) ادامه مي يابد.
مثالي را فرض کنيد که مجموعه U داراي تعداد زيادي کار با زمان اجراي کوچک باشد و يک کار با زمان اجراي بزرگ داشته باشد. با نگاشت کار با زمان اجرا طولاني تر به بهترين ماشين در ابتداي کار، باعث مي شود اين کار همزمان با کارهاي با زمان اجراي کوتاه اجرا شود. در چنين مواردي عملکرد الگوريتم بيشترين کمترين بهتر از کمترين کمترين مي باشد زيرا در الگوريتم کمترين کمترين ابتدا کارهاي با زمان اجراي کوتاه زمانبندي مي شوند.
حق راي20: عملکرد اين الگوريتم مثل الگوريتم کمترين کمترين ميباشد با اين تفاوت که علاوه بر کمترين زمان اتمام دومين کمترين زمان اتمام هم براي هر کار محاسبه ميشود و اختلاف اين دو زمان براي هر کار روي منابع مختلف محاسبه ميشود. کاري که داراي بيشترين اختلاف باشد براي زمانبندي انتخاب و به منبعي که کمترين زمان اتمام را داشته اختصاص داده مي شود.
علاوه بر اين الگوريتم هاي فوق الگوريتم هاي اکتشافي و فرا اکتشافي مانند الگوريتم Duplex ،SA، GA، GSA، Tabu search و … نيز در اين زمينه استفاده مي شود.
2-9 گذري بر تحقيقات پيشين
در اين قسمت شرح کوتاهي از مفاهيم اوليه جريان کارها و همچنين به بررسي چند الگوريتم حريصانه که براي حل مسئله زمانبندي جريان کارها ارائه شده است ميپردازيم.
2-9-1 مفاهيم اوليه
فرض کنيد نشان دهنده يک مجموعه m تايي از منابع و نشان دهنده يک مجموعه n تايي از کارها که بين آن ها وابستگي وجود دارد مي باشد. جهت نمايش وابستگي بين کارها از گراف هاي جهت دار بدون دور21 استفاده مي کنيم. گره هاي گراف نشان دهنده کارها و يال هاي گراف نشان دهنده وابستگي بين کارها (محدوديت اولويت) ميباشد. مقادير هر يال هزينه انتقال داده مورد نياز اين کار مي باشد (در صورتي که منبع اجرا کننده مشترک نباشند). بطور مثال فرض کنيد از گره 1 به گره 3 يک يال ارتباطي وجود دارد؛ به عبارتي کار 3 وابسته به کار 1 است. حال اگر کار 3 و کار 1 روي دو منبع مختلف زمانبندي شود بايد 12 واحد زماني (هزينه درج شده بر روي يال کار 1 به 3) براي انتقال خروجي کار 1 صرف کنيم. شکل (2-7 و 2-8) نمونه اي از يک جريان کاري و زمان اجرا را نشان مي دهد را نشان مي دهد.
در جريان کارها گراف با يک گره شروع و به يک گره خاتمه مييابد. براي نمايش يک جريان کار از دو ماتريس ETC و DTTS استفاده مي شود. ماتريسETC يک ماتريس n*m است که n تعداد کارها و m تعداد منابع را مشخص ميکنند. ETC (i,j) نشان دهنده زمان مورد انتظار پردازش کار i روي ماشين j ميباشد. ماتريس DTTS وابستگي دادهاي و زمان انتقال داده، بين کارها را نمايش مي دهد. که يک ماتريس n*n است. DTTS (i,j) نشان دهنده زمان انتقال داده از کار i به کارj است که اگر اين مقدار صفر باشد نشاندهنده عدم وابستگي کار j به i ميباشد.
زمان اتمام کار i، طبق فرمول (1) محاسبه ميشود.
(1)
نشان دهنده ميزان حجم کار منبع j (زمان آزادي منبع)، قبل از شروع پردازش کار i مي باشد (زماني که کار i بايستي روي منبع j منتظر بماند تا شروع به اجرا کند)؛ نشان دهنده زماني مي باشد که کار i از اين زمان به بعد مي تواند اجراي خود را شروع نمايد. (زمانيکه کار i کليه داده هاي مورد نياز خود را در اختيار دارد. اين داده ها توسط کارهائي توليد مي شوند که کار i به آنها وابسته است). بطور مثال اگر کار 3 و کار 1 بر روي منبع j زمانبندي شوند و کار 3 نياز به داده توليد شده توسط کار 1 داشته باشد، برابر با زمان اتمام کار 1است؛ در غير اين صورت زمان انتقال داده از کار 1 به کار 3 نيز، بايد به زمان اتمام کار1 اضافه گردد. کليه کارهايي که آمادگي اجرا دارند (کليه کارهاي پيش نيازشان زمانبندي شده است) درون صف آماده اجرا قرار مي گيرند الگوريتم هاي ارائه شده جهت جريان کارها از بين کارهاي موجود در صف، يکي را براساس تابع هدف خود انتخاب و زمانبندي مي نمايد بعد از زمانبندي کار منتخبي، کليه فرزندان کار منتخبي به صف کارهاي آماده اجرا اضافه مي گردند و همين روند ادامه مي يابد تا زماني که ديگر کاري درون صف آماده اجرا وجود نداشته باشد.
2-9-2 الگوريتم ETF22 ]17[:
اين الگوريتم از بين کارهاي موجود در صف آماده، کاري را انتخاب مي کند که داراي کمترين زمان شروع جهت اجرا باشد در حقيقت اين الگوريتم بدنبال مشغول نگهداشتن منابع مي باشد و با اين کار توازن بار را ايجاد مي نمايد. اين الگوريتم داراي سرعت اجرايي مناسبي مي باشد. و از معايب اين الگوريتم مي توان ناديده گرفتن زمان اتمام آخرين کار، کارايي و سرعت را نام برد.
2-9-3 الگوريتم Myopic ]18[ :
کارها را با ترتيبي که وارد صف کارهاي آماده مي گردند با همان ترتيب به آنها منابع اختصاص داده مي شود انتخاب منبع براي کار مورد نظر بر اين اساس است که منبعي که بتواند آن کار را زودتر از مابقي منابع به اتمام برساند در واقع اين الگوريتم بصورت FIFO از صف انتخاب مي کند اين الگوريتم بسيار ساده ميباشد ولي زمان اتمام آخرين کار23 خيلي مطلوب نميباشد.

2-9-4 الگوريتم کمترين کمترين، بيشترين کمترين، حق راي و … ]20-19[:
تمام الگوريتم هاي ارائه شده جهت کارهاي مستقل بر روي کارهاي وابستگي دار قابل اعمال مي باشد با اين تفاوت که اين الگوريتم ها از بين کارهاي موجود در صف آماده براساس سياست هاي خود انتخاب و مطابق با تابع هدف خود به منبع منتخبي ارسال مي نمايد.

2-9-5 الگوريتم HLEFT 24



قیمت: تومان


پاسخ دهید