N-gram language models for massively parallel devices

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 1944–1953, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics N-gram language models for massively parallel devices Nikolay Bogoychev and Adam Lopez University of Edinburgh Edinburgh, United Kingdom Abstract For many applications, the query speed of N-gram language models is a computa- tional bottleneck. Although massively par- allel hardware like GPUs offer a poten- tial solution to this bottleneck, exploiting this hardware requires a careful rethink- ing of basic algorithms and data structures. We present the first language model de- signed for such hardware, using B-trees to maximize data parallelism and minimize memory footprint and latency. Compared with a single-threaded instance of KenLM (Heafield, 2011), a highly optimized CPU- based language model, our GPU imple- mentation produces identical results with a smaller memory footprint and a sixfold increase in throughput on a batch query task. When we saturate both devices, the GPU delivers nearly twice the throughput per hardware dollar even when the CPU implementation uses faster data structures. Our implementation is freely available at https://github.com/XapaJIaMnu/gLM 1 Introduction N-gram language models are ubiquitous in speech and language processing applications such as ma- chine translation, speech recognition, optical char- acter recognition, and predictive text. Because they operate over large vocabularies, they are often a computational bottleneck. For example, in ma- chine translation, Heafield (2013) estimates that decoding a single sentence requires a million lan- guage model queries, and Green et al. (2014) esti- mate that this accounts for more than 50% of de- coding CPU time. To address this problem, we turn to mas- sively parallel hardware architectures, exempli- Figure 1: Theoretical floating point performance of CPU and GPU hardware over time (Nvidia Cor- poration, 2015). fied by general purpose graphics processing units (GPUs), whose memory bandwidth and compu- tational throughput has rapidly outpaced that of CPUs over the last decade (Figure 1). Exploiting this increased power is a tantalizing prospect for any computation-bound problem, so GPUs have begun to attract attention in natural language pro- cessing, in problems such as parsing (Canny et al., 2013; Hall et al., 2014), speech recognition (Chong et al., 2009; Chong et al., 2008), and phrase extraction for machine translation (He et al., 2015). As these efforts have shown, it is not trivial to exploit this computational power, be- cause the GPU computational model rewards data parallelism, minimal branching, and minimal ac- cess to global memory, patterns ignored by many classic NLP algorithms (Section 2). We present the first language model data struc- ture designed for this computational model. Our data structure is a trie in which individual nodes are represented by B-trees, which are searched in parallel (Section 3) and arranged compactly in 1944 memory (Section 4). Our experiments across a range of parameters in a batch query setting show that this design achieves a throughput six times higher than KenLM (Heafield, 2011), a highly effi- cient CPU implementation (Section 5). They also show the effects of device saturation and …

Content truncated to 500 words