Chip Architecture for Data Sorting Using Recursive Algorithm

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. “

  • Page Number : 93-102

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

  • DOI Number
    https://doi.org/10.15415/jtmge.2010.11006

  • Authors

    • Megha AgarwalIndian Institute of Technology, Roorkee,Uttarakhand
    • Indra GuptaIndian Institute of Technology, Roorkee,Uttarakhand

References

  • http://www.xilinx.com (Last viewed on 27/6/09)
  • Lipschutz, S. (2002) Theory and problems of data structures, New Delhi, Tata McGraw-Hill.
  • Ninos, S. and Dollas, A. (2008) ‘Modelling recursion data structures for FPGA-based implementation’, paper presented at International Conference on Field- Programmable Logic and Applications, September.
  • Roth, C.H. (2001) Digital system design using VHDL (3rd edn.), PWS publishing company.
  • Sklyarov, V. (1999) ‘Hierarchical finite-state machines and their use for digital control’, IEEE Transactions on VLSI Systems, 7: 2, 222–228.
  • Sklyarov, V. (2004) ‘FPGA-based implementation of recursive algorithm’, Microprocessors and Microsystems, 28, 197-211.
  • Sklyarov, V. (2005) ‘Hardware implementation of hierarchical FSMs’, ACM International Conference Proceeding, Proceedings of the 4th international symposium on Information and communication technologies, Cape Town, SA, p. 148–153.
  • Sklyarov, V. and Skliarova, I. (2006) ‘Reconfigurable Hierarchical Finite State Machines’, Proceedings of the 3rd International Conference on Autonomous Robots and Agents, Palmerston North, p. 599-604.
  • Sklyarov, V., Skliarova, I. and Pimentel, B. (2005) ‘FPGA- Based implementation and comparison of recursive and iterative algorithms’, Proceedings of the 15th International Conference on Field- Programmable Logic and Application, Finland, p. 235-240.
  • Sklyarove, V., Skliarova, I. and Ferrari, A.B. (nd) ‘Hierarchical Specification and Implementation of Combinatorial Algorithms based on RHS Model’ (online) (cited 27th June 2009). Available from http://www.ieeta.pt/~iouliia/Papers/2001/p13005.pdf.

  • Published Date : --