MOTIVATION: The Basic Local Alignment Search Tool (BLAST) is one of the most widely used bioinformatics tools. The widespread impact of BLAST is reflected in over 53,000 citations that this software has received in the past two decades, and the use of the word 'blast' as a verb referring to biological sequence comparison. Any improvement in the execution speed of BLAST would be of great importance in the practice of bioinformatics, and facilitate coping with ever increasing sizes of biomolecular databases. RESULTS: Using a general-purpose graphics processing unit (GPU), we have developed GPU-BLAST, an accelerated version of the popular NCBI-BLAST. The implementation is based on the source code of NCBI-BLAST, thus maintaining the same input and output interface while producing identical results. In comparison to the sequential NCBI-BLAST, the speedups achieved by GPU-BLAST range mostly between 3 and 4. AVAILABILITY: The source code of GPU-BLAST is freely available at http://archimedes.cheme.cmu.edu/biosoftware.html.

The Logarithmic Number System (LNS) makes multiplication, division and powering easy, but subtraction is expensive. Cotransformation converts the difficult operation of logarithmic subtraction into the easier operation of logarithmic addition. In this paper, a new variant of cotransformation is proposed, which is simpler to design and more economical in hardware than previous cotransformation methods. The novel method commutes operands differently for addition than for subtraction. Simulation results show how many guard bits are required by the new cotransformation to guarantee faithful rounding and that, even without guard bits, cotransformation produces an LNS unit more accurate than a previously published Hardware-Description-Language (HDL) library for LNS arithmetic that uses only multipartite tables or 2nd-order interpolation.

Serial arithmetic uses less hardware than parallel arithmetic. Serial floating point (FP) is slower than parallel FP. The Logarithmic Number System (LNS) simplifies operations, but a fast serial implementation of LNS has never been proposed previously. This paper presents a fast bit-serial LNS that combines a novel serial implementation of Mitchell's method and a new error correction method that is compatible with least-significant-bit-first serial arithmetic.

Simple algorithms can be analytically characterized, but such analysis is questionable or even impossible for more complicated algorithms, such as Model Predictive Control (MPC). Instead, Monte Carlo Arithmetic (MCA) enables statistical experimentation with an algorithm during runtime for detection and mitigation of numerical anomalies. Previous studies of MCA have been limited to software floating point. This paper studies how MCA can be used in an FPGA implementation of the Logarithmic Number System (LNS), forming the Monte Carlo Logarithmic Number System (MCLNS). Simulation studies present how MCLNS affects the accuracy vs. performance of an MPC implementation, and synthesis results give an estimate of the cost of utilizing MCLNS in a Xilinx Virtex-IV FPGA.

We present analytical formulas for the calculation of the memory requirements for a system using the complex logarithmic number system (CLNS). Certain properties of the CLNS addition algorithm allow replacement of a large memory by smaller multiple memories and combinational circuitry. The multiple memories combined with a parallel search algorithm offer memory savings up to 90% at the cost of extra hardware. However, depending on the particular case, there is a tradeoff between memory and combinational logic used