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

مقدمه
در سال های اخير صنعت کامپيوتر رشد بسيار شگفت انگيزی داشته است. در طی دو دهه اخير سرعت کامپيوتر های شخصی از چند دستور در ثانيه به چند ميليون دستور در ثانيه رسيده است در صورتی که قيمت آنها نيز از چند ميليون دلار به چند هزار دلار کاهش يافته است.
افزايش نياز به سيستم هایی با کارائی بسيار زياد و سرعت فوق العاده بالاي شبکه ها (شبکه هاي ترابيتی) سبب جلب علاقه محققان به پردازش هاي موازي و توزيع شده، شده است. از جمله دلايل افزايش توجه به سيستم های توزيع شده می توان به موارد زير اشاره کرد:
1: پيشرفت تکنولوژي پردازش.
2: سرعت بالاي شبکه ها.
3: انجام تحقيقات گسترده براي ارائه محيطهائی برای انجام محاسباتي توزيع شده.
بعلاوه به نظر می رسد با افزايش روزافزون نياز به توان پردازشی سريعتر، هيچ بستر محاسباتي منفرد، نمي تواند پاسخگوی اين نياز باشد بنابراين محيطهاي پردازشي آتي بايد بتواننداز منابع محاسباتی نا همگن موجود در شبکه استفاده کنند. فقط سيستم هاي موازي و توزيع شده امکان استفاده از منابع مختلف موجود در شبکه را ميسر می کنند.
از سوی ديگر تحول چشم گيری نيز در صنعت شبکه های کامپيوتری به وجود آمده است. امروزه هزاران کامپيوتر می توانند از طريق يک شبکه LAN به يکديگر متصل شده و در کسری از ثانيه داده های خود را با يکديگر مبادله کنند. يا به کمک يک شبکه WAN ميليون ها کامپيوتر از سرتاسر دنيا قادر به تبادل داده با يکديگر هستند.با توجه به اين تحولات، امروزه تصور مجموعه ای از کامپيوتر ها که به صورت يک کامپيوتر يکپارچه اما با قدرت بسيار بيشتر ،چندان بعيد نيست.
فصل اول
مفاهيم اوليه
1-1. سيستم های توزيع شده
در حالت کلی تعريف زير را می توان برای يک سيستم توزيع شده ارائه کرد:
يک سيستم توزيع شده مجموعه ای از کامپيوتر های مستقل می باشند که برای انجام کارهای مختلف با يکديگر همکاری کرده و به صورت يک سيستم واحد و قدرتمند برای کاربران ديده می شوند.
مزایا و معایب سيستم های توزيع شده
سيستم هاي کامپيوتري توزيع شده به وسيله پژوهشگران به طور گسترده مطالعه شده و مزاياي زيادي در رابطه با آن گزارش شده است. به عنوان مثال پيشرفت هاي اخير در تکنولوژی شبکه ها و پردازه ها، دستيابي به مزاياي زير را امکان پذير ساخته است :
1. افزايش کارايي: وجود چندين کامپيوتر در يک سيستم توزيع شده به برنامه کاربردي امکان پردازش و اجرا به صورت موازي را مي دهد بنابراين سرعت اجراي برنامه کاربردي و کارايي سيستم افزايش مي يابد براي مثال کارايي يک سيستم فايل مي تواند به وسيله تکرار توابع آن بر روي چندين کامپيوتر بيشتر شود. تکرار سيستم فايل باعث مي شود چندين برنامه کاربردي به سيستم فايل به صورت موازي دسترسي داشته باشند بعلاوه تکرار فايل ها ترافيک شبکه را بين سايت هاي مختلف توزيع کرده و تاخير ناشي از صف بندي را کاهش مي دهد.
2. به اشتراک گذاري منابع: به اشتراک گذاري منابع مقرون به صرفه بودن و امکان دسترسي کارا به منابع سيستم را فراهم ميکند يعني کاربران در عرض چند دقيقه مي توانند منابع سخت افزاري و نرم افزاري گران و خاص منظوره را مانند سرورهاي پايگاه داده ها، سرورهاي پردازش، سرورهاي پرينترو… را به اشتراک بگذارند.
3. افزايش توسعه پذيري: سيستم هاي توزيع شده مي توانند به صورت سازگار با محيط طراحي شوند مثلا براي يک محاسبه سنگين، سيستم خود را به گونه اي سازمان دهي مي کند که شامل تعداد زيادي از کامپيوترها و منابع باشد در صورتيکه براي پردازشهای کوچکتر فقط از چند منبع استفاده خواهد کرد بعلاوه در صورت لزوم محدوديتهائی مانند ظرفيت سيستم فايل و قدرت محاسبتی سيستم را مي توان به سادگی با اضافه کردن کامپيوترها يا سرورهاي بيشتر افزايش يابد.
4. افزايش قابليت اطمينان، دسترسي راحت و تحمل پذيري خطا: وجود چندين منبع ذخيره سازي و محاسباتي در يک
سيستم، ساخت سيستم توزيع شدۀ تحمل پذير خطا را مقرون به صرفه و جالب مي کند.
سيستم مي تواند خرابی يک کامپيوتر را به وسيله تخصيص وظايف آن به کامپيوتر ديگر تحمل کند بعلاوه سيستم مي تواند به وسيله تکرار توابع يا منابع، در کامپيوتر های مختلف، خطر از دست دادن آنها را برطرف کند.
5. مقرون به صرفه گي: کارايي کامپيوترها تقريباً هر دو سال يک بار دو برابر شده، در صورتيکه قيمت آنها در دهه اخير تقريبا در هر سال نصف شده است بعلاوه شبکه هايي با سرعت بسيار زياد نيز به وجود آمده است که ساخت سيستم هاي توزيع شده را نسبت به سيستم هاي موازي بر اساس نرخ قيمت به کارايي مقرون به صرفه تر کرده است.
البته اين پيشرفت ها به آساني به دست نمي آيد زيرا طراحي يک سيستم توزيع شده همه منظوره بسيار مشکلتر از طراحي يک سيستم متمرکز است. در طراحي يک سيستم توزيع شد چند منظوره تعداد زيادي از گزينه ها و مسائل بايد در نظر گرفته شوند که پيکر بندي فيزيکي سيستم ،خصوصيات بستر محاسباتي، شبکه ارتباطي، زمان بندي وظايف، سياست هاي تخصيص منابع و مکانيزم کنترل آن ها، ايجاد سازگاري و کنترل همروندي و امنيت، نمونه هايي از آنهاست. اين مشکلات را مي توان ناشي از عدم بلوغ سيستم هاي توزيع شده، ناهماهنگي و رفتار مستقل کامپيوترها، پراکندگي جغرافيايي منابع سيستم و… دانست. اين مشکلات در زير خلاصه شده اند:
1. فهم کامل تئوري محاسبات توزيع شده هنوز صورت نگرفته است. اين موضوع نسبتاً جديد بوده و ما، قبل از اينکه به تئوري طراحي چنين سيستم هاي پردازشي تسلط پيدا کنيم بايد تعداد زيادي سيستم توزيع شده معتبر با اهداف معمول و معماري های متفاوت را طراحي و آزمايش کنيم.
2. رفتار ناهماهنگ و مستقل منابع سيستم يا اجزاي آن، کنترل نرم افزار را پيچيده مي کند در حاليکه اين امر در يک سيستم متمرکز محاسباتي کار ساده اي است. اگر کامپيوترها به صورت مشتري-خدمتگذار سازماندهي شوند، کنترل نرم افزار ساده تر و رفتار آن قابل پيش بيني تر خواهد بود با اين حال اين ساختار با يکي از مشخصات سيستم هاي توزيع شده که همان مستقل بودن کامپيوترها و اجرای آسنکرونن مي باشد در تناقض است.
3. استفاده از شبکه هاي ارتباطي براي اتصال کامپيوترها به يکديگر مرحله ديگري از پيچيده گي را معرفي مي کند. طراحان سيستم توزيع شده نه تنها بايد در طراحي سيستم هاي کامپیوتري و سيستم هاي نرم افزاري و
سرويس ها ماهر باشد بلکه در طراحي شبکه ارتباطي مطمئن، ايجاد همزماني ، سازگاري و برطرف کردن خطاها در يک سيستم پيچيده از کامپيوترهاي ناهمگن و پراکنده از نظر جغرافيايي نيز تسلط داشته باشند. تعداد منابع استفاده شده در چنين سيستمهائی می تواند دهها، صدها و يا حتي هزاران منبع محاسباتي و ذخيره سازي باشد.
يک سيستم توزيع شده حداقل بايداهداف زير را برآورده کند: 1- به سادگی منابع موجود در شبکه را در اختيار کاربران قرار دهد.
2- کاربران نبايد از اين موضوع که منبع مورد استفاده آنها در کامپيوتر ديگری در شبکه قرار دارد مطلع شوند.(شفافيت) 3- سيستم توزيع شده بايد باز باشد.
4- سيستم توزيع شده بايد مقياس پذير باشد.
شفافيت می تواند در جنبه های مختلف سيستم های توزيع شده مطرح شود.
دستيابی: پنهان سازی تفاوت در ذخيره سازی داده ها و نحوه دسترسی به يک منبع
محل : پنهان سازی مکان واقعی منابع در شبکه
مهاجرت: پنهان سازی تغيير محل منابع يعنی در صورت تغيير محل منبع، کاربران از اين امر مطلع نگردند.
تجديد محل: پنهان سازی مهاجرت يک منبع در حال استفاده، از کاربر آن.
تکرار: پنهان سازی تکرار منابع به گونه ای که کاربران از اين امر مطلع نگردند.
همروندی: پنهان سازی استفاده اشتراکی از يک منبع بين چند کابر. به گونه ای که کاربران احساس می کنند تنها استفاده کننده منبع می باشند.
خطا: پنهان سازی بروز خطا در يک منبع و برطرف سازی آن از ديد کاربران. به عبارتی کاربران از بروز خطا در قسمتی از سيستم و برطرف سازی آن آگاه نمی شوند.
يکی از اهداف ديگر سيستم های توريع شده مخفی کردن اين واقعيت از ديد کاربران است که منابع مورد استفاده آنها در بين کامپيوتر های مختلف توزيع شده است. سيستمی که بتواند اين مخفی سازی را به خوبی انجام دهد شفافیت گفته می شود.
مسائل مربوط به مقياس پذيری نیز تا حد زيادی به ميزان مولفه های متمرکز سيستم بستگی دارد. هر چه اين ميزان زياد باشد مقياس پذير کردن سيستم مشکل تر خواهد بود.
با وجود اين مشکلات موفقيت هاي محدودي در طراحي سيستم هاي توزيع شده با اهداف خاص مانند سيستم هاي بانکداري، سيستم حمل و نقل و انبارداری توزيع شده به دست آمده است. با اين حال طراحي يک سيستم توزيع شده مطمئن همه منظوره که هم مزاياي سيستم هاي متمرکز (استفاده و مديريت ساده ويکپارچگي) و هم مزاياي سيستم هاي شبکه اي (وجود ارتباطات،توسعه پذيری ، قيمت وکارائی) را دارد هنوز هم يک کار چالش انگيز است.
انگیزش
ايده شي گرايي از محبوب ترين روش هاي توليد نرم افزار است,كه براي طراحي، توصيف و پياده سازي سيستم هاي توزيع شده نيز بسيار سودمند است.[11] مزيت اين روش براي ساخت سيستم هاي توزيع شده اين است كه ميتوان كدهاي برنامه را در اشيا كپسوله كرده و سپس اشيا را به ماژول هاي مستقلي دسته بندي كرد و هر ماژول را بر روي يك منبع محاسباتي مجزا مستقر نمود. با اين حال به عنوان يک اصل [8]توليد يک برنامه توزيع شده، همواره سخت تر از ايجاد يک برنامه غير توزيع شده است, که عملکردی معادل آن را دارد. به طوري كه ساخت يك سيستم توزيع شده ميتواند به يك كار خسته كننده و مملو از خطا تبديل شود.[4] با وجود اينكه امروزه ابزار ها و تكنيك هاي بسيار مفيدي مانند[29] RPC ،[15] CORBA و[8] DCOM جهت ساخت سيستم هاي توزيع شده با كارايي بالا ارائه گشته اند، اما در حالت كلي فرايند ساخت يك سيستم توزيع شده از بدو پيدايش سيستم هاي توزيع شده تغير اندكي كرده است : برنامه نويس برنامه را به ماژول هاي مختلفي تقسيم كرده، هر ماژول را به صورت مجزا پياده سازي كرده و امكان برقراري ارتباط بين آنها را ايجاد مي كند و در نهايت هر ماژول را در يك كامپيوتر مستقل در شبكه مستقر ميكند. برخي از چالش هايي كه در رابطه با ساخت سيستم هاي توزيع شده پيش روي يك برنامه نويس يا طراح نرم افزار مي تواند قرار گيرد عبارت اند از:
پيچيدگي طراحي و پياده سازي سيستم هاي توزيع شده.
پيدايش نوع جديدي از خطاها مانند خطاهاي ناشي ازهمروندي و همگام سازي پردازه ها.
مشكلات ناشي از سازگاري داده ها در كل سيستم.
موازنه كار بارگذاري شده در منابع موجود در سيستم.
لذا اتوماتيک سازی فرايند تبديل يک برنامه ترتيبی به يک برنامه قابل اجرا برروی يک محيط محاسباتی توزيع شده همواره به عنوان يک مساله باز تحقيقاتی مطرح بوده است. امروزه شبکه‌هاي کامپيوتري به واسطه پيشرفت تکنولوژي ارتباطات توانسته‌اند جايگزين کامپيوترهاي گران قيمت موازيگردند[1].
هنگام طراحي برنامه های توزيع شده براي مسائل کاربردي، اغلب الگوريتم ها به مجموعه اي از کارهاي کلاسيک، و تکراري تجزيه مي شوند. از جمله کارهاي بنيادي که در اغلب الگوريتم ها ديده مي شوند مي توان به انتشار اطلاعات به تمام گره ها،ارسال پيام به برخی از گره ها، سنکرون سازي عمومي تمام پردازه ها، شروع اجراي برخي رويداد ها، ضمن اجراي پردازه ها، يا انجام محاسبه اي که داده هاي مورد نياز آن بين گره هاي مختلف توزيع شده، اشاره کرد. اين عمليات ها معمولا با تبادل پيام بين پردازه ها انجام مي گيرند.با طراحی زير ساختی که بتواند اين primitive ها را در اختيار برنامه های ترتیبی قرار دهد می توان نسخه توزيع شده ای از يک برنامه ترتِبی توليد کرد.
يکي از چالشهاي مطرح در توزيع کد، ميزان تسريع حاصل از توزيع مي‌باشد[4] برنامه هاي علمي نياز به كامپيوترهايي با توان محاسباتي بالا دارند. اين نوع كامپيوترها معمولا بسيار گران قيمت ميباشند. امروزه سعي برآن است تا بجاي استفاده از سوپركامپيوترها از شبكه اي با كامپيوترهاي ارزان قيمت براي حل مسائل علمي استفاده شود. هدف ما توزيع كد برنامه ها جهت حصول حداكثر ميزان همروندي در اجراي كد است در صورت موفقيت مسلما زمان اجرايي به حداقل ممكن كاهش خواهد يافت.
محاسبه زمان اجراي يک برنامه بصورت دقيق امکان ندارد، چون برحسب مسيرهاي اجرايي متفاوت در يک برنامه، زمان اجراي آن متفاوت خواهد بود. بيشترين و کمترين زمان اجراي يک برنامه، به طولاني‌ترين و کوتاهترين مسير اجرايي برنامه از لحاظ زماني بستگي خواهد داشت. هدف از يافتن اطلاعات مسيرهاي اجرايي يک برنامه، تخمين زمان اجراي آن است.
همانطور که بيان شد توزيع کد با هدف افزايش سرعت پردازش صورت مي‌گيرد. بنابراين انتظار مي‌رود کد توزيع شده نسبت به قبل سريعتر اجرا گردد. نکته قابل تامل اين
است که آيا توزيع صورت گرفته باعث تسريع شده است؟ ميزان تسريع (تقويت توزيع) چقدر است؟ براي پاسخ به اين سوالات بايد مشخص گردد مدت زما ن اجراي برنامه، قبل و بعد از توزيع به چه ميزان بوده است.
به هنگام توزيع، بخشي از برنامه در ايستگاه کاري راه دور اجرا مي‌گردد. براي محاسبه زمانِ اجراي برنامه ترتيبي توزيع شده، بايد مدت زمانيکه طول مي کشد تا افراز احضار شده در ايستگاه کاري راه‌دور اجرا گردد و مدت زمان سپري شده بين دستور احضار تا اولين استفاده از نتيجه اين احضار، تخمين زده شود و بر اساس مدت زمان احضار و ارسال نتايج، زمان اجراي توزيع شده محاسبه گردد. بعنوان مثال در مرجع [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 تعويض مي شوند. همچنين با استفاده از آناليز وابستگي داده ها نقاطي از برنامه ترتيبي كه در آنها بايد همگام سازي صورت گيرد كشف شده و كد هاي مناسبي در آن نقاط از برنامه درج مي شود.
ساختار پايان نامه
فصل هاي بعدي در اين پايان نامه به شرح زير سازماندهي شده اند. در فصل دوم تحقیقات و ابزارهای مرتبط با اين پروژه و نحوه استخراج كد خلاصه شده از متن برنامه جهت ساخت گراف فراخواني متد ها ، بررسي شده اند. همچنین انواع روشهاي خوشه بندي براي رسيدن به اهداف مختلف با در نظر گرفتن پارامترهاي متفاوتي از قبيل محدوديت دسترسي به منابع ، پيوستگي، چسبندگي و تعداد فراخوانيهاي بين اشيا، وزن اشاره گرها و غیره نیز بررسی شده است.
در فصل سوم نحوه وزن گذاري گراف فراخواني استخراج شده و ساخت گراف کلاس های برنامه بررسي شده است. در این فصل به بررسي روشهاي مختلف تخمين زمان اجراي برنامه ها پرداخته خواهد شد كه شامل مفاهيم مرتبط با تخمين زمان اجراي برنامه در تحليل ايستا ، رعايت ميزان دقت تخمين زمان اجرا برنامه، معيارهاي موجود در تخمين زمان اجرا و راه حلهاي بهينه در حالتهاي پيش آمده پرداخته خواهد شد.
وزن گذاري به گونه اي صورت ميگيرد كه وزن هر يال نشان دهنده ميزان افزايش در كارايي سيستم در صورت همروندي توابع موجود در گره هاي آن يال باشد.
در فصل چهارم نحوه خوشه بندي گراف وابستگي استخراج شده توسط تكنيك هاي خوشه بندي سلسله مراتبي[4] و يافتن تعداد خوشه هاي بهينه براي كلاس هاي برنامه ترتيبي توصيف شده است. و در فصل پنجم به نحوه پياده سازي و ارزيابي روش پيشنهادي پرداخته خواهد شد كه ابتدا نمودار كلاسها و فعاليت آنها بررسي شده و جهت تكميل مطالب اين قسمت، نمودار اشياي حاصل از كلاسهاي مورد استفاده در ادامه آورده خواهد شد و روش پيشنهادی توسط مسئله فروشنده دوره گرد و مقایسه آن با ساير روش ها ارزيابي می شود.
در فصل ششم با نتیجه گیری از مطالب و نيز بيان کارهای آتی به پايان نامه خاتمه می دهيم.
1-5. جمع بندي

فایل : 133 صفحه

فرمت : Word