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

تعداد صفحات: 135 فرمت فایل: word کد فایل: 2428
سال: 1387 مقطع: مشخص نشده دسته بندی: مهندسی کامپیوتر
قیمت قدیم:۳۵,۷۶۰ تومان
قیمت: ۲۹,۸۰۰ تومان
دانلود فایل
  • خلاصه
  • فهرست و منابع
  • خلاصه پایان نامه ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن

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

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

    چکیده

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

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

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

    واژه‌های کلیدی

    خوشه بندی ، چسبندگی ، توزیع شده گی .

     

    مقدمه

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

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

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

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

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

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

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

                         

    فصل اول

    مفاهیم اولیه

    1. 

    2.مقدمه

     

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

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

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

     

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

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

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

    2. به اشتراک گذاری منابع: به اشتراک گذاری منابع مقرون به صرفه بودن و امکان دسترسی کارا به منابع سیستم را فراهم میکند یعنی کاربران در عرض چند دقیقه می توانند منابع سخت افزاری و نرم افزاری گران و خاص منظوره را مانند سرورهای پایگاه داده ها، سرورهای پردازش، سرورهای پرینترو... را به اشتراک بگذارند.

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

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

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

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

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

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

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

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

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

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

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

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

    دستیابی: پنهان سازی تفاوت در ذخیره سازی داده ها و نحوه دسترسی به یک منبع

    محل : پنهان سازی مکان واقعی منابع در شبکه

    مهاجرت:  پنهان سازی تغییر محل منابع یعنی در صورت تغییر محل منبع، کاربران از این امر مطلع نگردند.

    تجدید محل: پنهان سازی مهاجرت یک منبع در حال استفاده، از کاربر آن.

    تکرار: پنهان سازی تکرار منابع به گونه ای که کاربران از این امر مطلع نگردند.

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

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

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

     

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

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

     

    انگیزش

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

    پیچیدگی طراحی و پیاده سازی سیستم های توزیع شده.

    پیدایش نوع جدیدی از خطاها مانند خطاهای ناشی ازهمروندی و  همگام سازی پردازه ها.

    مشکلات ناشی از سازگاری داده ها  در کل سیستم.

     موازنه کار  بارگذاری شده در منابع موجود در سیستم.

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

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

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

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

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

    به هنگام توزیع، بخشی از برنامه در ایستگاه کاری راه دور اجرا می‌گردد. برای محاسبه زمانِ اجرای برنامه ترتیبی توزیع شده، باید مدت زمانیکه طول می کشد تا افراز[4] احضار شده در ایستگاه کاری راه‌دور اجرا گردد و مدت زمان سپری شده بین دستور احضار[5] تا اولین استفاده از نتیجه این احضار، تخمین زده شود و بر اساس مدت زمان احضار و ارسال نتایج، زمان اجرای توزیع شده محاسبه گردد. بعنوان مثال در مرجع [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

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

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

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

       1-2. انگیزش  .....................................................................................................................................................    6

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

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

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

    2-

       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

    3-5.

    3-6.

    3-7-1.

    3-7-2.

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

    3-7-4.

    3-7-5.

    3-7-6.

    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.

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

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

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

    3-15-1.

    3-15-2.

    3-15-3.

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

    3-15.

    3-16.

    3-17.

    4-

    4-1.           مقدمه ............................................................................................................................................ 82

    4-2.

    4-3.

    4-4.

    4-4-1.     Single Linkage.................................................................................................... 88

    4-4-2.             Complete Linkage .................................................................................................. 89

    4-4-3.             Group Average Linkage ...................................................................................... 89

    Simple Average Linkage ..................................................................................... 90

    Weighted Average Linkage ............................................................................... 91

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

    تکنیک های یافتن تعداد خوشه های بهینه ..................................................................................... 94

    جدول تلفیق (جدول ادغام) ........................................................................................... 94

    تراز تلفیق ...................................................................................................................... 96

    نمودار dendrogram ................................................................................................ 96

    تعیین تعداد خوشه های بهینه .......................................................................................... 98

    تکنیک های پیدا کردن نقطه پیچش در نمودار جدول تلفیق......................................................... 100

    روش پیشنهادی در این پایان نامه جهت خوشه بندی .................................................................. 103

    4-7-1.

    4-8.

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

    5-1.

    5-2.

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

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

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

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

     

    منبع:

    M. M. Fuad, M. J. Oudshoorn, “AdJava: Automatic Distribution of Java Applications”, the 25th Australasian Computer Science Conference, 2002.

    I. Attali, D. Caromel, R. Guider, “A Step toward automatic distribution of java programs”, ACM-ISCOPE conference on Java Grande, 2002.

    A. Spiegel, “Automatic Distribution of Object-Oriented Programs ”, PhD Thesis, FU Berlin, FB Mathematik und Informatik, December 2002.

    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.

    S. Vijay, and H. Laurie, “Practical virtual methods call for java” Proc. of the Conf. on Object-  Oriented programming, systems, languages, and applications ,2000.

    H. Zima, “Super compilers for Parallel and Vector Computers” ACM Press, 1990.

    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.

    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.

    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.

    “The Java Virtual Machine Specification”, Sun Microsystems, Inc. 1995.

    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.

    J. Gustafsson, “Analysing Execution-Time of Object-Oriented Programs using Abstract Interpretation”, PhD thesis, Uppsala University, Uppsala, Sweden, May 2000.

    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.

    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.

    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.

    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.

    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.

    C, A. Healy, “Automatic Utilization of Constraints for Timing Analysis”, PhD thesis, Florida State University, July 1999.

    J. Gustafsson, “Analysing Execution-Time of Object-Oriented Programs using Abstract Interpretation”, PhD thesis, Uppsala University, Uppsala, Sweden, May 2000.

    A. Ermedahl, F. Stappert, J. Engblom, “Clustered Worst-Case Execution-Time Calculation”, IEEE Transactions on Computers, Vol. 54, No. 9, September 2005.

    C. Sandberg , A. Ermedahl , J. Gustafsson , B. Lisper, “Faster WCET flow analysis by program slicing”, ACM SIGPLAN Notices, v.41 n.7, July 2006.

    P. Altenbernd, “On the false problem in hard real-time programs”, In Proc. 8th Euromicro Workshop on Real Time Systems, pages 102–107, L’Aquila,1996.

    P. Puschner, “Zeitanalyze von Echtzeitprogrammen”, PhD thesis, Technische Universitat, Institut fur Technische Informatik, Vienna, Austria, 1994.

    Y. S. Li, S. Malik, “Performance Analysis of embedded Software Using Implicit Path Enumeration”, In Proc. 32nd ACM/IEEE Design Automation Conference, pages 456–461, Jun. 1995.

    M. Schoeberl, “A time predictable Java processor”, In Proceedings of the Design, Automation and Test in Europe Conference, pages 800–805, Munich, Germany, March 2006.

    R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, F. K. Zadeck, “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph ”, ACM Transactions on Programming Languages and Systems, 13(4):451–490, October 1991.

    C. S. Ananian, “Harpoon Project Compiler Intermediate Representation”, October 12, 1998, www.flex-compiler.lcs.mit.edu/Harpoon/quads/quads.htm.

    M. Corti, “Approximating the Worst-Case Execution of Soft Real-Time Applications”, PhD Thesis, Swiss Federal Institute of Technology (ETH) Zurich, March 2005.

    J. Gustafsson, B. Lisper, C. Sandberg, N. Bermudo, “A tool for automatic flow analysis of C-programs for WCET calculation”, In Bob Werner, editor, Proc. 8th IEEE International Workshop on Object-oriented Real-time Dependable Systems , Guadalajara, Mexico, 2003.

    C. A. Healy. D. B. Whalley, “Tighter timing predictions by automatic detection and exploitation of value-dependent constraints”, In Proc. Real-Time Technology and Applications Symposium, pages 79–88. IEEE, Jun. 1999.

    W. H. Harrison, “Compiler analysis of the value ranges for variables”, IEEE Transactions on Software Engineering, SE-3(3):243-250, 1977.

    M. Obitko, “Introduction to genetic algorithms, University of Applied Sciences, Czech technical university of parague, 1998.

    V. R. Vemuri, “Genetic algorithms”, Computer Society meeting, Department of Applied Science University of California, Davis Livermore, CA, Ottawa, 1997.

    K. A. Dejong and W. M. Spears. “Using genetic algorithms to solve NP-complete problems”, Proc. of the Third Int. Conf. on Genetic Algorithms, 1989.

    J. L. Sobral and A. J. Proença, “Dynamic Grain-Size Adaptation on Object Oriented Parallel Programming The SCOOPP Approach” Universidade do Minho, 4710 Braga, PORTUGAL, 1999.

    Y. Gourhant, S. Louboutin and V. Cahill, “Dynamic Clustering in an Object-Oriented Distributed System” Trinity College , bublin 2 , Ireland , October 9, 1999.

    R. E. Diaconescu, L. Wang and M. Franz, “Automatic Distribution of Java Byte Code Based on Dependence Analysis” University of California, Irvine, 1999.  

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