The performance of a highly unstructured parallel algorithm on the KSR1
Tom Nurkkala, Vipin Kumar · 2002
This paper examines the performance on the Kendall Square Research KSR1 multicomputer of a highly unstructured algorithm for natural language parsing. It describes a Tree Adjoining Grammar parsing algorithm that exhibits near linear speedup and very high efficiency for grammars of even moderate size. The work reported demonstrates the utility of shared-address-space parallel architectures for algorithms that require shared data structures. Finally, the paper presents practical guidelines for the efficient use of the KSR1.>