مقدمه:

از مهم ترین مسائل در زمینه سیستم هاي محاسباتی توزیع شده ،مسـاله تخصـیص مجموعـه اي ازکارها به مجموعه اي از پردازنده ها در جهت ایجاد توازن بار و مینیمم کردن هزینه کل سیستم مـیباشد.[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هزار تومان