TL;DR
This paper introduces a novel parallel algorithm for Generalized LR (GLR) parsing that significantly improves performance over existing methods by eliminating unnecessary synchronization. By leveraging stream communication in GHC and employing Tree Structured Stacks (TSS), the algorithm allows parsing processes to proceed concurrently without waiting for others to complete shift actions, leading to greater parallelism.
What Problem Does This Paper Address?
Efficient parsing of natural language sentences is crucial for many NLP applications. While parallel processing offers a promising avenue for speeding up parsing, existing parallel GLR algorithms, like Tomita's, suffer from performance bottlenecks due to synchronization requirements. Specifically, Tomita's algorithm forces parsing processes to wait for each other to complete "shift" actions before merging their stacks. This synchronization, while necessary for managing multiple parsing paths, hinders the full exploitation of parallel hardware, especially when dealing with syntactically ambiguous sentences that naturally lead to multiple parsing paths. The paper aims to overcome this synchronization overhead to achieve higher parallel parsing performance.
Methods
The core of the paper's contribution lies in its novel parallel GLR parsing algorithm, which is presented as a natural extension of Tomita's approach. The key innovations are:
- Elimination of Shift Synchronization: Unlike Tomita's algorithm, which requires processes to synchronize after every "shift N" action to merge stacks, this new algorithm allows a process that completes a "shift N" to proceed immediately to subsequent actions. Merging of stacks occurs implicitly as other processes complete their "shift N" actions, placing their elements into the position established by the first process.
- Tree Structured Stacks (TSS): To avoid the complexity of implementing Graph Structured Stacks (GSS) in a parallel logic programming environment, the authors adopt Tree Structured Stacks (TSS). TSS are represented as list data structures in GHC and are used to manage the multiple parsing paths generated by ambiguities.
- GHC Stream Communication: The algorithm leverages the stream communication mechanism of the concurrent logic programming language GHC. This allows for efficient and asynchronous passing of stack information between parallel processes, facilitating the merging of stacks without explicit synchronization points.
Datasets
Not discussed in the paper. The paper uses a sample ambiguous English grammar and a corresponding LR parsing table for illustrative purposes.
Key Insights and Ideas
- Synchronization is the Bottleneck: The paper clearly identifies that the synchronization required by Tomita's algorithm for merging stacks is the primary reason for reduced parallel performance, not the inherent parallelism of GLR itself.
- Asynchronous Merging is Key: By allowing processes to proceed independently after a shift action and merging stacks implicitly through stream communication, the algorithm unlocks greater parallelism. This is particularly beneficial when dealing with incomplete stack information.
- TSS as a Practical Alternative: The adoption of TSS simplifies implementation in a parallel logic programming context (GHC) compared to GSS, while still effectively managing the complex structure of parallel parse trees.
- Stream Communication for Efficiency: GHC's stream communication provides a natural and efficient mechanism for inter-process communication, enabling the asynchronous merging of stacks and reducing the need for explicit synchronization primitives.
Key Results
The paper demonstrates through an example that their algorithm achieves greater parallel parsing performance than Tomita's original algorithm. While specific quantitative results are not detailed in terms of speedup percentages, the authors state that simulations indicate most processes run in parallel with a very small number of suspended processes. They also note that the computational complexity of their algorithm is identical to Tomita's, with the performance difference stemming solely from the reduced synchronization.
Limitations and Future Work
- Experimental Validation: The authors acknowledge that while simulations are promising, the true performance benefits need to be validated through experiments on a multi-processor machine. They mention preparations to conduct such experiments on the Multi-PSI machine with 64 processors.
- Complexity Analysis: The paper states that the computational complexity is identical to Tomita's, but a detailed complexity analysis is not provided.
- Future Work: The immediate future work involves conducting experiments on a multi-processor system to empirically verify the performance gains. The paper also implies that further exploration of parallel parsing algorithms and their implementation in concurrent logic programming languages is a natural extension.
Summary updated