Abstract

The proliferation of high-throughput sequencing machines ensures rapid generation of up to billions of short nucleotide fragments in a short period of time. This massive amount of sequence data can quickly overwhelm today's storage and compute infrastructure. This paper explores the use of hardware acceleration to significantly improve the runtime of short-read alignment, a crucial step in preprocessing sequenced genomes. We focus on the Levenshtein distance (edit-distance) computation kernel and propose the ASAP accelerator, which utilizes the intrinsic delay of circuits for edit-distance computation elements as a proxy for computation. Our design is implemented on an Xilinx Virtex 7 FPGA in an IBM POWER8 system that uses the CAPI interface for cache coherence across the CPU and FPGA. Our design is 200 × faster than an equivalent Smith-Waterman-C implementation of the kernel running on the host processor, 40-60 × faster than an equivalent Landau-Vishkin-C++ implementation of the kernel running on the IBM Power8 host processor, and 2 × faster for an end-to-end alignment tool for 120-150 base-pair short-read sequences. Further the design represents a 3760 × improvement over the CPU in performance/Watt terms.

Original languageEnglish (US)
Article number8490591
Pages (from-to)331-346
Number of pages16
JournalIEEE Transactions on Computers
Volume68
Issue number3
DOIs
StatePublished - Mar 1 2019

Fingerprint

Alignment
Edit Distance
Hardware
kernel
Field Programmable Gate Array
Program processors
Field programmable gate arrays (FPGA)
Hardware Acceleration
Cache Coherence
Nucleotides
Accelerator
Proliferation
C++
Period of time
Sequencing
High Throughput
Interfaces (computer)
Particle accelerators
Preprocessing
Fragment

Keywords

  • Bioinformatics
  • application-specific processor
  • genomics
  • hardware accelerator
  • levenshtein distance

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

ASAP : Accelerated Short-Read Alignment on Programmable Hardware. / Banerjee, Subho Sankar; El-Hadedy, Mohamed; Lim, Jong Bin; Kalbarczyk, Zbigniew T.; Chen, Deming; Lumetta, Steven S.; Iyer, Ravishankar K.

In: IEEE Transactions on Computers, Vol. 68, No. 3, 8490591, 01.03.2019, p. 331-346.

Research output: Contribution to journalArticle

@article{c06e3c9342a5449cba65c50217e9942f,
title = "ASAP: Accelerated Short-Read Alignment on Programmable Hardware",
abstract = "The proliferation of high-throughput sequencing machines ensures rapid generation of up to billions of short nucleotide fragments in a short period of time. This massive amount of sequence data can quickly overwhelm today's storage and compute infrastructure. This paper explores the use of hardware acceleration to significantly improve the runtime of short-read alignment, a crucial step in preprocessing sequenced genomes. We focus on the Levenshtein distance (edit-distance) computation kernel and propose the ASAP accelerator, which utilizes the intrinsic delay of circuits for edit-distance computation elements as a proxy for computation. Our design is implemented on an Xilinx Virtex 7 FPGA in an IBM POWER8 system that uses the CAPI interface for cache coherence across the CPU and FPGA. Our design is 200 × faster than an equivalent Smith-Waterman-C implementation of the kernel running on the host processor, 40-60 × faster than an equivalent Landau-Vishkin-C++ implementation of the kernel running on the IBM Power8 host processor, and 2 × faster for an end-to-end alignment tool for 120-150 base-pair short-read sequences. Further the design represents a 3760 × improvement over the CPU in performance/Watt terms.",
keywords = "Bioinformatics, application-specific processor, genomics, hardware accelerator, levenshtein distance",
author = "Banerjee, {Subho Sankar} and Mohamed El-Hadedy and Lim, {Jong Bin} and Kalbarczyk, {Zbigniew T.} and Deming Chen and Lumetta, {Steven S.} and Iyer, {Ravishankar K.}",
year = "2019",
month = "3",
day = "1",
doi = "10.1109/TC.2018.2875733",
language = "English (US)",
volume = "68",
pages = "331--346",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "3",

}

TY - JOUR

T1 - ASAP

T2 - Accelerated Short-Read Alignment on Programmable Hardware

AU - Banerjee, Subho Sankar

AU - El-Hadedy, Mohamed

AU - Lim, Jong Bin

AU - Kalbarczyk, Zbigniew T.

AU - Chen, Deming

AU - Lumetta, Steven S.

AU - Iyer, Ravishankar K.

PY - 2019/3/1

Y1 - 2019/3/1

N2 - The proliferation of high-throughput sequencing machines ensures rapid generation of up to billions of short nucleotide fragments in a short period of time. This massive amount of sequence data can quickly overwhelm today's storage and compute infrastructure. This paper explores the use of hardware acceleration to significantly improve the runtime of short-read alignment, a crucial step in preprocessing sequenced genomes. We focus on the Levenshtein distance (edit-distance) computation kernel and propose the ASAP accelerator, which utilizes the intrinsic delay of circuits for edit-distance computation elements as a proxy for computation. Our design is implemented on an Xilinx Virtex 7 FPGA in an IBM POWER8 system that uses the CAPI interface for cache coherence across the CPU and FPGA. Our design is 200 × faster than an equivalent Smith-Waterman-C implementation of the kernel running on the host processor, 40-60 × faster than an equivalent Landau-Vishkin-C++ implementation of the kernel running on the IBM Power8 host processor, and 2 × faster for an end-to-end alignment tool for 120-150 base-pair short-read sequences. Further the design represents a 3760 × improvement over the CPU in performance/Watt terms.

AB - The proliferation of high-throughput sequencing machines ensures rapid generation of up to billions of short nucleotide fragments in a short period of time. This massive amount of sequence data can quickly overwhelm today's storage and compute infrastructure. This paper explores the use of hardware acceleration to significantly improve the runtime of short-read alignment, a crucial step in preprocessing sequenced genomes. We focus on the Levenshtein distance (edit-distance) computation kernel and propose the ASAP accelerator, which utilizes the intrinsic delay of circuits for edit-distance computation elements as a proxy for computation. Our design is implemented on an Xilinx Virtex 7 FPGA in an IBM POWER8 system that uses the CAPI interface for cache coherence across the CPU and FPGA. Our design is 200 × faster than an equivalent Smith-Waterman-C implementation of the kernel running on the host processor, 40-60 × faster than an equivalent Landau-Vishkin-C++ implementation of the kernel running on the IBM Power8 host processor, and 2 × faster for an end-to-end alignment tool for 120-150 base-pair short-read sequences. Further the design represents a 3760 × improvement over the CPU in performance/Watt terms.

KW - Bioinformatics

KW - application-specific processor

KW - genomics

KW - hardware accelerator

KW - levenshtein distance

UR - http://www.scopus.com/inward/record.url?scp=85055031533&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85055031533&partnerID=8YFLogxK

U2 - 10.1109/TC.2018.2875733

DO - 10.1109/TC.2018.2875733

M3 - Article

AN - SCOPUS:85055031533

VL - 68

SP - 331

EP - 346

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 3

M1 - 8490591

ER -