پایان نامه کارشناسی ارشد رشته کامپیوتر نرم افزار : الگوریتم خوشه بندی

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

تعداد صفحات پایان نامه: 140 صفحه

دانلود متن کامل این پایان نامه با فرمت ورد word

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

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

موضوع:

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

 استاد راهنما:

دکتر سعید پارسا

 استاد مشاور :

مهندس معظمی

نگارش:

سید علی اسحقی

چکیده

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

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

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

مقدمه

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

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

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

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

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

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

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

فصل اول

 مفاهیم اولیه

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

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

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

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

سیستم های کامپیوتری توزیع شده به وسیله پژوهشگران به طور گسترده مطالعه شده و مزایای زیادی در رابطه با آن گزارش شده است. به عنوان مثال پیشرفت های اخیر در تکنولوژی شبکه ها و پردازه ها، دستیابی به مزایای زیر را امکان پذیر ساخته است :

1. افزایش کارایی: وجود چندین کامپیوتر در یک سیستم توزیع شده به برنامه کاربردی امکان پردازش و اجرا به صورت موازی را می دهد بنابراین سرعت اجرای برنامه کاربردی و کارایی سیستم افزایش می یابد برای مثال کارایی یک سیستم فایل می تواند به وسیله تکرار توابع آن بر روی چندین کامپیوتر بیشتر شود. تکرار سیستم فایل باعث می شود چندین برنامه کاربردی به سیستم فایل به صورت موازی دسترسی داشته باشند بعلاوه تکرار فایل ها ترافیک شبکه را بین سایت های مختلف توزیع کرده و تاخیر ناشی از صف بندی را کاهش می دهد.
2. به اشتراک گذاری منابع: به اشتراک گذاری منابع مقرون به صرفه بودن و امکان دسترسی کارا به منابع سیستم را فراهم میکند یعنی کاربران در عرض چند دقیقه می توانند منابع سخت افزاری و نرم افزاری گران و خاص منظوره را مانند سرورهای پایگاه داده ها، سرورهای پردازش، سرورهای پرینترو… را به اشتراک بگذارند.
3. افزایش توسعه پذیری: سیستم های توزیع شده می توانند به صورت سازگار با محیط طراحی شوند مثلا برای یک محاسبه سنگین، سیستم خود را به گونه ای سازمان دهی می کند که شامل تعداد زیادی از کامپیوترها و منابع باشد در صورتیکه برای پردازشهای کوچکتر فقط از چند منبع استفاده خواهد کرد بعلاوه در صورت لزوم محدودیتهائی مانند ظرفیت سیستم فایل و قدرت محاسبتی سیستم را می توان به سادگی با اضافه کردن کامپیوترها یا سرورهای بیشتر افزایش یابد.
4. افزایش قابلیت اطمینان، دسترسی راحت و تحمل پذیری خطا: وجود چندین منبع ذخیره سازی و محاسباتی در یک سیستم، ساخت سیستم توزیع شدۀ تحمل پذیر خطا را مقرون به صرفه و جالب می کند.

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

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

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

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

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

2- کاربران نباید از این موضوع که منبع مورد استفاده آنها در کامپیوتر دیگری در شبکه قرار دارد مطلع شوند.(شفافیت)   3- سیستم توزیع شده باید باز باشد.

4- سیستم توزیع شده باید مقیاس پذیر باشد.

شفافیت می تواند در جنبه های مختلف سیستم های توزیع شده مطرح شود.

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

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

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

•  انگیزش

     ایده شی گرایی از محبوب ترین روش های تولید نرم افزار است,که برای طراحی، توصیف و پیاده سازی سیستم های توزیع شده نیز بسیار سودمند است. مزیت این روش برای ساخت سیستم های توزیع شده این است که میتوان کدهای برنامه را در اشیا کپسوله کرده و سپس اشیا را به ماژول های مستقلی دسته بندی کرد و هر ماژول را بر روی یک منبع محاسباتی مجزا مستقر نمود. با این حال به عنوان یک اصل تولید یک برنامه توزیع شده، همواره سخت تر از ایجاد یک برنامه غیر توزیع شده است, که عملکردی معادل آن را دارد. به طوری که ساخت یک سیستم توزیع شده میتواند به یک کار خسته کننده و مملو از خطا تبدیل شود. با وجود اینکه امروزه ابزار ها و تکنیک های بسیار مفیدی مانند RPC ، CORBA و DCOM جهت ساخت سیستم های توزیع شده با کارایی بالا ارائه گشته اند، اما در حالت کلی فرایند ساخت یک سیستم توزیع شده از بدو پیدایش سیستم های توزیع شده تغیر اندکی کرده است : برنامه نویس برنامه را به ماژول های مختلفی تقسیم کرده، هر ماژول را به صورت مجزا پیاده سازی کرده و امکان برقراری ارتباط بین آنها را ایجاد می کند و در نهایت هر ماژول را در یک کامپیوتر مستقل در شبکه مستقر میکند. برخی از چالش هایی که در رابطه با ساخت سیستم های توزیع شده پیش روی یک برنامه نویس یا طراح نرم افزار می تواند قرار گیرد عبارت اند از:

• پیچیدگی طراحی و پیاده سازی سیستم های توزیع شده.
• پیدایش نوع جدیدی از خطاها مانند خطاهای ناشی ازهمروندی و همگام سازی پردازه ها.
• مشکلات ناشی از سازگاری داده ها در کل سیستم.
• موازنه کار بارگذاری شده در منابع موجود در سیستم.

     لذا اتوماتیک سازی فرایند تبدیل یک برنامه ترتیبی به یک برنامه قابل اجرا برروی یک محیط محاسباتی توزیع شده همواره به عنوان یک مساله باز تحقیقاتی مطرح بوده است. امروزه شبکه‌های کامپیوتری به واسطه پیشرفت تکنولوژی ارتباطات توانسته‌اند جایگزین کامپیوترهای گران قیمت موازی­­گردند.

هنگام طراحی برنامه های توزیع شده برای مسائل کاربردی، اغلب الگوریتم ها به مجموعه ای از کارهای کلاسیک، و تکراری تجزیه می شوند. از جمله کارهای بنیادی که در اغلب الگوریتم ها دیده می شوند می توان به انتشار اطلاعات به تمام گره ها،ارسال پیام به برخی از گره ها، سنکرون سازی عمومی تمام پردازه ها، شروع اجرای برخی رویداد ها، ضمن اجرای پردازه ها، یا انجام محاسبه ای که داده های مورد نیاز آن بین گره های مختلف توزیع شده، اشاره کرد. این عملیات ها معمولا با تبادل پیام بین پردازه ها انجام می گیرند.با طراحی زیر ساختی که بتواند این primitive ها را در اختیار برنامه های ترتیبی قرار دهد می توان نسخه توزیع شده ای از یک برنامه ترتِبی تولید کرد.

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

 متن کامل را می توانید دانلود نمائید چون فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به طور نمونه)

ولی در فایل دانلودی متن کامل پایان نامه

همراه با تمام ضمائم (پیوست ها) با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود است

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

اختصاصی از حامی فایل پایان نامه ارشد رشته کامپیوتر - ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن با فرمت 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

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

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

3-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.              تحلیل جریان داده ............................................................................................................. 59

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

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

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

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

• فصل چهارم - خوشه بندی ............................................................................................................... 81
  • خوشه بندی سلسله مراتبی .............................................................................................................. 82
  • خوشه بندی سلسله مراتبی پایین به بالا (تلفیق) ................................................................................. 85
  • روش های ادغام خوشه ها در خوشه بندی پایین به بالا .................................................................... 88
    • Single Linkage.................................................................................................... 88
    • Simple Average Linkage ..................................................................................... 90
    • Weighted 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

فهرست شکلها

عنوان

صفحه

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

   

دانلود مقاله ISI الگوریتم خوشه بندی موازی مبتنی بر موجک روی GPU با استفاده از CUDA

اختصاصی از حامی فایل دانلود مقاله ISI الگوریتم خوشه بندی موازی مبتنی بر موجک روی GPU با استفاده از CUDA دانلود با لینک مستقیم و پر سرعت .

موضوع فارسی : الگوریتم خوشه بندی موازی مبتنی بر موجک روی GPU با استفاده از CUDA

موضوع انگلیسی : Parallel wavelet-based clustering algorithm on GPUs using CUDA 

تعداد صفحه : 5

فرمت فایل :pdf

سال انتشار : 2010

زبان مقاله : انگلیسی

چکیده

دارای منافع قابل توجهی در جامعه علمی و مهندسی کامپیوتر به سرعت بخشیدن به کارهای CPU-فشرده در شده است وجود
واحد پردازش گرافیکی (GPU ها) با توسعه پردازنده های گرافیکی بسیاری از هسته به عنوان داشتن پهنای باند حافظه بسیار بزرگ و قدرت محاسباتی. تجزیه و تحلیل خوشه یک تکنیک به طور گسترده استفاده برای گروه بندی مجموعه ای از اشیاء را به کلاس از اشیاء "مشابه" است و معمولا در زمینه های بسیاری مانند داده کاوی، بیوانفورماتیک و تشخیص الگو استفاده می شود. WaveCluster مفهوم تعریف
خوشه به عنوان یک منطقه متراکم متشکل از اجزای متصل در فضای ویژگی تبدیل شده است. در این مطالعه، ما در حال حاضر
اجرای الگوریتم WaveCluster به عنوان یک روش خوشه رمان بر اساس تبدیل موجک به سطح GPU
موازی و بررسی عملکرد موازی برای مجموعه داده های بسیار بزرگ فضایی. پیاده سازی CUDA از دو اصلی
زیر الگوریتم از روش WaveCluster. یعنی استخراج مولفه های فرکانس پایین از سیگنال با استفاده از موجک
تبدیل و برچسب زدن وصل ارائه شده است. پس از آن، ارزیابی عملکرد مربوطه برای گزارش
هر یک از زیر الگوریتم. تقسیم و تسخیر روش بر اجرای موجک به دنبال تبدیل و چند پاس کشویی
پنجره رویکرد در اجرای برچسب وصل.حداکثر به دست آورد تسریع در هسته به عنوان 107x در محاسبه استخراج مولفه فرکانس پایین و 6X در محاسبه برچسب وصل با توجه به الگوریتم های پی در پی در حال اجرا بر روی CPU شده است.

کلمات کلیدی: محاسبات GPU؛ CUDA. آنالیز خوشه ای؛ الگوریتم WaveCluster

صفحات طراحی / فتوشاپ/ صفحات طراحی شده -psd -کشاورز خوشه چین

اختصاصی از حامی فایل صفحات طراحی / فتوشاپ/ صفحات طراحی شده -psd -کشاورز خوشه چین دانلود با لینک مستقیم و پر سرعت .

کشاورز خوشه چین

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

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

فرمت : Word

تعداد صفحات : 126

سیستم های توزیع شده

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

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

• مزایا و معایب سیستم های توزیع شده

  سیستم های کامپیوتری توزیع شده به وسیله پژوهشگران به طور گسترده مطالعه شده و مزایای زیادی در رابطه با آن گزارش شده است. به عنوان مثال پیشرفت های اخیر در تکنولوژی  شبکه ها و پردازه ها، دستیابی به مزایای زیر را امکان پذیر ساخته است :

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

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

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

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

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

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

2- کاربران نباید از این موضوع که منبع مورد استفاده آنها در کامپیوتر دیگری در شبکه قرار دارد مطلع شوند.(شفافیت)   3- سیستم توزیع شده باید باز باشد.

4- سیستم توزیع شده باید مقیاس پذیر باشد. 

شفافیت می تواند در جنبه های مختلف سیستم های توزیع شده مطرح شود.

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