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

توضیحات مختصر محصول

پایان نامه کارشناسی ارشد   کامپیوتر

گرایش نرم افزار

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

فرمت اجرایی : در قالب Word

تعداد صفحات : ۱۵۰ صفحه

حجم فایل : ۷۱۶ KB

پسورد فایل فشرده : www.asrefonon.ir ( پسورد را تایپ کنید )

 

چکیده

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

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

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

مقدمه

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

افزایش نیاز به  سیستم هایی با کارائی بسیار زیاد و سرعت فوق العاده بالای شبکه ها (شبکه های ترابیتی)  سبب جلب علاقه محققان به پردازش های موازی و توزیع شده، شده است.

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

۱: پیشرفت تکنولوژی پردازش.

۲: سرعت بالای شبکه ها.

۳: انجام تحقیقات گسترده برای ارائه محیطهائی برای انجام محاسباتی توزیع شده.

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

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

 

فهرست مطالب

عنوان                                                                                                    صفحه        
مقدمه ……………………………………………………  ۱

۱-    فصل اول – مفاهیم اولیه ……………………………………….   ۲

۱-۱. سیستم های توزیع شده ……………………………  ۳

۱-۱-۱. مزایا و معایب سیستم های توزیع شده…………………………………………..   ۳

۱-۲. انگیزش  ……………………………………………    ۶

۱-۳. مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده …………………….    ۸

۱-۴. ساختار پایان نامه………………………………………………………..     ۹

۱-۵. جمع بندی ………………………………………………….    ۱۰

۲-     فصل دوم – تکنیک ها و ابزارهای مرتبط …………………………………   ۱۱

۲-۱.ابزارهای تبادل پیام در مقایسه با حافظه اشتراکی توزیع شده……………    ۱۳

۲-۱-۱. تبادل پیام …………………………………    ۱۳

۲-۱-۲. خصوصیات مطلوب یک سیستم تبادل پیام………………………………   ۱۴

۲-۱-۳. طبقه بندی ابزارهای تبادل پیام…………………………………     ۱۴

۲-۲. توزیعگر های اتوماتیک …………………………………………        ۱۷

۲-۲-۱. ابزار های نیمه اتوماتیک ……………………………..     ۱۷

۲-۲-۲. ابزار های تمام اتوماتیک ……………………………….     ۱۸

۲-۲-۳. توزیع بایت­ کد جاوا بر مبنای تحلیل­ وابستگی به صورت اتوماتیک ……..     ۲۱

۲-۴. مطابقت اندازه گره در محیط برنامه نویسی شی­گرا به صورت پویا توسط روش اسکوپ .   ۲۴

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

۲-۵-۱. معیارهای دسته بندی اشیاء …………………………………………     ۲۶

۲-۵-۲. الگوریتم خوشه بندی مشتق شده از الگوریتم حریصانه lo,s  …………….     ۲۷

۲-۵-۳. دسته بندی اشیاء موجود در خوشه ها ……………………………     ۲۹

۲-۶. نتیجه گیری ………………………………………………………………………  ۳۰

۳- فصل سوم – استخراج گراف فراخوانی …………………………………………  ۳۱

۲-ساخت گراف فراخوانی

۳-۱. ساخت گراف جریان فراخوانی …………………………………….  ۳۲

۳-۲-۱.                 الگوریتم های  تعین مقصد فراخوانی ………………….  ۳۴

۳-۲-۲.                 روش آنالیز نوع ایستاتیک ……………………………..  ۳۴

روش آنالیز سلسله مراتب کلاس ……………………………….     ۳۵

۳-۲-۳.                 روش آنالیز نوع سریع ……………………………..۳۷

۳-۲-۴.                 روش آنالیز نوع سریع حساس به جریان برنامه …………………….۳۷

۳-۲.            استخراج گراف فراخوانی جهت ساخت گراف کلاسها …………………۴۱

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

۳-۴.            وزن گذاری گراف فراخوانی ………………………………..  ۴۵

۳-۵.            استراتژی وزن گذاری یال های گراف فراخوانی توابع  …………….  ۴۶

۳-۶.             برآورد زمان اجرای کد های ترتیبی ………………………  ۵۰

۳-۷-۱.            روش های برآورد زمان اجرای کد های ترتیبی …………………  ۵۱

۳-۷-۲.            برآورد زمان اجرای کدهای برنامه باآنالیز متن برنامه……………….  ۵۱

۳-۷-۳.            تخمین ایستای زمان اجرای برنامه ها ……………………….  ۵۶

۳-۷-۴.            تعیین سرحد تکرار حلقه­ها و فراخوانی­های بازگشتی ……………… ۵۷

۳-۷-۵.            حذف مسیرهای اجرا نشدنی ……………………….  ۵۷

۳-۷-۶.            بهینه سازی کامپایلرها و تخمین زمان اجرای برنامه …………………  ۵۷

۳-۷.            زبان های برنامه سازی و تخمین زمان اجرا …………………………..  ۵۸

۳-۸.            رعایت میزان دقت تخمین در زمان اجرا …………………………….. ۵۸

۳-۹.            معیارهای موجود در تخمین طولانی ترین زمان اجرا ……………….. ۵۹

۳-۱۰-۱.              تحلیل جریان داده …………………………………… ۵۹

۳-۱۰-۲.              تحلیل کاهش بازگشتی …………………………….. ۶۱

۳-۱۰-۳.              حجم زیاد اطلاعات ……………………………… ۶۲

۳-۱۰-۴.              استفاده از کد Object برنامه ……………………….. ۶۳

۳-۱۰.         بایت کد جاوا و محاسبه زمان اجرای دستورالعملها ………………… ۶۳

۳-۱۱.         محاسبه زمان اجرای حلقه ها ……………………… ۶۴

۳-۱۲-۱.              نحوه شناسایی حلقه های تکرار ……………………. ۶۵

۳-۱۲.         انتشار دامنه مقادیر ………………………….. ۶۷

۳-۱۳.         دستورات شرطی و نحوه شناسایی آنها ……………………. ۶۸

۳-۱۴.         محاسبه زمان اجرای کل برنامه با استفاده از روش پیشنهادی   ….. ۷۰

۳-۱۵-۱.               تشخیص حلقه های تکرار ………………… ۷۱

۳-۱۵-۲.               تخمین تعداد تکرار حلقه ها ………………. ۷۱

۳-۱۵-۳.               انتشار مقادیر …………………….. ۷۱

۳-۱۵-۴.               محاسبه زمان اجرای توابع موجود در یک دور از گراف……….  ۷۱

۳-۱۵.         یافتن نقاط همگام سازی ……………………… ۷۳

۳-۱۶.         بررسی نتیجه الگوریتم پیشنهادی برروی یک برنامه نمونه………. ۷۶

۳-۱۷.         جمع بندی …………………………… ۸۰

۴-             فصل چهارم – خوشه بندی ……………………. ۸۱

۴-۱.            مقدمه ……………………………… ۸۲

۴-۲.            خوشه بندی سلسله مراتبی ………………………… ۸۲

۴-۳.            خوشه بندی سلسله مراتبی پایین به بالا (تلفیق) …………… ۸۵

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

۴-۴-۱.                    Single Linkage………………………. ۸۸

۴-۴-۲.               Complete Linkage ……………………………. 89

۴-۴-۳.               Group Average Linkage ……………………….. 89

۴-۴-۴.               Simple Average Linkage …………………… 90

۴-۴-۵.               Weighted Average Linkage ………………. 91

۴-۴-۶.               سه روش مفید دیگر (Median, Centroid, Wards ) …….. 91

۴-۵.            تکنیک های یافتن تعداد خوشه های بهینه ………………. ۹۴

۴-۵-۱.                 جدول تلفیق (جدول ادغام) ……………. ۹۴

۴-۵-۲.                 تراز تلفیق ………………………….. ۹۶

۴-۵-۳.                 نمودار dendrogram ……………………. 96

۴-۵-۴.                 تعیین تعداد خوشه های بهینه …………………. ۹۸

۴-۶.            تکنیک های پیدا کردن نقطه پیچش در نمودار جدول تلفیق…………. ۱۰۰

۴-۷.            روش پیشنهادی در این پایان نامه جهت خوشه بندی ……………. ۱۰۳

۴-۷-۱.               الگوریتم پیشنهادی برای خوشه بندی کلاس ها ………………. ۱۰۳

۴-۸.            جمع بندی ………………………. ۱۰۶

۵-               فصل پنجم – پیاده سازی و ارزیــابــی …………………….. ۱۰۸

۵-۱.            محیط پیاده سازی شده ……………………… ۱۰۹

۵-۲.            مقایسه روش خوشه بندی پیشنهادی با روش حریصانه متداول…….. ۱۱۱

۶-               فصل ششم – نتیجـه‌گیـری ………………. ۱۲۰

۶-۱.            نتیجه گیری ……………………………. ۱۲۱

۶-۲.            کارهای آتی ………. …………………………………….. ۱۲۱

منابع و مراجع ………………………………………………………… ۱۲۳

فهرست شکلها

عنوان صفحه
۳-۱. یک برنامه نمونه و گراف فراخوانی آن ………………………………….. ۳۲

۳-۲. الگوریتم ساخت گراف فراخوانی به روش CHA ……………………………….   ۳۶

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

۳-۴. الگوریتم Travers برای روش FRTA ……………………….   ۴۰

۳-۵. الگوریتم روش FRTA …………………………………………….. 41

۳-۶. یک برنامه نمونه ساده ……………………………………. ۴۴

۳-۷. گراف فراخوانی اسخراج شده با استفاده از روش CHA …………………. 45

۳-۸. الگوریتم وزن گذاری گراف فراخوانی ……………………….. ۵۰

۳-۹.  نمونه ای از یک ماتریس ناهمبستگی……………………………………… ۵۰

۳-۱۰. الگوریتم برآورد زمان اجرای یک تکه کد ……………………………..  ۵۳

۳-۱۱. الگوریتم برآورد زمان اجرای یک تکه کد ……………………..   ۵۵

۳-۱۲. مثال برای حذف مسیرهای اجرا نشدنی ………………………….. ۵۷

۳-۱۳. حدود زمان اجرای برنامه  مطرح درشبیه‌ساز San ……………………. 59

۳-۱۴. قوانین مورد استفاده در روش شمای زمان سنجی …………………… ۶۱

۳-۱۵. الگوریتم ساده برای ایجاد درخت پوشا ……………………………… ۶۵

۳-۱۶. دو الگوریتم مجزا برای ساختن حلقه های طبیعی ………………….. ۶۷

۳-۱۷. الگوریتم یافتن مجموعه گره های مسلط بر هر گره در یک گراف……………    ۶۷

۳-۱۸. مثالی از انتشار مقادیر در متن یک برنامه ……………………….. ۶۸

۳-۱۹. نمونه گراف جریان کنترلی حلقه دارای شرط …………………… ۶۹

۳-۲۰. یک حلقه ساده در گراف حهت دار ………………………۷۲

۳-۲۱. روش محاسبه زمان اجرای نودها در گراف جهت دار………………… ۷۳

۳-۲۲. الگوریتم تعیین نقاط همگام سازی ……………………………… ۷۵

۳-۲۳. گراف وابستگی برنامه فروشنده دوره گرد……………………. ۷۸

۳-۲۴. تعداد فراخوانی های انجام شده بین کلاس های برنامه فروشنده دوره گرد……..   ۷۹

۴-۱. خوشه بندی بالا به پایین و پایین به بالا …………………… ۸۴

۴-۲. الگوریتم کلی خوشه بندی پایین به بالا ………………… ۸۶

۴-۳. Dissimilarity  Matrix ……………………………. 86

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

۴-۵. ماتریس همبستگی ۵ شی فرضی ………………………….. ۹۵

۴-۶. جدول تلفیق برای اشیا شکل۴-۵با استفاده از روش Complete Linkage …………  ۹۵

۴-۷. نمودار dendogram ……………………………….. 97

۴-۸. تخمین خوشه ها از روش نمودار Dendogram …………………… 98

۴-۹. نمودار تراز های تلفیق ……………………….. ۱۰۰

۴-۱۰. نقاط قرمز رنگ به عنوان نقطه برش مناسب …………………. ۱۰۲

۴-۱۱. نمودار تراز های تلفیق ……………………… ۱۰۲

۴-۱۲. الگوریتم خوشه بندی پایین به بالای پیشنهادی ………………….. ۱۰۴

۵-۱. مرحله سوم خوشه بندی برنامه فروشنده دوره گرد ………………… ۱۰۹

۵-۲. مرحله یازدهم از خوشه بندی برنامه فروشنده دوره گرد ………………….. ۱۱۱

۵-۳. خوشه های به دست آمده از الگوریتم حریصانه برای برنامه فروشنده دوره گرد ……… ۱۱۲

۵-۳. خوشه های به دست آمده از الگوریتم حریصانه برای برنامه فروشنده دوره گرد ……. ۱۱۲

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

۵-۶. روال اجرایی برنامه فروشنده دوره گرد ………………………   ۱۱۷

نمایش بیشتر
قیمت محصول

۳۰,۰۰۰ تومان

قوانین استفاده

خرید محصول توسط کلیه کارت های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود محصول در اختیار شما قرار خواهد گرفت. با خرید این محصول از مزایای زیر بهره‌مند می‌شوید:

  • گارانتی کیفیت عصرفنون
  • هفت روز ضمانت بازگشت وجه
  • شش ماه پشتیبانی تضمین شده
  • آپدیت رایگان، دسترسی مادام العمر به فایل
  • امکان نصب روی بینهایت دامین و بدون لایسنس