Chip Architecture for Data Sorting Using Recursive Algorithm
Authors
- Megha AgarwalIndian Institute of Technology, Roorkee,Uttarakhand
- Indra GuptaIndian Institute of Technology, Roorkee,Uttarakhand
Keywords
Binary search tree, Field programmable gate arrays (FPGA), Recurssive Algorythms, very high speed integrated circuits hardware description language (VHDL)
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. ā
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.
How to Cite
Megha Agarwal, Indra Gupta. Chip Architecture for Data Sorting Using Recursive Algorithm.
J.Technol. Manag. Grow. Econ.. 2023, 01, 93-102
Search
