| Presentation | 2013-11-08 The Approximate String Matching on the Hierarchical Memory Machine, with Performance Evaluation MANDUHU M, Koji NAKANO, Yasuaki ITO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computing on CUDA-enabled CPUs. The approximate string matching (ASM) for two strings X and Y of length ra and n is a task to find a substring of Y most similar to X. The main contribution of this paper is to show an optimal parallel algorithm for the approximate string matching on the HMM and to implement it on a CUDA-enabled CPU. Our algorithm runs in O(n/w+(mn)/(dw)+(nL)/p+(mnl)/p) on the HMM with d streaming processors, memory band width w, global memory access latency L, and shared memory access latency l. Further, we implement our algorithm on GeForce GTX 580 GPU and evaluate the performance. The experimental results show that the ASM of two strings of 1024 and 4M (= 2^<22>) characters can be computed in 419.6ms, while the sequential algorithm can compute it in 27720ms. Thus, our implementation on the GPU attains a speedup factor of 66.1 over the single CPU implementation. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | memory machine models / approximate string matching / edit distance / GPU / CUDA |
| Paper # | CPSY2013-41 |
| Date of Issue |
| Conference Information | |
| Committee | CPSY |
|---|---|
| Conference Date | 2013/11/1(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Computer Systems (CPSY) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | The Approximate String Matching on the Hierarchical Memory Machine, with Performance Evaluation |
| Sub Title (in English) | |
| Keyword(1) | memory machine models |
| Keyword(2) | approximate string matching |
| Keyword(3) | edit distance |
| Keyword(4) | GPU |
| Keyword(5) | CUDA |
| 1st Author's Name | MANDUHU M |
| 1st Author's Affiliation | Department of Information Engineering, Hiroshima University() |
| 2nd Author's Name | Koji NAKANO |
| 2nd Author's Affiliation | Department of Information Engineering, Hiroshima University |
| 3rd Author's Name | Yasuaki ITO |
| 3rd Author's Affiliation | Department of Information Engineering, Hiroshima University |
| Date | 2013-11-08 |
| Paper # | CPSY2013-41 |
| Volume (vol) | vol.113 |
| Number (no) | 282 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |