Log Time Parsing on the MasPar MP-1.
Randall A. Helzerman, Mary P. Harper · 1992
This paper describes the parallelization of Constraint Dependency Grammar (CDG) parsing. Though CDG provides a flexible framework for text-based and spoken language parsing and has an expressivity strictly greater than context-free grammars (CFGs), it also has a relatively slow serial running time (i.e., O(n 4 )). However, a parallelization for this algorithm is derived which uses O(n 4 ) processors to parse in O(k) time for a CRCW P-RAM, where n is the number of words in the sentence and k, the number of constraints, is a grammatical constant. Additionally, the paper describes an implementation of the algorithm on the MasPar MP-1, which uses the special features of the machine (particularly the global router) and O(n 4 ) processors to obtain an O(k + log(n)) running time. Because the average length of an English sentence is on the order of 10 words, the MasPar MP-1 has sufficient processors (i.e., 16,000) for parsing a typical sentence. Previous work in parallel parsing has fo...