A Fast Parallel Merge Algorithm Based on Coarse-Grained Decomposition

CHIBA Riki, NAKANISHI Masaki

doi:10.14923/transinfj.2022jdp7019

Bibliographic Information

Other Title

粗粒度分割を用いた並列マージ処理の高速化

Abstract

In this paper, we propose a fast parallel algorithm for merging two sorted strings that runs on CUDA devices. Due to coarse-grained decomposition of the data sequences, the proposed algorithm can reduce running time for the decomposition, and can exploit the bandwidth of the global memory. The experimental results show that for large-scale inputs, the performance of the proposed algorithm is nearly optimal. For non-large-scale inputs, the performance is also good since the proposed algorithm can reduce running time for memory allocation. The results also show that the proposed algorithm is better than the previously known algorithms.

Journal

電子情報通信学会論文誌D 情報・システム

電子情報通信学会論文誌D 情報・システム J106-D (2), 173-183, 2023-02-01

The Institute of Electronics, Information and Communication Engineers

Keywords

Details 詳細情報について

CRID: 1390294905209634944

DOI: 10.14923/transinfj.2022jdp7019

ISSN: 18810225; 18804535

Text Lang: ja

Data Source

JaLC
KAKEN

Abstract License Flag: Disallowed

Export