بخشی از مقاله
چکیده:
در این پژوهش مساله زمانبندي کارهاي مستقل بر روي منابع ناهمگن در محیط گرید محاسباتی در نظر گرفته شده است. منابع محاسباتی داراي توان پردازشی و میزان حافظه متفاوت هستند و میتوانند در سطوح ولتاژ-فرکانس مختلف عمل کنند. با توجه به اهمیت مصرف بهینه انرژي در سیستمهاي محاسباتی و نقش انرژي در پایداري سیستمها، در این پژوهش سعی شده با بکارگیري تکنیکهاي مقیاسگذاري پویاي فرکانس-ولتاژ و در نظر گرفتن حالت آمادهباش براي منابع در زمان بیکاري، مصرف انرژي تا حد امکان کاهش یابد.
بهمنظور افزایش رضایت کاربران سیستم و رسیدن به کیفیت سرویس1 مشتريمحور براي پردازشهایی که بعد از موعد تحویل تعیینشده از سوي کاربر تکمیل شوند جریمه دیرکرد در نظر گرفته میشود. پس از مدلسازي ریاضی مساله، تکنیکهاي خطیسازي و افزایش کارایی بر روي آن پیاده خواهد شد که باعث کاهش زمان حل آن میشود. در نهایت، تحلیل حساسیت روي پارامترهاي مساله انجام خواهد گرفت.
.1 مقدمه
امروزه فناوري محاسبات گرید، به عنوان مدل و رهیافتی نو جهت حل مسائل پیچیده و بزرگ در علوم، مهندسی، صنعت و تجارت مطرح شده است و هر روز بر تعداد برنامههاي کاربردي متفاوتی که از زیرساخت گرید بهمنظور تامین نیازهاي محاسباتی، ذخیرهسازي اطلاعات و سایر موارد بهرهبرداري میکنند، افزوده میشود.
مسائلی که توسط گرید حل میشوند معمولا مسائلی هستند که نیاز به حجم محاسباتی بالا و یا حجم زیاد داده و ذخیرهسازي دارند و ممکن است دادههاي ورودي مورد نیاز آنها در میان سایتهاي مختلف توزیع شده باشند. جهت حل این مسائل گرید، یک بستر محاسباتی ارائه میکند که در آن، قابلیتها و امکانات و کیفیت سرویس کلیه منابع و به خصوص منابع محاسباتی در کنار یکدیگر جمع شده است و دیدي از یک ماشین مجازي بسیار قدرتمند در اختیار برنامههاي کاربردي جهت اجرا قرار میگیرد.
منابع در دسترس یک گرید، به لحاظ جغرافیایی توزیعشده هستند و حتی ممکن است ناهمگن نیز باشند. منابع در سایتهاي مختلف قرار دارند و متعلق به سازمانها و نهادهاي متفاوت هستند و هر سازمان، سیاستهاي مدیریتی خود را بر نحوه به اشتراكگذاري و دسترسی به منابعش اعمال میکند.
از طرف دیگر محیط گرید یک محیط اختیاري و پویا است. بدین معنی که ماشینها و بهطور کلی کلیه منابع در دسترس گرید در طول زمان ممکن است تغییر کنند. بنابراین محیط گرید به لحاظ منابع تحت پوشش، محیطی بسیار پیچیده است. کاملاً واضح است مدیریت موثر منابع، امري حیاتی در سیستمهاي گرید محسوب میشود و به علاوه زمانبندي باید به بهترین شکل در این سیستمها انجام شود تا از یک طرف کاربران و برنامههاي کاربردي به بهترین نحو سرویس دریافت کنند و از طرف دیگر از کلیه منابع گرید، بهرهبرداري بهینه و حداکثر صورت گیرد.
محاسبات گرید یک فناوري جدید است که با استفاده از زیرساختهاي ارتباطی و شبکههاي کامپیوتري و نیز با بهکارگیري مفاهیم و امکانات سیستمهاي توزیع شده به کاربران امکان دسترسی به انواع مختلف منابع را بهصورت راه دور میدهد. امروزه تقسیمبنديهاي مختلفی براي گرید ارائه شده که آنها را به لحاظ محدوده جغرافیایی و سرویسدهی تقسیمبندي میکنند.
گرید دپارتمانی فقط جهت حل مسائل براي گروه خاصی از یک سازمان ایجاد میشود و منابع آن در اختیار سایرگروههاي سازمان قرار نمیگیرد. گرید سازمانی در سطح یک سازمان بزرگ توزیع شده و به کل کاربران سازمان سرویس میدهد و گرید فراسازمانی میان چند سازمان، شرکت و موسسه جهت پروژهها و نیازهاي مشترك بنا میشوند. گرید گسترده در سطح دنیا توسط سازمانها براي تسهیل کردن کارهایشان یا جهت سرویس دادن به کاربران مختلف بنا میشود.
استفاده از سیستمهاي گرید داراي مزایاي متعددي است. یکی از جذابترین ویژگیهاي گرید، توانایی آن در اجراي برنامهها بهصورت موازي و توزیع شده است.
ایده اصلی این دید این است که یک برنامه کاربردي تحت گرید به تعدادي بسیاري زیربرنامه شکسته شود و هر زیر برنامه روي یک کامپیوتر اجرا شود. از دیگر مزایاي محاسبات گرید این است که امکان ایجاد یک محیط همکاري بین گروه بزرگتري از افراد را به شکلی کاملاً عملی و ساده فراهم کند. سیستمهاي محاسباتی پیشرفته از سخت افزارهاي گرانقیمت براي افزایش قابلیت اطمینان و تحملپذیري در مقابل خطاها بهره میبرند درحالیکه سیستمها در گرید از نظر جغرافیایی بهگونهاي نسبتاً ارزان پراکنده شدهاند
کارها در سیستم گرید به چهار دسته کارهاي سخت، ذوبشونده، تکمیلشونده و چکشخوار تقسیم میشوند. کارهاي سخت کارهایی هستند که به تعداد ثابتی پردازنده در طول اجراي خود نیاز دارند. کارهاي ذوبشونده این قابلیت را دارند که تعداد پردازنده موردنیاز براي آن، قبل از شروع اجراي کار تعیین شود ولی به محض اینکه اجراي کار آغاز شد دیگر نمیتوان تغییري در تعداد پردازندههاي مورد استفاده ایجاد نمود. تعداد پردازنده موردنیاز براي یک کار تکمیل شونده در طول اجراي آن تغییر میکند. این نوع کارها عموماً به چند فاز مختلف در طول اجرا تقسیم میشوند بهنحوي که تعداد پردازنده مورد نیاز در هر فاز با فاز دیگر متفاوت است. تعداد پردازنده مورد استفاده در طول اجراي کارهاي چکشخوار میتواند تغییر کند و سیستم زمانبندي براي انجام این نوع کارها از انعطافپذیري بیشتري برخوردار است
مصرف انرژي در سیستمهاي با مقیاس بزرگ به علت افزایش هزینه و به دنبال داشتن مسائل اکولوژي یک موضوع بسیار مهم میباشد. به عنوان مثال، یک مرکز داده با مقیاس بزرگ مانند گوگل به اندازه یک شهر انرژي الکتریسیته مصرف میکند. مراکز داده تقریباً به اندازه ي 1/3 درصد مصرف انرژي الکتریسیته جهان را در سال 2010 مصرف کردهاند و برآورد میشود که این مقدار در سال 2020 به 8 درصد برسد.
در یکی از تحقیقات برآورد شده است که در یک مرکز داده با 50000 منبع محاسباتی بیش از صد میلیون کیلووات در سال انرژي برق مصرف میشود، که این مقدار معادل با مصرف برق یک سال شهري با جمعیت صد هزار نفر میباشد.
بنابراین برنامهریزي براي کاهش مصرف انرژي در این سیستمها بسیار اهمیت دارد. تکنیک مقیاسگذاري پویاي ولتاژ-فرکانس2از معروفترین تکنیکها براي کاهش مصرف انرژي در سیستمهاي محاسباتی میباشد. این تکنیک سطح ولتاژ و فرکانس یک دستگاه را به صورت پویا تنظیم میکند و مصرف انرژي را بهدلیل وجود رابطه مستقیم بین میزان مصرف انرژي و ولتاژ عملیاتی کاهش میدهد. با استفاده از این تکنیک، فرکانس عملیاتی سیستم پردازشگرها کنترل میشود و زمانی که کارها به سرعت کامل پردازنده نیاز ندارند، سرعت پردازنده را پایین میآورد.
پیشرفتهاي انجام گرفته در زیرساختهاي گرید باعث بهوجود آمدن مفهومی به نام کیفیت سرویس شده که عموماً بر روي سرویس و خدمات ارائهشده به مشتریان تعریف میشود. در مدلهاي کیفیت سرویس مشتريمحور هنگامیکه کاري براي پردازش به سیستم واگذار میشود مشتري یک تابع سود را براي آن کار پیشنهاد میدهد. این تابع سود نشاندهنده میزان شارژي است که مشتري در ازاي تکمیل شدن کار در هر لحظه از زمان مایل به پرداخت آن است. از سوي دیگر، سیستم زمانبندي گرید میتواند درباره رد یا قبول یک سفارش براساس تابع سود پیشنهادي مشتري تصمیمگیري کند.
در ادامه، در بخش 2 ادبیات موضوع مورد بررسی قرار میگیرد و در بخش 3 تعریف دقیق مساله ارائه خواهد شد. در بخش 4 یک مدل برنامهریزي ریاضی براي حل مساله پیشنهاد شده و راهکارهایی براي خطیسازي و بهبود کارایی آن توسعه مییابد. نتایج محاسباتی و تحلیل حساسیت در بخش 5 خواهد آمد و آخرین بخش نیز به نتیجهگیري و پیشنهاد براي مطالعات آتی اختصاص داده شده است.
.2 مرور ادبیات
در این قسمت پیشینه و پژوهشهاي مرتبط با موضوع مورد بررسی در این تحقیق بیان میشوند. در جدول 1 تعدادي از جدیدترین مقالات در حوزه سیستمهاي گرید بههمراه تابع هدف، معیار کیفیت سرویس، نحوه درنظر گرفتن مصرف انرژي و روش حل آنها آمده است.
با توجه به جدول 1 به تعداد 8 مقاله در کنار موضوع زمانبندي گرید مبحث انرژي و موعد تحویل بهعنوان معیار کیفیت خدمات را در نظر گرفتهاند و از بین این مقالات 5 مرجع براي کاهش مصرف انرژي از تکنیک مقیاسگذاري ولتاژ-فرکانس پویا استفاده کردهاند.
در مرجع [10] براي کاهش مصرف انرژي از تکنولوژيهاي مجازيسازي براي افزایش بهرهبرداري از ماشینهاي فیزیکی و کاهش تعداد کل ماشینهاي فیزیکی فعال استفاده شد. در مرجع [8] براي کاهش مصرف انرژي بر روي درجه موازيسازي کارها تمرکز شدهاست.
در مرجع [13] بهمنظور کاهش مصرف انرژي، تمام گرههاي کلاستر با بار کمتر از میزان تعیین شده بهصورت پویا به حالت آمادهباش3در میآیند. در مرجع [16] براي کاهش مصرف انرژي از تکینک مدیریت انرژي به صورت پویا استفاده شده است. در این روش اجزایی از سیستم را در زمانی که بیکار هستند بهطور انتخابی خاموش میکند و زمانی که به آنها نیاز دارد دوباره آنها را روشن میکند. در مراجع [9] و [11] سیستم زمانبندي با توجه به موعد تحویل و بودجه در دسترس براي هر کار، کارهایی که داراي بیشترین سود براي سیستم هستند را براي انجام دادن انتخاب میکند.
در مرجع [14] تضمین زمان به پایان رساندن انجام کارها بهعنوان معیاري براي کیفیت خدمات در نظر گرفته شده است. هزینه انجام کارها متناسب با زمان مورد انتظار مشتري براي به پایان رساندن کارهایش میباشد.
جدول :1 جدول مرور ادبیات
پژوهش حاضر مساله زمانبندي کارهاي مستقل بر روي منابع ناهمگن در محیط گرید محاسباتی را در نظر گرفته است. هدف مساله کاهش هزینه انرژي الکتریکی مصرفی منابع و افزایش درآمد حاصل از انجام کارها طبق کیفیت سرویس مشتريمحور میباشد. در اکثر مقالاتی که مقدار هزینه انرژي برق بهعنوان تابع هدف در نظر گرفتهاند میزان هزینه بهازاي تمامی دورههاي زمانی ثابت است.
درحالیکه قیمت برق در طول شبانهروز با توجه به ساعات کمباري، ساعات میانباري و ساعات اوج بار مصرف متغیر است. استفاده از نرخهاي وابسته به زمان استفاده از انرژي، باعث مدیریت هزینه انرژي میشود. بنابراین با توجه به منطقی و کاربردي بودن این فرض در محیط گرید، جهت واقعیتر کردن تابع هدف یعنی هزینه انرژي و در نهایت سود حاصل از انجام کارها، قیمت برق در طول شبانهروز متفاوت در نظر گرفته میشود که این فرض در هیچکدام از پژوهشهاي قبلی درنظر گرفته نشده است. همچنین دو تابع هدف کاهش هزینه انرژي الکتریکی طبق تکنیک
DVFS و افزایش درآمد حاصل از انجام کارها با توجه به کیفیت سرویس مشتريمحور بهصورت همزمان در پژوهشهاي قبلی در نظر گرفته نشده است.
.3 بیان مساله
این پژوهش مساله زمانبندي ایستا کارهاي مستقل بر روي منابع ناهمگن را در محیط گرید محاسباتی در نظر گرفته شده است. کارها از نوع سخت هستند و به تعداد مشخصی پردازشگر در طول اجراي خود نیاز دارند. براي پردازش هر کار تعداد مشخصی دستورالعمل باید انجام شود و زمان اجراي هر کار تنها وابسته به سطح فرکانس منبع و تعداد دستورالعمل پردازشی در آن کار میباشد. در این مساله کارها مستقل از هم درنظر گرفته شدهاند و روابط پیشنیازي یا پسنیازي بین کارها وجود ندارد. منظور از منابع، پردازشگرهاي کارها میباشد و در این مساله هستههاي واحد پردازشگر مرکزي بهعنوان منابع در نظر گرفته شدهاند.
همچنین منابع بهطور مستقل از هم به پردازش کارها میپردازند. منابع ناهمگن یا ناهمسان هستند و قابلیتهاي پردازشی و میزان حافظه متفاوت دارند و میتوانند در سطوح ولتاژ-فرکانس مختلف عمل کنند. با توجه به متفاوت بودن قابلیتها و ویژگیهاي هر منبع، میزان انرژي الکتریکی مصرفی هر منبع براي انجام کارها متفاوت خواهد بود. با توجه به اهمیت مصرف بهینه انرژي هم از لحاظ هزینههاي مربوط به آن و هم از لحاظ اثرات مخرب زیستمحیطی، در این پژوهش سعی شده با بکارگیري تکنیکهاي کاهش مصرف انرژي، مصرف انرژي تا حد امکان کاهش یابد. براي کاهش مصرف انرژي از تکنیک مقیاسگذاري ولتاژ-فرکانس پویا و در نظر گرفتن حالت آمادهباش براي منابع در زمان بیکاري استفاده شده است. انرژي الکتریکی مصرفی براي پردازش هر کار به سطح ولتاژ-فرکانسی بستگی دارد که منبع مربوطه روي آن تنظیم شده است و هزینه هر کیلووات ساعت انرژي الکتریکی طبق تعرفه در اوقات مختلف شبانهروز متفاوت خواهد بود.
براي افزایش رضایت کاربران سیستم و رسیدن به معیار کیفیت سرویس مشتريمحور، براي هر کار یک موعد تحویل از طرف مشتري تعیین میشود و براي کارهایی که دیرتر از موعد تحویلشان تکمیل شوند جریمه دیرکرد در نظر گرفته خواهد شد. بدین منظور براي انجام هر کار یک تابع هزینه مطابق با شکل 1 از سوي مشتري تعیین میشود که در آن حداکثر پرداخت براي انجام کار، موعد تحویل کار و میزان جریمه به ازاي هر واحد زمانی دیرکرد از سوي مشتري تعیین میشود. تامینکننده منابع یا سیستم زمانبندي در خصوص رد یا قبول اجراي کارها بر اساس تابع هزینه پیشنهادي مشتري تصمیمگیري میکند.
