Sparser, Better, Faster GPU Parsing

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 208–217, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Sparser, Better, Faster GPU Parsing David Hall Taylor Berg-Kirkpatrick John Canny Dan Klein Computer Science Division University of California, Berkeley {dlwh,tberg,jfc,klein}@cs.berkeley.edu Abstract Due to their origin in computer graph- ics, graphics processing units (GPUs) are highly optimized for dense problems, where the exact same operation is applied repeatedly to all data points. Natural lan- guage 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 computa- tional power, obtaining a system that can compute Viterbi parses for a high-quality grammar at about 164 sentences per sec- ond on a mid-range GPU. In this work, we reintroduce sparsity to GPU parsing by adapting a coarse-to-fine pruning ap- proach 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 hard- ware. Moreover, our approach allows us to efficiently implement less GPU-friendly minimum Bayes risk inference, improv- ing throughput for this more accurate algo- rithm from only 32 sentences per second unpruned to over 190 sentences per second using pruning—nearly a 6x speedup. 1 Introduction Because NLP models typically treat sentences in- dependently, NLP problems have long been seen as “embarrassingly parallel” – large corpora can be processed arbitrarily fast by simply sending dif- ferent sentences to different machines. However, recent trends in computer architecture, particularly the development of powerful “general purpose” GPUs, have changed the landscape even for prob- lems that parallelize at the sentence level. First, classic single-core processors and main memory architectures are no longer getting substantially faster over time, so speed gains must now come from parallelism within a single machine. Second, compared to CPUs, GPUs devote a much larger fraction of their computational power to actual arithmetic. Since tasks like parsing boil down to repeated read-multiply-write loops, GPUs should be many times more efficient in time, power, or cost. The challenge is that GPUs are not a good fit for the kinds of sparse computations that most current CPU-based NLP algorithms rely on. Recently, Canny et al. (2013) proposed a GPU implementation of a constituency parser that sac- rifices all sparsity in exchange for the sheer horse- power that GPUs can provide. Their system uses a grammar based on the Berkeley parser (Petrov and Klein, 2007) (which is particularly amenable to GPU processing), “compiling” the grammar into a sequence of GPU kernels that are applied densely to every item in the parse chart. Together these kernels implement the Viterbi inside algorithm. On a mid-range GPU, their system can compute Viterbi derivations at 164 sentences per second on sentences of length 40 or less (see timing details below). In this paper, we develop algorithms that can exploit sparsity on a GPU by adapting coarse-to- fine …

Content truncated to 500 words