تاریخچه گرید، الگوریتم ها و مدل های زمانبندی در گرید

تاریخچه گرید، الگوریتم ها و مدل های زمانبندی در گرید

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

از آنجا كه گريد را مي‌توان از زواياي مختلف نگريست، الگوريتم‌هاي زمانبندي روي گريد را نيز مي‌توان از زواياي متعدد بررسي كرد. در اين پیوست به بررسي الگوريتم‌هاي مختلف مي‌پردازيم.
در [Don06] دسته‌بندي كاملي از الگوريتم‌هاي زمانبندي در گريد ارائه شده است. همانطور كه در شكل 1 ملاحظه مي‌گردد، الگوريتم‌هاي زمانبندي به دو دسته كلي الگوريتم‌هاي محلي و سراسري تقسيم‌بندي مي‌شوند:
شکل 1 دسته‌بندي الگوريتم‌هاي زمانبندي در گريد

• الگوريتم‌هاي زمانبندي محلي و سراسري
در الگوريتم‌هاي زمانبندي محلي، زمانبند تنها بر روي زمانبندي كارهاي محلي نظارت مي‌كند، در حاليكه الگوريتم‌هاي زمانبندي سراسري بر اساس اطلاعاتي كه درباره يك قسمت از گريد يا از كل گريد دارند، كارها را زمانبندي مي‌كنند، تا به يك هدف سراسري دست يابند.
الگوريتم‌هايي كه تاكنون براي گريد طراحي شده‌اند، اكثراً در دسته الگوريتم‌هاي سراسري مي‌گنجند، چرا كه هدف از زمانبندي كارها در گريد دستيابي به توزيع مناسب كارها در كل گريد است نه فقط در يك قسمت كوچك از گريد.
الگوريتم‌هاي سراسري خود به دو دسته الگوريتم‌هاي ايستا و پويا تقسيم مي‌شوند:

• الگوريتم‌هاي زمانبندي ايستا و پويا
ايستايي و پويايي الگوريتم‌هاي زمانبندي در گريد به زمان تصميم‌گيري در مورد زمانبندي بستگي دارد. اگر زمانبندي بر اساس اطلاعاتي كه از منابع و كارها در همان زمان در دسترس است، صورت گيرد، زمانبندي را ايستا گويند. در صورتي كه موقع زمانبندي اطلاعاتي راجع به زمانبندي و كارها (براي مثال مدت زمان اجرا) در دسترس نباشد، زمانبندي را پويا گويند.
مزيت زمانبندي ايستا، سادگي آن است چرا كه تمام اطلاعات حين زمانبندي راجع به منابع و كارها در دسترس است و با داشتن اين اطلاعات و يك الگوريتم زمانبندي مناسب، فرايند زمانبندي براحتي قابل پياده‌سازي خواهد بود.
با توجه به خاصيت پويا بودن گريد كه منابع در يك لحظه موجود و در لحظه ديگر ممكن است ديگر عضو گريد نباشند و لذا اطلاعاتي كه در زمان زمانبندي در دست بود، نامعتبر خواهد شد، زمانبندي پويا بر ايستا ارجحيت پيدا مي‌كند.
الگوريتم‌هاي ايستا به دو دسته الگوريتم‌هاي بهينه و نيمه‌بهينه تقسيم مي‌شود:

• الگوريتم‌هاي زمانبندي بهينه و نيمه بهينه
در مساله زمانبندي گريد، اگر تصميم‌گيري براي زمانبندي بر اساس اطلاعات وضعيت فعلي تمامي منابع و كارها صورت گيرد، زمانبندي مي‌تواند بر مبناي يكي از معيارهايي كه در قسمت مقدمه ذكر شد، همچون مينيمم makespan يا ماكسيمم throughput بصورت بهينه صورت گيرد.
از طرفي خاصيت پويا بودن گريد (اينكه اطلاعات وضعيت منابع و كارها قبل از زمانبندي و بعد از آن مي‌تواند متفاوت باشد) و مساله NP-complete بودن انتخاب منابع براي اجراي كار، موجب مي‌شود نتوان الگوريتم‌هاي كاملاٌ بهينه‌اي براي زمانبندي روي گريد ايجاد كرد، لذا محققان سراغ الگوريتم‌هايي رفته‌اند كه راه‌حل‌هاي نيمه بهينه يا نزديك بهينه‌اي را ارائه مي‌كنند.
الگوريتم‌هاي نيمه بهينه به دو دسته الگوريتم‌هاي تقريبي و اكتشافي تقسيم مي‌شوند:

• الگوريتم‌هاي زمانبندي تقريبي و اكتشافي
در الگوريتم‌هاي زمانبندي تقريبي، به محض رسيدن به يك جواب قابل قبول، متوقف مي‌شوند،‌ در حاليكه بايد در بين كل راه‌حل‌هاي موجود به دنبال يك راه‌حل بهينه بگردند. اين دسته الگوريتم‌ها داراي مزايا و معايبي هستند كه در مقايسه با روش اكتشافي ذكر خواهد شد.
از جمله مزاياي اين روش، كاهش مدت زمان پيدا كردن يك زمانبندي قابل قبول براي گريد است، چرا كه كل مجموعه راه‌حل‌هاي ممكن را جستجو نمي‌كند. البته اين مزيت در صورتي برقرار خواهد بود كه معياري براي ارزيابي قابل قبول بودن الگوريتم موجود باشد.
تنها الگوريتم تقريبي كه براي زمانبندي روي گريد ارائه شده است، بر اساس معيار « ميزان كل مصرف سيكل‌هاي پردازنده(TPCC )» [Fuj03] كار مي‌كند.
بر خلاف الگوريتم‌هاي تقريبي، الگوريتم‌هاي اكتشافي بر اساس اطلاعات واقعي راجع به ميزان بار سيستم و پردازنده تصميم‌گيري مي‌كنند، لذا فرضيه‌هاي واقعي‌تري را در نظر مي‌گيرند. ارزيابي چنين الگوريتم‌هايي بر مبناي تجارب واقعي يا شبيه‌سازي صورت مي‌گيرد، لذا الگوريتم‌هاي اكتشافي تصميم‌گيري‌هاي نزديك بهينه‌اي را انجام مي‌دهند. با توجه به خاصيت پويا بودن گريد، اين روش براي زمانبندي گريد مناسبتر از روش تقريبي است.

همانطور كه الگوريتم‌هاي ايستا به دو دسته الگوريتم‌هاي بهينه و نيمه بهينه تقسيم‌بندي شده‌اند، الگوريتم‌هاي پويا نيز به به مراتب به دو دسته متمركز و توزيع شده تقسيم مي‌شوند:

• الگوريتم‌هاي زمانبندي متمركز و توزيع شده
در الگوريتم‌هاي زمانبندي متمركز، همانطور كه از نامش پيداست، زمانبندي بصورت متمركز صورت مي‌گيرد، بدين معنا كه تمامي كارها به يك گره از گريد براي زمانبندي وارد مي‌شوند. ار آنجا كه تنها يك زمانبند در گريد وجود دارد، پياده‌سازي چنين الگوريتم‌هايي ساده مي‌باشد.
از طرفي با توجه به فزوني تعداد كارهايي كه به گريد وارد مي‌شوند، اين روش داراي معايبي به شرح زير مي‌باشد:
o با زياد شدن حجم كارهاي وارد شده به گريد، گرهي كه عمليات زمانيندي را انجام مي‌دهد به گلوگاه تبديل خواهد شد.
o با افزايش تعداد گره‌ها و به مراتب تعداد كارها در گريد، گريد ديگر مقياس‌پذير نخواهد بود و نمي‌تواند توانايي‌هاي عظيم اين سيستم توزيع‌شده در سطح وسيع را بخوبي نمايان سازد.
o ميزان تحمل خطا در گريد پايين خواهد آمد. با توجه به اينكه فقط يك زمانبند عمليات زمانبندي را انجام مي‌دهد، با خرابي اين گره، كل سيستم از كار خواهد افتاد.
در مقابل در زمانبندهاي توزيع شده، عمليات زمانبندي گريد در چندين زمانبند صورت مي‌گيرد. بنابراين معايب زمانبندي متمركز را پوشش خواهد داد.
الگوريتم‌هاي زمانبندي توزيع شده به دو دسته الگوريتم‌هاي مشاركتي و غير مشاركتي تقسيم مي‌شوند:
• الگوريتم‌هاي زمانبندي مشاركتي و غير مشاركتي
در الگوريتم‌هاي زمانبندي توزيع شده، بسته به اينكه گره‌هايي كه در زمانبندي مشاركت دارند، با يكديگر در تعامل باشند يا نباشند، دو گونه زمانبندي خواهيم داشت:
– اگر گره‌ها در زمانبندي با يكديگر مشاركت داشته باشند، زمانبندي را مشاركتي گويند؛
– در غير اين صورت، يعني گره‌ها با يكديگر در تعامل نباشند،‌ زمانبندي را غيرمشاركتي گويند.
در زمانبندي مشاركتي، زمانبندها همگي بر اساس يك هدف نهايي تصميم‌گيري مي‌كنند، بدين معنا كه هر زمانبند براي رسيدن به يك هدف نهايي (بسته به نوع الگوريتم مورد استفاده اين هدف مي‌تواند از الگوريتمي به الگوريتمي ديگر تفاوت كند، ولي مهم يكتا بودن هدف مي‌باشد.) تلاش مي‌كند نه براي ارضاي اهداف محلي.
در حاليكه در زمانبندي غيرمشاركتي، هر زمانبند بصورت يك موجوديت مستقل عمل كرده و فقط براي رسيدن به اهداف محلي خود تصميم‌گيري مي‌كند.

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

فهرست مطالب
فصل1 مقدمه 1
1-1 تاریخچه گرید 2
1-2 سیر تکاملی گرید 3
1-2-1 محاسبات با کارایی بالا 3
1-2-2 محاسبات کلاستری 3
1-2-3 محاسبات peer-to-peer 4
1-2-4 محاسبات اینترنتی 5
1-2-5 محاسبات گریدی 6
1-3 انواع گرید 6
1-3-1 گرید داده 7
1-3-2 گرید محاسباتی 7
1-4 ساختار گرید 8

فصل2 الگوریتم ها و مدل های زمانبندی در گرید 10
2-1 الگوریتم های زمانبندی در گرید 11
2-1-1 On line mode 11
2-1-1-1 MET 11
2-1-1-2 MCT 12
2-1-1-3 OLB 12
2-1-1-4 SA 12
2-1-2 Batch mode 14
2-1-2-1 Min-Min 14
2-1-2-2 Max-Min 15
2-1-2-3 Suffrage 16
2-1-2-4 XSuffrage 17
2-1-2-5 QoS Guided Min-Min 18
2-1-2-6 Segmented Min-Min 19
2-2 مدل های زمانبندی در گرید 19
2-2-1 زمانبندی متمرکز 19
2-2-2 زمانبندی غیر متمرکز 20
2-2-3 زمانبندی سلسله مراتبی 21