Parsing in Parallel on Multiple Cores and GPUs

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