The search functionality is under construction.

The search functionality is under construction.

The bulk execution of a sequential algorithm is to execute it for many different inputs in turn or at the same time. It is known that the bulk execution of an oblivious sequential algorithm can be implemented to run efficiently on a GPU. The bulk execution supports fine grained bitwise parallelism, allowing it to achieve high acceleration over a straightforward sequential computation. The main contribution of this work is to present a Bitwise Parallel Bulk Computation (BPBC) to accelerate the Smith-Waterman Algorithm (SWA) using the affine gap penalty. Thus, our idea is to convert this computation into a circuit simulation using the BPBC technique to compute multiple instances simultaneously. The proposed BPBC technique for the SWA has been implemented on the GPU and CPU. Experimental results show that the proposed BPBC for the SWA accelerates the computation by over 646 times as compared to a single CPU implementation and by 6.9 times as compared to a multi-core CPU implementation with 160 threads.

- Publication
- IEICE TRANSACTIONS on Information Vol.E102-D No.12 pp.2400-2408

- Publication Date
- 2019/12/01

- Publicized
- 2019/07/09

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2019PAP0013

- Type of Manuscript
- Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)

- Category
- Fundamentals of Information Systems

Takahiro NISHIMURA

Hiroshima University

Jacir Luiz BORDIM

University of Brasilia

Yasuaki ITO

Hiroshima University

Koji NAKANO

Hiroshima University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Takahiro NISHIMURA, Jacir Luiz BORDIM, Yasuaki ITO, Koji NAKANO, "Accelerating the Smith-Waterman Algorithm Using the Bitwise Parallel Bulk Computation Technique on the GPU" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 12, pp. 2400-2408, December 2019, doi: 10.1587/transinf.2019PAP0013.

Abstract: The bulk execution of a sequential algorithm is to execute it for many different inputs in turn or at the same time. It is known that the bulk execution of an oblivious sequential algorithm can be implemented to run efficiently on a GPU. The bulk execution supports fine grained bitwise parallelism, allowing it to achieve high acceleration over a straightforward sequential computation. The main contribution of this work is to present a Bitwise Parallel Bulk Computation (BPBC) to accelerate the Smith-Waterman Algorithm (SWA) using the affine gap penalty. Thus, our idea is to convert this computation into a circuit simulation using the BPBC technique to compute multiple instances simultaneously. The proposed BPBC technique for the SWA has been implemented on the GPU and CPU. Experimental results show that the proposed BPBC for the SWA accelerates the computation by over 646 times as compared to a single CPU implementation and by 6.9 times as compared to a multi-core CPU implementation with 160 threads.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019PAP0013/_p

Copy

@ARTICLE{e102-d_12_2400,

author={Takahiro NISHIMURA, Jacir Luiz BORDIM, Yasuaki ITO, Koji NAKANO, },

journal={IEICE TRANSACTIONS on Information},

title={Accelerating the Smith-Waterman Algorithm Using the Bitwise Parallel Bulk Computation Technique on the GPU},

year={2019},

volume={E102-D},

number={12},

pages={2400-2408},

abstract={The bulk execution of a sequential algorithm is to execute it for many different inputs in turn or at the same time. It is known that the bulk execution of an oblivious sequential algorithm can be implemented to run efficiently on a GPU. The bulk execution supports fine grained bitwise parallelism, allowing it to achieve high acceleration over a straightforward sequential computation. The main contribution of this work is to present a Bitwise Parallel Bulk Computation (BPBC) to accelerate the Smith-Waterman Algorithm (SWA) using the affine gap penalty. Thus, our idea is to convert this computation into a circuit simulation using the BPBC technique to compute multiple instances simultaneously. The proposed BPBC technique for the SWA has been implemented on the GPU and CPU. Experimental results show that the proposed BPBC for the SWA accelerates the computation by over 646 times as compared to a single CPU implementation and by 6.9 times as compared to a multi-core CPU implementation with 160 threads.},

keywords={},

doi={10.1587/transinf.2019PAP0013},

ISSN={1745-1361},

month={December},}

Copy

TY - JOUR

TI - Accelerating the Smith-Waterman Algorithm Using the Bitwise Parallel Bulk Computation Technique on the GPU

T2 - IEICE TRANSACTIONS on Information

SP - 2400

EP - 2408

AU - Takahiro NISHIMURA

AU - Jacir Luiz BORDIM

AU - Yasuaki ITO

AU - Koji NAKANO

PY - 2019

DO - 10.1587/transinf.2019PAP0013

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E102-D

IS - 12

JA - IEICE TRANSACTIONS on Information

Y1 - December 2019

AB - The bulk execution of a sequential algorithm is to execute it for many different inputs in turn or at the same time. It is known that the bulk execution of an oblivious sequential algorithm can be implemented to run efficiently on a GPU. The bulk execution supports fine grained bitwise parallelism, allowing it to achieve high acceleration over a straightforward sequential computation. The main contribution of this work is to present a Bitwise Parallel Bulk Computation (BPBC) to accelerate the Smith-Waterman Algorithm (SWA) using the affine gap penalty. Thus, our idea is to convert this computation into a circuit simulation using the BPBC technique to compute multiple instances simultaneously. The proposed BPBC technique for the SWA has been implemented on the GPU and CPU. Experimental results show that the proposed BPBC for the SWA accelerates the computation by over 646 times as compared to a single CPU implementation and by 6.9 times as compared to a multi-core CPU implementation with 160 threads.

ER -