Sparser, Better, Faster GPU Parsing

By David Leo Wright Hall, Taylor Berg-Kirkpatrick, Daniel Klein. 2014

21 citations recorded by the source corpus.

Due to their origin in computer graphics, graphics processing units (GPUs) are highly optimized for dense problems, where the exact same operation is applied repeatedly to all data points. Natural language processing algorithms, on the other hand, are traditionally constructed in ways that exploit structural sparsity. Recently, Canny et al. (2013) presented an approach to GPU parsing that sacrifices traditional sparsity in exchange for raw computational power, obtaining a system that can compute Viterbi parses for a high-quality grammar at about 164 sentences per second on a mid-range GPU. In this work, we reintroduce sparsity to GPU parsing by adapting a coarse-to-fine pruning approach to the constraints of a GPU. The resulting system is capable of computing over 404 Viterbi parses per second—more than a 2x speedup—on the same hardware. Moreover, our approach allows us to efficiently implement less GPU-friendly minimum Bayes risk inference, improving throughput for this more accurate algorithm from only 32 sentences per second unpruned to over 190 sentences per second using pruning—nearly a 6x speedup.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Natural Language Processing

Citations in the corpus

Grammar as a Foreign Language (2014, background): “This is better than the speed reported for this batch size in Figure 4 of [18] at 100 sentences per second, even though they run on a GPU and only on sentences of under 40 words.”
Learning-Based Single-Document Summarization with Compression and Anaphoricity Constraints (2016, methodology): “We preprocess all data using the Berkeley Parser (Petrov et al., 2006), speciﬁcally the GPU-accelerated version of the parser from Hall et al. (2014), and the Berkeley Entity Resolution System (Durrett and Klein, 2014).”
Distilling Neural Networks for Greener and Faster Dependency Parsing (2020, methodology): “Parsing can trivially be parallelised by allocating sentences to different cores, so speed per core is an informative metric to compare parsers (Hall et al., 2014). a fast and accurate parser, as described above, and is used as the parser architecture for our experiments.”