Dynamic expression evaluation in one of a class of problems which are efficiently solvable on mesh-connected computers

Let P be a recursively described and distributable problem of size n. We describe a general strategic approach which will often make an O(√n) parallel time solution of P possible on a 2-dimensional mesh-connected computer with O(n) PEs. Such a solution is time-optimal. It is likely that the class of such problems is large and will contain many that are non-trivial. We show that such a problem is dynamic expression evaluation. The methodology is easily extended to mesh-connected computers of arbitrary dimension to again obtain time-optimal solutions using O(n) processors