Due to the exponential growth of biological DNA sequence databases, some parallel gene prediction solutions on different high performance platforms have been proposed. Nevertheless, few exact parallel solutions to the spliced alignment problem to gene prediction in eukaryotic organisms have been proposed and none of these solutions use GPUs as the target platform. In this paper, we present the development of two GPU accelerators for an exact solution to the spliced alignment problem applied to gene prediction. Our main contributions are: (a) the identification of two forms to exploit parallelism in the spliced alignment algorithm; (b) two GPU accelerators that achieve speedups up to 52.62 and 90.86, respectively, when compared to a sequential implementation. The accelerators performance scales with input data size, outperforming related work results; (c) a particular organization for the data structures of the accelerators in order to optimize their efficiency; (d) a potential parallelism analysis of the biological data set with the goal of measuring the amount of parallelism that would in fact be available to be exploited by a parallel implementation; and (e) an accurate performance estimation model that enabled estimating the accelerators performance, before implementing them.

Comparing a biological sequence to a family of sequences is an important task in Bioinformatics, commonly performed using tools such as HMMer. The Viterbi algorithm is applied as HMMer main step to compute the similarity between the sequence and the family. Due to the exponential growth of biological sequence databases, implementations of the Viterbi algorithm on several high performance platforms have been proposed. Nevertheless, few implementations of the Viterbi algorithm use GPUs as main platform. In this paper, we present the development and optimization of an accelerator for the Viterbi algorithm applied to biological sequence analysis on GPUs. Some of the optimizations analyzed are applied to the sequence comparison problem for the first time in the literature and others are evaluated in more depth than in related works. Our main contributions are: (a) an accelerator that achieves speedups up to 102.90 and 60.46, with respect to HMMer2 and HMMer3 execution on a general purpose computer, respectively, (b) the use of the multi-platform OpenCL programming model for the accelerator, (c) a detailed evaluation of several optimizations such as memory, control flow, execution space, instruction scheduling, and loop optimizations, and (d) a methodology of optimizations and evaluation that can also be applied to other sequence comparison algorithms, such as the HMMer3 MSV.

As new protein sequences are discovered on an everyday basis and protein databases continue to grow exponentially with time, computational tools take more and more time to search protein databases to discover the common ancestors of them. HMMER is among the most used tools in protein search and comparison and multiple efforts have been made to accelerate its execution by using dedicated hardware prototyped on FPGAs. In this paper we introduce a novel algorithm called the Divergence Algorithm, which not only enables the FPGA accelerator to reduce execution time, but also enables further acceleration of the alignment generation algorithm of the HMMER programs by reducing the number of cells of the Dynamic Programming matrices it has to calculate. We also propose a more accurate performance measurement strategy that considers all the execution times while doing protein searches and alignments, while other works only consider hardware execution times and do not include alignment generation times. Using our proposed hardware accelerator and the Divergence Algorithm, we were able to achieve gains up to 182× when compared to the unaccelerated HMMER software running on a general purpose CPU.

Reconfigurable systems have been shown to achieve significant performance speedup through architectures that map the most time-consuming application kernel modules or inner loops to a reconfigurable datapath. As each portion of the application starts to execute, the system partially reconfigures the datapath so as to perform the corresponding computation. The reconfigurable datapath should have as few and simple hardware blocks and interconnections as possible, in order to reduce its cost, area, and reconfiguration overhead. To achieve that, hardware blocks and interconnections should be reused as much as possible across the application. We represent each piece of the application as a data-flow graph (DFG). The DFG merging process identifies similarities among the DFGs, and produces a single datapath that can be dynamically reconfigured and has a minimum area cost, when considering both hardware blocks and interconnections. In this paper we present a novel technique for the DFG merge problem, and we evaluate it using programs from the MediaBench benchmark. Our algorithm execution time approaches the fastest previous solution to this problem and produces datapaths with an average area reduction of 20%. When compared to the best known area solution, our approach produces datapaths with area costs equivalent to (and in many cases better than) it, while achieving impressive speedups.

Increasing nonrecurring engineering and mask costs are making it harder to turn to hardwired application specific integrated circuit (ASIC) solutions for high-performance applications. The volume required to amortize these high costs has been increasing, making it increasingly expensive to afford ASIC solutions for medium-volume products. This has led to designers seeking programmable solutions of varying sorts using these so-called programmable platforms. These programmable platforms span a large range from bit-level programmable field programmable gate arrays to word-level programmable application-specific, and in some cases even general-purpose processors. The programmability comes with a power and performance overhead. Attempts to reduce this overhead typically involve making some core hardwired ASIC like logic blocks accessible to the programmable elements. This paper presents one such hybrid solution in this space---a relatively simple processor with a dynamically reconfigurable datapath acting as an accelerating coprocessor. This datapath consists of hardwired function units and reconfigurable interconnect. We present a methodology for the design of these solutions and illustrate it with two complete case studies: an MPEG2 coder, and a GSM coder, to show how significant speedups can be obtained using relatively little hardware. This work is part of the MESCAL project, which is geared towards developing design environments for the development of application-specific platforms.