The balanced binary tree technique on mesh-connected computers (Q2638775)

The authors address the problem of transforming PRAM algorithms into algorithms on mesh-connected arrays. They characterize a class of tree- based PRAM algorithms which can be transformed systematically into optimal mesh algorithms using an efficient embedding of trees on a mesh. The technique is illustrated by some examples. The most important of these examples (bracket matching) suffers from an incorrect and incomplete descriiption of the computations performed in the nodes of the tree. More severely, the described algorithm for bracket matching is not an adequate example for the proposed technique, since its tree version is not in the above-mentioned class. Therefore, the mesh version is constructed explicitely and not by a systematic transformation from the tree version. Nevertheless, the article contains several interesting ideas.