Estimating the Speedup in Parallel Parsing

A model for the operation of bottom-up parallel parsing using asynchronous processors is proposed. The model is based on an extension of shift-reduce parsers which are able to merge the information they keep on their stacks. The main objective of the paper is to provide estimates of the speedup attainable when using the proposed model. Three programs were written to measure the speedup. The first is a classical simulator which keeps track of the times spent performing the shift, reduce, and merge operations for each processor. The second is a program which generates "typical" strings in a language and simultaneously keeps track of the number of operations needed to parse the generated strings. The third is a program capable of deducing the num-ber of parsing operations by counting the number of selected terminals appearing in an input string. The results, applicable to the paralel parsing of programs written in a Pascal-like language, show how the speedup varies with the number of processors for different ratios of the times to shift, reduce, and merge. Although the speedup falls considerably below that predicted by theory, substantial gains are still attainable by using a fairly large number of parallel processors. With the decreasing costs of processors, parallel parsing and parallel compilation will become increasingly important and should allow considerable gains in speedup.