![]() | Only 14 pages are availabe for public view |
Abstract Sorting data is one of the most important processes in data processing. Fast processing is urgently needed for real time data access. Therefore, hardware accelerator is used to fasten the data processing. In this work, Filed Programmable Gate Array (FPGA) based hardware accelerators for data sorting using the existing sorting algorithms; bubble, selection, insertion and merge sorting algorithms are presented. Further, a fair comparison is provided between them in terms of execution time, and area. Our implementations result in that for small data set, merge sort is the best sorting algorithm in terms of execution time. Therefore, it can be used as a parallel cooperative system with Central Processing Unit (CPU) for high speed data processing. All of the previous algorithms were software based. Therefore, working on finding a hardware friendly algorithm that can show better results as a hardware accelerator is necessary. As a result, the Index and Sort Algorithm (IaSA) is proposed as a new sorting algorithm. Our IaSA Hardware architecture is implemented, synthesized, and simulated using Verilog Hardware Description Language (HDL) using FPGA vertex-5 series to measure the performance and scalability. The results of our implementations show that IaSA has the best execution time over other existing sorting algorithms. Our proposed algorithm shows execution time smaller than the fastest literature algorithm, odd even merge sort, by about 11.4%, 40.9%, 62.8%, and 41.1% for 4, 8, 16, and 32 dataset sizes respectively. In order to further optimize the sorting algorithms in terms of execution time, many forms of comparator are presented in order to speed up data processing. Therefore, various sorting algorithm implementations dependent on the type of comparator is provided. To assess performance and scalability, all hardware designs are developed, synthesized, and simulated using Verilog HDL on FPGA vertex-5 series. The results of our implementations show that sorting algorithms based on signed comparator have a faster execution time in various data set sizes. For 4, 8, 16, and 32 dataset sizes, the algorithms with signed comparator execute faster than the algorithms with logical comparator by roughly 5.9 %, 5.8 %, 15.4 %, and 15.3 %, respectively. |