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

فهرست مطالب
مقدمه 1
1- فصل اول – مفاهيم اوليه 2
1-1. سيستم های توزيع شده 3
1-1-1. مزایا و معایب سيستم های توزيع شده3
1-2. انگیزش  6
1-3. مراحل کلی تبديل برنامه ترتيبی به برنامه توزيع شده 8
1-4. ساختار پايان نامه9
1-5. جمع بندي 10
2- فصل دوم – تکنيک ها و ابزارهای مرتبط 11
2-1.ابزارهاي تبادل پيام در مقايسه با حافظه اشتراکي توزيع شده13
2-1-1. تبادل پيام 13
2-1-2. خصوصيات مطلوب يک سيستم تبادل پيام
2-1-3. طبقه بندي ابزارهاي تبادل پيام14
2-2. توزیعگر های اتوماتیک 17
2-2-1. ابزار هاي نيمه اتوماتيك 17
2-2-2. ابزار هاي تمام اتوماتيك 18
2-2-3. توزيع بايت¬ كد جاوا بر مبنای تحليل¬ وابستگي به صورت اتوماتیک 21
2-4. مطابقت اندازه گره در محیط برنامه نويسي شي¬گرا به صورت پویا توسط روش اسكوپ 24
2-5.افرازبندي در سيستم توزيع شده شي گرا به صورت پويا 25
2-5-1. معیارهای دسته بندي اشياء 26
2-5-2. الگوريتم خوشه بندي مشتق شده از الگوريتم حريصانه lo,s  27
2-5-3. دسته بندي اشياء موجود در خوشه ها 29
2-6. نتيجه گيري 30
3- فصل سوم – استخراج گراف فراخواني 31
3-1. ساخت گراف جريان فراخوانی 32
3-2-1. الگوریتم های  تعين مقصد فراخواني 34
3-2-2. روش آناليز نوع ايستاتيك 34
روش آناليز سلسله مراتب کلاس 35
3-2-3. روش آناليز نوع سريع 37
3-2-4. روش آناليز نوع سريع حساس به جريان برنامه 37
3-2. استخراج گراف فراخواني جهت ساخت گراف کلاسها 41
3-3. مقايسه روش های ساخت گراف فراخوانی 43
3-4. وزن گذاری گراف فراخوانی 45
3-5. استراتژي وزن گذاري يال هاي گراف فراخواني توابع  46
3-6.  برآورد زمان اجراي كد هاي ترتيبي 50
3-7-1.  روش های برآورد زمان اجراي كد هاي ترتيبي 51
3-7-2.  برآورد زمان اجرای کدهای برنامه باآناليز متن برنامه51
3-7-3.  تخمين ايستاي زمان اجراي برنامه ها 56
3-7-4.  تعيين سرحد تكرار حلقه¬ها و فراخواني¬هاي بازگشتي 57
3-7-5.  حذف مسيرهاي اجرا نشدني 57
3-7-6.  بهينه سازي كامپايلرها و تخمين زمان اجراي برنامه 57
3-7. زبان هاي برنامه سازي و تخمين زمان اجرا 58
3-8. رعايت ميزان دقت تخمين در زمان اجرا 58
3-9. معيارهاي موجود در تخمين طولاني ترين زمان اجرا 59
3-10-1.  تحليل جريان داده 59
3-10-2.  تحليل كاهش بازگشتي 61
3-10-3.  حجم زياد اطلاعات 62
3-10-4.  استفاده از كد Object برنامه 63
3-10. بايت كد جاوا و محاسبه زمان اجراي دستورالعملها 63
3-11. محاسبه زمان اجراي حلقه ها 64
3-12-1.  نحوه شناسايي حلقه هاي تكرار 65
3-12. انتشار دامنه مقادير 67
3-13. دستورات شرطي و نحوه شناسايي آنها 68
3-14. محاسبه زمان اجراي کل برنامه با استفاده از روش پيشنهادي   70
3-15-1.  تشخيص حلقه هاي تكرار 71
3-15-2.  تخمين تعداد تكرار حلقه ها 71
3-15-3.  انتشار مقادير 71
3-15-4.  محاسبه زمان اجراي توابع موجود در يك دور از گراف71
3-15. يافتن نقاط همگام سازي 73
3-16. بررسي نتيجه الگوريتم پيشنهادي برروي يك برنامه نمونه76
3-17. جمع بندی 80
4- فصل چهارم – خوشه بندی 81
4-1. مقدمه 82
4-2. خوشه بندي سلسله مراتبي 82
4-3. خوشه بندي سلسله مراتبي پايين به بالا (تلفيق) 85
4-4. روش هاي ادغام خوشه ها در خوشه بندي پايين به بالا 88
4-4-1.      Single Linkage88
4-4-2. Complete Linkage 89
4-4-3. Group Average Linkage 89
4-4-4. Simple Average Linkage 90
4-4-5. Weighted Average Linkage 91
4-4-6. سه روش مفيد ديگر (Median, Centroid, Wards ) 91
4-5. تكنيك هاي يافتن تعداد خوشه هاي بهينه 94
4-5-1. جدول تلفيق (جدول ادغام) 94
4-5-2. تراز تلفيق 96
4-5-3. نمودار dendrogram 96
4-5-4. تعيين تعداد خوشه هاي بهينه 98
4-6. تكنيك هاي پيدا كردن نقطه پيچش در نمودار جدول تلفيق100
4-7. روش پيشنهادي در اين پايان نامه جهت خوشه بندي 103
4-7-1. الگوريتم پيشنهادي برای خوشه بندی کلاس ها 103
4-8. جمع بندي 106
5- فصل پنجم – پياده سازي و ارزيــابــي 108
5-1. محيط پياده سازی شده 109
5-2. مقايسة روش خوشه بندي پيشنهادي با روش حريصانه متداول111
6- فصل ششم – نتيجـه‌گيـري 120
6-1. نتيجه گيري 121
6-2. کارهاي آتي ………. 121
منابع و مراجع 123
فهرست شکلها
3-1. يک برنامه نمونه و گراف فراخوانی آن 32
3-2. الگوريتم ساخت گراف فراخوانی به روش CHA 36
3-3. الگوريتم انتخاب متد بعدی در روش FRTA 39
3-4. الگوريتم Travers برای روش FRTA 40
3-5. الگوريتم روش FRTA 41
3-6. يک برنامه نمونه ساده 44
3-7. گراف فراخواني اسخراج شده با استفاده از روش CHA 45
3-8. الگوريتم وزن گذاري گراف فراخواني 50
3-9.  نمونه اي از يک ماتريس ناهمبستگي50
3-10. الگوريتم برآورد زمان اجراي يک تکه کد 53
3-11. الگوريتم برآورد زمان اجراي يک تکه کد 55
3-12. مثال براي حذف مسيرهاي اجرا نشدني 57
3-13. حدود زمان اجراي برنامه  مطرح درشبيه‌ساز San 59
3-14. قوانين مورد استفاده در روش شماي زمان سنجي 61
3-15. الگوريتم ساده براي ايجاد درخت پوشا 65
3-16. دو الگوريتم مجزا براي ساختن حلقه هاي طبيعي 67
3-17. الگوريتم يافتن مجموعه گره هاي مسلط بر هر گره در يک گراف67
3-18. مثالي از انتشار مقادير در متن يک برنامه 68
3-19. نمونه گراف جريان كنترلي حلقه داراي شرط 69
3-20. يك حلقه ساده در گراف حهت دار 72
3-21. روش محاسبه زمان اجراي نودها در گراف جهت دار73
3-22. الگوريتم تعيين نقاط همگام سازي 75
3-23. گراف وابستگي برنامه فروشنده دوره گرد78
3-24. تعداد فراخواني هاي انجام شده بين کلاس های برنامه فروشنده دوره گرد79
4-1. خوشه بندي بالا به پايين و پايين به بالا 84
4-2. الگوريتم کلي خوشه بندي پايين به بالا 86
4-3. Dissimilarity  Matrix 86
4-4. جدول رابطه هاي روش هاي مختلف 94
4-5. ماتريس همبستگي 5 شي فرضي 95
4-6. جدول تلفيق براي اشيا شكل4-5با استفاده از روش Complete Linkage 95
4-7. نمودار dendogram 97
4-8. تخمين خوشه ها از روش نمودار Dendogram 98
4-9. نمودار تراز هاي تلفيق 100
4-10. نقاط قرمز رنگ به عنوان نقطه برش مناسب 102
4-11. نمودار تراز هاي تلفيق 102
4-12. الگوريتم خوشه بندي پايين به بالاي پيشنهادي 104
5-1. مرحله سوم خوشه بندي برنامه فروشنده دوره گرد 109
5-2. مرحله يازدهم از خوشه بندي برنامه فروشنده دوره گرد 111
5-3. خوشه هاي به دست آمده از الگوريتم حريصانه براي برنامه فروشنده دوره گرد 112
5-3. خوشه هاي به دست آمده از الگوريتم حريصانه براي برنامه فروشنده دوره گرد 112
5-5. کاهش زمان اجرای برنامه توزيع شده نسبت به برنامه ترتیبی در ورودی های بزرگ با استفاده از الگوريتم خوشه بندی پيشنهادی 115
5-6. روال اجرايي برنامه فروشنده دوره گرد 117