Fine-Grained Parallelism in Probabilistic Parsing with Habanero Java
Matthew Francis-Landau, Bing Xue, Jason M. Eisner, Vivek Sarkar · 2016
Structured prediction algorithms-used when applying machine learning to tasks like natural language parsing and image understanding-present some opportunities for fine-grained parallelism, but also have problem-specific serial dependencies. Most implementations exploit only simple opportunities such as parallel BLAS, or embarrassing parallelism over input examples. In this work we explore an orthogonal direction: using the fact that these algorithms can be described as specialized forward-chaining theorem provers [1], [2], and implementing fine-grained parallelization of the forward-chaining mechanism. We study context-free parsing as a simple canonical example, but the approach is more general.