TY - GEN
T1 - Hardware Architecture for a Bit-Serial Odd-Even Transposition Sort Network with On-The-Fly Compare and Swap
AU - Akkad, Ghattas
AU - Ayoubi, Rafic
AU - Mansour, Ali
AU - ElHassan, Bachar
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - Sorting algorithms are computationally expensive routines frequently executed on modern computers and embedded systems. Implementing sorting algorithms on dedicated hardware can contribute significantly to the overall execution time of the processes and applications embodying them. However, such algorithms are known to suffer from a trade off between convergence time and computational complexity. Consequently, this causes performance degradation i.e. bottleneck, when implemented on dedicated hardware with limited resources. In this respect, this paper proposes a novel sequential hardware architecture for a bit-serial Odd-Even transposition sorting network with on-the-fly compare and swap, on field programmable gate array (FPGA). In contrast to the classical parallel-data architecture, which operates on N data bits, this implementation significantly minimizes resource utilization while offering higher clock frequency, on the fly compare and swap and preserving O(N) performance complexity. Simulation and synthesis results demonstrates that the proposed architecture is parallel, minimal in size, can operate on much larger arrays for a reference area size, can be easily expanded, and can achieve higher operating frequency.
AB - Sorting algorithms are computationally expensive routines frequently executed on modern computers and embedded systems. Implementing sorting algorithms on dedicated hardware can contribute significantly to the overall execution time of the processes and applications embodying them. However, such algorithms are known to suffer from a trade off between convergence time and computational complexity. Consequently, this causes performance degradation i.e. bottleneck, when implemented on dedicated hardware with limited resources. In this respect, this paper proposes a novel sequential hardware architecture for a bit-serial Odd-Even transposition sorting network with on-the-fly compare and swap, on field programmable gate array (FPGA). In contrast to the classical parallel-data architecture, which operates on N data bits, this implementation significantly minimizes resource utilization while offering higher clock frequency, on the fly compare and swap and preserving O(N) performance complexity. Simulation and synthesis results demonstrates that the proposed architecture is parallel, minimal in size, can operate on much larger arrays for a reference area size, can be easily expanded, and can achieve higher operating frequency.
KW - Bit-serial
KW - Embedded systems
KW - FPGA
KW - Hardware architecture
KW - Low latency
KW - Median filter
KW - Odd-Even transposition
KW - Sorting
UR - https://www.scopus.com/pages/publications/85083344386
U2 - 10.1007/978-3-030-37277-4_17
DO - 10.1007/978-3-030-37277-4_17
M3 - Conference contribution
AN - SCOPUS:85083344386
SN - 9783030372767
T3 - Lecture Notes in Electrical Engineering
SP - 145
EP - 154
BT - Applications in Electronics Pervading Industry, Environment and Society - APPLEPIES 2019
A2 - Saponara, Sergio
A2 - De Gloria, Alessandro
PB - Springer
T2 - International Conference on Applications in Electronics Pervading Industry, Environment and Society, ApplePies 2019
Y2 - 11 September 2019 through 13 September 2019
ER -