Reconfigurable Computing Research Oriented Bioinformatics

After the completion of human genome sequencing, biologists desire for higher processing and analysis power to handle the huge gene data. Computing is a basic research method of bioinformatics, many bioinformatics programs have some common features,such as huge data volume, relative simple algorithm, few operation types, many repeating processes, showing that these programs are potentially parallelizable. When running in general computer, these programs not only waste a lot of system resources, but also need complex maintenance, however a lot of program still couldn't get a satisfying result within limited time. Reconfigurable computing is one of effective solutions, not only could it accelerate the most commonly used algorithm, but also could it be adapted to the changing of algorithms very quickly.The work of this thesis integrated very tightly with the project of Specific Computer oriented Bioinformatics, the author designed two kind of general purpose accelerator cards which based on PCI-X bus and DDR SDRAM bus separately, discussed the designing of DDR SDRAM interface, PCI-X interface and ZBT SRAM interface.Regarding hardware implementation of the algorithms, the thesis systemically discussed the similarity problem of two sequences, expatiated the original algorithm of edit distance and its simplification as well as the mapping method from algorithm to logic. According to this method, the thesis gave out a simple and effective design of the processing element, and further more, gave out the design of systolic array and core processing logic of the edit distance algorithm.Based on Stratix 1S30 FPGA of Altera Corp., 3072 PE was implemented on the accelerator card, its working frequency was limited to 133.3MHz, and the peak performance is 409.6GCUPS. The speedup test showed that, compared with general purpose CPU, when the sequences were long enough (tens of kilobasepairs to hundreds of kilobasepairs), the accelerator card could get a speedup of more than 3000 times, even if the sequences were only a few kilobasepairs short, it still could get a speedup of two orders of magnitude.In real application, this thesis utilized the accelerator card to accelerate the first step of ClustalW, which is a widely used multi-sequence alignment program. Randomly generated sequences were used to test the performance of the program, the length of the sequences is 3Kbp. When the number of sequences varied from 100 to 1000, the total speedup of the program scaled up to the number of sequences, and it could reach near 35 within this range, showed that the accelerator card would have a very well prospect in real application.