Accelerating the CKY Parsing Using FPGAs

スポンサーリンク

概要

• 論文の詳細を見る

• 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 speedup factor of approximately 750 over the software CKY parsing algorithm.

• 社団法人電子情報通信学会の論文
• 2003-05-01

著者

• BORDIM Jacir

  School of Information Science, Japan Advanced Institute of Technology

• NAKANO Koji

  School of Information Science, Japan Advanced Institute of Technology

• Bordim Jacir

  School Of Information Science Japan Advanced Institute Of Science And Technology

• Nakano Koji

  School Of Information Science Japan Advanced Institute Of Technology

• Ito Y

  School Of Information Science Japan Advanced Institute Of Science And Technology

• Ito Yasuaki

  School Of Engineering Hiroshima University

• Nakano Koji

  School Of Engineering Hiroshima University

関連論文

• An Energy-Efficient Initialization Protocol for Wireless Sensor Networks with No Collision Detection
• An Energy Efficient Leader Election Protocol for Radio Network with a Single Transceiver(Discrete Mathematics and Its Applications)
• Accelerating the CKY Parsing Using FPGAs
• An Energy Efficient Ranking Protocol for Radio Networks(Discrete Mathematics and Its Applications)
• Special Section on Foundations of Computer Science
• Randomized Time- and Energy-Optimal Routing Single-Hop, Single-Channel Radio Networks
• Halftoning Through Optimization of Restored Images : A New Approach with Hardware Acceleration
• An Image Retrieval System Using FPGAs
• Hardware n Choose k Counters with Applications to the Partial Exhaustive Search(Programmable Logic, VLSI, CAD and Layout, Recent Advances in Circuits and Systems-Part 1)

スポンサーリンク