الفهرس 
IntroductionOnly 14 pages are availabe for public view
 |  | from | 142 |  |  |
| | | from | 142 | | |
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.