15694

15694

زمان بندي گروهي كارها بر اساس اولويت بندي در سامانه هاي پردازشي چندهسته اي

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

الكترونيك

اسفندماه 1394

اسفندماه 1394

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

برق

چكيده زمان¬بندي گروهي، براي سامانه¬هاي محاسباتي روشي سودمند است. الگوريتم¬هاي زمان¬بندي در بالاترين سطح به دو دسته اشتراك مكاني و اشتراك زماني تقسيم مي¬شوند. در بين تمامي الگوريتم¬هاي زمان-بندي، زمان¬بندي گروهي به دليل كاهش ميزان اتلاف توان پردازنده¬ها از اهميت ويژه¬اي برخوردار است. نسخه پايه زمان¬بندي گروهي در چهار مرحله اصلي انجام مي¬شود. در بين مراحل چهارگانه زمان¬بندي گروهي مرحله چهارم آن پر كردن ماتريس نام دارد كه از اهميت بالايي برخوردار است. در اين مرحله زمان¬بند سعي مي¬كند شيارهاي بدون بار ماتريس زمان¬بندي را تا جاي ممكن با تكثير گروه¬هاي موجود در ماتريس زمان¬بندي پر نمايد. در اين پايان¬نامه روشي براي بهبود مرحله پر كردن ماتريس ارائه‌شدهاست كه سعي دارد تا آنجا كه امكان دارد، باعث افزايش ميزان به¬كارگيري پردازنده¬ها شده و فضاهاي خالي ماتريس زمان¬بندي را پر كند. در نسخه اوليه زمان¬بندي گروهي در مرحله پر كردن ماتريس، عمليات تكثير گروه¬ها بر اساس اولويت زمان شروع آن¬ها انجام مي¬شود و عمل پر كردن ماتريس تا آنجا كه مقدور باشد ادامه پيدا مي¬كند. اما در روش پيشنهادي، تعدادي از سطرهاي ماتريس زمان¬بندي، خالي نگه داشته مي¬شوند و در مرحله زمان-بندي، اجازه پر شدن به اين سطرها داده نمي¬شود و در مرحله پر كردن،عمل پر كردن را تا سطرهاي خالي انتهايي،به صورت روش پايه انجام داده و سپس گروه هاي موجود در شلوغ ترين سطر ماتريس، در سطرهاي خالي ماتريس تكثير داده مي¬شوند. اين روش به دو صورت باعث بهبود زمان پاسخ¬دهي ميانگين مي¬شود. با پر شدن بيشتر ماتريس زمان بندي باعث افزايش ميزان به‌كارگيري پردازنده ها شده و از طرفي به دليل تكراري بودن تعدادي از سطرهاي ماتريس زمان¬بندي باعث حذف شدن تعدادي از سربارهاي تغيير چهارچوب مي شود. روش ارائه‌شده با روش پايه مقايسه خواهد شد و خواهيم ديد كه باعث بهبود زمان پاسخ دهي ميانگين نسبت به روش پايه مي شود. در بهترين حالت، در سياست AFCFS كاهشي به ميزان 9% و در سياست LGFS كاهشي به ميزان تقريبا10% در زمان پاسخ دهي ميانگين نسبت به روش پايه را در پي دارد. واژه‌هاي كليدي: زمان بندي گروهي، پركردن ماتريس، زمان پاسخ دهي ميانگين، زمان پاسخ دهي ميانگين وزن دار، سياست هاي صف بندي