Υλοποίηση του αλγόριθμου ευθυγράμμισης ακολουθίας Smith-Waterman σε ενσωματωμένη πλατφόρμα FPGA
View/ Open
Subject
Field programmable gate arrays -- Design and construction ; System design -- Data processing ; Σχεδιασμός συστημάτων ; Integrated circuits -- Very large scale integrationAbstract
The sequence alignment, term derived from the field of bioinformatics, is concerned with finding common or similar regions of similarity between two sequences of DNA or proteins. To implement the process of sequence alignment, multiple algorithms over the years have been proposed, however the large volume of data being processed and the inability to exploit the parallel processing of such data, makes these methods extremely time consuming, if performed solely by computer software .
Therefore, there is a need for acceleration these algorithms using hardware, namely, through the technology of FPGAs (Field Programmable Gate Arrays) and embedded systems.The sequence alignment, term derived from the field of bioinformatics, is concerned with finding common or similar regions of similarity between two sequences of DNA or proteins. To implement the process of sequence alignment, multiple algorithms over the years have been proposed, however the large volume of data being processed and the inability to exploit the parallel processing of such data, makes these methods extremely time consuming, if performed solely by computer software .
Therefore, there is a need for acceleration these algorithms using hardware, namely, through the technology of FPGAs (Field Programmable Gate Arrays) and embedded systems.The FPGAs, as being reprogrammable logic units, enables us to transform a complex problem in an electronic circuit, easily and without prototyping’s cost, exploiting whichever possibility of data parallelism that software could not exploit. In this way, a calculations’ accelerator can be designed for the implementation of a dynamic programming algorithm, which in combination with other advantages of embedded systems, accelerates, considerably, the execution time of the algorithm.
In this thesis, we are about to implement a specific sequence alignment algorithm, the Smith-Waterman algorithm, into a FPGA embedded system. By examining the characteristics of the algorithm, we choose to implement a calculations’ accelerator in hardware by using the method of the systolic array, which is, then, added to the embedded system as an additional peripheral and interacts with the embedded processor, which executes the rest of the application. Our goal is to create an embedded and thus portable, efficient sound effects’ detection engine, for audio data streams, such as a movie. The sound effects’ detection system consists, primarily, of an application running on the embedded processor, which handles the pre-processing of the files consisting of the film and the to-be-detected sound effect. Furthermore, the system consists of the peripheral assuming the role of the calculations’ accelerator, as of the interconnection with each other through shared memory and registers. Specifically, the written in C programming language application, which runs on the embedded processor, is responsible for exporting the sound characteristics of the input files, updates the memories of the accelerator with these features, while making the accelerator to initiate by writing to their common registers. The accelerator is, thereby, developed by converting the S-W algorithm in a systolic array of logic elements (systolic array), each and every one of which elements functions identically, independently and in parallel, in a design architecture taking advantage of the data parallelism. In this way, the hardware taking advantage of the parallel processing, achieves acceleration in execution time by a considerable amount, in comparison with other implementations of the same algorithm designed to run only in software.