Accelerating HMMER on FPGA using Parallel Prefixes and Reductions

Naeem Abbas; Steven Derrien; Sanjay Rajopadhye; Patrice Quinton

inria-00515298, version 2

Accelerating HMMER on FPGA using Parallel Prefixes and Reductions

Naeem Abbas ()^a^, 1, Steven Derrien ()^b^, 1, Sanjay Rajopadhye ()^c^, 2, Patrice Quinton ()^d^, 1

N° RR-7370 (2010)

Abstract: HMMER is a widely used tool in bioinformatics, based on Profile Hidden Markov Models. The computation kernels of HMMER i.e. MSV and P7Viterbi are very compute intensive and data dependencies restrict to sequential execution. In this paper, we propose an original parallelization scheme for HMMER by rewriting their mathematical formulation, to expose the hidden potential parallelization opportunities. Our parallelization scheme targets FPGA technology, and our architecture can achieve 10 times speedup compared with that of latest HMMER3 SSE version, while not compromising on sensitivity of original algorithm.

a – INRIA
b – Université de Rennes I
c – Computer Science Department, Colorado State University, USA
d – École normale supérieure de Cachan - ENS Cachan
1: CAIRN (INRIA - IRISA)
INRIA – CNRS : UMR6074 – École normale supérieure de Cachan - ENS Cachan – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
2: Colorado State University (CSU)
Colorado State University

inria-00515298, version 2
http://hal.inria.fr/inria-00515298
oai:hal.inria.fr:inria-00515298
From: Naeem Abbas <>
Submitted on: Friday, 17 December 2010 10:04:09
Updated on: Monday, 20 December 2010 09:51:23

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00515298"><monogr>
<author><persName><forename>Naeem</forename><surname>Abbas</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">CAIRN</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">École normale supérieure de Cachan - ENS Cachan</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) - Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Steven</forename><surname>Derrien</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">CAIRN</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">École normale supérieure de Cachan - ENS Cachan</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) - Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Sanjay</forename><surname>Rajopadhye</surname></persName>
<affiliation>
<orgName type="laboratory">CSU</orgName>
<orgName type="team">Colorado State University</orgName>
<country>US</country>
<orgName type="institution">Colorado State University</orgName>
</affiliation>
</author>
<author><persName><forename>Patrice</forename><surname>Quinton</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">CAIRN</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">École normale supérieure de Cachan - ENS Cachan</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) - Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<title type="main" level="m">Accelerating HMMER on FPGA using Parallel Prefixes and Reductions</title><title type="main" level="m">Accelerating HMMER on FPGA using Parallel Prefixes and Reductions</title><imprint><biblScope type="publicationDate">2010-08-31</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00515298</idno><idno type="HALFile">http://hal.inria.fr/inria-00515298/PDF/RR-7370.pdf</idno></biblStruct>
</listBibl>
</listBibl>