1 Implementation of the Smith-Waterman Algorithm on A Reconfigurable Supercomputing Platform

An innovative reconfigurable supercomputing platform – XD1000 is being developed by XtremeData to exploit the rapid progress of FPGA technology and the high-performance of Hyper-Transport interconnection. In this paper, we present implementations of the Smith-Waterman algorithm for both DNA and protein sequences on the platform. The main features include: (1) we bring forward a multistage PE (processing element) design which significantly reduces the FPGA resource usage and hence allows more parallelism to be exploited; (2) our design features a pipelined control mechanism with uneven stage latencies – a key to minimize the overall PE pipeline cycle time; (3) we also present a compressed substitution matrix storage structure, resulting in substantial decrease of the on-chip SRAM usage. Finally, we implement a 384-PE systolic array running at 66.7MHz, which can achieve 25.6GCUPS peak performance. Compared with the 2.2GHz AMD Opteron host processor, the FPGA coprocessor results in speedup of 185 and 250 respectively. 1