DIGITAL ARCHITECTURE OF SORTING ALGORITHMS BASED ON FPGA

Abstract

Due to the burgeoning demand of programmable logic density having fast speed, high density and based on hardware description language (HDL), the engineers are being empowered to implement within Field Programmable Gate Array (FPGA) high performance digital functionality and various complex circuits. Sorting algorithms have marked an epoch in the life of computer engineers and the advancements related to these will only help in adding tranquility to their lives while they are maneuvering large amounts of data at a time.

This research encompasses the sorting algorithms covering all of their facets from the history of the algorithms up to their implementation in the software and also giving the details about the research that has been carried out comrade in the hardware domain. I have implemented 6 sorting algorithms in Verilog language i.e. Bubble sort, Merge sort, Insertion sort, Selection sort, Radix sort and Count sort. Bubble sort has the easiest hardware implementation as evident in the analysis carried whereas count sort is limited by the largest number present in the array. All of these have been compared on the basis of the three most important metrics which are always considered in the design and implementation in VLSI field i.e. area, timing and power.

Target device used for obtaining synthesis results is ZYNQ – 7000 FPGA, which is increasingly becoming popular among the FPGA engineers due to its advanced features that make it stand out among all boards in the presence of an ARM cortex A9 chip which is the main reason for its usage as a system on chip (SOC), having an integrated support for PCI Express also helps it to

v

persuade its dominance over other FPGAs known to us.

For simulations and synthesis, VIVADO 2019.1 has been used. The output waveforms of all the six sorting algorithms have been plotted. They have further been analyzed in terms of hardware utilization (number of slices, which is comprised of Look Up Tables or LUTs and flip flops) , timing (delay in ns) and power consumption (in mW).