پروژه آماده: ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن (205 صفحه فایل ورد - word)

پروژه آماده: ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن (205 صفحه فایل ورد - word)

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

چکیده

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

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

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

مقدمه .......  1

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

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

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

   1-2. انگیزش  ....    6    1-3. مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده ......    8    1-4. ساختار پایان نامه     9

   1-5. جمع بندی .......    10

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

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

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

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

 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

2-ساخت گراف فراخوانی    3-1. ساخت گراف جریان فراخوانی ......  32 3-2-1.                 الگوریتم های  تعین مقصد فراخوانی ....  34 3-2-2.                 روش آنالیز نوع ایستاتیک ...  34

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

3-2.            استخراج گراف فراخوانی جهت ساخت گراف کلاسها ....41 3-3.            مقایسه روش های ساخت گراف فراخوانی ...  43 3-4.            وزن گذاری گراف فراخوانی ......  45

استراتژی وزن گذاری یال های گراف فراخوانی توابع .......  46برآورد زمان اجرای کد های ترتیبی ...  50روش های برآورد زمان اجرای کد های ترتیبی .......  51برآورد زمان اجرای کدهای برنامه باآنالیز متن برنامه.  51تعیین سرحد تکرار حلقه­ها و فراخوانی­های بازگشتی  57حذف مسیرهای اجرا نشدنی ....  57بهینه سازی کامپایلرها و تخمین زمان اجرای برنامه ...  57نحوه شناسایی حلقه های تکرار ..... 65تشخیص حلقه های تکرار ... 71تخمین تعداد تکرار حلقه ها  71انتشار مقادیر ...... 71یافتن نقاط همگام سازی ... 73بررسی نتیجه الگوریتم پیشنهادی برروی یک برنامه نمونه.. 76جمع بندی .... 80

3-7-3.            تخمین ایستای زمان اجرای برنامه ها .  563-7.            زبان های برنامه سازی و تخمین زمان اجرا ..  58 3-8.            رعایت میزان دقت تخمین در زمان اجرا ...... 58 3-9.            معیارهای موجود در تخمین طولانی ترین زمان اجرا ... 59

3-10-1.              تحلیل جریان داده ....... 593-10-2.              تحلیل کاهش بازگشتی ...... 613-10-3.              حجم زیاد اطلاعات ... 623-10-4.              استفاده از کد Object برنامه ...... 63

3-10.         بایت کد جاوا و محاسبه زمان اجرای دستورالعملها .... 63 3-11.         محاسبه زمان اجرای حلقه ها ...... 643-12.         انتشار دامنه مقادیر ... 67 3-13.         دستورات شرطی و نحوه شناسایی آنها  68 3-14.         محاسبه زمان اجرای کل برنامه با استفاده از روش پیشنهادی   ..... 703-15-4.               محاسبه زمان اجرای توابع موجود در یک دور از گراف....  71

فصل چهارم - خوشه بندی . 81خوشه بندی سلسله مراتبی 82خوشه بندی سلسله مراتبی پایین به بالا (تلفیق) ... 85روش های ادغام خوشه ها در خوشه بندی پایین به بالا ..... 88Single Linkage...... 88Simple Average Linkage ....... 90Weighted Average Linkage . 91سه روش مفید دیگر (Median, Centroid, Wards ) ....... 91تکنیک های یافتن تعداد خوشه های بهینه ....... 94جدول تلفیق (جدول ادغام) ..... 94تراز تلفیق . 96نمودار dendrogram .. 96تعیین تعداد خوشه های بهینه .... 98تکنیک های پیدا کردن نقطه پیچش در نمودار جدول تلفیق.. 100روش پیشنهادی در این پایان نامه جهت خوشه بندی ... 103الگوریتم پیشنهادی برای خوشه بندی کلاس ها ..... 103جمع بندی ...... 106محیط پیاده سازی شده ....... 109مقایسة روش خوشه بندی پیشنهادی با روش حریصانه متداول..... 111

4-1.            مقدمه ... 824-4-2.               Complete Linkage .... 89 4-4-3.               Group Average Linkage  895-               فصل پنجم - پیاده سازی و ارزیــابــی . 1086-               فصل ششم - نتیجـه‌گیـری . 120 6-1.            نتیجه گیری ... 121 6-2.            کارهای آتی .. . 121

منابع و مراجع ....... 123