Accelerating the CKY Parsing Using FPGAs
Accelerating the CKY Parsing Using FPGAs
复制标题
使用 FPGA 加速 CKY 解析
DOI：
10.1007/3-540-36265-7_5
复制
发表时间：
2002
期刊：
影响因子：
5.8
通讯作者：
K. Nakano
中科院分区：
文献类型：
--
作者：
J. Bordim;Yasuaki Ito;K. Nakano
本文的主要贡献是提出基于FPGA的实例实现特定实例的硬件，该硬件可以加速CKY（Cook-Kasami-Younger）解析以进行无上下文的语法。给定无上下文的语法G和一个字符串X，CKY解析确定G是否衍生x。我们已经开发了一个硬件生成器，该硬件生成器可为任何给定的无上下文语法G执行CKY解析。创建的源使用FPGA供应商提供的设计软件嵌入了FPGA中。我们使用计时分析器评估了由硬件生成器生成的特定实例的硬件，并使用Altera FPGA进行了测试。在软件CKY解析算法上，生成的硬件的加速因子约为750。因此，我们认为我们的方法是CKY解析的有前途的解决方案。
The main contribution of this paper is to present an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cook-Kasami-Younger) parsing for context-free grammars. Given a context-free grammar G and a string x, the CKY parsing determines if G derives x. We have developed a hardware generator that creates a Verilog HDL source to perform the CKY parsing for any given context-free grammar G. The created source is embedded in an FPGA using the design software provided by the FPGA vendor. We evaluated the instance-specific hardware, generated by our hardware generator, using a timing analyzer and tested it using the Altera FPGAs. The generated hardware attains a speed-up factor of approximately 750 over the software CKY parsing algorithm. Hence, we believe that our approach is a promising solution for the CKY parsing.
影响因子：
14.9
作者：
SAKAKIBARA, Y;BROWN, M;HAUSSLER, D
通讯作者：
HAUSSLER, D