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

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

الكترونيك

اسفندماه 1394

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

برق

چكيده سامانه‌هاي پردازشي قابل‌بازپيكربندي امكان اجراي چندين عمليات (وظيفه) پيچيده را به طور همزمان و با استفاده از منابع سخت‌افزاري و نرم‌افزاري فراهم مي‌سازند. اين ويژگي سبب گرديده كه اين سامانه‌ها در سالهاي اخير مورد توجه بسياري قرار بگيرند چرا كه از يك سو با بهره‌گيري از منابع سخت‌افزاري موجب افزايش سرعت اجراي عمليات پيچيده مي‌گردند و از سوي ديگر به علت امكان تغيير پيكربندي تراشه در حين اجراي عمليات از انعطاف‌پذيري بسيار بالايي براي اجراي وظايف پيچيده برخوردارند. در اين پايان‌نامه روشي براي جايابي و زمان‌بندي وظايف بر روي سامانه‌هاي پردازشي قابل‌بازپيكربندي ارائه شده است. در روش پيشنهادي اندازه وظايف را تغيير داديم و براي هر وظيفه چندين نسخه‌ي متفاوت در نظر گرفتيم. اين تغيير اندازه تبادلي بين عرض وظيفه و زمان اجراي آن در سخت‌افزار مي‌باشد به گونه‌اي كه در نهايت حاصلضرب اين دو پارامتر در نسخه‌هاي متفاوت يك وظيفه يكسان مي‌ماند. براي جايابي و زمانبندي وظايف با ويژگي تغيير اندازه دو روش "نزديكترين زمان شروع" و "نزديكترين زمان اتمام" را ارائه كرديم و هر كدام از اين دو روش نيز در دو حالت پيوسته و گسسته شبيه‌سازي شدند. با توجه به نتايج حاصل از شبيه‌سازي، روش "نزديكترين زمان شروع"در شرايط باركاري زياد نسبت به روش "نزديكترين زمان اتمام" عملكرد بهتري دارد در حالي كه با افزايش مقدار u و كاهش بار كاري عملكرد روش "نزديكترين زمان اتمام" بهتر از ديگر روش پيشنهادي مي‌باشد اما هر دو روش در بار كاري كمتر بهبود بيشتري نسبت به الگوريتم وظايف چند نسخه‌اي ]33[ داشته‌اند. در بار كاري كم (u=2.5) روش "نزديكترين زمان شروع" نرخ رد وظايف را 51.56% و زمان كل اجراي وظايف را 36.92% و ميزان بهره‌برداري از سطح RPU را 2.73% بهبود بخشيده است و روش "نزديكترين زمان اتمام" نرخ رد وظايف را 57.01% و زمان اجراي وظايف را 50.17% و ميزان بهره‌برداري از سطح RPU را 6.14% بهبود بخشيده است. در بار كاري زياد (u=1.5) روش "نزديكترين زمان شروع" نرخ رد وظايف را 27.29% و زمان اجراي كل وظايف را 20% و ميزان بهره‌برداري از سطح RPU را 1.2% بهبود داده و روش "نزديكترين زمان اتمام" نرخ رد وظايف را 10.14% و زمان اجراي كل وظايف را 7.5% و ميزان بهره‌برداري از سطح RPU را 5.06% بهبود داده است. البته ميزان بهبود به پارامترهاي ديگري مانند ميزان زمان اضافي و باركاري و عرض RPU نيز بستگي دارد. كلمات كليدي: الگوريتم زمان‌بندي، وظايف چند نسخه‌اي، تغيير اندازه وظايف سخت‌افزاري

1396/01/19

1/1/1900 12:00:00 AM

Abstract: Reconfigurable computing units consist of a software an​d hardware resources an​d are able to do multiple complex tasks simultaneously. This feature made them increasingly popular in recent years, because on one hand, it has accelerate the speed of executing complex tasks using hardware resources an​d On the other hand, due to the possibility of changing the configuration of the chip during the operation, it has very high flexibility to run complex applications. In this thesis a new method for scheduling an​d placement of tasks on the reconfigurable computing unit is offered. In the proposed method the size of the tasks is changed an​d for each task we consider several different versions. This changing size is a trade-off between execution time an​d amount of hardware resources needed for a task so that ultimately the multiplication of these two parameters remain the same in different versions of a task. This feature increases flexibility an​d performance of the algorithm. For placement an​d scheduling of tasks with resizing features we offer two methods of history start an​d history finish, either of these two methods were simulated in both continuous an​d discrete modes. According to the results of the simulations, history start method has better performance than the history finish method in high workload. While by increasing the value of U an​d reducing the workload, the performance of history finish method is better than other proposed method, but both methods show better improvement than the multishape algorithm in low workload. In low workload(u=2.5), the history start finish has improved the rejection rate for 51.56% an​d make span for 36.92% an​d utility for 2.73%, at the same workload the history finish method has improved the rejection rate for 57% an​d make span for 50.17% an​d utility for 6.14%. in high workload(u=1.5), ), the history start finish has improved the rejection rate for 27.29% an​d make span for 20% an​d utility for 1.2%, at the same workload the history finish method has improved the rejection rate for 10.14% an​d make span for 7.5% an​d utility for5.06%. Of course, improvement of suggested methods also depends on other parameters such as slack an​d workload an​d the RPU width. Keywords: reconfigurable computing unit, placement algorithm, scheduling algorithm, multiple variant tasks