Optimal Tree Contraction and Term Matching on the Hypercube and
Related Networks
An optimal tree contraction algorithm for the boolean hypercube and
the constant degree hypercubic networks, such as the shuffle exchange
or the butterfly network, is presented. The algorithm is based on
novel routing techniques and, for certain small subtrees, simulates
optimal PRAM algorithms. For trees of size n, stored on a p processor
hypercube in in-order, the running time of the algorithm is
O(n/p*log(p)). The resulting speed-up of O(p/log(p)) is optimal due to
logarithmic communication overhead, as shown by a corresponding lower
bound. The same algorithmic ingredients can also be used to solve the
term matching problem, one of the fundamental problems in logic
programming.
