Efficient Parallel CKY Parsing on GPUs

Youngmin Yi, Chao-Yue Lai, Slav Petrov, Kurt Keutzer
University of Seoul, Seoul, Korea
12th International Conference on Parsing Technologies (IWPT 2011), 2011


   title={Efficient Parallel CKY Parsing on GPUs},

   author={Yi, Y. and Lai, C.Y. and Petrov, S. and Keutzer, K.},

   booktitle={Conference on Parsing Technologies},




Download Download (PDF)   View View   Source Source   



Low-latency solutions for syntactic parsing are needed if parsing is to become an integral part of user-facing natural language applications. Unfortunately, most state-of-the-art constituency parsers employ large probabilistic context-free grammars for disambiguation, which renders them impractical for real-time use. Meanwhile, Graphics Processor Units (GPUs) have become widely available, offering the opportunity to alleviate this bottleneck by exploiting the fine-grained data parallelism found in the CKY algorithm. In this paper, we explore the design space of parallelizing the dynamic programming computations carried out by the CKY algorithm. We use the Compute Unified Device Architecture (CUDA) programming model to reimplement a state-of-the-art parser, and compare its performance on two recent GPUs with different architectural features. Our best results show a 26-fold speedup compared to a sequential C implementation.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: