Accelerating the CKY Parsing Using FPGAs

Jacir L. BORDIM; Yasuaki ITO; Koji NAKANO

Accelerating the CKY Parsing Using FPGAs

Jacir L. BORDIM, Yasuaki ITO, Koji NAKANO

Full Text Views

0

Cite this

Summary :

The main contribution of this paper is to present an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cocke-Kasami-Younger) parsing for context-free grammars. Given a context-free grammar G and a string x, the CKY parsing determines whether 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 generated 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.

Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.5 pp.803-810

Publication Date: 2003/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Reconfigurable Computing)

Category

Cite this

Copy

Jacir L. BORDIM, Yasuaki ITO, Koji NAKANO, "Accelerating the CKY Parsing Using FPGAs" in IEICE TRANSACTIONS on Information, vol. E86-D, no. 5, pp. 803-810, May 2003, doi: .
Abstract: The main contribution of this paper is to present an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cocke-Kasami-Younger) parsing for context-free grammars. Given a context-free grammar G and a string x, the CKY parsing determines whether 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 generated 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_5_803/_p

Copy

@ARTICLE{e86-d_5_803,
author={Jacir L. BORDIM, Yasuaki ITO, Koji NAKANO, },
journal={IEICE TRANSACTIONS on Information},
title={Accelerating the CKY Parsing Using FPGAs},
year={2003},
volume={E86-D},
number={5},
pages={803-810},
abstract={The main contribution of this paper is to present an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cocke-Kasami-Younger) parsing for context-free grammars. Given a context-free grammar G and a string x, the CKY parsing determines whether 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 generated 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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Accelerating the CKY Parsing Using FPGAs
T2 - IEICE TRANSACTIONS on Information
SP - 803
EP - 810
AU - Jacir L. BORDIM
AU - Yasuaki ITO
AU - Koji NAKANO
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2003
AB - The main contribution of this paper is to present an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cocke-Kasami-Younger) parsing for context-free grammars. Given a context-free grammar G and a string x, the CKY parsing determines whether 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 generated 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.
ER -