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

Preethi; K G Mohan; Jacob Augustine; K Sudeendra Kumar

doi:10.17485/IJST/v15i45.1384

Article

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

VIEWS 564
PDF 181

Indian Journal of Science and Technology

DOI: 10.17485/IJST/v15i45.1384

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

Original Article

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

Preethi^1*, K G Mohan², Jacob Augustine³, K Sudeendra Kumar⁴

¹Assistant Professor, Department of Computer Science and Engineering, School of Engineering, Presidency University, Rajankunte, Bengaluru, 560064, Karnataka, India
²Professor, Department of Computer Science and Engineering, GITAM University, NH-207, Nagadenehalli, Doddaballapura, 561203, Karnataka, India
³Professor, Department of Computer Science and Engineering, School of Engineering, Presidency University, Rajankunte, Bengaluru, 5600642, Karnataka, India
⁴Associate Professor, Department of Electronics and Communication, PES University, Banashankari, Bengaluru, 560085, Karnataka, India

*Corresponding Author
Email: [email protected]

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

This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

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

References

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
Waterman A, Asanovic K. RISC-V About, RISC-V International. 2020. Available from: https://riscv.org/technical/specifications
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
Franklin M, Chamberlain R, Henrichs M, Shands B, White J. An Architecture for Fast Processing of Large Unstructured Data Sets. In: IEEE International Conference on Computer Design: VLSI in Computers and Processors, (ICCD). p. 280–287.
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
Alif AFMF, Islam SRM, Deb P. Design and implementation of sorting algorithms based on FPGA. In: International Conference on Computer, Communication, Chemical, Materials and Electronic Engineering (IC4ME2). p. 1–4.
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
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
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
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
Skliarova I. A Survey of Network-Based Hardware Accelerators. Electronics. 2022;11(7):1029. Available from: https://doi.org/10.3390/electronics11071029
Ayoubi R, Istambouli SS, Abbas AW, Akkad G. Hardware Architecture For A Shift-Based Parallel Odd-Even Transposition Sorting Network. In: Fourth International Conference on Advances in Computational Tools for Engineering Applications (ACTEA). IEEE. p. 1–6.
Yu L, Jing Z, Yang Y, Tao Y. Fast and Scalable Memristive In-Memory Sorting with Column-Skipping Algorithm. 2022. Available from: https://arxiv.org/pdf/2202.10424.pdf
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
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
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
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
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
Abdel-Hafeez S, Gordon-Ross A. A Comparison-Free Sorting Algorithm. In: International SoC Design Conference (ISOCC). .
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
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
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
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

Copyright

© 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)