Parallel Implementation of an Active Chart Parser in Orca

Active Chart Parsing is an efficient strategy used to generate all possible parsings of a sentence given an ambiguous grammar. This document describes several serial and parallel implementations of an Active Chart Parser. Timing results show that for this fine grained parallel application no speedup can be achieved on a LAN of workstations. 1 Introduction Active Chart Parsing is a technique that is used to efficiently generate all possible derivations of a sentence given an ambiguous grammar. For large grammars and for large sentences this can be a very computationally intensive task. This paper describes a parallel implementation of an Active Chart Parser using the Orca language [4]. This paper starts with a short introduction to Active Chart Parsing. The next three sections describe a serial ANSI C, a serial Orca and a parallel Orca implementation. In section 6 we present some performance results. Finally, in section 7 we discuss our experiences with the Orca programming language. 2..