مقدمه:

از مهم ترین مسائل در زمینه سیستم های محاسباتی توزیع شده ،مسـاله تخصـیص مجموعـه ای ازکارها به مجموعه ای از پردازنده ها در جهت ایجاد توازن بار و مینیمم کردن هزینه کل سیستم مـیباشد.[4-1] ،[18-17]،[27-25] مساله تخصیص کارها در محیط های محاسباتی توزیع شـده کـهبه منظور بدست آوردن بهره وری موثر از منابع سیستم و همچنین درجـه بـالایی از مـوازی سـازیانجام می شود، عبارت است از تخصیص یک برنامه کامپیوتری شامل مجموعه ای از کارها که با هـمدر ارتباط و همکاری می باشند، به مجموعه ای از کامپیوترها یا پردازنده ها در سیستم توزیع شـده،با در نظر گرفتن مجموعه ای از محدودیت ها روی منابع (پردازنده ها، کانال های ارتبـاطی و غیـره) می باشد. هدف نهایی این تخصیص بهینه سازی هزینه های کلی سیستم شامل هزینه های اجرایـی و ارتباطی می باشد. برای این منظور یک تابع هزینه مناسب برای مساله تخصیص کارهـا در محـیطهای محاسباتی توزیع شده تعریف می شود و هدف بهینه سازی این تابع هزینه بـا در نظـر گـرفتنمحدودیت های منابع موجود در سیستم (پردازنده ها و کانال های ارتباطی) می باشد. مباحث ارائـهشده در این نوشتار به بخش های زیر تقسیم می شود.
در فصل اول مجموعه کارهای سیستم به صورت یک گراف نشان داده می شود و برای تخصیص ایـنمجموعه کار به مجموعه پردازنده های سیستم که دارای اتصال کامل می باشـند، از الگـوریتم هـای ماکزیمم جریان استفاده می شود. در فصل دوم توابع اکتشافی برای خوشه بندی و تخصیص مجـددکارها از پردازنده های سربار به پردازنده های زیر بار مورد بررسی قرار می گیرد. در فصل سـوم یـکمدل ریاضی برای مساله تخصیص کار در سیستم های توزیع شده ارائه می گردد و تابع هزینه بـرایاین منظور تعریف می شود و جواب تخصیص بهینه با به کار بردن الگوریتم شـاخه و قیـد پیـدا مـیشود. در فصل چهارم از راهکار مبتنی بر تطابق گراف برای مسـاله تخصـیص کـار در سیسـتم هـایمحاسباتی توزیع شده بهره برده می شود. مساله تخصیص کار به صورت یک نگاشت از مجموعه کـاربه مجموعه پردازنده تعریف می شود و از الگوریتم معروف *A برای یافتن تخصیص بهینـه اسـتفادهمی شود. فصل پنجم چندین تابع اکتشافی را برای بهبود الگوریتم *A فصل قبل، پیشنهاد می کنـدکه کارایی خیلی خوبی را نشان می دهند. در فصل ششم از الگوریتم ژنتیک مبتنی بر فضای مسـالهبرای مساله تخصیص کار استفاده می شود. این الگوریتم در هـر دو حالـت پردازنـده هـای همگـن وپردازنده های ناهمگن مطرح می گردد. فصل هفتم دسته بندی کلی از الگوریتم های تخصـیص کـاررا نشان می دهد. همچنین از الگوریتم *A و نسخه موازی آن برای یـافت ن جـواب تخصـیص بهینـهبهره می برد. در فصل هشتم مساله تخصیص کار در سیستم های محاسباتی توزیـع شـده بـا فـرضاینکه هر کار از چندین ماژول تشکیل شده است، مورد بررسی قرار می گیرد. در این فصل برای هـرکار برای اجرا یک حافظه مصرفی در نظر گرفته می شود و محدودیت حافظه هر پردازنـده سیسـتمنیز لحاظ می شود. همچنین یک تابع هزینه یافته در این فصل معرفی می گردد. فصـل نهـم مسـالهفصل هشتم را با راهکار الگوریتم ژنتیک مورد بررسی قرار می دهد.
در پایان در فصل دهم مدل های متفاوت مساله تخصیص کـار در سیسـتم هـای محاسـباتی توزیـعشده مورد بررسی و تعریف قرار می گیرد.

توازن بار در سیستم های محاسباتی توزیع شده

توازن بار در سیستم های محاسباتی توزیع شده

برای دانلود رایگان قسمت های بیشتراز فایل به انتهای مطلب مراجعه کنید

فهرست مطالب

چکیده………………………………………………………………………………………………………………………………1

مقدمه……………………………………………………………………………………………………………………………. 2

فصل اول: الگوریتم های جریان شبکه برای مساله تخصیص کار

مساله زمانبندی کارها روی مجموعه ای از پردازنده ها به منظور کاهش هزینه کـل سیسـتم توسـطStone در سال 1977مورد بررسی قرار می گیرد. [6] در این فصل ایـن مسـاله از دو دیـدگاه کـلهزینه های اجرایی کارها روی تمام پردازنده ها و کل هزینه های بین کارهای متفاوت روی پردازنده های مجزا مورد بررسی قرار می گیرد. در سیستم های چند پردازنده ای با اتصال ضعیف6 از آنجـاییکه ارتباطات بین پردازنده ای زیاد است، تقسیم کردن یـک برنامـه اجرایـی بـه چنـدین قسـمت وتخصیص هر چند قسمت به یک پردازنده کار زیاد منطقـی نیسـت. ولـی در ایـن مقالـه از معمـاریکامپیوتری چند پردازنده ای دانشگاه Brown استفاده شده است، که به صورت اتصال متوسط7 می باشد. در این معماری جابه جا شدن قطعات یک برنامه بین پردازنـده هـا در زمـان تخصـیص یـا در زمان اجرای برنامه ممکن می باشد. این توانایی باعث می شود که بهترین استفاده از منابع سیسـتمدر انجام عملیات محاسباتی صورت گیرد.
مساله مورد نظر تخصیص کارهای یک برنامه به پردازنده ها در جهت می نـیمم کـردن کـل هزینـههای حاصل از ارتباطات بین کارها و هزینه های اجرایی کارها روی پردازنده های متفاوت می باشـد .
در این فصل از الگوریتم [12] و اصلاح شده آن در [9] برای پیدا کردن ماکزیمم مقـدار جریـان دریک شبکه برای پیدا کردن تخصیص بهینه کارها اسـتفاده مـی شـود. ابتـدا مسـاله بـرای حالـت دوپردازنده ای حل می شود و بعدا برای سه پردازنده ای و بیشتر تعمیم داده می شود. به عنوان مثـالشبکه داده شده در شکل 1-1 را در نظر بگیرید. گره های 2S1,S و 3S به عنـوان گـره هـای مبـدا وگره های 5S4,S و 6S به عنوان گره های مقصد می باشند. اعداد نشان داده شده روی یال ها معـرفمیزان ظرفیت آن شاخه از شبکه می باشد. هدف انتقال ماکزیمم مقدار جریان از گره های مبـدا بـهگره های مقصد با در نظر گرفتن ظرفیت یال های میانی می باشد.
Loosely Coupled ۶ Intermediate Coupled ٧
به عنوان مثال شکل داده شده در شکل 1-2 یک شبکه جریان را برای شبکه شکل 1-1 نشـان مـیدهد. هر کمان جهت دار در این شبکه حامل دو عدد می باشد که عدد اولی نشـان دهنـده ظرفیـتآن شاخه و عدد دومی نشان دهنده مقدار جریان واقعی روی آن می باشد. یک جریان امکـان پـذیردر این شبکه شروع شده از گره های مبدا و ختم شده به گره های مقصد می باشد به طوری که: 1) در هر گره میانی، مجموع جریانهای ورودی به گره برابر با مجموع جریانهای خروجی مـی باشـد. 2) در هر گره مقصد جریان شبکه وارد شده به آن منفی می باشـد و در هـر گـره مبـدا جریـان شـبکهخارج شده از آن منفی می باشد. 3) جریان شبکه در هر شاخه از شبکه از میزان ظرفیت آن شـبکهتجاوز نمی کند. طبق این تعریف جریان شبکه در شکل 1-2 امکان پذیر می باشد.
مقدار جریان شبکه مجموع جریان های خارج شده از گره های مبدا یا به عبارتی دیگر وارد شده بـهگره های مقصد می باشد. به عنوان مثال مقدار جریان شبکه برای شبکه شکل 1-2 بربر بـا 18 مـیباشد. ماکزیمم جریان برابر با یک جریان امکان پذیر است که بیشترین مقدار جریان را از بین همـهجریانهای امکان پذیر در شبکه دارد. شکل 1-3 ماکزیمم جریان را برای شبکه شکل 1-1 نشان مـیدهد. یک مجموعه برشی 8 از یک شبکه یک مجموعه ای از یال ها است به طـوری کـه حـذف آنهـاباعث قطع شدن ارتباط بین گره های مبدا و مقصد می شـود . هـیچ زیـر مجموعـه درسـتی از یـکمجموعـ ه برشـ ی خـ ودش یـ ک مجموعـ ه برشـ ی نیسـ ت . بـ

3 نشان می دهند. وزن یک مجموعه برشی برابر با مجموع ظرفیت های یال های آن مجموعه برشی می باشد. بـرای گـرافشکل 1-3 این وزن برابر با 24 یعنی همان ماکزیمم مقدار جریان شـبکه مـی باشـد. ایـن تصـادفینیست، زیرا طبق قضیه زیر داریم:

: یک مثال از شبکه جریان

1-1: سیستم توزیع شده با دو پردازنده ……………………………………………………………………………………… 7
1-2: سیستم توزیع شده با سه پردازنده …………………………………………………………………………………… 9
1-3: تعمیم مساله به حالت بیشتر از سه پردازنده ………………………………………………………………………. 11
1-4: محدودیت های الگوریتم ……………………………………………………………………………………………….. 13

فصل دوم: توابع اکتشافی برای خوشه بندی و تخصیص مجدد کارها

در این فصل بعضی توابع اکتشافی برای تخصیص کار در سیسـتم هـای محاسـباتی توزیـع شـده درجهت ایجاد توازن بار مورد بررسی قرار می گیرد. [11] یک سیستم پردازشی توزیع شده دارای تناقض های زیر می باشد:
1) درحالی که بهینه کردن IPC سعی در تخصیص کل یک کـار بـه یـک پردازنـده را دارد، راهکـارتوازن بار سعی دارد تا حد ممکن این کار را بین پردازنده های سیستم توزیع کند.
2) درحالی که یک محدودیت بلادرنگ16 تاحد ممکن تعدادی پردازنده را برای افزایش اجرای موازی به کار می برد، روابط اولویت بین کارها اجرای موازی را محدود می کند.
3) اثر اشباع17 استفاده از تعداد کمتر پردازنده را پیشنهاد می کند به دلیـل اینکـه عـدم کـارایی بـاافزایش تعداد پردازنده، افزایش می یابد.
واضح است که ارضای همه این نیازمندی ها به طور همزمان غیر ممکن می باشد. بنابر این باید یک مصالحه برای پیدا کردن تخصیص بهینه یک کار ایجاد شود. راهکارهای متفاوتی بـرای حـل مسـالهتخصیص کار پیشنهاد شده اند و به سه دسته 1) تئوری گراف 2) برنامـه نویسـی ریاضـی 3) توابـعاکتشافی تقسیم می شوند.
در اینجا یک تابع اکتشافی جدید برای این مساله پیشنهاد می شود. در ابتـدا یـک الگـوریتم خوشـهبندی ماژول ها18 (MCA) بدون توجه به محدودیت ها، یک هزینه IPC بهینـه را بـه دسـت مـیآورد. نتیجه این الگوریتم ممکن است همچنین محدودیت توازن بار را ارضا کند. اگر چنـین نباشـد،پردازنده های زیر بار19 و سربار20 شناسایی می شوند. سپس بعضـی از مـاژول هـا از پردازنـده هـایسربار به پردازنده های زیر بار با استفاده از الگوریتم تخصـیص مجـدد مـاژول21 (MRA) ، شـیفتداده می شوند. اگر تعداد زیادی از ماژول ها به وسیله MRA شیفت داده شوند که باعث شود یـکپردازنده ای که قبلا زیر بار بوده است سربار شود، این الگوریتم تا زمانی که جواب به یک توزیـع بـارمتوازن همگرا شود، تکرار خواهد شد.
در اینجا یک شمایی از الگوریتم تخصیص ماژول پیشنهاد می شود. الگوریتم های MCA و MRA و یک روش برای تشخیص پردازنده های سربار و زیر بار در جلوتر ارائه خواهد شد. بـرای لحظـه ایدر نظر بگیرید که این الگوریتم ها در دسترس هستند، یک عبارت رسمی تر از اسـتراتژی تخصـیصماژول پیشنهاد شده در دو مرحله زیر داده شده است:

2-1: الگوریتم MCA …ا……………………………………………………………………………………………………….. 17
2-2: الگوریتم MRA ….ا………………………………………………………………………………………………………. 19

فصل سوم: مدل ریاضی مساله تخصیص کار

در این فصل یک مدل برای تخصیص کارها در سیستم محاسباتی توزیع شده ارائـه شـده اسـت کـهشرایط زیر را ارضا می کند.[17]
1) مینیمم کردن هزینه های ارتباطی بین فرآیندی 2) متوازن کردن بـار محاسـباتی روی پردازنـدهها 3) ارضا کردن همه نیازمندی های کاربردی
پیشرفت سریع تکنولوژی کامپیوتر باعث استفاده مقرون به صرفه سیسـتم هـای کـامپیوتری توزیـعشده از لحاظ اقتصادی شده است. با این حال هنوز بعضی مشکلات در رابطه با سیستم هـای توزیـعشده در مراحل اولیه توسعه خود قرار دارنـد .[22،24] مهمتـرین ایـن مسـائل عبارتنـد از 1) تنـزلکارایی در سیستم به دلیل “اثر اشباع”٢۶[۵٢]: یک اثر اشباع در اثر ترافیک بالا در سیسـتم توزیـعشده ، وقتی که داده های زیادی بین فرآیندهای قرار گرفته روی پردازنده های مجزا رد و بـدل مـیشود به وجود می آید. این ترافیک بین پردازنده ای همیشه پر هزینـه تـرین و کـم اطمینـان تـرینعامل در سیستم های با اتصال ضعیف می باشد.[22،6] یک نتیجه نامطلوب این اثر اشباع ، کـاهشبازدهی سیستم در نتیجه افزایش تدریجی استفاده از منابع سیستم می باشد. 2) مشـکل تـوازن بـارروی پردازنده ها: برای کاهش اثر اشباع می توان کارهای با هزینه ارتباطی سنگین را روی پردازنـدههای یکسان اجرا کرد تا اینکه هزینه کل سیستم کاهش یابد. که این خود باعث عدم توازن بـار رویپردازنده ای و در نتیجه کاهش بازدهی سیستم می شود. 3) فاصله27 زیاد بین نیازمندی کاربردهـا 28 و معماری سیستم های توزیع شده موجود: برنامه های کاربردی تعریف شده بوسیله طراحان، اغلـببه صورت بهینه داخل معماری سیستم توزیع شـده نگاشـت29 نمـی شـود. 4) مشـکل بـودن اعتبـارسنجی نتایج تخصیص کارها در هر مدل تخصیص کار: به دلیل کمبود داده های واقعی، بیشتر نتایج تحقیق در زمینه تخصیص کار محدود به مدل های ریاضی و تئوری می شود.
چندین راهکار در رابطه با مدل های تخصیص کارها ارائه شده اسـت . ایـن راهکارهـا شـامل تئـوریگراف ، برنامه ریزی صحیح30 و روش های اکتشافی31 می باشند. در روش مبتنـی بـر گـراف از یـکگراف برای نمایش کارها در سیستم استفاده می شود و هدف آن مینیمم کردن کل هزینـه سیسـتمبا به کار بردن الگوریتم مینیمم برش می باشد که در فصل هـای قبلـی مـورد بررسـی قـرار گرفـت.
مشکل آن در پیچیدگی زمانی بالا بـرای تعمـیم آن بـه بیشـتر از سـه پردازنـده و در نظـر نگـرفتنمحدودیت های سیستم می باشد. روش برنامه ریزی صحیح محدودیت های سیستم را در نظـر مـیگیرد ولی دارای پیچیدگی نمایی از لحاظ زمان پردازشی و میزان حافظه مصرفی می باشـد . در ایـنفصل از یک تکنیک مبتنی بر برنامه نویسی صفر و یـک بـه نـام شـاخه و قیـد32 بـرای پیـدا کـردن
تخصیص بهینه با در نظر گرفتن محدودیت های سیستم، استفاده می شود. همچنـین بـرای اثبـاتاعتبار آن، این الگوریتم روی یک مدل سیستم هوایی شامل 23 کـار دارای 3 پردازنـده تسـت شـدهاست که کارایی خوب را در مقیاس های بزرگ نشان می دهد.
3-1: ارائه یک مدل ریاضی برای مساله تخصیص کار
یک مدل تخصیص کارهایی که بتواند 3 شرط ذکر شده در بالا را برآورده کند، باید دارای سـاختاریمشابه شکل 3-1 به همراه توابع پشتیبانی باشد. پردازنده کار33، کارهای کاربردی موجود در سیستم را تحلیل می کند تا اطلاعاتی در رابطه با فاکتورهای اتصال34 بین کارها و اندازه خواص آنها را جمع آوری کند. عامل اتصال بین کارها به وسیله تعداد واحدهای داده ای انتقال یافته از یک کار بـه کـاردیگر اندازه گیری می شود. واحد داده بستگی به کار مورد نظر دارد و ممکن است که کلمه، بایت یـابیت باشد. خواص کارها شامل مشخصات ذاتی آنها مثل تعداد جملات قابل اجرا یـا مـاکزیمم زمـاناجرایی می باشد. پردازنده شبکه35 اطلاعاتی در مورد معماری شبکه که شامل فاصله بـین پردازنـدهای36 و محدودیت های پردازنده37 می باشد را تامین می کند. فاصله بین پردازنده ای منظور همـانفاصله فیزیکی بین پردازنده ها می باشد که در بردارنده هزینه ای از قبیل زمان یا پول می باشد. هر پردازنده دارای محدودیت های سخت افزاری مخصوص به خود می باشد که خواص پردازنده نامیـدهمی شود و می تواند شامل مواردی مثل نرخ MIPS38 ، فضای ذخیره سازی و غیـره باشـد. بـا ایـنفرض که همه اطلاعات در مورد کارها و پردازنده های موجود در سیسـتم توسـط دو پردازنـده ذکـرشده (پردازنده کار و پردازنده شبکه) تامین شده باشد، در این مقاله یک مدل برای تخصـیص کارهـاارائه می شود.

3-1: ارائه یک مدل ریاضی برای مساله تخصیص کار …………………………………………………………………… 27
3-2: تابع هزینه برای مساله تخصیص کار ……………………………………………………………………………….. 28
3-3: الگوریتم شاخه و قید …………………………………………………………………………………………………. 30
3-4: محدودیت های الگوریتم ……………………………………………………………………………………………… 32

فصل چهارم: راهکار مبتنی بر تطابق گراف برای تخصیص کار در سیستم های محاسباتی توزیع شده

در این فصل مساله تخصیص کار بهینه در جهت ایجاد توازن بار با اسـتفاده از راهکـار تطـابق گـرافمورد بررسی قرار می گیرد. [4]
الگوریتم های تخصیص کار در سیستم های محاسباتی توزیع شده معمـولا بـه 3 دسـته مبتنـی بـرتئوری گراف، برنامه ریزی ریاضی و روش های اکتشافی تقسیم می شوند. در روش گراف با اسـتفادهاز مینیمم برش تخصیص با کمترین هزینه میان پردازنده ای پیدا می شود. در برنامه ریـزی ریاضـیمساله تخصیص کار به یک مساله بهینه سازی تبدیل شده و با استفاده از فرمول هـای ریاضـی حـلمی شود. در روش های اکتشافی جواب های سریع ولی نه لزومـا بهینـه پیـدا مـی شـوند کـه بـرایکاربردهایی مفید است که در آن یک جواب بهینه برای مساله در زمان واقعی بدست نمی آید.
تابع هزینه در هر کدام از الگوریتم های ذکر شده به صورت مجموع هزینه های بـین پردازنـده ای وهزینه پردازشی می باشد. اما این دو هزینه واحدهای اندازه گیری متفاوتی دارند. در این فصـل یـکمدل جدید مبتنی بر تطابق گراف با تابع هزینه دارای یک واحد اندازه گیری یعنی زمان مطرح مـیشود. هر تطبیق گراف متناسب با یک تخصیص کار می باشد و مینیمم کردن تابع هزینه بـر اسـاسیک معیار minimax می باشد و از یک روش جستجوی مبتنی بر فضای حالت برای بدست آوردن جواب بهینه استفاده می شود.
فرضیات در باره سیستم محاسباتی توزیع شده مورد بحث در این فصل به صورت زیر می باشد:
1) پردازنده های سیستم ناهمگون می باشند، یعنی هر ماژول یک برنامـه اگـر روی پردازنـده هـایمتفاوت اجرا شود، هزینه های اجرایی متفاوتی خواهد داشت.
2) لینک های ارتباطی غیر یکسان توسط پردازنده ها برای انتقال پیام استفاده می شود. یعنـی یـکمیزان یکسانی از پیام اگر روی لینک های ارتباطی متفاوتی منتقل شود زمان های انتقـال متفـاوتیخواهد داشت.
3) نیازی نیست که پردازنده های سیستم دارای ارتباط کامل64 باشند، ولی ارتباط بین دو پردازنـدهمتقارن می باشد. یعنی زمان مورد نیاز برای انتقال پیام در هر دو جهت یکسان می باشد.
4) مقدار کم یا هیچ ارتباط یا همگام سازی بین ماژول های برنامه وجود ندارد به طوری که بیکـارییک پردازنده در حین اجرای یک برنامه ناچیز می باشد.

4-2: مساله تطابق گراف ……………………………………………………………………………………………….. 36
4-3: الگوریتم *A ……….ا………………………………………………………………………………………………… 40
4-4: یک مثال از الگوریتم …………………………………………………………………………………………………. 44

فصل پنجم: توابع اکتشافی برای بهبود الگوریتم *A

5-1: توابع اکتشافی برای الگوریتم *A ……ا…………………………………………………………………………….. 50

فصل ششم: الگوریتم ژنتیک مبتنی بر فضای مساله برای تخصیص کار

در روش جستجوی الگوریتم ژنتیک مبتنی بـر فضـای مسـاله (PSGA) ، یـک الگـوریتم اکتشـافیسریع و مبتنی بر توصیف مساله با جستجوی محلی ترکیب می شود. نکته کلیدی در این روش ایـناست که جستجو را بر اساس یک جفت (h,p) تعریف کنیم که در آن h یک تـابع اکتشـافی سـریعمعلوم و p نشان دهنده داده های مساله می باشد. از آنجایی که تابع اکتشافی h یک نگاشت از یـکمساله به یک جواب می باشد، جفت (h,p) یک کد گذاری75 برای یک جواب مشخص می باشد. بـاتغییر76 در مساله p ، یک همسایگی از جوابها به دست می آید. این همسایگی پایه جستجوی محلی را تشکیل می دهد. فضای مساله با تغییر در داده های مساله ایجاد می شود. فرض کنید که P یـکمجموعه ای از m مساله باشد که با تغییر در داده های مساله اصـلی بـه دسـت آمـده باشـد. یعنـیP  p j  p0 , j 1,…,m که در آن 0p مقـدار مسـاله اصـلی و بـردار تغییـر بـه صـورتتصادفی تولید شده می باشد. بازه تغییر بستگی به توصیف مساله دارد. برای اینکه مقـادیر تصـادفیتولید شده در نزدیکی مقادیر مساله اصلی باشند، یک حد بالا و پائین برای این تغییـر بایـد در نظـرگرفته شود. زیر مجموعه جواب S متناظر با مجموعه مساله P می تواند با استفاده از تابع اکتشـافیh که در آن S  h(p j ), j 1,…,m می باشد، تولید شود.
الگوریتم PSGA با الگوریتم ژنتیک ترکیبی77 (HGA) متفاوت می باشد. HGA از یک روش کـدگذاری مرتب برای نمایش کروموزوم استفاده می کند. و سپس از یک الگوریتم حریصانه بـه عنـوانیک رمزگشا78 برای نگاشت از کروموزوم به جواب استفاده می کنـد . الگـوریتمHGA نیـاز بـه یـکعملگر جهش مخصوص و یک عملگر ترکیـب مرتـب یکنواخـت دارد، در حـالی کـهPSGA از هـر عملگر جهش و ترکیب می تواند استفاده کند. در PSGA همان طوری که در شکل 6-1 نشان داده شده است، کروموزوم مبتنی بر داده های مساله می باشـد و عملگرهـای ژنتیـک بـه فضـای مسـالهاعمال می شوند. بنابر این نیاز به تغییر عملگرهای ژنتیک بـرای هـر کـاربرد از مسـاله نیسـت. یـکجواب از مساله با اعمال یک تابع اکتشافی ساده برای نگاشت از فضای مساله به فضای جواب

6-1: الگوریتم PSGA ..ا…………………………………………………………………………………………………… 54
6-2-1: حالت سیستم همگن ………………………………………………………………………………………….. 57
6-2-2: حالت سیستم ناهمگن ………………………………………………………………………………………… 61

فصل هفتم: تخصیص کار بهینه در سیستم محاسباتی توزیع شده

7-1: دسته بندی الگوریتم های تخصیص کار …………………………………………………………………………. 67
7-2: الگوریتم *A برای یافتن جواب بهینه …………………………………………………………………………….. 67
7-3: الگوریتم جستجوی موازی برای تخصیص بهینه ………………………………………………………………… 72

فصل هشتم: تخصیص کار با در نظر گرفتن محدودیت حافظه

8-1: تابع هزینه تغییر یافته ……………………………………………………………………………………………..81
8-2: محدودیت حافظه …………………………………………………………………………………………………..82

.فصل نهم: الگوریتم ژنتیک برای مساله تخصیص چندین کار

9-1: تعریف تابع هزینه …………………………………………………………………………………………………. 91
9-2-1: نمایش کروموزومی ……………………………………………………………………………………………. 93
9-2-2: روش انتخاب …………………………………………………………………………………………………… 95
9-3: یک مثال از الگوریتم …………………………………………………………………………………………….. 96
9-4: محدودیت های الگوریتم ……………………………………………………………………………………….. 101

فصل دهم: مدل های متفاوت مساله تخصیص کار در سیستم های محاسباتی توزیع شده

10-1: تخصیص ماژول ها با در نظر گرفتن محدودیت ……………………………………………………………… 104
10-2: تخصیص ماژول متوازن ……………………………………………………………………………………….. 104
10-3: تخصیص ماژول ها با در نظر گرفتن محدودیت های کلی ……………………………………………….. 105
10-4: تخصیص ماژول ها در حالت کلی با در نظر گرفتن محدودیت های شبکه …………………………….. 106

منابع…………………………………………………………………………………………………………………..107

واژه نامه …………………………………………………………………………………………………………… 109

فهرست جداول

1-1: هزینه اجرایی هر یک از کارها روی هر پردازنده …………………………………………………………….. 8
1-2: زمان اجرای کارها روی سه پردازنده …………………………………………………………………………. 10
3-1: محدودیت های مدل تخصیص کار ……………………………………………………………………………. 30
4-1: زمان ارتباطی بین ماژول ها ………………………………………………………………………………….. 45
4-2: زمان پردازشی ماژول ها …………………………………………………………………………………….. 46
6-1: محاسبه هزینه و تابع ارزیابی برای جمعیت اولیه ………………………………………………………… 60
8-1: هزینه اجرای ماژول های کار 1T روی پردازنده های متفاوت …………………………………………….. 86
8-2: هزینه اجرای ماژول های کار 2T روی پردازنده های متفاوت …………………………………………….. 86
8-3: هزینه اجرای ماژول های کار 3T روی پردازنده های متفاوت …………………………………………….. 86
8-4: هزینه ارتباطی بین ماژول های کار 1T ………..ا………………………………………………………….. 86
8-5: هزینه ارتباطی بین ماژول های کار 2T …….ا……………………………………………………………… 86
8-6: هزینه ارتباطی بین ماژول های کار 3T ……..ا…………………………………………………………….. 87
8-7: ماتریس همجواری پردازنده ها (L1pq ) …ا…………………………………………………………………. 87
8-8: ماتریس همجواری پردازنده ها (L2 pq ) …….ا…………………………………………………………….. 87
8-9: میزان حافظه مصرفی ماژول ها بر حسب واحد حافظه …………………………………………………… 87
9-1: هزینه اجرایی ماژول های کار 1T روی پردازنده های متفاوت ……………………………………………..97
9-2: هزینه اجرایی ماژول های کار 2T روی پردازنده های متفاوت ……………………………………………..97
9-3: هزینه اجرای ماژول های کار 3T روی پردازنده های متفاوت ……………………………………………….98
9-4: هزینه اجرای ماژول های کار 4T روی پردازنده های متفاوت ……………………………………………….98
9-5: هزینه اجرای ماژول های کار 5T روی پردازنده های متفاوت ……………………………………………….98
9-6: هزینه IMC ماژول های کار 1T …ا……………………………………………………………………………..99
9-7: هزینه IMC ماژول های کار 2T …ا……………………………………………………………………………..99
9-8: هزینه IMC ماژول های کار 3T …ا…………………………………………………………………………….99
9-9: هزینه IMC ماژول های کار 4T .ا………………………………………………………………………………..99
9-10: هزینه IMC ماژول های کار 5T ….ا……………………………………………………………………………99
9-11: ماتریس همجواری پردازنده ها (Li pq ) ..ا…………………………………………………………………..100
9-12: میزان حافظه مورد نیاز ماژول های کارها بر حسب واحد حافظه ………………………………………….100

برای دانلود رایگان قسمت های بیشتراز فایل به انتهای مطلب مراجعه کنید

فهرست اشکال

1-1: یک مثال از شبکه جریان ……………………………………………………………………………………………….. 5
1-2: نمونه ای از جریان امکان پذیر در شبکه جریان ……………………………………………………………………….. 6
1-3: ماکزیمم جریان و مینیمم برش ………………………………………………………………………………………….. 7
1-4: گراف کارها ………………………………………………………………………………………………………………… 8
1-5: گراف کارهای تغییر داده شده به همراه یک برش …………………………………………………………………….. 9
1-6: برش معادل با تخصیص کار بهینه ……………………………………………………………………………………….. 10
1-7: گراف کارها ………………………………………………………………………………………………………………… 10
1-8: برش نشان دهنده تخصیص کار به سه پردازنده ……………………………………………………………………… 11
1-9: گراف کارهای تغییر یافته برای تخصیص کار با سه پردازنده ………………………………………………………….. 11
1-10: دو تخصیص ممکن برای کار D در یک سیستم n پردازنده ای ………………………………………………………. 12
1-11: دو مجموعه برشی در یک گراف ………………………………………………………………………………………… 12
2-1: یک گراف کار و تخصیص ماژول ها ………………………………………………………………………………………… 20
2-2: گراف کار تغییر یافته ……………………………………………………………………………………………………….. 22
3-1: ساختار کلی مدل تخصیص کار و توابع پشتیبانی آن ………………………………………………………………….. 28
3-2: درخت جستجو با سه کار و سه پردازنده ……………………………………………………………………………….. 31
4-1: گراف کار ……………………………………………………………………………………………………………………… 38
4-2: گراف پردازنده ……………………………………………………………………………………………………………….. 39
4-3: گراف کار …………………………………………………………………………………………………………………….. 44
4-4: گراف پردازنده ……………………………………………………………………………………………………………….. 45
4-5: درخت جستجوی حالت ……………………………………………………………………………………………………. 46
5-1: درخت گسترش یافته ……………………………………………………………………………………………………….. 49
5-2: همریختی …………………………………………………………………………………………………………………….. 49
5-3: درخت گسترش یافته ……………………………………………………………………………………………………….. 49
6-1: الگوریتم ژنتیک مبتنی بر فضای مساله …………………………………………………………………………………… 55
6-2: یک مثال از گراف TIG ……..ا………………………………………………………………………………………………. 56
6-3: جمعیت اولیه با چهار کروموزوم ……………………………………………………………………………………………. 58
6-4: شبه کد تابع اکتشافی نگاشت ……………………………………………………………………………………………. 59
6-5: عملگر ترکیب برای تولید جمعیت جدید …………………………………………………………………………………… 60
6-6: گراف پردازنده و گراف کار …………………………………………………………………………………………………… 62
6-7: کد گذاری کروموزوم برای پردازنده های ناهمگن …………………………………………………………………………. 62
6-8: یک جمعیت اولیه از شش کروموزوم ………………………………………………………………………………………. 63
7-1: طبقه بندی الگوریتم های تخصیص کار ……………………………………………………………………………………. 68
7-2: گراف کارها و گراف پردازنده ها ……………………………………………………………………………………………… 70
7-3: درخت جستجو ………………………………………………………………………………………………………………… 71
7-4: یک تخصیص ایستای اولیه …………………………………………………………………………………………………… 74
7-5: عملیات الگوریتم تخصیص موازی با به کار بردن سه PE …ا………………………………………………………………. 76
7-6: نمایش فرآیند خوشه بندی ………………………………………………………………………………………………….. 78
8-1: گراف کارها هراه با گراف پردازنده …………………………………………………………………………………………… 85
9-1: گراف کارها ……………………………………………………………………………………………………………………..94
10-1: یک مثال از گراف ارتباطی ماژول های یک کار …………………………………………………………………………..103
10-2: یک مثال از شبکه ارتباطی ……………………………………………………………………………………………… 106

 

Abstract
The high speed growth of Distributed Computing Systems (DCS) has been led to substantial number of problems. One of the most interesting of them which has been investigated by several researchers is the task assignment problem. The reasons for task assignment in a DCS are to acheaive an effective utilization of resources in the system and most importantly a reasonable degree of load balancing.
The task assignment in a DCS is defined as dividing one executing program into some logically equivalent cooperative modules and then assigning them to a set of processors with considering some certain constraints which have been imposed on the resources of the system. The final goal of this assignment is to optimize the total costs including execution and communication costs. For satisfying this goal a suitable cost function is defined. Then the objective includes the optimization of this cost function subject to some constraints.
In this near lengthly writing, we survey some different algorithms that are related to the subject of task assignment in a typically DCS.



مقطع : کارشناسی ارشد

قیمت 25 هزار تومان

خرید فایل pdf به همراه فایلword

قیمت:35هزار تومان