Chip Architecture for Data Sorting Using Recursive Algorithm

DOI
10.15415/jtmge.2010.11006

AUTHORS

Megha Agarwal and Indra Gupta

ABSTRACT

“This paper suggests a way to implement recursive algorithm on hardware with an example of sorting of numeric data. Every recursive call/return needs a mechanism to store/restore parameters, local variables and return addresses respectively. Also a control sequence is needed to control the flow of execution as in case of recursive call and recursive return. The number of states required for the execution of a recursion in hardware can be reduced compared with software. This paper describes all the details that are required to implement recursive algorithm in hardware. For implementation all the entities are designed using VHDL and are synthesized, configured on Spartan-2 XC2S200-5PQ208. “

KEYWORDS

Binary search tree, Field programmable gate arrays (FPGA), Recurssive Algorythms, very high speed integrated circuits hardware description language (VHDL)

REFERENCES

  • Valery Sklyarov, Iouliia Skliarova, Bruno Pimentel, “FPGA- Based implementation and comparison of recursive and iterative algorithms” Proceedings of the 15th International Conference on Field- Programmable Logic and Applications - FPL\'2005, Finland, August 2005, Pages: 235-240.
  • Valery Sklyarov, “FPGA-based implementation of recursive algorithm”, Microprocessors and Microsystems Vol.28, 2004, Pages: 197-211.
  • Spyridon Ninos, Apostolos Dollas, “Modelling recursion data structures for FPGA-based implementation”, International Conference on Field- Programmable Logic and Applications, FPL’2008, Sept 2008.
  • Sklyarov, “Hierarchical finite-state machines and their use for digital control”, IEEE Transactions on VLSI Systems, Volume 7, Issue 2, June 1999, Pages: 222 – 228.

RNI Registration No. CHAENG/2016/68678