著者

伊藤 靖朗 ボルジン ジャシル 中野 浩嗣

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.2002, no.70, pp.35-42, 2002-07-25

参考文献数

10

---

本論文では,文脈自由文法に対するCKYパージングを高速に行う入力依存回路によるFPGAへの実装を提案する.文脈自由文法Gと文字列xが与えられたときに,CKYパージングはGがxを導出するか否かを判定する.このCKYパージングは,xの長さがnのときに,O(n^3)時間で導出するかを判定するできることが知られている.任意の文脈自由文法Gが与えられたときに,その文法に対するCKYパージングを行うハードウェアのVelilog HDL記述を生成するハードウェアジェネレータを示す.生成された記述は,FPGAに実装され,任意の文字列xに対して,Gがxを導出するかを判定する.このFPGAは,特定の文法Gに対してのみパージングを行うので,入力依存ハードウェアであり,究極の高速化が可能である.このハードウェアの性能をタイミング解析により評価し,また,アルテラ社のFPGAを用いて動作確認を行った.結果として,ソフトウェアによるCKYパージングより約750倍高速であることがわかった.

著者

中野 浩嗣 伊藤 靖朗 川上 賢介 重本 耕司

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム (ISSN:09135685)

巻号頁・発行日

vol.109, no.198, pp.79-84, 2009-09-10

被引用文献数

3

---

本稿では,単純,スケーラブル,かつポータブルで,FPGAに実装可能なTiny processing systemを提案する.このシステムは,16-bitのプロセッサ,クロスアセンブラ,クロスコンパイラを含んでいる.このシステムのソースコードは極めて少なく,16-bitのプロセッサはVerilog HDLで268行で書かれている.クロスアセンブラは38行のPerlスクリプトである.クロスコンパイラは,23行の字句解析のためのFlex文法ファイルと,90行の構文解析とコード生成のためのBison文法ファイルから構成される.よって,このTiny processing systemは容易に理解でき,機能拡張も難しくない.このシステムの教育と小型組込みシステムへの応用を示す.

著者

本田 巧 伊藤 靖朗 中野 浩嗣

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 (ISSN:09135685)

巻号頁・発行日

vol.114, no.302, pp.81-86, 2014-11-13

---

本稿では,コラッツ予想の網羅的検証のGPU実装を提案する.我々はNVIDIA Geforce GTX TITAN上を用いて実装及びその性能評価を行った.実験結果より,提案するGPU実装は1秒間に5.01×10^<11>個の64bitの自然数を検証可能であることを確認した.同様の処理をおこなうCPU実装は1秒間に1.80×10^9個の64bitの自然数の検証が可能であることより,提案するGPU実装はCPU実装と比較して278倍の高速化を実現した.

著者

船坂峻慈 中野浩嗣 伊藤靖朗

雑誌

研究報告システム・アーキテクチャ(ARC) (ISSN:21888574)

巻号頁・発行日

vol.2016-ARC-222, no.6, pp.1-6, 2016-09-29

---

データ圧縮はコンピュータエンジニアリングの分野で非常に重要である.しかし,多くの可逆圧縮と展開アルゴリズムは並列化が非常に難しい.本論文では Light Loss - Less (LLL) 圧縮と呼ぶ,新しい可逆圧縮法を提案する.この圧縮法の展開アルゴリズムは高い並列化が可能であり GPU を用いて非常に高速に処理することができる.データ展開は圧縮と比較して何度も行うためにこの圧縮法は多くのアプリケーションで応用できる.我々は LLL 展開の並列アルゴリズムを提案し GeForce GTX 1080 GPU に実装した.GPU を用いた LLL 展開の実効速度を Core i7- 4790 への逐次 CPU 実装と比較し 91.1-176 倍の高速化を達成した.また,よく知られている圧縮手法である LZSS と LZW との比較も行う.提案手法は圧縮率は同程度である一方で LZSS 展開の GPU 実装と比較して 4.30-14.1 倍,LZW 展開の GPU 実装と比較して 2.49-9.13 倍の高速化を達成した.