Hardware Sorting Algorithm

Today, array sorting is a highly required task. Generating a photo histograms on cameras, folder and file trees on computers, displaying a contact list on a cell phone - all use sorting. Therefore, a quick and efficient sorter will be very useful. This project implements a sorting mechanism that receives an input stream of integer arrays and outputs sorting results in real time, and with zero latency. To do so, the Firmware on the FPGA implements the "Bucket Sort" algorythm. In addition, the mechanism computes the array minimum, maximum, median, common element and array average. The sorting mechanism is implemented on an FPGA which is operated and tested by a MATLAB designated GUI. The GUI and FPGA handle a 2-way communication that allows generation of various data arrays, sending the arrays for sorting and validating the sorting results.

Everyday tasks on computer systems make use of large data sets. Those data sets get processed and analyzed billions of times a day.

The representation of any data set is essentially a series of numbers, often integers. This leads us to the understanding that many basic, core computations should be done as efficiently and optimally as possible.

One of the examples for such data set analysis would be binning of a set of numerical samples. This action is often called a Histogram and is used in a variety of data processing fields such as dynamic range stretching in image processing, building the probability function of a specific set for parameter estimation, etc.

The above leads us to realizing the need for a fast efficient way for quick, hardware dedicated histogram builder.