The Implementation And Analysis Of Smith&Waterman Algorithm On Systolic Array

Bioinformatics is an area based on mathematics, computer science and biology. It employs the methods from these areas to collect, process, manage, spread, analyze and resolve the data from biology in order to understand its biological meaning.One basic problem in bioinformatics is to find the similarity between sequences. To get more accurate results yet requiring less space and time is an important subject. Sequence alignment uses some kind of algorithm to compare two or more seqences to find the similarity between them. The algorithm of Smith&Waterman is one of the classical sequence alignment algorithms. It shows good speed and result when compare two sequences, but consumes too much time when compare a sequence to sequences in a database.This dissertation mainly focuses on the algorithm of Smith&Waterman and accelerating it on the systolic array. It discusses the algorithm of Smith&Waterman and the general method to parallel it at first and leads to the method of the fine granularity parallel and customized hardware, especially the systolic array. Then, it analyzes the architecture of the systolic array, and introduced the the newly designed systolic styled co-processor of Godson I based on the underlying parallel requirement of the Smith&Waterman algorithm. Afterwards, it finalizes the implementation of the algorithm on the array. Then, it compares the performance on the original and revised simulators of Godson I, and concludes the impact of each aspect on accelerating the alogrithm and the adavantages and disadvantages of the array. At last it previews some subjects to be investigated in the future work.