Parsing in Parallel on Multiple Cores and GPUs

Parsing in Parallel on Multiple Cores and GPUs Mark Johnson Centre for Language Sciences and Department of Computing Macquarie University Sydney, Australia Mark.Johnson@MQ.edu.au Abstract This paper examines the ways in which par- allelism can be used to speed the parsing of dense PCFGs. We focus on two kinds of parallelism here: Symmetric Multi-Processing (SMP) parallelism on shared-memory multi- core CPUs, and Single-Instruction Multiple- Thread (SIMT) parallelism on GPUs. We de- scribe how to achieve speed-ups over an al- ready very efficient baseline parser using both kinds of technology. For our dense PCFG parsing task we obtained a 60×speed-up us- ing SMP and SSE parallelism coupled with a cache-sensitive algorithm design, parsing sec- tion 24 of the Penn WSJ treebank in a little over 2 secs. 1 Introduction Performance improvements in computing come in- creasingly through greater parallelism. This paper studies ways in which this parallelism can be used to improve the speed of PCFG parsing in computa- tional linguistics. Although we focus on a particu- lar task here (constructing the inside chart for dense PCFGs), we expect the insights to be generally ap- plicable. There are three major ways in which computers are becoming more parallel. At the broadest level, it is now common to network large numbers of com- puters together into clusters, which are controlled by software such as the Message-Passing Interface (MPI) (Gropp et al., 1999) or Map-Reduce (Lin and Dyer, 2010). At a lower level, even commodity computers typ- ically have multiple processors or cores, which are connected by a high-speed bus to a shared memory, enabling Symmetric Multi-Processor (SMP) paral- lelism. SMP parallelism is typically controlled by software such as OpenMP (Chapman et al., 2007) or pThreads. Commodity computers also possess on-chip parallel floating point vectorised arithmetic units. The CPUs we used here have SSE (Streaming SIMD Extensions) vectorised arith- metic, where SIMD abbreviates “Single-Instruction Multiple-Data”. SSE is enabled by appropriate com- piler flags. Finally, Graphics Processor Units (GPUs) are increasingly becoming both less specialised and more powerful (on many commodity machines they can perform more floating-point operations per sec- ond than the CPU); as we will see here, a GPU can yield quite respectable parsing performance. GPUs are designed for massively parallel Single- Instruction Multiple-Thread (SIMT) programs; each GPU thread is comparatively slow, but the GPU can execute hundreds or thousands of threads in parallel. GPUs are typically programmed using tools such as OpenCL or CUDA (Sanders and Kandrot, 2011). We concentrate on SMP multi-core and GPU par- allelism in this paper because we expect that com- munication latencies with conventional network- ing hardware make parallel parsing with networked clusters impractically inefficient. Communication latency is much less of a problem with shared mem- ory SMP and GPU parallelism as communication takes place over the machine’s high-speed bus. A base-line approach for exploiting parallelism in parsing is simply to parse different sentences in parallel on separate instances of the parser. This Mark Johnson. 2011. Parsing in Parallel on Multiple Cores and GPUs. In Proceedings of …

Content truncated to 500 words