An Efficient GPU Implementation of CKY Parsing Using the Bitwise Parallel Bulk Computation Technique

• FUJITA Toru

  Department of Information Engineering, Hiroshima University

• NAKANO Koji

  Department of Information Engineering, Hiroshima University

• ITO Yasuaki

  Department of Information Engineering, Hiroshima University

• TAKAFUJI Daisuke

  Department of Information Engineering, Hiroshima University

抄録

The main contribution of this paper is to present an efficient GPU implementation of bulk computation of the CKY parsing for a context-free grammar, which determines if a context-free grammar derives each of a lot of input strings. The bulk computation is to execute the same algorithm for a lot of inputs in turn or at the same time. The CKY parsing is to determine if a context-free grammar derives a given string. We show that the bulk computation of the CKY parsing can be implemented in the GPU efficiently using Bitwise Parallel Bulk Computation (BPBC) technique. We also show the rule minimization technique and the dynamic scheduling method for further acceleration of the CKY parsing on the GPU. The experimental results using NVIDIA TITAN X GPU show that our implementation of the bitwise-parallel CKY parsing for strings of length 32 takes 395µs per string with 131072 production rules for 512 non-terminal symbols.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E100.D (12), 2857-2865, 2017

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

キーワード

• parallel algorithms
• bulk computation
• bitwise operations
• context-free grammar

詳細情報

• CRID: 1390001204381485184
• NII論文ID: 130006236562
• DOI: 10.1587/transinf.2017pap0018
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E100.D/12/E100.D_2017PAP0018/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可