• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

Year: 2022, Volume: 15, Issue: 45, Pages: 2458-2467

Original Article

FPGA Design for Low Delay Comparison-free, Odd-even Merge Sorter

Received Date:21 July 2022, Accepted Date:04 October 2022, Published Date:05 December 2022


Background/Objective: Reduced Instruction Set Computer (RISC) is one of the most common types of architecture involved in microprocessor that has several blocks. There is a lot of scope that can be observed in optimizing these blocks involved in RISC resulting in better and effective microprocessors. Method: One of the sub-blocks that plays a prominent role in RISC architecture is sorter, and it can be achieved by modifying the sorting algorithm. Findings: A novel odd-even comparison-free sorting that assists in arranging N several data components in roughly N clock cycles is proposed here. N identical blocks are arranged in streamlined manner that are stacked using handful primary logic elements resulting in sorter computation. In the proposed framework, classification and categorization activities are executed in a channeled fashion. The entire design is amalgamated for numerous data sets from imitated indiscriminately generated data elements to all exceptional elements, to all the similar elements, and also from random to completely sorted data elements. It has been observed that, the algorithm appears impartial to the input ordering. Novelty: comparison-free unit was implemented on odd-even sorter. Synthesis results indicate that the proposed approach consumes reasonably low FPGA resource. The number of elements consider for sorting was N=8, this architecture takes per element sorting delay as approximately 2.1 to 4.4 ns (1 clock cycle).

Keywords: Comparisonfree technique; Hardware sorting engine; Look ip tables; RISC; Delay


  1. Fang J, Mulder YTB, Hidders JJ, Lee J, Hofstee HP. In-memory database acceleration on FPGAs: a survey. The VLDB Journal. 2020;29(1):33–59. Available from: https://link.springer.com/article/10.1007/s00778-019-00581-w
  2. Waterman A, Asanovic K. RISC-V About, RISC-V International. 2020. Available from: https://riscv.org/technical/specifications
  3. Meng X, Yu L, Qin Z. An FPGA-based accelerator platform implements for convolutional neural network. Proceedings of the 3rd International Conference on High Performance Compilation, Computing and Communications. 2019. Available from: https://doi.org/10.1145/3318265.3318285
  4. Preethi DR, K.G DM, K DTT. FPGA Based Hardware Accelerator for Data Analytics: An Overview. SSRN Electronic Journal. 2019;p. 1–8. Available from: https://dx.doi.org/10.2139/ssrn.3664586
  5. Jmaa YB, Atitallah RB. A Comparative Study of Sorting Algorithms with FPGA Acceleration by High Level Synthesis. Computacion Y Sistemas. 2019;23(1):213–230. Available from: https://doi.org/10.13053/CyS-23-1-2999
  6. Ali R. Hardware Solution to Sorting Algorithms: A Review. Turkish Journal of Computer and Mathematics Education. 2022;13(02):254–272. Available from: https://turcomat.org/index.php/turkbilmat/article/download/12198/8860/21626
  7. Papaphilippou P, Luk W, Brooks C. FLiMS: a Fast Lightweight 2-way Merger for Sorting. IEEE Transactions on Computers. 2022. Available from: https://ieeexplore.ieee.org/document/9695338
  8. Ghosh S, Dasgupta S, Ray SS. A Comparison-free Hardware Sorting Engine. Proceedings of IEEE Computer Society Annual Symposium on VLSI, ISVLSI. 2019;p. 586–591. Available from: https://ieeexplore.ieee.org/document/8839318
  9. Skliarova I. A Survey of Network-Based Hardware Accelerators. Electronics. 2022;11(7):1029. Available from: https://doi.org/10.3390/electronics11071029
  10. Gladies EJ. An Efficient Comparison-Free Sorting Unit. International Journal of Pure and Applied Mathematics. 2018;118(20):4931–4937. Available from: https://ieeexplore.ieee.org/ielaam/92/7932577/7862290-aam.pdf
  11. Abdel-hafeez S, AGR, SA. A comparison-free sorting algorithm on CPUs and GPUs. The Journal of Supercomputing . 2018;74:6369–6400. Available from: https://doi.org/10.1007/s11227-018-2567-3
  12. Ghosh S, Dasgupta S, Ray SS. A Comparison-free Hardware Sorting Engine. 2019 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). 2019;p. 586–591. Available from: https://ieeexplore.ieee.org/document/8839318
  13. Yoon M. The VLSI Design of a High-Speed Sorting Engine By Using Demultiplexer Array. International Journal of Engineering Research and Technology. 2019;12(6):814–819. Available from: https://www.ripublication.com/irph/ijert19/ijertv12n5_14.pdf
  14. Bhargav TAS, Prabhu EE. Power and Area Efficient FSM with Comparison-Free Sorting Algorithm for Write-Evaluate Phase and Read-Sort Phase. Communications in Computer and Information Science. 2019;968:433–442. Available from: https://doi.org/10.1007/978-981-13-5758-9_37
  15. Abdel-Hafeez S, Gordon-Ross A. An Efficient O( $N$ ) Comparison-Free Sorting Algorithm. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2017;25(6):1930–1942. Available from: https://doi.org/10.1109/TVLSI.2017.2661746
  16. Issartel D, Gao S, Pittet P, Cellier R, Golanski D, Cathelin A, et al. Architecture optimization of SPAD integrated in 28 nm FD-SOI CMOS technology to reduce the DCR. Solid-State Electronics. 2022;191:108297. Available from: https://doi.org/10.1016/j.sse.2022.108297
  17. Mashimo S, Chu TV, Kise K. High-Performance Hardware Merge Sorter. 2017 IEEE 25th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). 2017;p. 1–8. Available from: https://ieeexplore.ieee.org/document/7966636
  18. Rjabov A. Hardware-based systems for partial sorting of streaming data. 2016 15th Biennial Baltic Electronics Conference (BEC). 2016;p. 59–62. Available from: https://ieeexplore.ieee.org/document/7743728


© 2022 Preethi et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Published By Indian Society for Education and Environment (iSee)


Subscribe now for latest articles and news.