بخشی از مقاله
عمل و تئوری مدل بندی شبیه سازی
عملکرد و اجرای استراتژیهای زمانبندي 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) توزیع می شوند.
