Abstract
String comparison is a critical issue in many application domains, including speech recognition, contents search, and bioinformatics. The similarity between two strings of lengths N and M can be computed in O(N×M) steps by means of a dynamic programming algorithm developed by Needleman and Wunsh. The algorithm can be effectively mapped onto a systolic array, resulting in a parallel implementation that executes in O(N+M) steps. In this paper we present a parallel implementation of the Needleman-Wunsh algorithm on the BioWall, a giant reconfigurable computing tissue conceived to prototype bio-inspired cellular systems. Our implementation is not aimed at competing with existing parallel implementations of the Needleman-Wunsh algorithm, since the BioWall suffers from the typical performance limitations of a large prototyping platform. Rather, it is a significant design experience in the field of reconfigurable computing because of the bio-inspired peculiarities of the BioWall architecture.