Estimating the speedup in parallel parsing

A method for estimating the speedup for asynchronous bottom-up parallel parsing is presented. Two models for bottom-up parallel parsing are proposed, and the speedup for each of the two models is estimated. The speedup obtained for model A is a very close to the simulation result already available in literature; however, the model is restrictive because it can only communicate with its immediate left and right neighbors. This increases the processor coordination and interprocessor communication times. Model B, while showing a greater speedup time, is expensive to construct when the number of processors is large