| Presentation | 2015-08-06 Parallelization of Approximate String Matching Based on Computation of Prefix Sums Yasuaki Mitani, Fumihiko Ino, Kenichi Hagihara, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, aiming at accelerating string search, we propose a parallel method for a shift-or algorithm. Our method achieves parallelization by interpreting the shift-or algorithm as computation of prefix sums. This interpretation allows the shift-or algorithm to run efficiently on a graphics processing unit (GPU), because prefix-sum computation can be parallelized so that threads in a warp can access contiguous memory region. We firstly define two binary operators to realize this interpretation. We then show a proof on the associativity of these operators needed for parallelization of prefix-sum computation. In experiments, we compared our method with a previous method based on data segmentation. As a result, for exact string matching, our method was 1.5 times faster than the previous method. However, for approximate string matching, our method resulted in 76-104% search throughput compared with the previous method. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | approximate string matching / bit parallel algorithm / prefix sums / shift-or algorithm / GPU |
| Paper # | CPSY2015-39 |
| Date of Issue | 2015-07-28 (CPSY) |
| Conference Information | |
| Committee | CPSY / DC / IPSJ-ARC |
|---|---|
| Conference Date | 2015/8/4(3days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | B-Con Plaza (Beppu) |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Parallel, Distributed and Cooperative Processing |
| Chair | Yasuhiko Nakashima(NAIST) / Nobuyasu Kanekawa(Hitachi) |
| Vice Chair | Koji Nakano(Hiroshima Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Michiko Inoue(NAIST) |
| Secretary | Koji Nakano(Fujitsu Labs.) / Hidetsugu Irie(NII) / Michiko Inoue(RTRI) / (Kyoto Sangyo Univ.) |
| Assistant | Shinya Takameda(NAIST) / Takeshi Ohkawa(Utsunomiya Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Computer Systems / Technical Committee on Dependable Computing / Special Interest Group on System Architecture |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Parallelization of Approximate String Matching Based on Computation of Prefix Sums |
| Sub Title (in English) | |
| Keyword(1) | approximate string matching |
| Keyword(2) | bit parallel algorithm |
| Keyword(3) | prefix sums |
| Keyword(4) | shift-or algorithm |
| Keyword(5) | GPU |
| 1st Author's Name | Yasuaki Mitani |
| 1st Author's Affiliation | Osaka University(Osaka Univ.) |
| 2nd Author's Name | Fumihiko Ino |
| 2nd Author's Affiliation | Osaka University(Osaka Univ.) |
| 3rd Author's Name | Kenichi Hagihara |
| 3rd Author's Affiliation | Osaka University(Osaka Univ.) |
| Date | 2015-08-06 |
| Paper # | CPSY2015-39 |
| Volume (vol) | vol.115 |
| Number (no) | CPSY-174 |
| Page | pp.pp.229-234(CPSY), |
| #Pages | 6 |
| Date of Issue | 2015-07-28 (CPSY) |