A Multi-Teraflop Constituency Parser using GPUs

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1898–1907, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics A multi-Teraflop Constituency Parser using GPUs John Canny David Hall Dan Klein UC Berkeley Berkeley, CA, 94720 canny@berkeley.edu, dlwh,klein@cs.berkeley.edu Abstract Constituency parsing with rich grammars re- mains a computational challenge. Graph- ics Processing Units (GPUs) have previously been used to accelerate CKY chart evalua- tion, but gains over CPU parsers were mod- est. In this paper, we describe a collection of new techniques that enable chart evaluation at close to the GPU’s practical maximum speed (a Teraflop), or around a half-trillion rule eval- uations per second. Net parser performance on a 4-GPU system is over 1 thousand length- 30 sentences/second (1 trillion rules/sec), and 400 general sentences/second for the Berkeley Parser Grammar. The techniques we introduce include grammar compilation, recursive sym- bol blocking, and cache-sharing. 1 Introduction Constituency parsing with high accuracy (e.g. latent variable) grammars remains a computational chal- lenge. The O(Gs3) complexity of full CKY pars- ing for a grammar with G rules and sentence length s, is daunting. Even with a host of pruning heuris- tics, the high cost of constituency parsing limits its uses. The most recent Berkeley latent variable gram- mar for instance, has 1.7 million rules and requires about a billion rule evaluations for inside scoring of a single length-30 sentence. GPUs have previously been used to accelerate CKY evaluation, but gains over CPU parsers were modest. e.g. in Yi et al. (2011) a GPU parser is described for the Berkeley Parser grammar which achieves 5 sentences per sec- ond on the first 1000 sentences of Penn Treebank section 22 Marcus et al. (1993), which is compa- rable with the best CPU parsers Petrov and Klein (2007). Our parser achieves 120 sentences/second per GPU for this sentence set, and over 250 sen- tences/sec on length ≤ 30 sentences. These results use a Berkeley Grammar approximately twice as big as Yi et al. (2011), an apparent 50x improvement. On a 4-GPU system, we achieve 1000 sentences/sec for length ≤ 30 sentences. This is 2 orders of mag- nitude faster than CPU implementations that rely heavily on pruning, and 5 orders of magnitude faster than full CKY evaluation on a CPU. Key to these results is a collection of new tech- niques that enable GPU parsing at close to the GPU’s practical maximum speed (a Teraflop for re- cent GPUs), or around a half-trillion rule evaluations per second. The techniques are: 1. Grammar compilation, which allows register- to-register code for application of grammar rules. This gives an order of magnitude (10x) speedup over alternative approaches that use shared memory. 2. Symbol/rule blocking of the grammar to re- spect register, constant and instruction cache limits. This is precondition for 1 above, and the details of the partitioning have a big (> 4x) effect on performance. 3. Sub-block partitioning to distribute rules across the stream processors of the GPU and allow L2 cache …

Content truncated to 500 words