A Data Sorting Hardware Accelerator on FPGA

In recent years, with the rise of the application of big data, efficiency has become more important for data processing, and simple sorting methods require higher stability and efficiency in large-scale scenarios. This thesis explores topics related to hardware acceleration for data sorting networks of massive input resource or data stream, which leads to our three different design approaches: running the whole data processing fully on the software side (sorting and merging on PC), a combination of PC side and field- programmable gate arrays (FPGA) platform (hardware sorting with software merging), and fully hardware side (sorting and merging on FPGA). Parallel data hardware sorters have been proposed before, but they do not consider that the loading and off-loading of data often is serial in nature. In this analysis, we explore an insertion-sort solution that can sort data in the same clock cycle as is written to the sorter and compare it with standard parallel sorters.‌ The main contributions in this thesis are techniques for data sorting acceleration for large data streams, which involve fully software design, hardware/software co-design and fully hardware design solution on a reconfigurable FPGA platform. The results of this whole experiment mostly meet our predictions, and we show that Insertion-Sort implemented in hardware can improve the data processing speed for small input data sizes.De senaste årens ökning av tillämpad big data har inneburit att effektiviteten blivit viktigare vid databehandling. Enkla sorteringsmetoder kräver högre stabilitet och effektivitet i storskaliga scenarier. Den här avhandlingen undersöker ämnen relaterade till hårdvaruacceleration av datasorteringsnätverk med massiv inmatning eller strömmande data, vilket leder till tre olika designmetoder: att köra databehandlingen helt på mjukvarusidan (sortering och sammanslagning på PC), en kombination av PC och Fält- Programmerbara Gate-Arrays (FPGA) plattform (hårdvarusortering med mjukvarusammanslagning), och enbart hårdvarulösning (sortering och sammanslagning på FPGA). Parallella hårdvarusorterare has föreslagits förr, men de tar vanligtvis inte hänsyn till att indata och utdata ofta är seriell till sin natur. I den här avhandlingen undersöker vi en insertion-sort lösning, som kan sortera indata i samma clock cykel som den läses in, och jämför den med några standard parallella sorterare.‌ De viktigaste bidragen i den här avhandlingen är tekniker för datasorteringsacceleration av stora dataströmmar, vilket involverar en implementering helt i mjukvara, en HW/SW codesign lösning och en implementering helt i hårdvara på en rekonfigurerbar FPGA plattform. Resultaten av experimenten uppfyller mestadels våra förutsägelser, och vi visar att Insertion-Sort implementerad i hårdvara kan förbättra databehandlingshastigheten för små dataserier