18753

۱۸۷۵۳

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

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

الكترونيك

مهرماه ۱۳۹۶

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

برق

سربار بازپيكربندي يكي از مشـكلات اصـلي پـيش روي افـزايش سـرعت پردازنـده هـاي قابـل بازپيكربنـدي (پردازندههاي پياده سازي شده بر روي تراشه هاي قابل بازپيكربندي نظير اف پي جي اي) است، تا جايي كـه در برخي موارد بيش از نيمي از زمان كار يـك پردازنـده ي قابـل بازپيكربنـدي صـرف جايـابي مناسـب وظـايف و پيكربندي مجدد آنها ميشود. اگر بتوانيم زماني كه يك وظيفه بر روي سطح تراشه وجود دارد به درسـتي تشخيص دهيم كه در آينده ي نزديك مجددا اين وظيفه بر روي سطح تراشه مورد نياز خواهد بود، ميتوانيم با پايان يافتن زمان اجراي آن وظيفه، آن را بر روي سطح تراشه نگاه داريم تا اگر مجددا براي اجـرا بـه سـطح تراشه وارد شد، بدون نياز به پيكربندي مجدد آن را در همان نقطه اجرا كنيم و زمان بازپيكربندي و جايابي آن را حذف نماييم. در اين پايان نامه يك روش جديد براي استفاده ي مجدد از وظايف موجود بر سـطح تراشـۀ دوبعدي پيشنهاد شده است. در اين روش، وظايفي كه براي اجرا به تراشه مي آيند بر اساس مشخصه هايشان به دو دستۀ بااولويت و بدون اولويت تقسيم بندي ميگردند و وظايف هر دسته بر روي سـطح تراشـه بـر روي يك قسمت مشخص پيكربندي ميگردند. براي وظايف بااولويت در صورتي كه استفادة مجدد از وظايف قبلي امكانپذير نباشد و جايي براي آن بر روي سطح تراشه يافت نشود، از روشهاي ديگري نيز براي كاهش نرخ برگشت خوردن استفاده ميگردد. جابجايي با وظايف موجود بر سطح، استفاده از فضاي خالي قسمت مقابل، تغيير مكان مرز بين دو قسمت، جلوگيري از جابجايي نادرست مرز بين قسمت مهم و غيرمهم، تخمين نـرخ تكرار و آستانۀ مهم بودن پويا از جملۀ اين روشها هستند. همچنين يك محيط شبيه سـازي مناسـب بـراي ارزيابي عملكرد و مقايسۀ اين كنترل كننده با ديگر كنترل كنندهها توليد شده است كه در آن مشخصـه هـاي گروه بندي برنامه جهت شبيه سازي وابستگي وظايف، در نظر گرفتن جريمۀ برگشت خوردن، چندشكلي بودن وظايف و ارزيابي صحيح عملكرد الگوريتمها با استفاده از محاسبۀ آمار مناسب پياده سازي شـده انـد. اجـراي شبيه سازي نشان ميدهد كه الگـوريتم پيشـنهادي، در اجـراي برنامـۀ شـبيه سـازي شـده بـيش از %15 از الگوريتمهاي قدرتمند فعلي سريعتر است و محاسبات مورد نياز آن براي جايابي و تصميم گيري نيز بـيش از %70نسبت به ديگر الگوريتمها كاهش داشته است

1397/02/10

10/14/2017 12:00:00 AM

Reconfiguration overhead is one of the main obstacles in increasing speed performance in dynamically reconfigurable Field-Programmable Gate Arrays (FPGA), sometimes consuming more than half of time needed to execute a task. If it is recognized and forecasted correctly, a task can be preserved on FPGA’s surface after it has finished, in order to be used again if repeated in the future. In this thesis, an approach for reusing a repetitive hardware task in 2- dimensional hardware is proposed. At first, incoming tasks are divided into significant and non-significant task groups based on their features using fuzzy logic controller. Each group is placed in a specific partition of hardware and several methods such as replacement of significant tasks, using empty spaces in other partition, changing the partition border and trying to maintain border’s place, repetition ratio approximation and dynamic threshold for task significance are applied to reduce the rejection ratio. A simulation environment has been made to evaluate the algorithm’s performance and to make comparison with other state-of-the-art algorithms in this field which considers lots of necessary features like grouping tasks to simulate task dependency, rejection penalty, performance evaluation and etc. Conducted simulation shows that in repetitive programs, the proposed method has %15 less makespan and decides more than %70 faster than state-of-the-art algorithms in this field.