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

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

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

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

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

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

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

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

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

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

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

 فایل فشرده حاوی  یک فایل:

95,000 ریال – افزودن به سبد خرید پرداخت به سبدخرید اضافه شد

.

.

فهرست مطالب
فصل۱ مقدمه ۱
۱-۱ تاریخچه گرید ۲
۱-۲ سیر تکاملی گرید ۳
۱-۲-۱ محاسبات با کارایی بالا ۳
۱-۲-۲ محاسبات کلاستری ۳
۱-۲-۳ محاسبات peer-to-peer 4
1-2-4 محاسبات اینترنتی ۵
۱-۲-۵ محاسبات گریدی ۶
۱-۳ انواع گرید ۶
۱-۳-۱ گرید داده ۷
۱-۳-۲ گرید محاسباتی ۷
۱-۴ ساختار گرید ۸

فصل۲ الگوریتم ها و مدل های زمانبندی در گرید ۱۰
۲-۱ الگوریتم های زمانبندی در گرید ۱۱
۲-۱-۱ 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 مدل های زمانبندی در گرید ۱۹
۲-۲-۱ زمانبندی متمرکز ۱۹
۲-۲-۲ زمانبندی غیر متمرکز ۲۰
۲-۲-۳ زمانبندی سلسله مراتبی ۲۱