Sequence Alignment or finding the Edit Distance between two strings is one of the most fundamental dynamic programming algorithms ever existed. However the asymptotic complexity of the general version of the problem has still remained O(n^2), although the Four Russian algorithm improves this asymptotic bound to O(n^2/log(n)) that result has remained purely theoritical this is because the algorithm needs to spend some time on preprocessing and building a lookup table which is used during the algorithm, however the need of preprocessing can be totally avoided in Four Russian algorithm if the underlying hardware can perform the same functionality of that lookup table used in Four Russian algorithm. This can be provided as a hardware instruction to compute the Edit Distance between two strings of length 't'. Thus in this work we develop a new algorithm for computing Edit Distance in hardware (Please note that the algorithm for Edit Distance in software cannot be realized in hardware because of un-synthesizable constructs like the loops etc...) our algorithm takes only O(n) hardware resources and experiments estimate that a 8x8 hardware instruction can speed up the Edit Distance computation by a factor of 4X. Please see this paper for details paper
This hardware instruction is implemented as a verilog IP block, the design is fully asynchronous and synthesizable. The design has been verified using both Synopsys VCS and Cadence NC-Verilog, and synthesized using Cadence Encounter RTL Compiler and Design Compiler. This IP is high speed and we acheive a speed of 1GHz. Also the IP block has testbenches for each of the modules. Please download it here
Please set NCVERILOG or VCS in your path before running make in the extracted directory, by default the Makefile uses NCVERILOG to use VCS type make use_vcs , this generates the simulation file FinalAlgo.vcd you can use SIMVISION or VIRSIM to view the waveforms.