著者
伊藤 靖朗 ボルジン ジャシル 中野 浩嗣
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告. 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倍高速であることがわかった.

言及状況

Twitter (3 users, 4 posts, 0 favorites)

こんな論文どうですか? FPGAを用いたCKYパージングの高速化(伊藤靖朗ほか),2002 https://t.co/4ahKmx665S 本論文では,文脈自由文法に対するCKYパージングを高速に行う入力依…
2 2 https://t.co/nQd9tKBegM
こんな論文どうですか? FPGAを用いたCKYパージングの高速化(伊藤靖朗ほか),2002 https://t.co/4ahKmx665S 本論文では,文脈自由文法に対するCKYパージングを高速に行う入力依…

収集済み URL リスト