The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
순차 알고리즘의 대량 실행은 여러 다른 입력에 대해 차례로 또는 동시에 실행하는 것입니다. 망각 순차 알고리즘의 대량 실행을 구현하여 GPU에서 효율적으로 실행할 수 있는 것으로 알려져 있습니다. 대량 실행은 세분화된 비트별 병렬 처리를 지원하므로 간단한 순차 계산보다 높은 가속도를 달성할 수 있습니다. 이 작업의 주요 기여는 아핀 갭 페널티를 사용하여 SWA(Smith-Waterman 알고리즘)를 가속화하기 위한 BPBC(Bitwise Parallel Bulk Computation)를 제시하는 것입니다. 따라서 우리의 아이디어는 여러 인스턴스를 동시에 계산하기 위해 BPBC 기술을 사용하여 이 계산을 회로 시뮬레이션으로 변환하는 것입니다. SWA를 위해 제안된 BPBC 기술은 GPU와 CPU에 구현되었습니다. 실험 결과, 제안된 SWA용 BPBC는 단일 CPU 구현에 비해 646배 이상, 6.9개의 스레드를 사용하는 멀티 코어 CPU 구현에 비해 160배 이상 계산 속도를 향상시키는 것으로 나타났습니다.
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.
부
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
부
@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},}
부
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 -