Title :
The performance of a highly unstructured parallel algorithm on the KSR1
Author :
Nurkkala, Tom ; Kumar, Vipin
Author_Institution :
Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA
Abstract :
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
Keywords :
computational complexity; grammars; natural languages; parallel algorithms; parallel architectures; performance evaluation; shared memory systems; KSR1; Kendall Square Research; Tree Adjoining Grammar; highly unstructured algorithm; highly unstructured parallel algorithm; multicomputer; natural language parsing; near linear speedup; parallel algorithm performance; parsing algorithm; shared data structures; shared-address-space parallel architectures; Computational complexity; Computer science; Concurrent computing; Data structures; Delay; Guidelines; Natural language processing; Natural languages; Parallel algorithms; Technical Activities Guide -TAG;
Conference_Titel :
Scalable High-Performance Computing Conference, 1994., Proceedings of the
Conference_Location :
Knoxville, TN
Print_ISBN :
0-8186-5680-8
DOI :
10.1109/SHPCC.1994.296646
