Recursion in reconfigurable computing: A survey of implementation approaches

Reconfigurable systems are widely used nowadays to increase performance of computationally intensive applications. There exist a lot of synthesis tools that automatically generate customized hardware circuits from specifications in both high-level and hardware description languages. However, such tools have a limited applicability because they are unable to handle recursive functions whereas it is known that recursion is a powerful problem-solving method widely used in computer science. Therefore a great deal of research effort is aimed at efficient implementation of recursion in reconfigurable hardware. This paper presents the state of the art in this area. The existing proposals are described, analyzed, and compared according to such criteria as level of parallelism supported, approach to concurrency, ease of use, availability of automated high-level synthesis tools, etc.