| Title: | OS13-2 Burrows-Wheeler transform acceleration based on CUDA |
|---|---|
| Publication: | ICAROB2021 |
| Volume: | 26 |
| Pages: | 596-599 |
| ISSN: | 2188-7829 |
| DOI: | 10.5954/ICAROB.2021.OS13-2 |
| Author(s): | Chang Sheng, Fengzhi Dai |
| Publication Date: | January 21, 2021 |
| Keywords: | BWT, acceleration, CUDA, GPU |
| Abstract: | Burrows-Wheeler transform (BWT) is a commonly used transform in compression or text comparison. For example, in bzip2, BWT is used to preprocess the original data, then the same characters in the original data are close to each other, which improves the compression rate. Because the prefix tree of the original string can be easily obtained from the result of the BWT, BWT is also applied to the search and comparison of strings. For instance, the comparison of DNA sequences uses the BWT algorithm. However, BWT is not a fast algorithm, only tens of megabytes per second on CPU. This article uses the GPU to sort the original string by the base of the 4-byte key size radix sort. After radix sort, the part with insufficient length is sorted again to complete the BWT algorithm. |
| PDF File: | https://alife-robotics.co.jp/members2021/icarob/data/html/data/OS/OS13/OS13-2.pdf |
| Copyright: | © The authors. This article is distributed under the terms of the Creative Commons Attribution License 4.0, which permits non-commercial use, distribution and reproduction in any medium, provided the original work is properly cited. See for details: https://creativecommons.org/licenses/by-nc/4.0/ |
(c)2008 Copyright The Regents of ALife Robotics Corporation Ltd. All Rights Reserved.