tailieunhanh - Báo cáo khoa học: "A Generic Approach to Parallel Chart Parsing with an Application to LinGO"

Multi-processor systems are becoming more commonplace and affordable. Based on analyses of actual parsings, we argue that to exploit the capabilities of such machines, unification-based grammar parsers should distribute work at the level of individual unification operations. We present a generic approach to parallel chart parsing that meets this requirement, and show that an implementation of this technique for LinGO achieves considerable speedups. Callmeier, 2000). | 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@ Abstract Multi-processor systems are becoming more commonplace and affordable. Based on analyses of actual parsings we argue that to exploit the capabilities of such machines unification-based grammar parsers should distribute work at the level of individual unification operations. We present a generic approach to parallel chart parsing that meets this requirement and show that an implementation of this technique for LinGO achieves considerable speedups. 1 Introduction The increasing demand for accuracy and robustness for today s unification-based grammar parsers brings on an increasing demand for computing power. In addition as these systems are increasingly used in applications that require direct user interaction . webbased applications responsiveness is of major concern. In the mean time small-scale desktop multiprocessor systems . 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 considerably 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 performance of parsers by many factors Oepen and Callmeier 2000 . If a design of a parallel parser is tied too much to a particular approach to parsing it may be hard to incorporate such improvements as they become available. 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 .