CHIP ARCHITECTURE FOR DATA SORTING USING RECURSIVE ALGORITHM

Abstract

Recursive algorithms are widely used for variety of purposes like in non-linear data storage applications, Genetic algorithms, Data compression and Optimization etc. Recursion shows better performance in case of non-linear data structures. The recursion can be implemented in hardware much more effectively. The number of states required for the execution of a recursion in hardware can be reduced compared with software. With the result for the same known methods implemented through recursive calls in hardware show Significantly better performances than software program. This report covers the way to implement recursive algorithm on hardware with an example of sorting of numeric data by binary inorder tree traversal. The required support for recursion has been provided through a modular and a hierarchical specification of a control unit and through a mechanism that permits the contents of an execution unit to be stored / restored between hierarchical calls / returns. Both the units are designed through VHDL and simulated by ModelSim 6.0d and the results are verified through the test bench. Further the design is synthesized and configured into Spartan-2 XC2S200-5Q208 FPGA of Xilinx family by ISE 8.1 synthesis tool. The design for data sorting is verified for different data sizes for several times. Unlike the software the hardware simulation takes the same time for the same data and it is proportional to the data sizes. In software it is found that number of ticks varied for the same data this is due to the execution of multiple processes in the CPU simultaneously. For different data sizes the hardware resources used also shows slight changes.