Efficient Matrix-Encoded Grammars and Low Latency Parallelization Strategies for CYK
Aaron Dunlop, Nathan Bodenstab, Brian Roark · 2011
We present a matrix encoding of contextfree grammars, motivated by hardware-level efficiency considerations. We find efficiency gains of 2.5–9 × for exhaustive inference and approximately 2 × for pruned inference, resulting in high-accuracy parsing at over 20 sentences per second. Our grammar encoding allows fine-grained parallelism during chart cell population; we present a controlled study of several methods of parallel parsing, and find nearoptimal latency reductions as core-count increases. 1