Modeling and prototyping dynamically reconfigurable systems for efficient computation of dynamic programming methods by rewriting-logic

摘要

Systolic arrays provide a large amount of parallelism. However, their applicability is restricted to a small set of computational problems due to their lack of flexibility. This limitation can be circumvented by using reconfigurable systolic arrays, where the node interconnections and operations can be redefined even at run time. In this context, several alternative systolic architectures can be explored and powerful tools are needed to model and evaluate them. We show how well-known rewriting-logic environments could be used to quickly model and simulate complex application specific digital systems speeding-up its subsequent prototyping. We show how to use rewriting-logic to model and evaluate reconfigurable systolic architectures which are applied to the efficient treatment of several dynamic programming methods for resolving well-known problems such as global and local sequence alignment (Smith-Waterman algorithm), approximate string matching and computation of the longest common subsequence. AVHDL description of the conceived architecture was implemented from the rewriting-logic based abstract models and synthesized over an FPGA of the APEX family.