دانلود مقاله عمل و تئوری مدل بندی شبیه سازی

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

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

1- مقدمه :
در سیستم های موازی چند برنامه ای، نشان داده شده است که زمانبندی پردازش موازی در پردازشگرها عاملی مهم و حیاتی در نیل به اجرای موازی موثر و کارآمد است. کاربرها انتظار دارند که تک تک پردازش شان به اجرا و عملکرد عالی برسند. موضوع اصلی این است که چگونه از بین پردازش های رقیب در منابع سیستم و به نحوی سهیم و شریک شویم که نیازهای پردازش ها مورد نظر را برآورده سازد و عملکرد و اجرای کلی خوب را در بر داشته باشد. این اهداف تعدادی موضوع مرتبط با سیاست زمان بندی را با توجه محیطهای رقیب موازی بزرگ ایجاد می کنند. این مقاله سیستم موازی قابل تقسیم را مدنظر قرار می دهد که در آن تقسیم بندیها زیر سیستم هایی به پردازش های مستقل اختصاص یافته اند (13) . پردازش ها از وظایف موازی ترکیب و تشکیل می گردند که برای اجرای همزمان در مجموعه ای از پردازشگرها برنامه ریزی شده اند. پردازش های موازی نیاز دارند که اساسا در زمان و احدی شروع شوند، اجرای خود را هماهنگ کنند، و هم این که سرعت واحدی را هم محاسبه کنند. این نوع مدیریت منبع برنامه ریزی مشترک یا جدول زمان بندی Gangنامیده می شود و بطور گسترده ای در مطالب سیستم های حافظه مشترک و توزیع شده مورد مطالعه قرار گرفته است.
علل معمول استفاده از زمان بندیGang عبارت است از اجرا و تکمیل آن و استفاده موثر و کارآمد از منابع نمونه هایی از برنامه ریزی عبارت است از اجرای آن دستگاه ارتباط cm-5 ، IBM SP2 و کلاسترهایی از ایستگاه های کاری پردازش ها فقط موقع شروع به اجرا شدن می کنند که پردازشگرهای بیکار کافی برای ارزیابی آنها موجود و قابل دسترس می باشد. با این وجود، سیاست برنامه ریزی برای تعیین این که کدام برنامه ریزی موازی باید برای آن پردازشگرهای موجود مشخص شود مورد نیاز است، در نظامهای موازی چند برنامه ای، تقسیمات پردازشگر معمولا بر اساس قانون و اصل FCFS اختصاص می یابد. این رویکرد می تواند به تقسیم بندی شدیدی منجر شود، چونکه پردازشگرها یی که نمی توانند نیازها و خواسته های پردازش بعد در آن را تامین نمایند تا موقعی بی کار می مانند که منابع مورد نیاز آزاد شوند. برای اجتناب از تقسیم بندی، باید از سیستم سیاست غیر FCFS برای ردیف کردن پردازش ها در انتظار در سیستم استفاده کرد. در(8) ما اجرای دو روش زمانبندی Gang معروف یعنی (LJFS) و (AFCFS) یعنی اصل زودتر آمده زودتر خدمات رسانی شده برگزیده را مورد مطالعه قرار دادیم. این مقاله مدلهای شبکه صف بسته را با تعداد ثابتی از پردازش مورد نظر قرار می دهد. نشان داده شده است که در بسیاری از موارد LJFS عملکرد بهتری نسبت به AFCFS دارد. با این وصف، عیب و ایراد LJFS این استه که در برگیرنده مقدار قابل توجهی اورهد است چونکه صف و پردازشگر مجددا تنظیم و مرتب می شود هر بار که شکل موازی جدید افزوده می شود.
بخش اعظم تحقیق راجع به سیاست زمانبندی پروس شغلی موازی بر ارتقا و بهبود عملکرد و اجرای کلی متمرکز شده است که در آن فرض بر این است که اورهد زمانبندی ناچیز باشد. اما، اورهد زمان بندی می تواند بطور جدی عملکرد و اجرا را تقلیل دهد. در این کار، ما به همراه روشهای AFCFS,LJFS دو سیاست دیگر یعنی روشهای PLJFS (بزرگترین پردازش دوره ای نخست سرویس دهی شده) و LJFS وابسته به درجهای صف (QLJFS) را هم مد نظر قرار می دهیم. با سیاست PLJFS صف پردازشگر فقط در پایان پریودهای زمانی از قبل تعیین شده P مجددا مرتب و منظم می شود. در پایان دوره، برنامه ریز زمانی اولویت های همه پردازش در آن صف را با استفاده از ملاک و معیار LJFS مجددا محاسبه می کند. وقتی که از سیاست QLJFS استفاده شد، صف مورد نظر مطابق با ملاک و معیار LJFS هر مورد درج پررس i در آن صف مجددا مرتب می شود.
هدف ما یافتن این نکته است که آیا روشهای درج وابسته دوره ای صف هم در مقایسه با سیاست LJFSو به حداقل رسانیدن عیب و ایراد آن تا حد ممکن عمل می کنند یا نه. بهینه سازی زمانبندی بصورت به حداقل رسانیدن تعداد موارد تنظیم و ترتیب مجد صف تعریف می شود. ما سیاستهای زمانبندی را برای بارهای کاری مختلف و برای دوره های زمانی متفاوت P و تعداد i درجهای پروس در آن صف را مورد مطالعه قرار داده و با هم مقایسه می کنیم. نتایج تطبیق با استفاده از تکنیک های شبیه سازی بدست می آید. در مقاله قبلی (a) ما روش جدول بندی میانی دوره ای را مورد مطالعه قرار دادیم. اما در آن مقاله مدلهای سیستم و بار کاری متفاوت از مواردی هستند که در اینجا مورد بررسی و آزمایش قرار می گیرند. آن مقاله سیستم توزیع شده ای را مورد مطالعه قرار می دهد که در آن هر پردازشگر به صف خاصی مجهز است. آن مدل شبکه بسته ای را با تعداد ثابتی از پروس مد نظر قرار می دهد. علاوه بر این، اینکه آن زمانبندی Gang گروهی را مورد بررسی قرار نمی دهد. آن پردازش ها را با وظایف مستقل مد نظر قرار می دهد که می توانند در هر پردازشگر و با هر ترتیبی اجرا شوند. جدول زمانبندی Gang دوره ای مدل شبکه باز از سیستم موازی قابل تقسیم در (10) مورد مطالعه قرار گرفته است. در آن مقاله عملکرد و اجرای کلی با متوسط زمان واکنش و پاسخ پروس ها مطرح و بیان می شود در این مقاله ما متریک های اضافی را مورد مطالعه قرار می دهیم که به نحوی بهتر عملکرد و اجرای استراتژیهای زمانبندی را منعکس می کنند. یکی از آنها میانگین SLOWDOWN است. علاوه بر این، اینکه ما دو متریک دیگر یعنی متوسط زمان پاسخ weighted و متوسط weighted slowdown را مورد بررسی قرار می دهیم که در آنها weight تعداد پردازشگرهای مورد نیاز یک پروس است، که همان میزان (تعادل) پروس است. بدین ترتیب، از این که پروس ها با زمان اجرا واحد و یکسان، ولی با نیازهای منبع متفاوت تاثیر واحد بر عملکرد و اجرا کلی برخوردار باشند اجتناب بعمل می آید. علاوه بر این، این مقاله روش زمانبندی اضافی یعنی روشی غیر مستقل از درج های ردیف و صف را مورد مطالعه قرار دهد که (10) مورد مطالعه قرار نگرفته است. سیاست زمانبندی زیاد برای سیستم های چند پردازشگر پیشنهاد شده است، که ارزشیابی آنها معمولا روی بارهای وظیفه با تنوع و تغییر نسبتا اندک در نیازهای فرآوری و پردازش taskاجرا شد. اما، مراکز کامپیوتر چند پردازشگری گزارش داده اند که ضریب تنوع زمان خدمت آنها در واقع می تواند بیشتر از یک باشد. این مقاله تحقیق قبلی ما (11) را توسعه و بسط می دهد که در آن از توزیع مطلوب برای نیازهای خدماتی کارهای موازی استفاده می شود. این مقاله همچنین اجرای استراتژیهای جدول زمانبندیGang در موردی را مورد بررسی قرار می دهد که در آن نیازهای خدماتی پروس های موازی تنوع و تغییر زیاد و بالائی را ارائه می دهند. بدین ترتیب قادریم که تاثیر تنوع و تغییر نیازهای خدماتی کاربری اجرای استراتژیهای زمانبندی را مورد بررسی قرار دهیم.
این مقاله نتایج اضافی بوجود آمده از طریق استفاده از توزیع Branching Erlang برای نیازهای پروس task ها را ارائه داده و مورد تجزیه و تحلیل قرار می دهد، و مطالعه و بررسی مفصل تر از تاثیر بر اجرای پارامترهای بار کاری متعدد را فراهم می آورد. به نظر ما، زمانبندی Gang در سیستم های پارالل قابل در این مدلهای بار تقسیم workload کار در مطالب و ارائه نشده است. در این مقاله نتایج از مطالعات به جای سنجش هایی از سیستم های واقعی بدست آمده است. اما، ما معتقدیم که نتایجی را که ارائه می دهیم از ارزش عملی برای سیستم های واقعی برخوردارند. استراتژیهایی را که مورد مطالعه قرار می دهیم از این سیستم های موازی ویژه و بارهای کاری بدست نمی آوریم، اجرای نسبی استراتژیهای زمانبندی Gang متفاوت را برای بارهای کاری متعدد مورد مطالعه قرار می دهیم و این که چگونه این تغییرات در بار کار بر عملکرد و اجرا تاثیر می گذارند را مورد بررسی و آزمایش قرار می دهیم. برای سیستم های ساده، می توان با استفاده از تئوری صف برای کسب کارایی در مقیاسهای اندازه گیری عملکرد و اجرا مدلهای عملکرد و اجرا را بصورت ریاضی مورد تجزیه و تحلیل قرار داد. سیستم های b ، علاوه بر توزیع مطلوب برای نیازهای پردازش کار، شامل توزیع Branching Erlang هم می باشد. همینطور شامل سیاست زمانبندی با پیچیدگیهای متفاوت هم می باشد. برای سیستم های پیچیده مدل بندی تحلیلی دشوار است و اغلب اوقات مستلزم فرضهای اضافی ساده کننده است چنین فرضهایی ممکن است تاثیر غیر قابل پیش بینی بر نتایج داشته باشد. به این دلیل، در برخی از موارد پژوهش زیادی برای پیدا کردن آنالیزهای تقریبی، برای ایجاد و توسعه مدلهای مطلوب در برخی موارد، و اجرای شبیه سازیها وجود داشته است. در این پژوهش ما از شبیه سازی استفاده کردیم جونکه شبیه سازی شبکه تحت مطالعه بطور مفصل تر ممکن است. مدلهای شبیه سازی مفصل به تعیین مشکلات عملکرد و اجرا در معماری کمک می کنند و همین طور در تعیین مشکل و ترکیب سیستم هم کمک می کند. ساختمان این مقاله به شرح زیر است: قسمت دوم مدلهای سیستم و بارکار را معین می کند، استراتژیهای زمانبندی را توصیف می کند، و متریکهای مورد استفاده را ارائه می دهد در حالی که عملکرد و اجرا استراتژیهای زمان بندی را مورد ارزیابی و بررسی قرار می دهد. قسمت سوم اصول و روش تحقیق آزمایش و پارامترهای ورودی را توصیف می کند، و همینطور هم نتایج آزمایشی را ارائه داده و تجزیه و تحلیل می کند. قسمت چهارم حاوی نتیجه گیری ها و پیشنهادها برای پژوهشی بیشتر است و بخش آخر منابع و ماخذ می باشد.
2- مدل و روش تحقیق
1-2: مدل های سیستم و بارکاری
مدل شبکه صف باز ملاحظه می شود که از p=128 پردازشگر موازی متجانس تشکیل و ترکیب شده است. نمونه ای از ماشین با این اندازه sweetgum است که ابر رایانه SGI origin 2800 مجهز به CPU ، 128 است. همه پردازشگرها در حافظه واحدی مشترک هستند. تاثیرات نیازهای حافظه و موارد پنهانی برقراری ارتباط به صورت صریح در این مدل سیستم ارائه نشده است. در عوض، آنها در زمان اجرای پروس به صور ت واضح بنظر می رسند. ما با پوشش دادن انواع متفاوت عملکردها و رفتارهای اجرای پروس انتظار داریم که ویژگی های معماری متعددی هم مد نظر قرار بگیرد.
بخش مهمی از طراحی سیستم چند پردازشگر اشتراک بارکاری در بین پردازشگرهاست. این امر شامل تقسیم پروس های ورودی به وظایفی می شود که می تواند بصورت موازی اجرا شود و وظایف را برای پردازشگرها تعیین می کند و اجرای task در هر پردازشگر را برنامه ریزی می کند. از سیستم پردازشی موازی قابل تقسیم استفاه می شود که بصورت دینامیک پروس را برای سیستم های فرعی پردازشگر تخصیص می دهد. ملاحظه می کنیم که هر پروس X از Tx task تشکیل و ترکیب می شود که در آن 1<TX<P0. بنابراین، ما تعداد task ها در هر پروس را به تعداد پردازشگرها در سیستم ارتباط می دهیم. تعداد پردازشگرهای مورد نیاز پروس X بصورت P(X) ارائه و نشان داده می شود، که به آن اندازه پروس x گفته می شود. به پروس کوچک یا بزرگ اطلاق می شود، که مستلزم تعداد اندک یا زیادی از پردازشگرهاست. واضح است که tx=P(X) . پردازشگر P(X) باید بصورت همزمان برای X پروس اختصاص یابد، و وقتی که این امر صورت گرفت ، با پروس X نگه داشته می شوند تا وقتی که تکمیل گردد. پروس x1,…..XJ را می توان بصورت همزمان اجرا کرد اگر که رابطه زیر حفظ شود:
P(X1)+P(X2)+…+P(XJ)<P
هر پروس فقط وقتی اجرا را شروع می کند که چردازشگرهای بیکار کافی برای برآورده کردن نیازهایش موجود و قابل دسترس باشد. وقتی شغلی اجرای خود را خاتمه می دهد، همه پردازشگرهای تعیین شده برای آن اصلاح می شوند. فرض ما بر این است که هیچ رابطه متقابلی بین اندازه پروس و تقاضای سرویس task وجود ندارد. مثلا، ممکن است که پروس کوچکی زمان سرویس طولانی داشته باشد. تعداد پروس را که می وان بصورت موازی پردازش کرد بستگی به اندازه های پروس و سیاست زمانبندی مورد استفاده دارد. تکنیک مورد استفاده برای ارزشیابی عملکرد و اجرای دیسیپلین زمانبندی با استفاده از شبیه سازی بار کار ترکیبی است. در مطالعاتی نظیر این عموماً یک نفر ملزم است که از بارهای کار ترکیبی استفاده کند چونکه سیستم های واقعی دارای بارهای کار واقعی معمولا برای آزمایش موجود نمی باشد. همینطور بدست آوردن مدلهای تحلیل مفید دشوار است چونکه مدل بندی موارد ظریف دیسیپلین های نظم و انضباط متنوع دشوار است و چونکه مدل بارکاری کاملا پیچیده است. ما عملکرد و اجرای الگوریتم های زمان بندی پروس مورد نظر مدلهای بارکار متعدد را مورد بررسی قرار می دهیم، که هریک از آنها از ویژگیهای معینی در ارتباط با (A) توزیع زمان Iinter-arrival پروس (b) توزیع تعداد task های پروس و (c) توزیع تقاضای سرویس کاری برخوردار است.
1-1-2: توزیع زمان inter-arrival پروس
ملاحظه می کنیم که زمانهای inter-arrival متغیرهای تصادفی مطلوب با میانگین 1 هستند.
2-1-2: توزیع اندازه های پروس:
فرض ما این است که اندازه های پروس بصورت هماهنگ در رنج [1-128] توزیع می شوند.
2-1-2: توزیع اندازه های پروس:
فرض ما این است که اندازه های پروس بصورت هماهنگ در رنج (128-1) توزیع می شوند.
3-1-2 : توزیع تقاضای سرویس کار:
ما تاثیر تنوع و تغییر در تقاضای سرویس کاری (زمانبندیGang ) را در مورد اجرای سیستم مورد آزمایش و بررسی و آزمایش قرار می دهیم. تنوع و تغییر بالا و زیاد در تقاضای سرویس کار دلالت بر این دارد که در تعداد نسبتا بالا و زیادی از تقاضاهای سرویس وجود دارد که در مقایسه با میانگین زمان سرویس خیلی اندک و کوچک هستند و تعداد نسبتا کمی از تقاضاهای سرویس وجود دارد که خیلی بزرگ هستند. وقتی که گروهی با تقاضای سرویس بلند مدت اجرا را شروع می کند، پردازشگرهای معین شده خود را برای فاصله زمانی درازی مشغول می کند. و بسته به سیاستگذاری و سیاست زمانبندی ممکن است که وقفه های صف مورد نظر را برای کارهای دیگر منتظر سرویس دهی معرفی و عرضه کند. پارامتری که نشان گر و نماینده تغییر و تنوع در تقاضای سرویس کاری است ضریب تنوع تقاضای سرویس کار است.
- (C ) : این نسبت خطای استاندارد زمان اجرای task به میانگین خود می باشد.
- ما موارد زیر را با توجه به توزیع تقاضای سرویس task مورد بررسی و آزمایش قرار می دهیم:
- تقاضای سرویس کاری بصورت میانگین 1 توزیع می شوند.
- تقاضای سرویس task از توزیع [2]Branching Erlang با دو مرحله برخوردارند. ضریب تنوع c>1 و میانگین 1 می باشد.
2-2: خط مشی های زمان بندی پروس:
اجرای برنامه هایی که متشکل از task های موازی است بطور قابل ملاحظه ای تحت تاثیر انتخاب سیاست مورد استفاده برای زمان بندی task قرار می گیرد. هدف اصلی زمانبندی پردازشگر نیل به عملکرد مطلوب کلی و بالای سیستم است در حالی که همزمان تضمین لازم برای اجرای تک تک پروس در سیستم را فراهم می آورد. در این وظایف فقط سیاست جدول زمان بندی را مورد بررسی و آزمایش قرار می دهیم. زمانهای اجرای task از پیش معلوم نیست. فرض ما این است که زمانبندی تعداد task های موازی هر پروس را می داند. بعد ما استراتژیهای زمانبندی مورد استفاده در این task را مورد بررسی قرار می دهیم.
1-2-2: (AFCFS) : نخست آمده نخست سرویس دهی شده برگزیده:
این روش زمانبندی پروس هر گاه که پردازشگر کافی موجود باشد. وقتی که تعداد پردازشگر های موجود برای پروس بزرگی که در بالا و شروع صف حاضر منتظر است کافی نیست، سپس سیاست AFCFS زمانبندی پروس کوچکتر را قبل از پروس کوچکتر مد نظر قرار می دهد. یک مسئله عمده مرتبط با این سیاست زمانبندی این است که مایل به استفاده از پروس هایی که به تعداد کمتری از پردازشگرها نیاز دارند و ممکن است که تقسیم بندی در سیستم را افزایش دهند.
2-2-2: بزرگترین پروس نخست سرویس دهی شده(LJFS):
با این سیاست پروس در صف اندازه پروس در حال افزایش در صف پردازشگر قرار داده می شوند(پروسی که از تعداد زیادی از task ها موازی تشکیل می شوند در بالای صف قرار می گیرند). همه پروس در آن صف به ترتیب سویچ می شوند، و اولین پروسی که برای آنها پردازشگرهای تعیین شده موجود و قابل دسترس هستند کار اجرا را شروع می کنند، این روش اجرای پروس های موازی بزرگ را به بهای پروس کوچکتر ارتقا می دهند، ولی در موارد زیادی این تبعیض قابل قبول است. مثلا، ابررایانه ها اغلب اوقات پروس بزرگ خیلی موازی را اداره می کنند که نمی توانند در جای دیگری اداره شوند. LJFS از این عیب و نقص برخوردار است که پروس اورهد می باشد چونکه صف پردازشگرها هر بار که گروه جدیدی اضافه می شوند مجددا مرتب می شود.
3-2-2: بزرگترین پروس نخست سرویس دهی شده وابسته به درجهای صف (QLJFS) :
با این سیاست و پروس ها اضافه شدن به صف با توجه به اینکه بزرگترین پروس نخست سرویس دهی می شود. صف مطابق معیار LJFS مجددا مرتب و منظم می شود با هر پروس j که در صف قرار داده می شود. یعنی اینکه صف فقط در زمانی مجددا مرتب می شود که در آن تعداد کل موارد وارد کردن q ضریبی از i است، یعنی وقتی که qmodei=0.

4-2-2: بزرگترین پروس نخست سرویس دهی شده دوره ی (PLJFS):
با این سیاست ، صف پردازشگرها فقط در پایان دوره های زمانی از قبل تعریف شده p مجددا مرتب می شود. سپس اولویت ها و خواص همه پروس ها موازی در صف را با استفاده از ملاک و معیار LJFS مجددا محاسبه می کند. هدف QLJFS و PLJFS کاهش تعداد صف بندی مجدد صف در مقایسه با LJFS و ارتقا و بهبودی اجرای خوب است. هنگام استفاده از اولویت ها در مورد ارتباطات از روش FCFS استفاده می شود. شایان توجه است که دانش اولیه مراجع به پروس به شکل تقاضای سرویس قبل دسترسی و موجود است. فرض فهرست کننده بر این است که اطلاعات قبلی همیشه موجود نیست. چنانچه در این مقاله بیان می کنیم، فهرست کننده اطلاعات قبلی راجع به زمان اجرای کار ندارد. به همین علت ما از این پژوهش استفاده نمی کنیم.
3-2: معیارهای سنجش اجرا:
زمان پاسخ rj یک پروس j فاصله زمانی از ورود آن پروس به صف پردازشگر تا زمان تکمیل سرویس برای آن پروس است (یعنی زمان صرف شده در صف پردازشگران بعلاوه زمان سرویس پروس). پارامتر دیگر متریک slowdown است. پروس زمان پاسخ آن پروس تقسیم بر زمان اجرا اجرای پروس است. مضافا بر این که ما زمان پاسخ هر پروس و slowdown آنرا با اندازه اش مورد بررسی قرار می دهیم(16). بدین ترتیب، از این که پروس ها با زمان اجرای واحد، ولی با تعداد متفاوتی کارهای موازی از تاثیر واحد و یکسانی بر اجرای کلی برخور باشند اجتناب می شود. به این دلیل زمان پاسخ slowdown weighted مورد بررسی و آزمایش قرار می گیرند. پارامترهای مورد استفاده در محاسبات شبیه سازی (که بعدا ارائه می شود) در جدول یک نشان داده شده است. فرض می کنیم که i تعداد کل پروس های پردازش شده باشد. اگر ej زمان اجرا (زمان سرویس) پروس xj,j=1,2,…….i باشد، آنگاه sj پروس xj بصورت زیر تعریف می شود:
S=rj/ej

فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد

تعداد صفحات این مقاله   28 صفحه

پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید