20460

۲۰۴۶۰

طراحي و شبيه سازي زمانبندي گروهي وظايف به صورت تطبيقي در سامانه هاي پردازشي موازي

كارشناسي ارشد

سيستم هاي الكترونيك ديجيتال

۱۳۹۴

۱۳۹۷/۱۱/۱۷

دكتر هادي شهريار شاه حسيني

برق

زمان‌بندي گروهي تركيبي از اشتراك زماني و اشتراك مكاني مي‌باشد. در اين زمان‌بندي، وظايف با يكديگر دسته¬بندي شده و يك گروه را تشكيل مي¬دهند. همه وظايف در يك گروه بر روي مجموعه‌اي از پردازنده¬ها، هم‌زمان اجرا مي¬شوند. يكي از معايب زمان¬بندي گروهي اين است كه علي¬رغم وجود گروه¬هايي در صف، پردازنده¬هاي بدون بار وجود دارند كه منجر به قطعه¬قطعه شدن فضاي پردازشي مي¬شوند. مهاجرت، راه حلي براي غلبه بر اين مشكل است كه بايد سربارهاي ناشي از آن را در نظر گرفت. به منظور گرفتن تصميمات زمان¬بندي گروهي، از ماتريس اوسترهاوت كه در چهار مرحله انجام مي‌شود، استفاده مي¬كنند. در مرحله دوم كه فشرده‌سازي ماتريس نام دارد، از طريق يكپارچه‌سازي فضاي بي‌بار داخل ماتريس، نقش كليدي در زمان‌بندي گروه‌ها ايفا مي‌كند و اين رويكرد سبب افزايش سرعت زمان‌بندي گروه‌ها و كاهش زمان پاسخ‌دهي ميانگين مي‌شود. الگوريتم بهبود فشرده¬سازي ماتريس (ICMA) از دو ايده، معيار اختلاف و تعويض گروه¬ها استفاده مي-كند و سبب اصلاح مرحله فشرده‌سازي ماتريس مي¬شود. علاوه بر اين با يكپارچه كردن فضاي بي‌بار براي زمان¬بندي گروه¬هاي ديگر، سبب كاهش زمان پاسخ¬دهي ميانگين مي‌شود؛ اما با افزايش سربار زماني ناشي از مهاجرت، زمان پاسخ¬دهي ميانگين نسبت به روش پايه با مهاجرت (BASICwM) به دليل تعداد مهاجرت‌هاي زياد افزايش مي‌يابد. در اين پايان¬نامه با قرار دادن آستانه¬اي براي هزينه‌هاي‌ مهاجرت، به طور موثر از سربارهاي زماني بالا جلوگيري مي¬شود تا زمان پاسخ‌دهي ميانگين كاهش يابد. نتايج شبيه‌سازي شده حاصل از الگوريتم زمان‌بندي گروهي با مهاجرت محدود شده (CMG) در شرايط مختلف، نشان مي¬دهد كه زمان پاسخ¬دهي ميانگين و زمان پاسخ‌دهي ميانگين وزن‌دار نسبت به روش پايه با مهاجرت (BASICwM) كاهش مي¬يابد. با در نظر گرفتن 20، 25 و 30 % طول برش زماني، كاهش زمان پاسخ‌دهي ميانگين در حدود 9 تا 15%، 1/6 تا 7/12 % و 25/2 تا 8/7 % مي‌باشد. نتايج آزمايشات اثبات مي‌كند كه روش مطرح شده براي سربارهاي زماني كم‌تر و بارهاي كاري سنگين‌تر، بهتر عمل مي¬كند. علاوه بر اين مي‌توان از نتايج برداشت كرد كه استفاده از سياست AFCFSwM، عملكرد بهتري در مقايسه با سياست LGFSwM دارد.

1398/02/16

Adaptive Design and Simulation of Gang Scheduling in Parallel Processing Systems

2/6/2019 12:00:00 AM

As a combination of time-sharing and space-sharing, in Gang scheduling tasks are grouped together, and they are executed on processors, simultaneously. Although some processors are idle, gangs are inevitably queued. This approach makes fragmentation in the processing space. One solution technique to overcome this pitfall is using Migration, however it requires consideration of migration overheads. In order to make gang scheduling decisions, Ousterhout matrix with four main steps is employed. The second step that is called Compact matrix is of significant importance due to playing a key roll in scheduling gangs, thereby increasing scheduling speed in other gangs, while reducing the mean response time. Improved Compact Matrix Algorithm (ICMA) utilizes two distinct concepts, namely Difference Criterion and Exchange Idea to improve the performance of the compact matrix. Moreover, it combines gaps for scheduling other gangs, reducing the mean response time. However, with the increase in the migration overhead, the mean response time also increases as compared to the Basic Scheduling with Migration (BasicwM), because the number of occuring migration is much higher than it. In this thesis, high migration overheads are effectively prevented by setting a predefined threshold level for the migration cost. Simulation results achieved from executing the proposed Constrained Migration Gang scheduling (CMG) in different conditions, indicate that the mean response time as well as the weighted mean response time have been conspicuously reduced, compared to the (BASICwM) method. In this regard, it is observed for 20, 25, and 30 percent of the time slots, the mean response time have been declined to 9% to 15%, 6.1% to 12.7%, and 2.25% to 7.8 percent. The simulation results also prove the better performance of the proposed method for smaller migration overheads and the heavier workloads. Furthermore, it can be inferred from the simulation results that adoption of AFCFSwM policy induces a better performance as compared to LGFSwM policy.