ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن

بخشی از فهرست مطالب پروژه ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن

مقدمه

1-    فصل اول - مفاهیم اولیه

   1-1. سیستم های توزیع شده

      1-1-1. مزایا و معایب سیستم های توزیع شده

   1-2. انگیزش

   1-3. مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده

   1-4. ساختار پایان نامه

   1-5. جمع بندی

2-    فصل دوم - تکنیک ها و ابزارهای مرتبط

   2-1.ابزارهای تبادل پیام در مقایسه با حافظه اشتراکی توزیع شده

2-1-1. تبادل پیام

        2-1-2. خصوصیات مطلوب یک سیستم تبادل پیام

 2-1-3. طبقه بندی ابزارهای تبادل پیام

    2-2. توزیعگر های اتوماتیک

 2-2-1. ابزار های نیمه اتوماتیك

 2-2-2. ابزار های تمام اتوماتیك

        2-2-3. توزیع بایت¬ كد جاوا بر مبنای تحلیل¬ وابستگی به صورت اتوماتیک

  2-4. مطابقت اندازه گره در محیط برنامه نویسی شی¬گرا به صورت پویا توسط روش اسكوپ

  2-5.افرازبندی در سیستم توزیع شده شی گرا به صورت پویا

      2-5-1. معیارهای دسته بندی اشیاء

      2-5-2. الگوریتم خوشه بندی مشتق شده از الگوریتم حریصانه lo,s

       2-5-3. دسته بندی اشیاء موجود در خوشه ها

    2-6. نتیجه گیری

3- فصل سوم - استخراج گراف فراخوانی

   3-1. ساخت گراف جریان فراخوانی

3-2-1.    الگوریتم های  تعین مقصد فراخوانی

3-2-2.    روش آنالیز نوع ایستاتیك

روش آنالیز سلسله مراتب کلاس

3-2-3.    روش آنالیز نوع سریع

3-2-4.    روش آنالیز نوع سریع حساس به جریان برنامه

3-2.    استخراج گراف فراخوانی جهت ساخت گراف کلاسها

3-3.    مقایسه روش های ساخت گراف فراخوانی

3-4.    وزن گذاری گراف فراخوانی

3-5.    استراتژی وزن گذاری یال های گراف فراخوانی توابع

3-6.     برآورد زمان اجرای كد های ترتیبی

3-7-1.     روش های برآورد زمان اجرای كد های ترتیبی

3-7-2.     برآورد زمان اجرای کدهای برنامه باآنالیز متن برنامه

3-7-3.     تخمین ایستای زمان اجرای برنامه ها

3-7-4.     تعیین سرحد تكرار حلقه¬ها و فراخوانی¬های بازگشتی

3-7-5.     حذف مسیرهای اجرا نشدنی

3-7-6.     بهینه سازی كامپایلرها و تخمین زمان اجرای برنامه

3-7.    زبان های برنامه سازی و تخمین زمان اجرا

3-8.    رعایت میزان دقت تخمین در زمان اجرا

3-9.    معیارهای موجود در تخمین طولانی ترین زمان اجرا

3-10-1.     تحلیل جریان داده

3-10-2.     تحلیل كاهش بازگشتی

3-10-3.     حجم زیاد اطلاعات

3-10-4.     استفاده از كد Object برنامه

3-10.    بایت كد جاوا و محاسبه زمان اجرای دستورالعملها

3-11.    محاسبه زمان اجرای حلقه ها

3-12-1.     نحوه شناسایی حلقه های تكرار

3-12.    انتشار دامنه مقادیر

3-13.    دستورات شرطی و نحوه شناسایی آنها

3-14.    محاسبه زمان اجرای کل برنامه با استفاده از روش پیشنهادی

3-15-1.     تشخیص حلقه های تكرار

3-15-2.     تخمین تعداد تكرار حلقه ها

3-15-3.     انتشار مقادیر

3-15-4.     محاسبه زمان اجرای توابع موجود در یك دور از گراف

3-15.    یافتن نقاط همگام سازی

3-16.    بررسی نتیجه الگوریتم پیشنهادی برروی یك برنامه نمونه

3-17.    جمع بندی

4-    فصل چهارم - خوشه بندی

4-1.    مقدمه

4-2.    خوشه بندی سلسله مراتبی

4-3.    خوشه بندی سلسله مراتبی پایین به بالا (تلفیق)

4-4.    روش های ادغام خوشه ها در خوشه بندی پایین به بالا

4-4-1.         Single Linkage

4-4-2.    Complete Linkage

4-4-3.    Group Average Linkage

4-4-4.    Simple Average Linkage

4-4-5.    Weighted Average Linkage

4-4-6.    سه روش مفید دیگر (Median, Centroid, Wards )

4-5.    تكنیك های یافتن تعداد خوشه های بهینه

4-5-1.    جدول تلفیق (جدول ادغام)

4-5-2.    تراز تلفیق

4-5-3.    نمودار dendrogram

4-5-4.    تعیین تعداد خوشه های بهینه

4-6.    تكنیك های پیدا كردن نقطه پیچش در نمودار جدول تلفیق

4-7.    روش پیشنهادی در این پایان نامه جهت خوشه بندی

4-7-1.    الگوریتم پیشنهادی برای خوشه بندی کلاس ها

4-8.    جمع بندی

5-    فصل پنجم - پیاده سازی و ارزیــابــی

5-1.    محیط پیاده سازی شده

5-2.    مقایسه روش خوشه بندی پیشنهادی با روش حریصانه متداول

6-    فصل ششم - نتیجـه‌گیـری

6-1.    نتیجه گیری

6-2.    کارهای آتی

منابع و مراجع

فهرست شکلها

3-1. یک برنامه نمونه و گراف فراخوانی آن

3-2. الگوریتم ساخت گراف فراخوانی به روش CHA

3-3. الگوریتم انتخاب متد بعدی در روش FRTA

3-4. الگوریتم Travers برای روش FRTA

3-5. الگوریتم روش FRTA

3-6. یک برنامه نمونه ساده

3-7. گراف فراخوانی اسخراج شده با استفاده از روش CHA

3-8. الگوریتم وزن گذاری گراف فراخوانی

3-9.  نمونه ای از یک ماتریس ناهمبستگی

3-10. الگوریتم برآورد زمان اجرای یک تکه کد

3-11. الگوریتم برآورد زمان اجرای یک تکه کد

3-12. مثال برای حذف مسیرهای اجرا نشدنی

3-13. حدود زمان اجرای برنامه  مطرح درشبیه‌ساز San

3-14. قوانین مورد استفاده در روش شمای زمان سنجی

3-15. الگوریتم ساده برای ایجاد درخت پوشا

3-16. دو الگوریتم مجزا برای ساختن حلقه های طبیعی

3-17. الگوریتم یافتن مجموعه گره های مسلط بر هر گره در یک گراف

3-18. مثالی از انتشار مقادیر در متن یک برنامه

3-19. نمونه گراف جریان كنترلی حلقه دارای شرط

3-20. یك حلقه ساده در گراف حهت دار

3-21. روش محاسبه زمان اجرای نودها در گراف جهت دار

3-22. الگوریتم تعیین نقاط همگام سازی

3-23. گراف وابستگی برنامه فروشنده دوره گرد

3-24. تعداد فراخوانی های انجام شده بین کلاس های برنامه فروشنده دوره گرد

4-1. خوشه بندی بالا به پایین و پایین به بالا

4-2. الگوریتم کلی خوشه بندی پایین به بالا

4-3. Dissimilarity  Matrix

4-4. جدول رابطه های روش های مختلف

4-5. ماتریس همبستگی 5 شی فرضی

4-6. جدول تلفیق برای اشیا شكل4-5با استفاده از روش Complete Linkage

4-7. نمودار dendogram

4-8. تخمین خوشه ها از روش نمودار Dendogram

4-9. نمودار تراز های تلفیق

4-10. نقاط قرمز رنگ به عنوان نقطه برش مناسب

4-11. نمودار تراز های تلفیق

4-12. الگوریتم خوشه بندی پایین به بالای پیشنهادی

5-1. مرحله سوم خوشه بندی برنامه فروشنده دوره گرد

5-2. مرحله یازدهم از خوشه بندی برنامه فروشنده دوره گرد

5-3. خوشه های به دست آمده از الگوریتم حریصانه برای برنامه فروشنده دوره گرد

5-3. خوشه های به دست آمده از الگوریتم حریصانه برای برنامه فروشنده دوره گرد

5-5. کاهش زمان اجرای برنامه توزیع شده نسبت به برنامه ترتیبی در ورودی های بزرگ با استفاده از الگوریتم خوشه بندی پیشنهادی

5-6. روال اجرایی برنامه فروشنده دوره گرد

مقدمه
  در سال های اخیر صنعت کامپیوتر رشد بسیار شگفت انگیزی داشته است. در طی دو دهه اخیر سرعت کامپیوتر های شخصی از چند دستور در ثانیه به چند میلیون دستور در ثانیه رسیده است در صورتی که قیمت آنها نیز از چند میلیون دلار به چند هزار دلار کاهش یافته است.
  افزایش نیاز به  سیستم هایی با کارائی بسیار زیاد و سرعت فوق العاده بالای شبکه ها (شبکه های ترابیتی)  سبب جلب علاقه محققان به پردازش های موازی و توزیع شده، شده است. از جمله دلایل افزایش توجه به سیستم های توزیع شده می توان به موارد زیر اشاره کرد:
1: پیشرفت تکنولوژی پردازش.
2: سرعت بالای شبکه ها.
3: انجام تحقیقات گسترده برای ارائه محیطهائی برای انجام محاسباتی توزیع شده.
  بعلاوه به نظر می رسد با افزایش  روزافزون نیاز به توان پردازشی سریعتر، هیچ بستر محاسباتی منفرد،  نمی تواند پاسخگوی این نیاز باشد بنابراین محیطهای پردازشی آتی باید بتواننداز منابع محاسباتی نا همگن موجود در شبکه استفاده کنند. فقط سیستم های موازی و توزیع شده امکان استفاده از  منابع مختلف موجود در شبکه را میسر می کنند.
 از سوی دیگر تحول چشم گیری نیز در صنعت شبکه های کامپیوتری به وجود آمده است. امروزه هزاران کامپیوتر می توانند از طریق یک شبکه LAN به یکدیگر متصل شده و در کسری از ثانیه داده های خود را با یکدیگر مبادله کنند. یا به کمک یک شبکه WAN میلیون ها کامپیوتر از سرتاسر دنیا  قادر به تبادل داده با یکدیگر هستند.با توجه به این تحولات، امروزه تصور مجموعه ای از کامپیوتر ها که به صورت یک کامپیوتر یکپارچه  اما با قدرت بسیار بیشتر ،چندان بعید نیست.   
فصل اول

مفاهیم اولیه
 
1-1. سیستم های توزیع شده
در حالت کلی تعریف زیر را می توان برای یک سیستم توزیع شده ارائه کرد:
  یک سیستم توزیع شده مجموعه ای از کامپیوتر های مستقل می باشند که برای انجام کارهای مختلف با یکدیگر همکاری کرده و به صورت یک سیستم واحد و قدرتمند برای کاربران دیده می شوند.

1-1-1     مزایا و معایب سیستم های توزیع شده
  سیستم های کامپیوتری توزیع شده به وسیله پژوهشگران به طور گسترده مطالعه شده و مزایای زیادی در رابطه با آن گزارش شده است. به عنوان مثال پیشرفت های اخیر در تکنولوژی  شبکه ها و پردازه ها، دستیابی به مزایای زیر را امکان پذیر ساخته است :
1. افزایش کارایی: وجود چندین کامپیوتر در یک سیستم توزیع شده به برنامه کاربردی امکان پردازش و اجرا به صورت موازی را می دهد بنابراین سرعت اجرای برنامه کاربردی و کارایی سیستم افزایش می یابد برای مثال کارایی یک سیستم فایل می تواند به وسیله تکرار توابع آن بر روی چندین کامپیوتر بیشتر شود. تکرار سیستم فایل باعث می شود چندین برنامه کاربردی به سیستم فایل به صورت موازی دسترسی داشته باشند بعلاوه تکرار فایل ها ترافیک شبکه را بین سایت های مختلف توزیع کرده و تاخیر ناشی از صف بندی را کاهش می دهد.
2. به اشتراک گذاری منابع: به اشتراک گذاری منابع مقرون به صرفه بودن و امکان دسترسی کارا به منابع سیستم را فراهم میکند یعنی کاربران در عرض چند دقیقه می توانند منابع سخت افزاری و نرم افزاری گران و خاص منظوره را مانند سرورهای پایگاه داده ها، سرورهای پردازش، سرورهای پرینترو... را به اشتراک بگذارند.
3. افزایش توسعه پذیری: سیستم های توزیع شده می توانند به صورت سازگار با محیط طراحی شوند مثلا برای یک محاسبه سنگین، سیستم خود را به گونه ای سازمان دهی می کند که شامل تعداد زیادی از کامپیوترها و منابع باشد در صورتیکه برای پردازشهای کوچکتر  فقط از چند منبع استفاده خواهد کرد بعلاوه در صورت لزوم محدودیتهائی مانند ظرفیت سیستم فایل و قدرت محاسبتی سیستم را می توان به سادگی با اضافه کردن کامپیوترها یا سرورهای بیشتر افزایش یابد.
4. افزایش قابلیت اطمینان، دسترسی راحت و تحمل پذیری خطا:  وجود چندین منبع ذخیره سازی و محاسباتی در یک سیستم، ساخت سیستم توزیع شد? تحمل پذیر خطا را مقرون به صرفه و جالب می کند.
سیستم می تواند خرابی یک کامپیوتر را به وسیله تخصیص  وظایف آن به کامپیوتر دیگر تحمل کند بعلاوه سیستم می تواند به وسیله تکرار توابع یا منابع، در کامپیوتر های مختلف،  خطر از دست دادن آنها  را برطرف کند.
5. مقرون به صرفه گی: کارایی کامپیوترها تقریباً هر دو سال یک بار دو برابر شده، در صورتیکه قیمت آنها در دهه اخیر تقریبا در هر سال نصف شده است بعلاوه  شبکه هایی با سرعت بسیار زیاد نیز به وجود آمده است که ساخت سیستم های توزیع شده را نسبت به سیستم های موازی بر اساس نرخ قیمت به کارایی مقرون به صرفه تر کرده است.
البته این پیشرفت ها به آسانی به دست نمی آید زیرا طراحی یک سیستم توزیع شده همه منظوره بسیار مشکلتر از طراحی یک سیستم متمرکز است. در طراحی یک سیستم توزیع شد چند منظوره تعداد زیادی از گزینه ها و مسائل باید در نظر گرفته شوند که پیکر بندی فیزیکی سیستم ،خصوصیات بستر محاسباتی، شبکه ارتباطی، زمان بندی وظایف، سیاست های تخصیص منابع و مکانیزم کنترل آن ها، ایجاد سازگاری و کنترل همروندی و امنیت، نمونه هایی از آنهاست. این مشکلات را می توان  ناشی از عدم بلوغ سیستم های توزیع شده، ناهماهنگی و رفتار مستقل کامپیوترها، پراکندگی جغرافیایی منابع سیستم و... دانست. این مشکلات در  زیر خلاصه شده اند:
   1.  فهم کامل تئوری محاسبات توزیع شده هنوز صورت نگرفته است. این موضوع نسبتاً جدید بوده و ما، قبل از اینکه به تئوری طراحی چنین سیستم های پردازشی تسلط پیدا کنیم باید تعداد زیادی سیستم توزیع شده معتبر با اهداف معمول و معماری های متفاوت را طراحی و آزمایش کنیم.
   2. رفتار ناهماهنگ و مستقل منابع سیستم یا اجزای آن، کنترل نرم افزار را پیچیده می کند در حالیکه این امر در یک سیستم متمرکز محاسباتی کار ساده ای است. اگر کامپیوترها به صورت مشتری-خدمتگذار سازماندهی شوند، کنترل  نرم افزار ساده تر و رفتار آن قابل پیش بینی تر خواهد بود با این حال این ساختار با یکی از مشخصات سیستم های توزیع شده که همان مستقل بودن کامپیوترها و اجرای آسنکرونن می باشد در تناقض است.
  3. استفاده از شبکه های ارتباطی برای اتصال کامپیوترها به یکدیگر مرحله دیگری از پیچیده گی را معرفی می کند. طراحان سیستم توزیع شده نه تنها باید در طراحی سیستم های کامپیوتری و سیستم های نرم افزاری و سرویس ها ماهر باشد بلکه در طراحی شبکه ارتباطی مطمئن، ایجاد همزمانی ، سازگاری و برطرف کردن خطاها در یک سیستم پیچیده از کامپیوترهای ناهمگن و پراکنده از نظر جغرافیایی نیز تسلط داشته باشند. تعداد منابع استفاده شده در چنین سیستمهائی می تواند دهها، صدها و یا حتی هزاران منبع محاسباتی و ذخیره سازی باشد.
 یک سیستم توزیع شده حداقل بایداهداف زیر را برآورده کند:      1- به سادگی منابع موجود در شبکه را در اختیار کاربران قرار دهد.
2- کاربران نباید از این موضوع که منبع مورد استفاده آنها در کامپیوتر دیگری در شبکه قرار دارد مطلع شوند.(شفافیت)   3- سیستم توزیع شده باید باز باشد.
4- سیستم توزیع شده باید مقیاس پذیر باشد. 

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

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

1-2    انگیزش
      ایده شی گرایی از محبوب ترین روش های تولید نرم افزار است,كه برای طراحی، توصیف و پیاده سازی سیستم های توزیع شده نیز بسیار سودمند است.[11] مزیت این روش برای ساخت سیستم های توزیع شده این است كه میتوان كدهای برنامه را در اشیا كپسوله كرده و سپس اشیا را به ماژول های مستقلی دسته بندی كرد و هر ماژول را بر روی یك منبع محاسباتی مجزا مستقر نمود. با این حال به عنوان یک اصل [8]تولید یک برنامه توزیع شده، همواره سخت تر از ایجاد یک برنامه غیر توزیع شده است, که عملکردی معادل آن را دارد. به طوری كه ساخت یك سیستم توزیع شده میتواند به یك كار خسته كننده  و مملو از خطا تبدیل شود.[4] با وجود اینكه امروزه  ابزار ها و تكنیك های بسیار مفیدی مانند[29] RPC ،[15] CORBA و[8] DCOM جهت ساخت سیستم های توزیع شده با كارایی بالا ارائه گشته اند، اما در حالت كلی فرایند ساخت یك سیستم توزیع شده از بدو پیدایش سیستم های توزیع شده تغیر اندكی كرده است : برنامه نویس برنامه را به ماژول های مختلفی تقسیم كرده، هر ماژول را به صورت مجزا پیاده سازی كرده و امكان برقراری ارتباط بین آنها را ایجاد می كند و در نهایت هر ماژول را  در یك كامپیوتر مستقل در شبكه مستقر میكند. برخی از چالش هایی كه در رابطه با ساخت سیستم های توزیع شده پیش روی یك برنامه نویس یا طراح نرم افزار می تواند قرار گیرد عبارت اند از:
•    پیچیدگی طراحی و پیاده سازی سیستم های توزیع شده.
•    پیدایش نوع جدیدی از خطاها مانند خطاهای ناشی ازهمروندی و  همگام سازی پردازه ها.
•    مشكلات ناشی از سازگاری داده ها  در كل سیستم.
•     موازنه كار  بارگذاری شده در منابع موجود در سیستم.
      لذا اتوماتیک سازی فرایند تبدیل یک برنامه ترتیبی به یک برنامه قابل اجرا برروی یک محیط محاسباتی توزیع شده همواره به عنوان یک مساله باز تحقیقاتی مطرح بوده است. امروزه شبکه‌های کامپیوتری به واسطه پیشرفت تکنولوژی ارتباطات  توانسته‌اند جایگزین کامپیوترهای گران قیمت موازی¬¬گردند[1].
هنگام طراحی برنامه های توزیع شده برای مسائل کاربردی، اغلب الگوریتم ها به مجموعه ای از کارهای کلاسیک، و تکراری  تجزیه می شوند. از جمله کارهای بنیادی که در اغلب الگوریتم ها دیده می شوند می توان به انتشار  اطلاعات به تمام گره ها،ارسال پیام به برخی از گره ها ، سنکرون سازی عمومی تمام پردازه ها، شروع اجرای برخی رویداد ها، ضمن اجرای پردازه ها، یا انجام محاسبه ای که داده های مورد نیاز آن بین گره های مختلف توزیع شده، اشاره کرد. این عملیات ها معمولا با تبادل پیام بین پردازه ها انجام می گیرند.با طراحی زیر ساختی که بتواند این primitive ها را در اختیار برنامه های ترتیبی قرار دهد می توان نسخه توزیع شده ای از یک برنامه ترتِبی تولید کرد.
یکی از چالشهای مطرح در توزیع کد، میزان تسریع حاصل از توزیع می‌باشد[4] برنامه های علمی نیاز به كامپیوترهایی با توان محاسباتی بالا دارند. این نوع كامپیوترها معمولا بسیار گران قیمت میباشند. امروزه سعی برآن است تا بجای استفاده از سوپركامپیوترها از شبكه ای با كامپیوترهای ارزان قیمت برای حل مسائل علمی استفاده شود. هدف ما توزیع كد برنامه ها جهت حصول حداكثر میزان همروندی در اجرای كد است در صورت موفقیت مسلما زمان اجرایی به حداقل ممكن كاهش خواهد یافت.
محاسبه زمان اجرای یک برنامه بصورت دقیق امکان ندارد، چون برحسب مسیرهای اجرایی  متفاوت در یک برنامه، زمان اجرای آن متفاوت خواهد بود. بیشترین و کمترین زمان اجرای یک برنامه، به طولانی‌ترین و کوتاهترین مسیر اجرایی برنامه از لحاظ زمانی بستگی خواهد داشت. هدف از یافتن اطلاعات مسیرهای اجرایی یک برنامه، تخمین زمان اجرای آن است.
  همانطور که بیان شد توزیع کد با هدف افزایش سرعت پردازش صورت می‌گیرد. بنابراین انتظار می‌رود کد توزیع شده نسبت به قبل سریعتر اجرا¬ گردد. نکته قابل تامل این است که آیا توزیع صورت گرفته باعث تسریع شده است؟ میزان تسریع (تقویت توزیع) چقدر است؟ برای پاسخ به این سوالات باید مشخص گردد مدت زما ن اجرای برنامه، قبل و بعد از توزیع به چه میزان بوده است.
به هنگام توزیع، بخشی از برنامه در ایستگاه کاری راه دور اجرا می‌گردد. برای محاسبه زمانِ اجرای برنامه ترتیبی توزیع شده، باید مدت زمانیکه طول می کشد تا افراز  احضار شده در ایستگاه کاری راه‌دور اجرا گردد و مدت زمان سپری شده بین دستور احضار  تا اولین استفاده از نتیجه این احضار، تخمین زده شود و بر اساس مدت زمان احضار و ارسال نتایج، زمان اجرای توزیع شده محاسبه گردد. بعنوان مثال در مرجع [4] میزان تسریع توزیع محاسبه شده است. این عامل بر اساس زمان محاسبه شده  دو ایستگاه کاری بر روی لبه اتصال دهنده آنها، مشخص می شود.
1-3-  مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده
در حالت کلی برای تبدیل  یك برنامه ترتیبی به یك برنامه توزیع شده مراحل زیر پیموده می شود 
-    با پیمایش برنامه ترتیبی توسط یك تجزیه گر ویژه كه از كلاس های كتابخانه[7] COMPOST استفاده میكند، اطلاعات لازم جهت ساخت گراف وابستگی كلاس ها،  خوشه بندی ، برآورد زمان اجرای متد های برنامه و ایجاد كد توزیع شده  در قالب سه کدخلاصه  با نام های SourceModel ، DepModel و CostModel استخراج می گردد. در این مرحله علاوه بر خلاصه سازی اطلاعات برنامه, نقاط همگام سازی برنامه نیز تعیین می گردد. یك نقطه همگام سازی مكانی درمتن برنامه است كه درآن یكی از نتایج یك فراخوانی متد دور استفاده شده است.  نتایج به دست آمده از این مرحله مستفیما در هر یك از مراحل  بعدی استفاده می شوند.
-    پس از استخراج اطلاعات لازم ، گراف فراخوانی متد های برنامه ترتیبی با استفاده از اطلاعات موجود در  کد خلاصه  SourceModel یا مدل منبع, استخراج و رسم می شود. در محیط پیاده سازی شده, استخراج گراف فراخوانی به سه روش[5] CHA ، RTA و FRTA  امكان پذیر است.
-    پس از ساخت گراف فراخوانی به كمك الگوریتمی كه مدت زمان بین فراخوانی یك متد و استفاده از یكی از نتایج اجرای  آن را محاسبه می كند, یال های موجود در گراف فراخوانی توابع  به گونه ای وزن دار میشوند كه وزن یك یال میزان افزایش كارایی برنامه در صورت فراخوانی آن متد  به صورت آسنكرون  را نشان دهد. جهت انجام این كار دو الگوریتم دیگر كه یكی مدت زمان اجرای یك متد و دیگری مدت زمان اجرای یك تكه كد را برآورد می كند طراحی وپیاده سازی شده اند.  بر آورد زمان اجرای متدها از طریق یکی دیگر از كد های خلاصه تولید شده در مرحله اول به نام CostModel صورت می گیرد. در این پایان نامه برآورد زمان اجرای یك تكه كد به کمک برآورد میزان پیچیدگی آن انجام می شود.
-    پس از وزن گذاری یال های موجود درگراف فراخوانی و استخراج گراف وابستگی بین كلاس ها، این گراف به گونه ای خوشه بندی می شود كه كلاس هایی با حد اكثر درجه همبستگی در یك خوشه قرار گیرند و همچنین میزان كلاس های بار گذاری شده در هر خوشه متناسب و ارتباط بین خوشه ها تا حد امکان کم باشد به عبارت دیگر خوشه ها دارای خصوصیت Load Balancing بوده و تعداد فراخوانی های بین خوشه ای تا حد امكان كم باشد.  در سیستم پیاده سازی شده فرایند خوشه بندی می تواند به صورت كاملا اتوماتیك توسط سیستم یا نیمه اتوماتیك انجام گیرد. در حالت دوم كاربر می تواند تغییرات مورد نظر خود را در خوشه بندی كلاس ها اعمال كند . درحالت اول نیز به كمك یك الگوریتم تعیین تعداد خوشه های بهینه [18] ، ساختار و تعداد خوشه های بهینه برای كلاس های برنامه مشخص می شود.
-    در نهایت پس از مشخص شدن خوشه های برنامه، كد توزیع شده تولید می شود. برای این منظور یک شی Proxy به هر یک از خوشه ها تخصیص می یابد که این شی مدیریت ایجاد اشیا دور و فراخوانی متد های آنها را بر عهده می گیرد. یك شی Proxy  جهت ایجاد اشیا دور و مدیریت فراخوانی متد های آنها از دو شی دیگر به نام های Object Manager و Synchronizer استفاده می كند. این اشیا نیز  از کلاس های کتابخانه Java Symphony جهت انجام وظایف خود استفاده می کند.
-    با تحلیل متن برنامه ترتیبی و با توجه به نتیجه خوشه بندی، تمام دستورات ایجاد اشیا، و فراخوانی متد هایی كه كلاس آنها در خوشه دیگری قرار گرفته با فراخوانی متد های مناسبی از شی Proxy تعویض می شوند. همچنین با استفاده از آنالیز وابستگی داده ها نقاطی از برنامه ترتیبی كه در آنها باید همگام سازی صورت گیرد كشف شده و كد های مناسبی در آن نقاط از برنامه درج می شود.

1-4-    ساختار پایان نامه
   فصل های بعدی در این پایان نامه به شرح زیر سازماندهی شده اند. در فصل دوم تحقیقات و ابزارهای  مرتبط با این پروژه و نحوه استخراج كد خلاصه شده از متن برنامه جهت ساخت گراف فراخوانی متد ها ، بررسی شده اند.  همچنین انواع روشهای خوشه بندی برای رسیدن به اهداف مختلف با در نظر گرفتن پارامترهای متفاوتی از قبیل محدودیت دسترسی به منابع ، پیوستگی، چسبندگی و تعداد فراخوانیهای بین اشیا، وزن اشاره گرها و غیره نیز بررسی شده است.
 در فصل سوم نحوه وزن گذاری گراف فراخوانی استخراج شده و ساخت گراف کلاس های برنامه بررسی شده است. در این فصل  به بررسی روشهای مختلف تخمین زمان اجرای برنامه ها پرداخته خواهد شد كه شامل مفاهیم مرتبط با تخمین زمان اجرای برنامه در تحلیل ایستا ، رعایت میزان دقت تخمین زمان اجرا برنامه، معیارهای موجود در تخمین زمان اجرا و راه حلهای بهینه در حالتهای پیش آمده پرداخته خواهد شد.
 وزن گذاری  به گونه ای صورت میگیرد كه وزن هر یال نشان دهنده میزان افزایش در كارایی سیستم در صورت همروندی توابع موجود در گره های آن یال باشد.
در فصل چهارم نحوه خوشه بندی گراف وابستگی استخراج شده توسط تكنیك های خوشه بندی سلسله مراتبی[4] و یافتن تعداد خوشه های بهینه برای كلاس های برنامه ترتیبی توصیف شده است. و در فصل پنجم به نحوه پیاده سازی و ارزیابی روش پیشنهادی پرداخته خواهد شد كه ابتدا نمودار كلاسها و فعالیت آنها بررسی شده و جهت تكمیل مطالب این قسمت، نمودار اشیای حاصل از كلاسهای مورد استفاده در ادامه آورده خواهد شد و روش پیشنهادی توسط مسئله فروشنده دوره گرد و مقایسه آن با سایر روش ها ارزیابی می شود.
در فصل ششم با نتیجه گیری از مطالب و نیز بیان کارهای آتی به پایان نامه خاتمه می دهیم.

1-5.  جمع بندی
  در این فصل دلایل نیاز به یك توزیعگر اتوماتیك، كار های مرتبط انجام شده با این موضوع  و  ساختار كلی محیط پیاده سازی شده جهت تبدیل برنامه های ترتیبی به نسخه های توزیع شده از همان برنامه بررسی گردید. همانطور كه گفته شد برای تبدیل یك برنامه ترتیبی به یك برنامه توزیع شده متن برنامه ترتیبی ابتدا به كمك كتابخانه Compost تحلیل شده گراف فراخوانی، از متن برنامه استخراج می شوند. سپس با برآورد زمان اجرای متد ها و تخمین زمان صرفه جویی شده در اجرا در صورت توزیع آنها، یال های موجود در گراف فراخوانی وزن دار شده و گراف وابستگی كلاس های برنامه ساخته می شود. پس از ساخت گراف فراخوانی این گراف توسط یك الگوریتم خوشه بندی سلسله مراتبی ویژه  خوشه بندی شده و پس از مشخص شدن وضعیت و تعداد خوشه ها با تخصیص یك شی Proxy به هر خوشه و كشف نقاط همگام سازی، برنامه ترتیبی به یك برنامه توزیع شده تبدیل می شود. ترجمه کد های ترتیبی به توزیع شده نیز به کمک کتابخانه کلاس های Compost صورت می گیرد.
 
فصل دوم

تکنیک ها و ابزارهای مرتبط
 
ساخت برنامه های کاربردی توزیع شده و موازی راحت و سر راست نبوده و نیاز به طراحی دقیق و شفاف معماری برنامه وجود دارد. اگر چه یک سیستم موازی و توزیع شده توان محاسباتی بالا و قابلیت انعطاف زیاد برای کاربر ارائه می دهد اما همین ویژگی باعث افزایش پیچیدگی ساخت سیستم نیز می شود. برای مثال در طی ساخت نرم افزار، طراح باید بهترین پیکربندی سخت افزاری برای نرم افزار ، بهترین حالت توزیع مسئله بر روی شبکه ، بهترین شیو? ارتباطی با حداقل تاخیر و بهترین استراتژی همگام سازی و... انتخاب کند . مجموعه راه حل های که برای یک مساله می تواند انتخاب شود بسیار وسیع بوده و انتخاب بهترین راه حل کار ساده ای نیست. ازاین رو به  ابزارهای ساده و portable نرم افزاری نیاز است که به طراح جهت توزیع مناسب محاسبات برنامه بر روی منابع پردازشی کمک کند. چنین ابزارهایی باید کل چرخه حیات نرم افزار را پشتیبانی کرده و سازنده را در هر مرحله از طراحی برنامه، پشتیبانی کند. این مراحل میتواند از فازهای مشخصه سازی و  طراحی آغاز شده و تا فاز های  برنامه نویسی، توزیع، موازنه سازی، اشکال زدایی،ارزیابی و نگهداری ادامه یابد.
در کلی ترین حالت ابزار های ساخته شده برای سیستم های توزیع شده را می توان در دو دسته ابزار های مبتنی بر تبادل پیام و ابزار های مبتنی بر حافظه اشتراکی طبقه بندی کرد.
ابزارهای تبادل پیام چند منظوره مانند  P4[], MPI[], PVM[] ,Made line[] وسیستم ارتباطی My Net[] پرمیتیو های ساده ای برای تبادل هر نوع پیام ارائه کرده اند.در حالیکه سیستم های خاص منظوره همچون BLACS[] ( سیستم ارتباطی جبر خطی پایه ) و TCGMSG[] (گروه شیمی نظری سیستم تبادل پیام ) برای برنامه های کاربردی مخصوص طراحی شده اند. بعلاوه، برخی از سیستم ها مانند GRIDS[] و CANOPY[] نیز ساختمان داده های ارتباطی مناسبی برای برنامه های مختلف ارائه می دهند.  این ابزارها و محیط های برنامه نویسی، مدل های محاسباتی متفاوتی از لحاظ موازی سازی داده ها، موازی سازی کارها و حافظه اشتراکی را برای کاربران ارائه می کنند. ابزارهای مختلف از تکنیک های پیاده سازی متفاوتی  مانند remote procedure call ، پردازش وقفه ها، تبادل پیام ها و یا استفاده از معماری client-server  برای برقراری ارتباطات استفاده می کنند. از این رو هر ابزار برای گروه خاصی از برنامه های کاربردی مناسب می باشد.   سیستم هایی  مانند CMMD و NX/2  در مقایسه با سیستم هایportable  مانند PVM و MPI برای ساخت برنامه های خاصی طراحی شده اند.

بخشی از منابع و مراجع پروژه ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن
[1]    M. M. Fuad, M. J. Oudshoorn, “AdJava: Automatic Distribution of Java Applications”, the 25th Australasian Computer Science Conference, 2002.
[2]    I. Attali, D. Caromel, R. Guider, “A Step toward automatic distribution of java programs”, ACM-ISCOPE conference on Java Grande, 2002.
[3]    A. Spiegel, “Automatic Distribution of Object-Oriented Programs ”, PhD Thesis, FU Berlin, FB Mathematik und Informatik, December 2002.
[4]    S.Parsa, V.Khalilpoor, “Automatic Distribution of Sequential Code Using JavaSymphony Middleware”, 32nd International Conference On current Trends in Theory and Practice of Computer Science 2006.
[5]    S. Vijay, and H. Laurie, “Practical virtual methods call for java” Proc. of the Conf. on Object-  Oriented programming, systems, languages, and applications ,2000.
[6]    H. Zima, “Super compilers for Parallel and Vector Computers” ACM Press, 1990.
[7]    D. Raysidey, S. Reussz, E. Hedgesy, and K. Kontogiannis, “The Effect of Call Graph Construction Algorithms for Object-Oriented Programs on Automatic Clustering” IEEE Computer Society   Washington, DC, USA, ISBN: 0-7695-0656-9: 2000.
[8]    D. Grove, G. DeFouw, J. Dean , and C. Chambers “Call Graph Construction in Object-Oriented Languages” Proc of the 12th ACM SIGPLAN conference on Object-oriented programming , Atlanta, Georgia, United States    October 05 - 09, 1997.
[9]    P. Puschner, A. Burns: Guest Editorial, “A Review of Worst-Case Execution-Time Analysis”, Journal of Real-Time Systems, 18(2/3):115–128, May 2000.
[10]    “The Java Virtual Machine Specification”, Sun Microsystems, Inc. 1995.
[11]    C. A. Healy, M. Sjodin, D. B. Whalley, “Ounding Loop Iterations for Timing Analysis”, In Proc. IEEE Real-Time Technology and Aplications Symposium, pages 12–21, Jun. 1998.
[12]    J. Gustafsson, “Analysing Execution-Time of Object-Oriented Programs using Abstract Interpretation”, PhD thesis, Uppsala University, Uppsala, Sweden, May 2000.
[13]    R. Kirner, “Extending Optimising Compilation to Support Worst-Case Execution Time Analysis”, PhD Thesis, Institut für Technische Informatik, Technischen Universität Wien, May 2003.
[14]     L. Patcas, “Basic Timing and Control-Flow Analysis of Programs Written in Assembly Languages”, Diploma Thesis, Department of Computer and Software Engineering Politehnica University of Timisoara, June 2004.
[15]    R. Kirner, P. Puschner, “A Simple and Effective Fully Automatic Worst-Case Execution Time Analysis for Model-Based Application Development”, In Proc. Workshop on Intelligent Solutions in Embedded Systems, 2003.
[16]    A. Mok, “Evaluating tight execution time bounds of programs by annotations”, In Proc. 6th Workshop on Real-Time Operating Systems and Software, pages 74-80. IEEE, May 1989.
[17]    C. A. Healy, M. Sjodin, D. B. Whalley, “Ounding Loop Iterations for Timing Analysis”, In Proc. IEEE Real-Time Technology and Aplications Symposium, pages 12–21, Jun. 1998.
[18]    C, A. Healy, “Automatic Utilization