پروژه دانشجویی مقاله پیاده سازی الگوریتم FLB فایل ورد (word)
پروژه دانشجویی مقاله پیاده سازی الگوریتم FLB فایل ورد (word) دارای 98 صفحه می باشد و دارای تنظیمات و فهرست کامل در microsoft word می باشد و آماده پرینت یا چاپ است
فایل ورد پروژه دانشجویی مقاله پیاده سازی الگوریتم FLB فایل ورد (word) کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه و مراکز دولتی می باشد.
این پروژه توسط مرکز مرکز پروژه های دانشجویی آماده و تنظیم شده است
توجه : توضیحات زیر بخشی از متن اصلی می باشد که بدون قالب و فرمت بندی کپی شده است
بخشی از فهرست مطالب پروژه پروژه دانشجویی مقاله پیاده سازی الگوریتم FLB فایل ورد (word)
فصل اول : مقدمه
1-1مفهوم گرید;;;;;;;;;;;;;;;;
1-2طبقه بندی گرید;;;;;;;;;;;;;;;
3-1 ارزیابی گرید;;;;;;;;;;;;;;;
1-4کاربردگرید;;;;;;;;;;;;;;;;;
1-5 تعریف زمانبندی گرید;;;;;;;;;;;;;
1-6 مروری بر تحقیقات گذشته;;;;;;;;;;;;
1-7 مفهوم اصطلاحات به کار برده شده;;;;;;;;;;
1-8 نمای کلی پایان نامه;;;;;;;;;;;;;
فصل دوم:زمانبندی کارها در سیستم های توزیع شده
2-1 زمانبندی کلاستر و ویژگیهای آن ;;;;;;;;;;
2-2 زمانبندی گرید و ویژگیهای آن;;;;;;;;;;
3-2 رده بندی الگوریتم های زمانبندی گرید;;;;;;;
2-3-1 زمانبندی محلی/سراسری;;;;;;;;;;;
2-3-2 زمانبندی ایستا/پویا;;;;;;;;;;;
2-3-3 زمانبندی بهینه/نزدیک به بهینه;;;;;;;;;
2-3-4 زمانبندی توزیع شده/مرکزی;;;;;;;;;;
2-3-5 زمانبندی همکار و مستقل;;;;;;;;;;
2-3-6 زمانبندی زمان کامپایل /اجرا;;;;;;;;
2-4-1 رده بندی الگوریتم های زمانبندی از دیدگاهی دیگری;
2-4-2 اهداف زمانبندی;;;;;;;;;;;;;
2-4-3 زمانبندی وفقی;;;;;;;;;;;;;
2-4-4 رده بندی برنامه های کاربردی;;;;;;;;;
2-4-4-1 کارهای وابسته;;;;;;;;;;;;
2-4-4-2 گراف کار;;;;;;;;;;;;;;
2-4-5 وابستگی کارهای تشکیل دهنده برنامه کاربردی;;;..
2-4-6 زمانبندی تحت قیود کیفیت سرویس;;;;;;;;
2-4-7 راهکارهای مقابله با پویایی گرید;;;;;;;
2-5 الگوریتم های زمانبندی کارهای مستقل;;;;;;;
2 -5-1 الگوریتم MET ;;;;;;;;;;;;;;
2-5-2 الگوریتم MCT ;;;;;;;;;;;;;;;.32
2-5-3 الگوریتم Min-min;;;;;;;;;;;;;;;
2-5-4 الگوریتم Max-Min ;;;;;;;;;;;;;;;;
2 -5-5 الگوریتم Xsuffrage ;;;;;;;;;;;;;;;
2 -5-6- الگوریتم GA . ;;;;;;;;;;;;;;
2-5-7- الگوریتم SA. ;;;;;;;;;;;;;;
فصل سوم:الگوریتم های زمانبندی گراف برنامه
3-1 مشکلات زمانبندی گراف برنامه;;;;;;;;;;;
3-2 تکنیکهای مهم زمانبندی گراف برنامه در سیستمهای توزیع شده;..40
3-2-1- روش ابتکاری بر پایه لیست ;;;;;;;;;;.. 40
3-2-2- روش ابتکاری بر پایه تکثیر;;;;;;;;;;..40
3-2-3- روش ابتکاری کلاسترینگ;;;;;;;;;;;;..41
3-3- دسته بندی الگوریتمهای زمانبندی گراف برنامه در سیستمهای توزیع شده;;;;;;;;
3-4- پارامترها و مفاهیم مورد استفاده در الگوریتمهای زمانبندی گراف برنامه;;;;;;;
3-5- الگوریتمهای زمانبندی گراف برنامه با فرضیات محدودکننده
3-5-1- الگوریتمی با زمان چند جملهای برای گراف های درختی – الگوریتم HU ;;;;;;
3-5-2- الگوریتمی برای زمانبندی گراف برنامه با ساختار دلخواه در سیستمی با دو پردازنده;;;.51
3-5-3- الگوریتمی برای زمانبندی گراف بازهای مرتب شده;;;;52
3-6- الگوریتمهای زمانبندی گراف برنامه در محیطهای همگن ;;;.54
3-6-1- الگوریتم Sarkar;;;;;;;;;;;;;;;;54
3-6-2- الگوریتمHLFET;;;;;;;;;;;;;;;;55
3-6-3- الگوریتم ETF;;;;;;;;;;;;;;;;55
3-6-4- الگوریتم ISH ;;;;;;;;;;;;;;;.56
3-6-5- الگوریتم FLB;;;;;;;;;;;;;;;;56
3-6-6- الگوریتم DSC;;;;;;;;;;;;;;;;57
3-6-7- الگوریتم CASS-II;;;;;;;;;;;;;;;.59
3-6-8- الگوریتم DCP;;;;;;;;;;;;;;;;60
3-6-9- الگوریتم MCP;;;;;;;;;;;;;;;;61
3-6-10- الگوریتم MD;;;;;;;;;;;;;;;..61
3-6-11- الگوریتم TDS.;;;;;;;;;;;;;;;.62
3-7- الگوریتمهای زمانبندی گراف برنامه در محیطهای ناهمگن;;;;;
3-7-1- الگوریتم HEFT;;;;;;;;;;;;;;;;63
3-7-2- الگوریتم CPOP;;;;;;;;;;;;;;;;..63
3-7-3- الگوریتم LMT;;;;;;;;;;;;;;;;
3-7-4- الگوریتمTANH ;;;;;;;;;;;;;;;;.65
فصل چهارم :الگوریتم FLB
1-4 ویژگیهای الگوریتم;;;;;;;;;;;;;.66
4-2 اصطلاحات به کار برده شده;;;;;;;;;;;
4-3 الگوریتم;;;;;;;;;;;;;;;;
4-4 پیچیدگی الگوریتم;;;;;;;;;;;;;
4-5 کارایی الگوریتم;;;;;;;;;;;;;
فصل پنجم: شبیه سازی گرید
5-1 ابزار شبیه سازی;;;;;;;;;;;..79
5-1-1- optosim;;;;;;;;;;;;;;;;..
5-1-2 SimGrid ;;;;;;;;;;;;;;;;..
5-1-3- Gridsim ;;;;;;;;;;;;;;;;..
کارهای انجام شده;;;;;;;;;;;;;;;..82
پیشنهادات;;;;;;;;;;;;;;;;;;;;
منابع ;;;;;;;;;;;;;;;;;;;;
بخشی از فهرست مطالب پروژه پروژه دانشجویی مقاله پیاده سازی الگوریتم FLB فایل ورد (word)
شکل 1-2 ساختار کلاستر ;;;;;;;;;;;;..11
شکل 2-2 ساختار زمانبند گرید ;;;;;;;;;;.
شکل 2-3-2 رده بندی الگوریتم های ایستا;;;;;;;..19
شکل 2-4 رده بندی برنامه های کاربردی;;;;;;;;.
شکل 2-5-6کلاس بندی برنامه های کاربردی ;;;;;;;..
شکل 3-2-3 گراف نمونه با هزینه محاسباتی و ارتباطی ;;;;.43
شکل 3-3 دسته بندی الگوریتم های گراف برنامه;;;;;;45
شکل 3-4 گراف کارها ;;;;;;;;;;;;;..50
شکل 3-5-3 گراف بازه ای مرتب شده با هزینه محاسباتی یکسان ;..53
شکل 3-5-3 مقایسه الگوریتم های زمانبندی گراف برنامه در محیطهای همگن ;;;;;;.
شکل 4-1 گراف کار;;;;;;;;;;;;;;.76
شکل 5-2 ساختار Gridsim ;;;;;;;;;;;;.
چکیده
پیاده سازی الگوریتم FLB
گرید محاسباتی مجموعه ای از منابع نا همگن و پویا که بوسیله یک شبکه به یکدیگر متصل می شوندو کاربران زیادی در مکان های مختلف آنها را به اشتراک می گذارند.اغلب برنامه های کاربردی بوسیله گراف جهت دار بدون سیکل خلاصه می شوندکه رئوس آن کارها و یالهای آن ارتباطات بین کارها را نشان می دهد. که در آن کارها وابسته هستند و بر اساس اولویت باید اجرا شوند به این معنی که در گراف تا والد یک کار انجام نشود فرزند یا فرزندان نباید انجام شوند
برای اینکه تمام این اصول رعایت شود و از منابع به صورت بهینه استفاده گردد از الگوریتم های زمانبندی استفاده می کنیم
در اینجا ما ابتدا به بررسی مفهوم گرید وفواید آن وسپس انواع زمانبندی در سیستم های توزیع شده و بررسی برخی از الگوریتم های زمانبندی در کارهای مستقل و وابسته می پردازیم و روشهای زمانبندی گراف برنامه وبعضی از الگوریتم های آنها در محیطهای ناهمگن وهمگن را معرفی می کنیم.سپس الگوریتمFLB راتشریح کردوشبیه ازهای گرید را بررسی می کنیم
واژه های کلیدی
گراف جهت دار بدون سیکل ، کارهای وابسته، زمانبندی ،گرید، تکثیر
فصل اول : مقدمه
قبل از ابداع کامپیوترهای شخصی، عملا سیستم های توزیع شده ای وجود نداشته است . در آن دوران ، استفاده از کامپیوتر، شامل نشستن پشت یک ترمینال و برقراری ارتباط با یک سیستم بزرگ بود. با اینکه ترمینال ها در چندین ساختمان و یا حتی محل فیزیکی قرار می گرفتند ، ولی عملا یک کامپیوتر مرکزی وجود داشت که مسئولیت انجام تمامی پردازش ها و ذخیره سازی داده ها را برعهده می گرفت
Mainfram معایب
هزینه سیستم های Mainfarme . یکی از اولین دلایل مهم ، هزینه های بالای سیستم های Mainframe است . این مسئله از دو زاویه متفاوت قابل بررسی است : هزینه بالای سرمایه گذاری اولیه که بسیاری از سازمان ها و موسسات توان مالی آن را ندارند و دوم اینکه در این مدل ، دارای صرفا” یک نقطه آسیب پذیر با ریسک بالا می باشیم
مالکیت اختصاصی داده ها. یکی از فاکتورهای مهم دیگر، سیاست های مربوط به مالکیت داده ها است . سازمان ها و موسسات که دارای داده های اختصاصی خود می باشند، علاقه مند به واگذاری مسئولیت مدیریت داده های مربوطه ، به سایر مکان های فیزیکی نمی باشند
· امنیت . یکی دیگر از فاکتورهای مهم در این زمینه موضوع امنیت است . برای یک سازمان ، اولا” دستیابی به اغلب داده های آن می بایست بسادگی محقق گردد و ثانیا” داده ها ی حساس موجود در سازمان می بایست از بعد امنیتی، ایمن نگهداری گردند . تامین دو خواسته فوق ( رویکردهای رقابتی و رویکردهای امنیتی ) با جدا سازی فیزیکی داده از یکدیگر محقق خواهد شد ( انباشت داده ها، با نگرش های متفاوت در رابطه با سرعت در دستیابی و ایمن در ذخیره سازی ، ضرورت وجود برنامه های توزیع شده را بخوبی نمایان می سازد )
مسائل فوق، ضرورت حرکت بسمت ایجاد یک الگوی جدید بمنظور طراحی برنامه های کامپیوتری را مطرح و بر همین اساس نسل جدیدی از برنامه های کامپیوتری با عنوان ” برنامه های توزیع شده” در عرصه نرم افزار بوجود آمد.که این برنامه ها به سیستم های توزیع شده نیاز دارد
یک برنامه توزیع شده، برنامه ای است که پتانسیل های پردازشی آن ممکن است توسط چندین کامپیوتر فیزیکی تامین و داده های آن در چندین محل فیزیکی، مستقر شده باشد
یک سیستم توزیع شده مجموعه ای از کامپیوتر هاست که دارای منابع اجرایی مختلف و زیادی هستند
1-1مفهوم گرید
در گرید هر شخصی می تواند به راحتی وارد یک شبکه شود و از توان محاسباتی موجود در شبکه استفاده کند.در شیوه های نوین به جای استفاده از رایانه های اختصاصی برای حل مسائل بزرگ ، با استفاده از رایانه های موجود پراکنده که از همه توان محاسباتی خود استفاده نمی کنند، سعی می شود با جمع آوری این توانهای پراکنده که اغلب بی استفاده می مانند، کارهای خود را انجام دهند. این منابع محاسباتی اگرچه اغلب قدرت و هماهنگی رایانه های اختصاصی را ندارند، اما تعداد زیادی از آنها به وفور در مراکز عمومی از قبیل دانشگاه ها، اداره ها، کتابخانه ها و غیره و حتی در منازلی که اتصال قوی به اینترنت دارند یافت می شوند و این موجب می شود که توان محاسباتی آن در مجموع بسیار بالا باشد و در عین حال هزینه آن به مراتب پایین تر می باشد
مخصوصاً اینکه هزینه های نگهداری به عهده مالکین منابع می باشد و مدیریت این سیستم صرفاً از منابع برخط در زمانبندی برنامه ها استفاده می کنند. با استفاده از گرید توان کامپیوتر ها دیگر بی معنا است ، صرف نظر از آن که کامپیوتر شما ضعیف و ابتدایی است ، می توانید به بیش از قدرت کامپیوتری دست یابید که هم اکنون در پنتاگون وجود دارد
یکی از مزایای مهم سیستمهای توزیع شده سرعت بالای اجرای برنامههاست چرا که یک برنامه همزمان می‌تواند از چندین کامپیوتر برای اجراء شدنش استفاده کند.[22]
همچنین به علت توزیع شدن اطلاعات, بانکهای اطلاعاتی حجیم می‌توانند روی یکسری کامپیوترهای شبکه شده قرار بگیرند. و لازم نیست که همه اطلاعات به یک کامپیوتر مرکزی فرستاده شود(که در نتیجه این نقل و انتقالات حجیم زمان زیادی به هدر می‌رود.(
به علت تأخیر‌های انتقال در شبکه و نویزهای احتمالی در خطوط انتقالی قابلیت اعتماد اجرای یک برنامه دریک سیستم تنها,بیشتر از قابلیت اجرای آن دریک سیستم توزیع شده است
همچنین درسیستم توزیع شده اگر یکی از کامپیوترهایی که وظیفه اصلی برنامه جاری را برعهده دارد خراب شود کل عمل سیستم مختل خواهد شد . از طرف دیگر اگر اطلاعاتی همزمان در چند کامپیوتر به صورت یکسان ذخیره گردد ویکی از کامپیوترها خراب شود, داده هارا میتوان از کامپیوترهای دیگر بازیابی کرد از این نظر امنیت افزایش مییابد
اشتراک به منابع محاسباتی محدود نمیشود. انواع منابع اعم از انبارهها،نرمافزار و بانکهای اطلاعاتی را در بر میگیرد. در عین حال، امنیت و سیاست محلی نیز تضمین میشود.[21]
بعد از اتصال به گرید، کاربر استخر بزرگی از منابع را در اختیار دارد. هنگامی که بار کاری سیستم محلی سنگین باشد، میتوان بخشی از بارکاری را به سایر منابع گرید منتقل کرد
2-1طبقه بندی گرید
گرید محاسباتی: شامل گرههایی است که محاسبات کارها را انجام میدهد. معمولا از گرید محاسباتی برای اجرای موازی برنامهها به منظور دست یافتن به کارایی بهتر استفاده میشود
گرید داده: شامل گرههایی است که امکان ذخیره و بازیابی حجم بالایی از دادهها را فراهم میکند. در چنین سیستمی، هم دادهها و هم کاربران توزیع شده اند. این سیستم با مشکلاتی از قبیل حجم بالای داده که ممکن است افراز شده باشد، تکرار در چندین سایت و ناسازگاری دادهها روبروست
گرید خدماتی: شامل گرههایی است که تقاضاها را به کمک سرویسهای از قبل موجود، پاسخ میدهند. زمانی که تقاضایی به چنین گرهای ارسال میشود، ابتدا تقاضا معنا میشود تا مشخص شود که تقاضا کننده، خواستار انجام چه سرویسی است و نهایتا نتیجه به متقاضی برگشت داده میشود
هرچند مرز مشخصی بین این سه دسته وجود ندارد، اما بحث ما معطوف به گریدهای محاسباتی است
انگیزه گرید محاسباتی، مجتمع کردن منابع توزیع شده ناهمگون جهت حل مسائل پیچیده علمی، صنعتی و تجاری است . جهت رسیدن به این هدف یک سیستم زمانبندی کارآمد به عنوان یک بخش حیاتی برای گرید لازم است . متاسفانه پویایی و ناهمگونی منابع گرید باعث پیچیدگی زمانبندی وظایف می شوند. بعلاوه با معرفی مدل اقتصادی گرید، علاوه بر زمان اتمام کار،
هزینه اجرای کار نیز به نگرانی های کاربران اضافه شد
1 – 3 ارزیابی گرید
سه مرحله برای ارزیابی گرید وجود دارد اول:تولید سیستم هایی که در اوایل 1990 متولد شد. دوم:تولید سیستم با تمرکز روی ابزار برای حمایت از معیار های بزرگ داده و محاسبه جریان الکتریکی . سوم: تولید سیستم هایی که برای همکاری جهانی بر تغییرات تاکیید دارد
اولین تولید فوریتی فرا محاسبه یا محیط های گرید نام گذاری شده است. عموما واقعیت این پروژه بهبود بخشیدن به منابع محاسباتی در یک دامنه کاربردوسیع بود. پروژه ارائه شده پیشگام این تکنولوژی [3]فافنر بود
نسل دوم گرید در نتیجه یک فوریت از یک زیر ساخت که قادر به بهم پیوند دادن بیشتر مرکزهای سوپر محاسباتی مشخص شده است. اکنون با ارتقا تکنولوژیهای شبکه وسازگاری آن با استانداردهای گرید می تواند به عنوان یک زیر ساخت توزیع کننده ممکن و قابل قبول در مقیاس های بزرگ که محاسبات را می خواهند حمایت کنند. در این نوع گرید به طور معمول طبیعت نا همگون منبع ها و بهبود بخشیدن کاربرد ها با محیط همگون ویکنواخت را با مجموعه ای از واسط های استاندارد پنهان می کند.گلو باس [20]یکی از پروژه های توزیع شده است که برای اینکه گرید را استوار کند
نسل سوم:سازگاری و انطباق زیادی از مدل های خدمات هدفمند وجود دارد . یک حالت قوی از اتوماسیون در سیستم های این نسل وجود دارد . برای مثال زمانی که انسانها نمی توانند برای مدت طولانی مقیاس و ناهمگونی منابع را ارتباط دهند اما ارسال برای پردازش انجام می شود که باعث خود گردانی درون سیستم ها می شود
4-1 کاربردهای گرید
اخیرا تلاش زیادی برای انتقال دادن برنامه های کاربردی به گرید صورت گرفته است.یک مثال پروژه EGEE است. هدف های آن بهبود بخشیدن کار محققان در دانشگاه و صنعت با دسترسی به منبع های محاسباتی اصلی و مستقل از محل جغرافیایی آنها است.تمرکز روی تعداد زیادی از کاربران گرید است.دو کاربرد برای پیدا کردن تایید اجرا و کارایی زیر ساختها انتخاب شده است یکی محاسبه برخوردها با پشتیبانی از انرژی فیزیکی بالا در آزمایشات فیزیک ودیگری گرید های پزشکی که چندین گروه به طور یکسان با مشکلات سیل عظیم اطلاعات و داده های مراقبت از سلامت روبه رو هستند.[14]
نمونه : تلسکوپ جادوگر(majic)
تلسکوپ طراحی شده برای جستجو در آسمان تا منابع انرژی گاما را مشاهده و کشف کند و اطلاعات فیزیکی زیادی را بررسی کند
آن بزرگترین تلسکوپ اشعه گاما در جهان است و چندین تلسکوپ دیگر در کشورهای اروپایی به آن در جمع آوری اطلاعات کمک می کنند.توزیع جغرافیایی منابع مدیریت آنها را مشکل می کند و این یک نمونه برای گرید محاسباتی است که می تواند کمک بزرگی بکند زیرا محققان می تواند به طور یکسان به تمام منابع دسترسی داشته باشند. تلسکوپ در شبهای اول ماه کار می کند و حدود 600 گیگا بایت اطلاعات در شب ثبت می کند داده های اضافی تلسکوپ و اطلاعات هوا شناسی نیز ذخیره می شوند.تمام این داده ها باید دریافت و آنالیز شوند.[11]
نمونه رایج استفاده از گرید در هواشناسی است.که در آن ایستگاه تلوزیون و شرکت ماهواره ای و مر کز تجسم و یک کامپیوتر مرکزی وجود دارد که ایجاد امنیت و ارتباطات آنها در محیط گرید فراهم می شود
قدرت گرید بخصوص در پردازش های فشرده مثل تحقیقات علمی و نمونه های مالی و طراحی های صنعتی و نمودار پرداخت تصویر مفید تر است
1-5 تعریف زمان بندی گرید
زمانبند، مدیر منبعی میانی است و واسطی است بین مصرف کنندهها و منابع
در محیطهای توزیع شده، گروهی از کاربران برنامههای خود را برای اجرا به مجموعه ای از منابع میفرستند. سیستم زمانبند چنین محیط توزیع شدهای، مسئول مدیریت منابع و برنامههاست. سیستم زمانبند بایستی بتواند منابع مناسبی به برنامهها اختصاص داده و اهداف کارایی را نیز برآورده سازد. سیستم زمانبند محیطهای محاسباتی موازی سنتی به دلیل خصوصیات یکسان برنامهها وخصوصیات یکسان منابع، ساده تر است. در فرهنگ لغت GGF [1]، مراحل زمانبندی گرید به شرح زیر بیان شده است: کشف منبع در دسترس برای برنامه، انتخاب سیستم یا سیستمهای مناسب آن و پذیرش برنامه. به طور خلاصه میتوان گفت زمانبندی گرید، قالبی است نرمافزاری که اطلاعات وضعیت منابع را جمع نموده، منابع مناسب را نامزد نموده، کارایی هر نامزد را پیش بینی نموده و بهترین منبع را تعیین میکند
1-6 مروری بر تحقیقات گذشته
طیف وسیع کاربران گرید دارای برنامههایی با نیازمندیهای متفاوت هستند. ممکن است برنامههای آنان دستهای و یا به خط[2] باشد، شامل کارهای وابسته به هم و یا مستقل باشد. به همین دلیل، ارائه الگوریتم زمانبندی همه منظوره که بتواند برای تمامی سناریوها مناسب باشد، امکانپذیر نیست. از این رو ما بحث خود را به زمانبندی کارهای وابسته، معطوف نموده ایم. هنگامی که کارهای تشکیل دهنده برنامه دارای ترتیب تقدمی باشند، برنامه، به شکل گراف جهتدار بدون سیکل (DAG[3]) مدل میشود که در آن گرهها نشان دهنده کارها و لبهها نشان دهنده ترتیب گرههاست. گاهی اوقات وزنی نیز به گرهها و لبهها اضافه میشود که به ترتیب نشان دهنده هزینههای محاسباتی و هزینههای ارتباطی است. ایجاد تعادل بین به حداکثر رساندن موازی سازی و به حداقل رساندن تاخیر ارتباطی به عنوان مسئله مهمی در زمانبندی کارها مطرح است. برای زمانبندی گراف برنامه، الگوریتمهای ابتکاری[4] متعددی مطرح شده است. برای زمانبندی گراف برنامه، الگوریتمهای ابتکاری[5] متعددی مطرح شده است. این الگوریتمها را میتوان به سه دسته کلی تقسیم کرد. الگوریتمهای بر پایه لیست[6]، الگوریتمهای بر پایه تکرار[7] و الگوریتمهای کلاسترینگ[8].
در روش بر پایه لیست به هر کار، اولویتی داده میشود و کارها به ترتیب اولویت در لیست قرار میگیرند. اولویت باید به گونهای تعیین شود که ترتیب تقدمی کارها، نقض نشود. انتخاب کار برای پردازش به ترتیب اولویت انجام میگیرد و کار با اولویت بالاتر زودتر به منبع واگذار میشود. تفاوت اصلی الگوریتمهای این دسته، در چگونگی تعریف اولویت و تعریف آماده بودن کار برای واگذاری است.
یکی از روشهای کم کردن زمان اجرای گراف برنامه، تکثیر کارها در منابع مختلف است. ایده اصلی الگوریتمهای بر پایه تکرار، بهرهوری از زمان بیکاری منابع است. تکثیر یک کار در چندین منبع، باعث اجتناب از انتقال نتایج از کار قبلی به کار بعدی شده و به همین دلیل هزینه ارتباطی را کاهش میدهد. الگوریتمهای مختلف این روش، بر اساس نحوه گزینش کار برای تکثیر، از هم متمایز میشوند. این الگوریتمها دارای پیچیدگی بالاتری نسبت به الگوریتمهای ابتکاری لیست هستند
در سیستمهای موازی و توزیع شده، کلاسترینگ روش مناسبی برای کاهش تاخیر ارتباطی گراف به حساب میآید. در این روش کارهایی که ارتباط زیادی باهم دارند در یک کلاستر قرار میگیرند و اعضای یک کلاستر به یک منبع واگذار میشوند و بدین شکل، تاخیر ارتباطی کاهش مییابد.
1- 7 مفهوم اصطلاحات بکاربرده شده در این پایان نامه
ü application: مجموعهای از کارهای وابسته و یا مستقل است که به حل مسئله معینی منتهی میشود. در این تحقیق از واژه فارسی “برنامه” به جای واژه ” application ” استفاده شده است. در این تحقیق واژه job نیز معادل واژه application تلقی شده است
ü task : واحد کار application گرید به شمار میآید که میتوان آن را برای اجرا فقط به یک منبع محاسباتی فرستاد . در این تحقیق از واژه فارسی “کار” به جای واژه ” task ” استفاده شده است
ü scheduling: به فرایند کشف منبع، انتخاب منبع و ارسال کار به منبع گفته میشود . در این تحقیق “زمانبندی” ترجمه شده است
DAG: برنامه حاوی چندین کار موازی، به شکل گراف جهتدار بدون سیکل “DAG” مدل میشود. از این واژه با عنوان گراف برنامه و یا به اختصار گراف یاد شده است
1- 8 نمای کلی پایان نامه
در فصل اول (فصل جاری)، مفاهیم و تعاریف پایه بیان شده است. مفهوم گرید و مسئله زمانبندی تبیین شده، روشهای موجود زمانبندی گراف برنامه به طوراجمال بیان شده است
در فصل دوم، به بحث زمانبندی در سیستمهای توزیع شده پرداخته شده و موانع
زمانبندی گرید ذکر شده و الگوریتمهای موجود، مطرح و مقایسه گردیده است
در فصل سوم، موضوع زمانبندی گراف برنامه در سیستمهای توزیع شده، مورد بحث و بررسی قرار گرفته، پارامترها و عناصر تاثیرگذار بر الگوریتمها بیان شده است
در فصل چهارم الگوریتم flb را بیان نموده که می خواهیم آن را پیاده سازی کنیم ودر فصل پنجم شبیه سازهای گرید رامورد بررسی قرار می دهیم.در انتها نیز کارهای انجام شدهو نتایج بدست آمده و پیشنهادات رامطرح می کنیم
فصل دوم: زمانبندی کارها در سیستمهای توزیع شده
2-1- زمانبندی کلاسترها و ویژگیهای آن
کلمات کلیدی :
» نظر