Efficient Parallel CKY Parsing on GPUs
University of Seoul, Seoul, Korea
12th International Conference on Parsing Technologies (IWPT 2011), 2011
@inproceedings{yi2011efficient,
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},
pages={175},
year={2011}
}
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.
January 13, 2012 by hgpu
