| Item type |
学術雑誌論文 / Journal Article(1) |
| 公開日 |
2016-03-25 |
| タイトル |
|
|
タイトル |
Simultaneous Finite Automata : An Efficient Data-Parallel Model for Regular Expression Matching |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者 |
Sin'ya, Ryoma
Matsuzaki, Kiminori
Sassa, Masataka
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
Automata play important roles in wide area of computing and the growth of multicores calls for their efficient parallel implementation. Though it is known in theory that we can perform the computation of a finite automaton in parallel by simulating transitions, its implementation has a large overhead due to the simulation. In this paper we propose a new automaton called simultaneous finite automaton (SFA) for efficient parallel computation of an automaton. The key idea is to extend an automaton so that it involves the simulation of transitions. Since an SFA itself has a good property of parallelism, we can develop easily a parallel implementation without overheads. We have implemented a regular expression matcher based on SFA, and it has achieved over 10-times speedups on an environment with dual hexa-core CPUs in a typical case. |
| 書誌情報 |
Parallel Processing (ICPP), 2013 42nd International Conference on
p. 220-229,
発行日 2013
|
| DOI |
|
|
関連タイプ |
isVersionOf |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
10.1109/ICPP.2013.31 |
| 権利 |
|
|
権利情報 |
IEEE, Ryoma Sinya ; Kiminori Matsuzaki, Masataka Sassa, Parallel Processing (ICPP), 2013 42nd International Conference on, 2013, p220-229 |
| 著者版フラグ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 出版者 |
|
|
出版者 |
IEEE |
27-32.pdf (216.8 kB)
