Evaluation of a Parallel Chart Parser

EVALUATION OF A PARALLEL CHART PARSER Ralph Grishman and Mahesh Chitrao Computer Science Department New York University 251 Mercer Street New York, New York 10012 Abstract We describe a parallel implementation of a chart parser for a shared-memory multipro- cessor. The speed-ups obtained with this parser have been measured for a number of small natural-language grammars. For the largest of these, part of an operational question-answering system, the parser ran 5 to 7 times faster than the serial version. 1. Introduction We report here on a series of experiments to deter- mine whether the parsing component of a natural language analyzer can be easily converted to a par- allel program which provides significant speed-up over the serial program. These experiments were prompted in part by the rapidly growing availability of parallel proces- sor systems. Parsing remains a relatively time- consuming component of language analysis sys- tems. This is particularly so if constraints are being systematically relaxed in order to handle ill-formed input (as suggested, for example, in (Weischedel and Sondheimer, 1983)) or if there is uncertainty regarding the input (as is the case for speech input, for example). This time could be reduced if we can take advantage of the new par- allel architectures. Such a parallel parser could be combined with parallel implementations of other components (the acoustic component of a speech system, for example) to improve overall system performance. 2. Background There have been a number of theoretical and algo- rithmic studies of parallel parsing, beginning well before the current availability of suitable experi- mental facilities. For general context-free grammars, it is possi- ble to adapt the Cocke-Younger-Kasami algorithm (Aho and Ullman 1972, p. 314 if) for parallel use. This algorithm, which takes time proportional to rt 3 (rt -" length of input string) on a single pro- cessor, can operate in time n using n 2 proces- sors (with shared memory and allowing concur- rent writes). This algorithm, and its extension to unification grammars, has been described by Haas (1987b). The matrix form of this algorithm is well suited to large arrays of synchronous pro- cessors. The algorithm we describe below is basi- cally a CYK parser with top-down filtering 1, but the main control structure is an event queue rather than iteration over a matrbc. Because tile CYK matrix is large and typically sparse 2, we felt that the event-driven algorithm would be more efficient in our environment of a small number of asyn- chronous processors (<< n 2 for our longest sen- tences) and grammars augmented by conditions which must be checked on each rule application and which vary widely in compute time. Cohen et al. (1982) present a general upper bound for speed-up in parallel parsing, based ou the number of processors and properties of the grammar. Their more detailed analysis, and the subsequent work of Sarkar and Deo (1985) focus on algorithms and speed-ups for parallel parsing of deterministic context-free grammars. Most pro- gramming language grammars are deterministic, but most natural language grammars …

Content truncated to 500 words