20027

۲۰۰۲۷

ارائه يك معماري جديد قابل بازپيكربندي براي پياده سازي الگوريتم هاي مرتب سازي با استفاده از مدارهاي مجتمع قابل برنامه ريزي

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

معماري سيستم هاي كامپيوتري

۹۵-۹۷

۱۳۹۷/۱۰/۲۳

دكتر حاكم بيت الهي

كامپيوتر

مرتب سازي روش پردازش داده مرسومي است كه در بسياري از كاربردها استفاده مي شود. پياده سازي شتاب دهنده سخت افزاري براي تسريع مرتب سازي داده هاي بزرگ و استفاده از تمام پهناي باند حافظه اصلي، موضوعي است كه اخيراً مورد علاقه بسياري از محققان قرار گرفته است. مرتب سازهاي سخت افزاري موازي به منظور افزايش كارايي ارائه شده اند كه پياده سازي آنها در مدارهاي مجتمع با كاربرد خاص و مدارهاي مجتمع قابل برنامه ريزي ترجيح داده مي شود. شبكه مرتب ساز ادغامي بايتونيك يكي از بهترين الگوريتم هاي مرتب سازي موازي بر پايه ادغام است. منابع سخت افزاري مورد نياز اين شبكه مرتب ساز به واحد هاي مقايسه و مبادله(CAS) وابسته است. با افزايش تعداد ركوردهاي ورودي به شبكه مرتب ساز، تعداد واحدهاي CAS افزايش يافته و منابع مورد نياز افزايش و فركانس كاري كاهش مي يابد. در سيستم هاي بلادرنگ ثابت بودن زمان اجرا ترجيح داده مي شود و زمانبند بايد بدترين زمان اجراي مرتب سازي را بداند. در اين پايان نامه، قصد معرفي روش ابتكاري براي مرتب سازي ركوردهاي ورودي به صورت جزئي را داريم كه با افزايش ركوردهاي ورودي به ارائه زمان اجرا ثابت نزديك شويم. نتايج نشان داده اند كه تعداد جداول جستجو روش ارائه شده نسبت به مرتب ساز بايتونيك متداول 70.2 درصد و نسبت به جديدترين معماري مرتب ساز 87.3 درصد كاهش يافته است. همچنين تعداد ثبات مورد نياز روش ارائه شده نسبت به جديدترين معماري مرتب-ساز 94.8 درصد كاهش يافته است.

1397/11/16

A New Reconfigurable Architecture to Implement Sorting Algorithms using FPGA

1/13/2019 12:00:00 AM

Sorting is a traditional data processing technique, used in various applications. Implementing hardware accelerators along with using full memory bandwidth, has gained extensive attention from research community. Application-specific integrated circuits (ASIC) and field-programmable gate arrays (FPGA) are preferable for implementing several Parallel Hardware Sorting Architectures (PHSA). Bitonic sorting is a parallel comparison-based sorting network, which is used in many hardware implementations. Number of Compare-And-Swap (CAS) blocks determines the amount of resources used in a Bitonic network. By increasing the number of input records in a sorting network, the number of CAS blocks will increase as well, which leads to a rise in resource consumption. The frequency also decreases, due to the increase in the number of steps in the Bitonic sorting. Schedulers often sort their task queues, depending on their scheduling policy. In Real-Time systems, it is preferable to have a constant time for sorting operations, so Scheduler should know the worst execution time. This paper proposes a novel approach for PHSA, in which a set of partial sorters sorts the input records to approach a constant time. The sorting time is almost constant, even if input records are increased, which is suitable for Real-Time applications. The results show that the number of LUTs of the proposed method has decreased by 70.2% and 87.3% compared to the Conventional Bitonic Sorting Network (CBSN) and the state-of-the-art PHSA, respectively. Also, the number of registers of the proposed method has decreased by 94.8% compared to the state-of-the-art PHSA.