Search

We expose the implementation challenges to sustaining acceleration speedups on FPGAs as the size of the data set to be processed scales. We examine the implementation of an FPGA platform for the processing of gigabyte scale biological sequences, and illustrate the significant design changes that must be made to achieve a successful implementation. In doing so, we demonstrate that conventional accelerator architecture design choices that focus on throughput speedup, in isolation of system level IO bandwidth feasibility, cannot sustain their throughput levels as the input data set scales. This is shown to be primarily due to currently unavailable high-bandwidth large-scale data storage and retrieval for FPGAs. As a solution to this problem, we propose a general FPGA based IO infrastructure to utilize high bandwidth hard-drive storage options, as means to achieving sustained throughput in the face of large data.

Finding a biologically relevant sequence alignment may be difficult since several sequence alignments are possible, taking different parameters in consideration. A perceptron neuron can be used to associate weights to a set of alignment characteristics and to decide if two residues should be aligned. Finding a good set of weights can be a hard problem and simulated annealing can be used for this purpose but it can take a long time. In this paper, we propose a parallelization strategy for simulated annealing optimizing a Fragment Based Alignment in Linear Space (FBALS). The results were superior to the competing algorithm and the obtained speedups were compatible with the number of processing cores, indicating a good parallel strategy.

Multiple sequence alignment (MSA) is an important problem in Bioinformatics since it is often used to identify evolutionary relationships and predict secondary/tertiary structure, among others. MSAs are usually scored with the Sum-of-Pairs (SP) function and the exact SP MSA is known to be NP-Hard. Therefore, heuristic methods are used to tackle this problem. In this chapter, we propose and evaluate a parallel island injection genetic algorithm to solve the MSA problem. Unlike the other strategies, our parallel solution uses two types of interconnected archipelagoes, each with distinct types of individuals. Also, we added a relaxed coordination mechanism among the archipelagoes that contributes to reduce the execution time of our strategy. The results obtained with real protein data sets show that our strategy is able to obtain better results, when compared to the traditional island model. Also, we were able to reduce considerably the execution time, when compared to the sequential version.

Sequence alignment is a very important problem in Bioinformatics since it is very useful to discover relationships among biological sequences. In this article we propose a new sequence alignment algorithm that is able to identify sequence similarities in linear space. Our solution is capable of using several parameters specifying in which conditions a given residue can be aligned. This decision is taken based on a perceptron neuron and the best set of parameters is found using simulated annealing. Comparing our algorithm to a well established algorithm, we found that for pairwise alignments, our approach was faster for all instances tested with speedups up to 7.63 and yields better quality results for the majority of the instances.

DNA sequence alignment is a very important problem in bioinformatics. The algorithm proposed by Smith-Waterman (SW) is an exact method that obtains optimal local alignments in quadratic space and time. For long sequences, quadratic complexity makes the use of this algorithm impractical. In this scenario, the use of a reconfigurable architecture is a very attractive alternative. This article presents the design and evaluation of an FPGA-based architecture that obtains the similarity score between DNA sequences, as well as its coordinates. The results obtained in a Xilinx xc2vp70 FPGA prototype presented a speedup of 246.9 over the software solution to compare sequences of size 100 MBP and 100 BP, respectively. Different from others hardware solutions that just calculate alignment scores, our design was able to avoid architecture's bottlenecks and accelerate the most computer intensive part of a sequence alignment software algorithm.

Processor scheduling in its general formulation is a NP-Complete problem. In the Dynamic Load Balancing problem the scheduler has to redistribute processes during their running lifetime trying to improve the performance according some optimization criterion. To tackle such a difficult problem is worth use heuristics to seek for better results. Among various heuristics, genetic algorithms are often used to handle problems with high complexity. In this paper we try to optimize the decisions taken by a dynamic load balancer with preemptive migration in a distributed environment using a Classifier System (CS). CS is an adaptive program that evolves decision rules applying genetic algorithms over a population of rules and selecting the best of them. CS has the ability of adapt to environment changes. The rules are rewarded or punished depending on their performance. This performance-driven behavior allows them to perform well even with few information. The results have been impressive and the classifier system was able to surpass, without previous knowledge of the properties of workload, the performance of a well designed analytic criterion.