Paper: Sparser, Better, Faster GPU Parsing

ACL ID P14-1020
Title Sparser, Better, Faster GPU Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2014

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 par...