A Generic Approach to Parallel Chart Parsing with an Application to LinGO

A Generic Approach to Parallel Chart Parsing with an Application to LinGO Marcel van Lohuizen Faculty of Information Technology and Systems Delft University of Technology Delft, The Netherlands mpvl@acm.org Abstract Multi-processor systems are becom- ing more commonplace and afford- able. Based on analyses of ac- tual parsings, we argue that to ex- ploit the capabilities of such ma- chines, unification-based grammar parsers should distribute work at the level of individual unification oper- ations. We present a generic ap- proach to parallel chart parsing that meets this requirement, and show that an implementation of this tech- nique for LinGO achieves consider- able speedups. 1 Introduction The increasing demand for accuracy and ro- bustness for today’s unification-based gram- mar parsers brings on an increasing demand for computing power. In addition, as these systems are increasingly used in applications that require direct user interaction, e.g. web- based applications, responsiveness is of major concern. In the mean time, small-scale desk- top multiprocessor systems (e.g. dual or even quad Pentium machines) are becoming more commonplace and affordable. In this paper we will show that exploiting the capabilities of these machines can speed up parsers con- siderably, and can be of major importance in achieving the required performance. There are certain requirements the design of a parallel parser should meet. Over the past years, many improvements to existing parsing techniques have boosted the perfor- mance of parsers by many factors (Oepen and Callmeier, 2000). If a design of a parallel parser is tied too much to a particular ap- proach to parsing, it may be hard to incorpo- rate such improvements as they become avail- able. For this reason, a solution to parallel parsing should be as general as possible. One obvious way to ensure that optimizations for sequential parsers can be used in a parallel parser as well is to let a parallel parser mimic a sequential parser as much as possible. This is basically the approach we will take. The parser that we will present in this pa- per uses the LinGO grammar. LinGO is an HPSG-based grammar which was developed at Stanford (Copestake, 2000). It is currently used by many research institutions. This al- lows our results to be compared with that of other research groups. In Section 2, we explore the possibilities for parallelism in natural language parsing by an- alyzing the computational structure of pars- ings. Section 3 and 4 discuss respectively the design and the performance of our system. Finally, we compare our work with other re- search on parallel parsing. 2 Analysis of Parsings To analyze the possibilities for parallelism in computations they are often represented as task graphs. A task graph is a directed acyclic graph, where the nodes represent some unit of computation, called a task, and the arcs represent the execution dependencies between the tasks. Task graphs can be used to an- alyze the critical path, which is the mini- mal time required to complete a computa- tion, given an infinite amount of processors. From Brent …

Content truncated to 500 words