Massively Parallel Suffix Array Queries and On-Demand Phrase Extraction for Statistical Machine Translation Using GPUs

Proceedings of NAACL-HLT 2013, pages 325–334, Atlanta, Georgia, 9–14 June 2013. c⃝2013 Association for Computational Linguistics Massively Parallel Suffix Array Queries and On-Demand Phrase Extraction for Statistical Machine Translation Using GPUs Hua He Dept. of Computer Science University of Maryland College Park, Maryland huah@cs.umd.edu Jimmy Lin iSchool and UMIACS University of Maryland College Park, Maryland jimmylin@umd.edu Adam Lopez HLTCOE Johns Hopkins University Baltimore, Maryland alopez@cs.jhu.edu Abstract Translation models in statistical machine translation can be scaled to large corpora and arbitrarily-long phrases by looking up translations of source phrases “on the fly” in an indexed parallel corpus using suffix arrays. However, this can be slow because on-demand extraction of phrase tables is computationally expensive. We address this problem by developing novel algorithms for general purpose graphics processing units (GPUs), which enable suffix array queries for phrase lookup and phrase extraction to be massively parallelized. Compared to a highly-optimized, state-of-the-art serial CPU-based implementation, our techniques achieve at least an order of magnitude improvement in terms of throughput. This work demonstrates the promise of massively parallel architectures and the potential of GPUs for tackling computationally- demanding problems in statistical machine translation and language processing. 1 Introduction Efficiently handling large translation models is a perennial problem in statistical machine translation. One particularly promising solution (§2) is to use the parallel text itself as an implicit representation of the translation model and extract translation units “on the fly” when they are needed to decode new input (Brown, 2004). This idea has been applied to phrase-based (Callison-Burch et al., 2005; Zhang and Vogel, 2005), hierarchical (Lopez, 2007; Lopez, 2008b; Lopez, 2008a), and syntax-based (Cromieres and Kurohashi, 2011) models. A benefit of this technique is that it scales to arbitrarily large models with very little pre-processing. For instance, Lopez (2008b) showed that a translation model trained on a large corpus with sparse word alignments and loose extraction heuristics substantially improved Chinese-English translation. An explicit represen- tation of the model would have required nearly a terabyte of memory, but its implicit representation using the parallel text required only a few gigabytes. Unfortunately, there is substantial computational cost in searching a parallel corpus for source phrases, extracting their translations, and scoring them on the fly. Since the number of possible translation units may be quite large (for example, all substrings of a source sentence) and their translations are numerous, both phrase lookup and extraction are performance bottlenecks. Despite considerable research and the use of efficient indexes like suffix arrays (Manber and Myers, 1990), this problem remains not fully solved. We show how to exploit the massive parallelism offered by modern general purpose graphics pro- cessing units (GPUs) to eliminate the computational bottlenecks associated with “on the fly” phrase ex- traction. GPUs have previously been applied to DNA sequence matching using suffix trees (Schatz et al., 2007) and suffix arrays (Gharaibeh and Ri- peanu, 2010). Building on this work, we present two novel contributions: First, we describe improved GPU algorithms for suffix array queries that achieve greater parallelism (§3). Second, …

Content truncated to 500 words