講演名 2016-05-19
文字列検索アクセラレータのためのブロックサイズ制約に基づく簡潔データ構造
張山 昌論(東北大), ウィッデヤスーリヤ ハシタ ムトゥマラ(東北大),
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 簡潔データ構造は少ない記憶容量で効率の良く処理を行うために用いられている.しかしながら,現在主流であるソフトウェア的な簡潔データ構造の実装では,記憶容量が大きくメモリアクセスがボトルネックとなるため,性能が十分ではない.本稿では,処理時間を増加することなしに記憶容量を削減できる,ハードウェア向きのデータ圧縮手法を提案する.提案手法では,カスタムハードウェアによる並列処理によりデータ伸長のオーバーヘッドを削減する.実験結果により,少ない伸長オーバーヘッドで,37.5%の圧縮と高速メモリアクセスを可能にできることを示している.
抄録(英) Succinct data structures are introduced to efficiently solve a given problem while representing the data using as a little space as possible. However, the full potential of the succinct data structures have not been utilized in software-based implementations due to the large storage size and the memory access bottleneck. This paper proposes a hardware-oriented data compression method to reduce the storage space without increasing the processing time. We use a parallel processing architecture to reduce the decompression overhead. The evaluation result demonstrates that the data is compressed by 37.5% still having fast data access with small decompression overhead.
キーワード(和) 簡潔データ構造 / データ圧縮 / FPGA / テキスト検索 / ビッグデータ
キーワード(英) Succinct data structures / data compression / text-search / FPGA / big-data applications
資料番号 RECONF2016-2
発行日 2016-05-12 (RECONF)

研究会情報
研究会 RECONF
開催期間 2016/5/19(から2日開催)
開催地(和) 富士通研究所
開催地(英) FUJITSU LAB.
テーマ(和) リコンフィギャラブルシステム、一般
テーマ(英) Reconfigurable Systems, etc.
委員長氏名(和) 渡邊 実(静岡大)
委員長氏名(英) Minoru Watanabe(Shizuoka Univ.)
副委員長氏名(和) 本村 真人(北大) / 柴田 裕一郎(長崎大)
副委員長氏名(英) Masato Motomura(Hokkaido Univ.) / Yuichiro Shibata(Nagasaki Univ.)
幹事氏名(和) 山田 裕(東芝) / 山口 佳樹(筑波大)
幹事氏名(英) Yutaka Yamada(Toshiba) / Yoshiki Yamaguchi(Univ. of Tsukuba)
幹事補佐氏名(和) 谷川 一哉(広島市大) / 三好 健文(イーツリーズ・ジャパン)
幹事補佐氏名(英) Kazuya Tanikagawa(Hiroshima City Univ.) / Takefumi Miyoshi(e-trees.Japan)

講演論文情報詳細
申込み研究会 Technical Committee on Reconfigurable Systems
本文の言語 ENG-JTITLE
タイトル(和) 文字列検索アクセラレータのためのブロックサイズ制約に基づく簡潔データ構造
サブタイトル(和)
タイトル(英) Succinct-Data-Structure Based on Block-Size-Constrained Compression for a Text-Search Accelerator
サブタイトル(和)
キーワード(1)(和/英) 簡潔データ構造 / Succinct data structures
キーワード(2)(和/英) データ圧縮 / data compression
キーワード(3)(和/英) FPGA / text-search
キーワード(4)(和/英) テキスト検索 / FPGA
キーワード(5)(和/英) ビッグデータ / big-data applications
第 1 著者 氏名(和/英) 張山 昌論 / Masanori Hariyama
第 1 著者 所属(和/英) 東北大学(略称:東北大)
Tohoku University(略称:Tohoku Univ.)
第 2 著者 氏名(和/英) ウィッデヤスーリヤ ハシタ ムトゥマラ / Hasitha Muthumala Waidyasooriya
第 2 著者 所属(和/英) 東北大学(略称:東北大)
Tohoku University(略称:Tohoku Univ.)
発表年月日 2016-05-19
資料番号 RECONF2016-2
巻番号(vol) vol.116
号番号(no) RECONF-53
ページ範囲 pp.3-8(RECONF),
ページ数 6
発行日 2016-05-12 (RECONF)