انجام پایان نامه

درخواست همکاری انجام پایان نامه  بانک مقالات رایگان انجام پایان نامه

سفارش پایان نامه

|

انجام پایان نامه ارشد

پایان نامه پیاده سازی الگوریتم FLB ( پایان نامه نرم افزار کامپیوتر )

انجام پایان نامه|پیاده سازی الگوریتم FLB ( پایان نامه نرم افزار کامپیوتر ) 100 ص

فصل اول : مقدمه

    قبل از ابداع کامپيوترهای شخصی،  عملا سیستم های توزيع شده ای  وجود نداشته است . در آن دوران ، استفاده از کامپيوتر،  شامل نشستن پشت يک ترمينال و برقراری ارتباط با يک سيستم بزرگ  بود. با اينکه ترمينال ها در  چندين ساختمان و يا حتی محل فيزيکی قرار می گرفتند ،  ولی عملا  يک کامپيوتر مرکزی وجود داشت که مسئوليت  انجام تمامی پردازش ها و ذخيره سازی  داده ها را برعهده می گرفت .
Mainfram  معایب
•    هزينه سيستم های Mainfarme  . يکی از اولين دلايل مهم ، هزينه های بالای سيستم های Mainframe است . اين مسئله از دو زاويه متفاوت قابل بررسی است : هزينه بالای سرمايه گذاری اوليه که بسياری  از سازمان ها و موسسات توان مالی آن را ندارند و دوم اينکه در اين مدل ، دارای صرفا" يک نقطه  آسيب پذير با ريسک بالا می باشيم .
•    مالکيت اختصاصی داده ها. يکی از فاکتورهای مهم ديگر،  سياست های مربوط به مالکيت داده ها است . سازمان ها و موسسات که  دارای داده های اختصاصی خود می باشند،  علاقه مند به واگذاری مسئوليت مديريت داده های مربوطه ،  به ساير مکان های فيزيکی نمی باشند .
•    امنيت . يکی ديگر از فاکتورهای مهم در اين زمينه موضوع امنيت است . برای يک سازمان ،  اولا" دستيابی به اغلب داده های آن می بايست بسادگی محقق گردد و ثانيا"  داده ها ی حساس موجود در  سازمان می بايست از بعد امنيتی،  ايمن نگهداری گردند . تامين دو خواسته فوق ( رويکردهای رقابتی  و رويکردهای امنيتی ) با جدا سازی فيزيکی داده از يکديگر محقق خواهد شد ( انباشت داده ها، با نگرش های متفاوت در رابطه با سرعت در دستيابی و ايمن در ذخيره سازی ، ضرورت وجود برنامه های توزيع شده را بخوبی نمايان می سازد )   
 مسائل فوق،   ضرورت حرکت بسمت ايجاد يک الگوی جديد بمنظور طراحی برنامه های کامپيوتری را مطرح و بر همين اساس نسل جديدی از برنامه های کامپيوتری با عنوان " برنامه های توزيع شده" در عرصه نرم افزار بوجود آمد.که این برنامه ها به سیستم های توزیع شده نیاز دارد.
يک برنامه توزيع شده،   برنامه ای است که پتانسيل های پردازشی آن ممکن است توسط چندين کامپيوتر فيزيکی تامين  و داده های آن در چندين محل فيزيکی،  مستقر شده باشد .
یک سیستم توزیع شده مجموعه ای از کامپیوتر هاست که دارای منابع اجرایی مختلف و زیادی هستند.
مفهوم گرید 1-1
  در گريد  هر شخصي مي تواند به راحتي وارد يك شبكه شود و از توان محاسباتي موجود در شبكه استفاده كند.در شیوه های نوین به جای استفاده از رایانه های اختصاصی برای حل مسائل بزرگ ، با استفاده از رایانه های موجود پراکنده که از همه توان محاسباتی خود استفاده نمی کنند، سعی می شود با جمع آوری این توانهای پراکنده که اغلب بی استفاده می مانند، کارهای خود را انجام دهند. این منابع محاسباتی اگرچه اغلب قدرت و هماهنگی رایانه های اختصاصی را ندارند، اما تعداد زیادی از آنها به وفور در مراکز عمومی از قبیل دانشگاه ها، اداره ها، کتابخانه ها و غیره و حتی در منازلی که اتصال قوی به اینترنت دارند یافت می شوند و این موجب می شود که توان محاسباتی آن در مجموع بسیار بالا باشد و در عین حال هزینه آن به مراتب پایین تر می باشد.
 
  مخصوصاً اینکه هزینه های نگهداری به عهده مالکین منابع می باشد و مدیریت این سیستم صرفاً از منابع برخط در زمانبندی برنامه ها استفاده می کنند.  با استفاده از گرید توان کامپیوتر ها دیگر بی معنا است ، صرف نظر از آن که کامپیوتر شما ضعیف و ابتدایی است ، می توانید به بیش از قدرت کامپیوتری دست یابید که هم اکنون در پنتاگون وجود دارد .
یکی از مزایای مهم سیستمهای توزیع شده سرعت بالای اجرای برنامه‌هاست چرا که یک برنامه همزمان می‌تواند از چندین کامپیوتر برای اجراء شدنش استفاده کند.[22]
  همچنین به علت توزیع شدن اطلاعات, بانکهای اطلاعاتی حجیم می‌توانند روی یکسری کامپیوترهای شبکه شده قرار بگیرند. و لازم نیست که همه اطلاعات به یک کامپیوتر مرکزی فرستاده شود(که در نتیجه این نقل و انتقالات حجیم زمان زیادی به هدر می‌رود.(
به علت تأخیر‌های انتقال در شبکه و نویزهای احتمالی در خطوط انتقالی قابلیت اعتماد اجرای یک برنامه دریک سیستم تنها,بیشتر از قابلیت اجرای آن دریک سیستم توزیع شده است .
همچنین درسیستم توزیع شده اگر یکی از کامپیوترهایی که وظیفه اصلی برنامه جاری را برعهده دارد خراب شود کل عمل سیستم مختل خواهد شد . از طرف دیگر اگر اطلاعاتی همزمان در چند کامپیوتر به صورت یکسان ذخیره گردد ویکی از کامپیوترها خراب شود, داده هارا می‌توان از کامپیوترهای دیگر بازیابی کرد از این نظر امنیت افزایش می‌یابد.
اشتراک  به منابع محاسباتی محدود نمی¬شود. انواع منابع اعم از انباره¬ها،نرم¬افزار و بانک¬های اطلاعاتی را در بر می¬گیرد. در عین حال، امنیت و سیاست محلی نیز تضمین می¬شود.[21]
بعد از اتصال به گرید، کاربر استخر بزرگی از منابع را در اختیار دارد. هنگامی که بار کاری سیستم محلی سنگین باشد، می¬توان بخشی از بارکاری را به سایر منابع گرید منتقل کرد.




  2-1طبقه بندی گرید

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

1 – 3 ارزیابی گرید
   سه مرحله برای ارزیابی گرید وجود دارد اول:تولید سیستم هایی که در اوایل 1990 متولد شد. دوم:تولید سیستم با تمرکز روی ابزار برای حمایت از معیار های بزرگ داده و محاسبه جریان الکتریکی . سوم: تولید سیستم هایی که برای همکاری جهانی بر تغییرات تاکیید دارد .
اولین تولید فوریتی فرا محاسبه یا محیط های گرید نام گذاری شده است. عموما واقعیت این پروژه بهبود بخشیدن به منابع محاسباتی در یک دامنه کاربردوسیع بود. پروژه ارائه شده پیشگام این تکنولوژی [3]فافنر بود.
نسل دوم  گرید در  نتیجه یک فوریت از یک زیر ساخت که قادر به بهم پیوند دادن بیشتر مرکزهای سوپر محاسباتی مشخص شده است. اکنون  با ارتقا تکنولوژیهای شبکه وسازگاری آن با استانداردهای گرید می تواند به عنوان یک زیر ساخت توزیع کننده ممکن و قابل قبول در مقیاس های بزرگ که محاسبات را می خواهند حمایت کنند. در این نوع گرید به طور معمول طبیعت نا همگون منبع ها و بهبود بخشیدن کاربرد ها با محیط همگون ویکنواخت را با مجموعه ای از واسط های استاندارد پنهان می کند.گلو باس  [20]یکی از پروژه های توزیع شده است که برای اینکه گرید را استوار کند.
نسل سوم:سازگاری و انطباق زیادی از مدل های خدمات هدفمند وجود دارد . یک حالت قوی از اتوماسیون در سیستم های این نسل وجود دارد . برای مثال زمانی که انسانها نمی توانند برای مدت طولانی مقیاس و ناهمگونی منابع را ارتباط دهند اما ارسال برای پردازش انجام می شود که باعث خود گردانی درون سیستم ها می شود.

    4-1 کاربردهای گرید

    اخیرا تلاش زیادی برای انتقال دادن برنامه های کاربردی به گرید صورت گرفته است.یک مثال پروژه EGEE است. هدف های آن بهبود بخشیدن کار محققان در دانشگاه و صنعت  با دسترسی به منبع های محاسباتی اصلی و مستقل از محل جغرافیایی آنها است.تمرکز روی تعداد زیادی از کاربران گرید است.دو کاربرد برای پیدا کردن تایید اجرا  و کارایی زیر ساختها انتخاب شده است یکی محاسبه برخوردها با پشتیبانی از انرژی فیزیکی بالا در آزمایشات فیزیک ودیگری گرید های پزشکی که چندین گروه به طور یکسان با مشکلات سیل عظیم اطلاعات و داده های مراقبت از سلامت روبه رو هستند.[14]   
نمونه : تلسکوپ جادوگر(majic)
تلسکوپ طراحی شده برای جستجو در آسمان تا منابع انرژی گاما را مشاهده و کشف کند و اطلاعات فیزیکی زیادی را بررسی کند.
آن بزرگترین تلسکوپ اشعه گاما در جهان است و چندین تلسکوپ دیگر در کشورهای اروپایی به آن در جمع آوری اطلاعات کمک می کنند.توزیع جغرافیایی منابع مدیریت آنها را مشکل می کند و این یک نمونه برای گرید محاسباتی است که می تواند کمک بزرگی بکند زیرا محققان می تواند به طور یکسان به تمام منابع دسترسی داشته باشند. تلسکوپ در شبهای اول ماه کار می کند و حدود 600 گیگا بایت اطلاعات در شب ثبت می کند داده های اضافی  تلسکوپ و اطلاعات هوا شناسی نیز ذخیره می شوند.تمام این داده ها باید دریافت و آنالیز شوند.[11]    
   نمونه رایج استفاده از گرید در هواشناسی است.که در آن ایستگاه تلوزیون و شرکت ماهواره ای و مر کز تجسم و یک کامپیوتر مرکزی وجود دارد که ایجاد امنیت و ارتباطات آنها در محیط گرید فراهم می شود.
قدرت گرید بخصوص در پردازش های فشرده مثل تحقیقات علمی و نمونه های مالی و طراحی های صنعتی و نمودار پرداخت تصویر مفید تر است.



1-5   تعریف زمان بندی گرید

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

  1-6 مروری بر تحقیقات گذشته
     طیف وسیع کاربران گرید دارای برنامه¬هایی با نیازمندی¬های متفاوت هستند. ممکن است برنامه¬های آنان دسته¬ای و یا به خط  باشد،  شامل کارهای  وابسته به هم و یا مستقل  باشد.  به همین دلیل، ارائه الگوریتم زمان¬بندی همه منظوره که بتواند برای تمامی سناریوها مناسب باشد، امکان¬پذیر نیست. از این رو ما بحث خود را به زمان¬بندی کارهای وابسته، معطوف نموده ایم. هنگامی که کارهای تشکیل دهنده برنامه دارای ترتیب تقدمی باشند، برنامه، به شکل گراف جهتدار بدون سیکل (DAG ) مدل می¬شود که در آن گره¬ها نشان دهنده کارها و لبه¬ها نشان دهنده ترتیب گره¬هاست. گاهی اوقات وزنی نیز به گره¬ها و لبه¬ها اضافه می¬شود که به ترتیب نشان دهنده هزینه¬های محاسباتی و هزینه¬های ارتباطی است.  ایجاد تعادل بین به حداکثر رساندن موازی سازی و به حداقل رساندن تاخیر ارتباطی به عنوان مسئله مهمی در زمان¬بندی کارها مطرح است. برای زمان¬بندی گراف برنامه، الگوریتم¬های ابتکاری  متعددی مطرح شده است. برای زمان¬بندی گراف برنامه، الگوریتم¬های ابتکاری  متعددی مطرح شده است. این الگوریتم¬ها را می¬توان به سه دسته کلی تقسیم کرد. الگوریتم¬های بر پایه  لیست ، الگوریتم¬های بر پایه تکرار  و الگوریتمهای  کلاسترینگ . ¬
در روش بر پایه لیست به هر کار، اولویتی داده می¬شود و کارها به ترتیب اولویت در لیست قرار می¬گیرند. اولویت باید به گونه¬ای تعیین شود که ترتیب تقدمی کارها، نقض نشود. انتخاب کار برای پردازش به ترتیب اولویت انجام می¬گیرد و کار با اولویت بالاتر زودتر به منبع واگذار می¬شود. تفاوت اصلی الگوریتم¬های این دسته، در چگونگی  تعریف اولویت و تعریف آماده بودن کار برای واگذاری است.
یکی از روشهای کم کردن زمان اجرای گراف برنامه، تکثیر کارها در منابع مختلف است. ایده اصلی الگوریتم¬های بر پایه تکرار،  بهره¬وری از زمان بیکاری منابع است. تکثیر یک کار در چندین منبع، باعث اجتناب از انتقال نتایج از کار قبلی به کار بعدی شده و به همین دلیل هزینه ارتباطی را کاهش می¬دهد. الگوریتم¬های مختلف این روش، بر اساس نحوه گزینش  کار برای تکثیر، از هم متمایز می¬شوند. این الگوریتم¬ها دارای پیچیدگی بالاتری نسبت به الگوریتم¬های ابتکاری لیست هستند.
در سیستم¬های موازی و توزیع شده، کلاسترینگ روش مناسبی برای کاهش تاخیر ارتباطی  گراف به حساب  می¬آید.  در این روش کارهایی که ارتباط زیادی باهم دارند در یک کلاستر قرار می¬گیرند و اعضای یک کلاستر به یک منبع  واگذار می¬شوند و بدین شکل، تاخیر ارتباطی کاهش می¬یابد.
1-    7 مفهوم اصطلاحات بکاربرده شده در این پایان نامه
    application: مجموعه¬ای از کارهای  وابسته و یا مستقل  است که به حل مسئله معینی منتهی می¬شود. در این تحقیق  از واژه فارسی "برنامه" به جای واژه " application " استفاده شده  است. در این تحقیق واژه job نیز معادل واژه application تلقی شده است.
    task : واحد کار application گرید به شمار می¬آید که می¬توان آن را برای اجرا فقط به یک منبع محاسباتی فرستاد . در این تحقیق  از واژه فارسی "کار" به جای واژه " task " استفاده شده  است.

    scheduling: به فرایند کشف منبع، انتخاب منبع و ارسال کار به منبع گفته می¬شود . در این تحقیق "زمان¬بندی" ترجمه شده است.

DAG: برنامه حاوی چندین کار موازی، به شکل گراف جهتدار بدون سیکل "DAG" مدل می¬شود. از این  واژه با عنوان گراف برنامه و یا به اختصار گراف  یاد شده است.
1-    8 نمای کلی پایان نامه
در فصل اول (فصل جاری)، مفاهیم و تعاریف پایه بیان شده است. مفهوم گرید و مسئله زمان¬بندی تبیین شده، روش-های موجود زمان¬بندی گراف برنامه به طوراجمال بیان شده است.
در فصل دوم، به بحث زمان¬بندی در سیستم¬های توزیع شده پرداخته شده و موانع
زمان¬بندی گرید ذکر شده و الگوریتم¬های موجود، مطرح و مقایسه گردیده است.
در فصل سوم، موضوع  زمان¬بندی گراف برنامه در سیستم¬های توزیع شده، مورد بحث و بررسی قرار گرفته، پارامترها و عناصر تاثیرگذار بر الگوریتم¬ها بیان شده است.
در فصل چهارم الگوریتم flb را بیان نموده که می خواهیم آن را پیاده سازی کنیم ودر فصل پنجم شبیه سازهای گرید رامورد بررسی قرار می دهیم.در انتها نیز کارهای انجام شدهو نتایج بدست آمده و پیشنهادات  رامطرح می کنیم.





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


انجام پایان نامه کامپیوتر

 

پایان نامه

برای دیدن ادامه مطلب از لینک زیر استفاده نمایید

سفارش پایان نامه

نقشه